Сумма всех определителей порядка mxm матрицы mxn, m<n

[0101]

Многоуважаемые.
Существует ли алгоритм полиномиальной сложности вычисления суммы определителей всех матриц порядка $m\cdot m$, полученных из столбцов матрицы порядка $m\cdot n$, $m<n$?

[Ende]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы)

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Ende]

Тема перемещена из форума «Карантин» в форум «Математика (общие вопросы)»
Причина переноса: не указана.

[mihiv]

Пусть $m=2$, и мы нашли определитель матрицы $\left (\begin {array}{ccc}a_{11}&a_{12}\\a_{21}&a_{22}\end {array}\right )$. Нужно ли в сумме определителей учитывать определитель матрицы с переставленными столбцами?

[ozheredov]

mihiv в сообщении #1605148 писал(а):

Нужно ли в сумме определителей учитывать определитель матрицы с переставленными столбцами?

Иными словами, переформулируем задачу так:

0101 в сообщении #1605063 писал(а):

Существует ли алгоритм полиномиальной сложности

, печатающий на экране число "ноль"?

[0101]

mihiv в сообщении #1605148 писал(а):

Пусть $m=2$, и мы нашли определитель матрицы $\left (\begin {array}{ccc}a_{11}&a_{12}\\a_{21}&a_{22}\end {array}\right )$. Нужно ли в сумме определителей учитывать определитель матрицы с переставленными столбцами?

Хорошее уточнение. Не нужно.
Можно переформулировать так?
Существует ли алгоритм полиномиальной сложности вычисления суммы определителей всех матриц порядка $m\cdot m$, полученных из столбцов (с сохранением их очередности) матрицы порядка $m\cdot n$, $m<n$?

[Geen]

А не пробовали матрицу дополнить чем-нибудь до квадратной?

[0101]

Какими-то дробными числами?

[mihiv]

Общее число определителей, которые нужно вычислить, равно $C^m_n$, сложность вычисления одного определителя $O(m^3)$, поэтому, по крайней мере при фиксированном $m,$ сложность алгоритма полиномиальна по $n$.

[0101]

А если учесть, что каждый столбец является линейной комбинацией некоторых $m$ столбцов?

[mihaild]

Можно методом Гаусса по строкам сказать, что первые $m$ столбцов это вообще единичная матрица. Но непонятно, что дальше.

Geen в сообщении #1605157 писал(а):

А не пробовали матрицу дополнить чем-нибудь до квадратной?

А это просто идея или Вы знаете алгоритм?

[Geen]

mihaild в сообщении #1605473 писал(а):

А это просто идея или Вы знаете алгоритм?

Скорее попытка уточнить условие... не очень хорошая, правда

[pppppppo_98]

блин это какая-то смесь перманента и детерминанта.... Взятие перманента задача переборная - одна из задач квантового превосходства - не вижу я как-то полиномиальной сложности по n. по m - как сказали выше полиномиальна...только надо правильно перебор организовать по множеству числа сочетаний $m\choose n$

PS

При чем похоже сумма будет зависеть от порядка столбцов

[svv]

Geen в сообщении #1605157 писал(а):

А не пробовали матрицу дополнить чем-нибудь до квадратной?

0101 в сообщении #1605166 писал(а):

Какими-то дробными числами?

В случае $n=m+1$ требуемую сумму можно получить, если к исходной матрице дописать сверху строку $1,-1,1,-1,...$ и найти определитель полученной матрицы $n\times n$. Возможно, Geen предлагал попробовать как-то обобщить этот приём на случай $n>m+1$.

-- Чт авг 17, 2023 01:09:19 --

0101 в сообщении #1605465 писал(а):

А если учесть, что каждый столбец является линейной комбинацией некоторых $m$ столбцов?

Боюсь, это ничего не даст. Например, каждый столбец произвольного определителя является линейной комбинацией столбцов единичной матрицы
$\begin{bmatrix}1\\0\\...\\0\\0\end{bmatrix},\begin{bmatrix}0\\1\\...\\0\\0\end{bmatrix},...,\begin{bmatrix}0\\0\\...\\1\\0\end{bmatrix},\begin{bmatrix}0\\0\\...\\0\\1\end{bmatrix}$
Причём с известными коэффициентами (это элементы столбца). Но это никак не облегчает задачу вычисления определителя.

[Geen]

svv в сообщении #1605604 писал(а):

Возможно, Geen предлагал попробовать как-то обобщить этот приём на случай $n>m+1$.

Не сработает - уже при $n-m=2$ у нас будет $2n$ неизвестных при $n(n-1)/2$ условий (детерминанты на дополнительных строках).