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

[worm2]

Определённо можно сильно сократить количество действий, необходимых для расчёта.
Например, для матрицы 3x2 сумму трёх определителей можно сократить в один:

$$ \left|\begin{array}{cc}a_{11}&a_{12}\\a_{21}&a_{22}\end{array}\right| + \left|\begin{array}{cc}a_{11}&a_{13}\\a_{21}&a_{23}\end{array}\right| + \left|\begin{array}{cc}a_{12}&a_{13}\\a_{22}&a_{23}\end{array}\right| = \left|\begin{array}{cc}a_{11}+a_{12}&a_{12}+a_{13}\\a_{21}+a_{22}&a_{22}+a_{23}\end{array}\right|. $$

Для матрицы 5x3, составленной из пяти векторов-столбцов: $\mathbf{a}_1$, $\mathbf{a}_2$, ..., $\mathbf{a}_5$, сумму десяти определителей можно сократить до суммы трёх:

$$ \left|\mathbf{a}_1\quad\mathbf{a}_2\quad\left(\mathbf{a}_3+\mathbf{a}_4+\mathbf{a}_5\right)\right|\quad+\quad \left|\left(\mathbf{a}_1+\mathbf{a}_2\right)\quad\mathbf{a}_3\quad\left(\mathbf{a}_4+\mathbf{a}_5\right)\right|\quad+\quad \left|\left(\mathbf{a}_1+\mathbf{a}_2+\mathbf{a}_3\right)\quad\mathbf{a}_4\quad\mathbf{a}_5\right|. $$

Так что есть определённый оптимизм, что удастся достичь полиномиальной сложности. Но конкретный путь к ней неясен.

[Sender]

Сумму шести определителей 2-го порядка можно сократить до суммы двух.

$$ \left|\begin{array}{cc}a_{11}&a_{12}\\a_{21}&a_{22}\end{array}\right| + \left|\begin{array}{cc}a_{11}&a_{13}\\a_{21}&a_{23}\end{array}\right| + \left|\begin{array}{cc}a_{11}&a_{14}\\a_{21}&a_{24}\end{array}\right| + \left|\begin{array}{cc}a_{12}&a_{13}\\a_{22}&a_{23}\end{array}\right| + \left|\begin{array}{cc}a_{12}&a_{14}\\a_{22}&a_{24}\end{array}\right| + \left|\begin{array}{cc}a_{13}&a_{14}\\a_{23}&a_{24}\end{array}\right| = $$

$$\left|\begin{array}{cc}a_{11}+a_{12}+a_{13}&a_{12}+a_{13}+a_{14}\\a_{21}+a_{22}+a_{23}&a_{22}+a_{23}+a_{24}\end{array}\right|+ \left|\begin{array}{cc}a_{12}&a_{13}\\a_{22}&a_{23}\end{array}\right|.$$

-- Чт авг 17, 2023 18:17:40 --

Равно как и сумму десяти.

$$ \left|\begin{array}{cc}a_{11}&a_{12}\\a_{21}&a_{22}\end{array}\right| + \left|\begin{array}{cc}a_{11}&a_{13}\\a_{21}&a_{23}\end{array}\right| + \dots +\left|\begin{array}{cc}a_{14}&a_{15}\\a_{24}&a_{25}\end{array}\right|= $$

$$\left|\begin{array}{cc}a_{11}+a_{12}+a_{13}+a_{14}&a_{12}+a_{13}+a_{14}+a_{15}\\a_{21}+a_{22}+a_{23}+a_{24}&a_{22}+a_{23}+a_{24}+a_{25}\end{array}\right|+ \left|\begin{array}{cc}a_{12}+a_{13}&a_{13}+a_{14}\\a_{22}+a_{23}&a_{23}+a_{24}\end{array}\right|.$$

-- Чт авг 17, 2023 18:35:22 --

Сумма четырёх определителей для матрицы 4x3 сворачивается так:

$$\left|\begin{array}{ccс}a_{11}+a_{12}&a_{12}+a_{13}&a_{13}+a_{14}\\a_{21}+a_{22}&a_{22}+a_{23}&a_{23}+a_{24}\\a_{31}+a_{32}&a_{32}+a_{33}&a_{33}+a_{34}\end{array}\right|.$$

По-моему, закономерность определённо прослеживается.

[Sender]

Впрочем, дальше у меня затык, например, на 5x3 идея так просто не обобщается.¯\_(ツ)_/¯

[mihaild]

Для $(n + 1) \times n$ сворачивается до одного.

Это хочется описать через покрытия всех максимальных парасочетаний $K_{n,m}$ какими-то избранными парасочетаниями подграфов вида "$i$-ю вершину соединяем с вершинами от $a_i$ до $b_i$". Но пока не вижу, как это хорошо сделать.

[worm2]

Я ошибся в выкладках ниже.

О, для $(2n-1) \times n$ тоже сворачивается до одного:

$$ \left|\mathbf{a}_1+\mathbf{a}_2+\dots+\mathbf{a}_{n}\quad\mathbf{a}_2+\mathbf{a}_3+\dots+\mathbf{a}_{n+1}\quad\dots\quad\mathbf{a}_n+\mathbf{a}_{n+1}+\dots+\mathbf{a}_{2n-1}\right|. $$

-- Пт авг 18, 2023 17:03:55 --

Хотя подождите, чего-то я не соображу... Разве это не обобщается до общего случая?

$$ \left|\mathbf{a}_1+\dots+\mathbf{a}_{m-n+1}\quad\mathbf{a}_2+\dots+\mathbf{a}_{m-n+2}\quad\dots\quad\mathbf{a}_n+\dots+\mathbf{a}_{m}\right|. $$

[mihaild]

Для $2 \times n$ сворачивается до $\lfloor \frac{n}{2} \rfloor$ определителей. Обозначив $f(A)$ искомую функцию (сумма определителей подматриц матрицы $A$, имеем

$$f(A) = |\mathbf a_1 + \ldots \mathbf a_{n - 1} \quad \mathbf a_2 + \ldots + \mathbf a_n| + f(A[2:n-1])$$

[mihaild]

Кажется идея со сложением столбцов записывается таким образом:
Составим булеву матрицу $m \times n$, в которой $b_{ij} = 1$ если $i$-й столбец входит в $j$-й столбец нашей суммы. Нулевые столбцы вычеркиваем. Матрица должна быть выпукла по строкам и столбцам (т.е. каждая строка и каждый столбец читаются как "сначала нули, потом единицы, потом опять нули"). Набор исходных столбцов включается в определитель преобразованной матрицы, если соответствующая ему подматрица булевой матрицы нижнетреугольная, с единичной диагональю.

Пока не выглядит сильно полезным описанием, но хоть что-то комбинаторное.

[0101]

Sender в сообщении #1605653 писал(а):

Впрочем, дальше у меня затык, например, на 5x3 идея так просто не обобщается.¯\_(ツ)_/¯

На 5x3 все остановилось?

[0101]

В итоге искомый алгоритм полиномиальной сложности существует?

[worm2]

Может быть и существует.
Но не нашли пока.

[0101]

По крайней мере отрицать существование полиномиального алгоритма после продемонстрированных примеров с уверенностью нельзя. Искать алгоритм полиномиальной сложности вычисления суммы определителей всех матриц порядка $n\cdot n$, полученных из строк (с сохранением их очередности) матрицы порядка $m\cdot n$, $m>n$ можно аналогичным образом?

[0101]

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

[0101]

А можно рассмотреть подобную этой задачу в следующей формулировке.
Для квадратной матрицы $A=(a_{ij})$ размера $n\times n$ её недоопределитель $\det A$ порядка $m,\, m<n$ вычисляется по формуле:

$\sum\limits_{i_{1}j_{1}\, i_{2}j_{2}\dots \, i_{m}j_{m}}^{} (-1)^{N(i_{1}j_{1}\, i_{2}j_{2}\dots \, i_{m}j_{m})}\ast a_{i_{1}j_{1}} \ast a_{i_{2}j_{2}}\ast\dots \ast a_{i_{m}j_{m}}$,

где $i_{1}\ne i_{1},j_{1}\ne j_{1},\dots, i_{m-1}\ne i_{1_{m}},j_{m-1}\ne j_{m}$,

где суммирование проводится по всем перестановкам $m$ чисел $i_{1}i_{2}\dots i_{m}$ из $n$ чисел $1,\, 2,\,\dots, n$, а также всем перестановкам $m$ чисел $j_{1}j_{2}\dots j_{m}$ из $n$ чисел $1,\, 2,\,\dots, n$,

а ${N(i_{1}j_{1}\, i_{2}j_{2}\dots \, i_{m}j_{m})}$ обозначает число инверсий в перестановке.

Есть ли алгоритмы полиномиальной сложности вычисления таких недоопределителей или проверки их на равенство 0?
Задавались ли подобными вопросами Артур Кэли и его современники?

[0101]

Нужно:
недоопределитель $\det A$ обозначить как $under \det A$
исправить
$i_{1}\ne i_{1},j_{1}\ne j_{1}$
на
$i_{1}\ne i_{2},j_{1}\ne j_{2}$,
и добавить
$j_{1}> j_{2},\dots, j_{m-1}>j_{m}$.

Недоопределитель $under \det A$ включает $m!(C_{n}^{m})^2$ элементов.
Есть ли у матрицу $A$ преобразовать к диагональному виду, поможет ли это найти искомый недоопределитель?