Конденсация Доджсона (Tku;yuvgenx :k;'vkug)

В математике, конденсация Доджсона — это метод вычисления определителей. Метод назван в честь его создателя Чарльза Доджсона (более известного как Льюис Кэрролл). Метод заключается в понижении порядка определителя специальным образом до порядка 1, единственный элемент которого и является искомым определителем.

Общий метод

Алгоритм может быть описан с помощью следующих четырёх этапов:

1. Пусть $A$ — заданная квадратная матрица размера $n\times n$. Запишем матрицу $A$ таким образом, чтобы она содержала только ненулевые элементы во внутренней части, то есть $a_{ij}\neq 0$, если $i,j\neq 1,n$. Это может быть сделано, например, с помощью операции добавления к строке матрицы некоторой другой строки, умноженной на некоторое число.

2. Запишем матрицу $B$ размера $(n-1)\times (n-1)$, состоящую из миноров порядка 2 матрицы $A$. В явном виде:

$b_{i,j}={\begin{vmatrix}a_{i,j}&a_{i,j+1}\\a_{i+1,j}&a_{i+1,j+1}\end{vmatrix}},\quad i,j=1\ldots n-1.$

3. Применяя этап № 2 к матрице $B$, запишем матрицу $C$ размера $(n-2)\times (n-2)$, разделив соответствующие элементы полученной матрицы на внутренние элементы матрицы $A$:

$c_{i,j}={\dfrac {\begin{vmatrix}b_{i,j}&b_{i,j+1}\\b_{i+1,j}&b_{i+1,j+1}\end{vmatrix}}{a_{i+1,j+1}}},\quad i,j=1\ldots n-2.$

4. Пусть $A=B$ и $B=C$. Повторяем этап № 3 до тех пор, пока не получим матрицу порядка 1. Её единственный элемент и будет искомым определителем.

Примеры

Без нулей

Пусть необходимо вычислить определитель

${\begin{vmatrix}-2&-1&-1&-4\\-1&-2&-1&-6\\-1&-1&2&4\\2&1&-3&-8\end{vmatrix}}.$

Составим матрицу $B$ из миноров порядка 2:

$B={\begin{bmatrix}{\begin{vmatrix}-2&-1\\-1&-2\end{vmatrix}}&{\begin{vmatrix}-1&-1\\-2&-1\end{vmatrix}}&{\begin{vmatrix}-1&-4\\-1&-6\end{vmatrix}}\\[0.5ex]{\begin{vmatrix}-1&-2\\-1&-1\end{vmatrix}}&{\begin{vmatrix}-2&-1\\-1&2\end{vmatrix}}&{\begin{vmatrix}-1&-6\\2&4\end{vmatrix}}\\[0.5ex]{\begin{vmatrix}-1&-1\\2&1\end{vmatrix}}&{\begin{vmatrix}-1&2\\1&-3\end{vmatrix}}&{\begin{vmatrix}2&4\\-3&-8\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}3&-1&2\\-1&-5&8\\1&1&-4\end{bmatrix}}.$

Составим матрицу $C$:

${\begin{bmatrix}{\begin{vmatrix}3&-1\\-1&-5\end{vmatrix}}&{\begin{vmatrix}-1&2\\-5&8\end{vmatrix}}\\[0.5ex]{\begin{vmatrix}-1&-5\\1&1\end{vmatrix}}&{\begin{vmatrix}-5&8\\1&-4\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}-16&2\\4&12\end{bmatrix}}.$

$C={\begin{bmatrix}8&-2\\-4&6\end{bmatrix}}.$

Элементы матрицы $C$ мы получили, разделив элементы полученной матрицы

${\begin{bmatrix}-16&2\\4&12\end{bmatrix}}$

на внутренние элементы матрицы $A$

${\begin{bmatrix}-2&-1\\-1&2\end{bmatrix}}.$

Повторяем этот процесс, пока не получим матрицу порядка 1:

${\begin{bmatrix}{\begin{vmatrix}8&-2\\-4&6\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}40\end{bmatrix}}.$

Делим на внутреннюю часть матрицы размера $3\times 3$, то есть на $-5$, получаем ${\begin{bmatrix}-8\end{bmatrix}}$.

$-8$ и есть искомый определитель исходной матрицы.

С нулями

Запишем необходимые матрицы:

${\begin{bmatrix}2&-1&2&1&-3\\1&2&1&-1&2\\1&-1&-2&-1&-1\\2&1&-1&-2&-1\\1&-2&-1&-1&2\end{bmatrix}}\to {\begin{bmatrix}5&-5&-3&-1\\-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\end{bmatrix}}\to {\begin{bmatrix}-30&6&-12\\0&0&6\\6&-6&8\end{bmatrix}}.$

Возникает проблема. Если мы продолжим этот процесс, то возникнет необходимость деления на 0. Однако мы можем переставить строки исходной матрицы и повторить процесс:

${\begin{bmatrix}1&2&1&-1&2\\1&-1&-2&-1&-1\\2&1&-1&-2&-1\\1&-2&-1&-1&2\\2&-1&2&1&-3\end{bmatrix}}\to {\begin{bmatrix}-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\\3&-5&1&1\end{bmatrix}}\to {\begin{bmatrix}0&0&6\\6&-6&8\\-17&8&-4\end{bmatrix}}\to {\begin{bmatrix}0&12\\18&40\end{bmatrix}}\to {\begin{bmatrix}36\end{bmatrix}}.$

Таким образом, определитель исходной матрицы 36.

Тождество Доджсона и корректность конденсации Доджсона

Тождество Доджсона

Доказательство метода конденсации Доджсона основано на тождестве, известном, как тождество Доджсона (тождество Якоби).

Пусть $A=(m_{i,j})_{i,j=1}^{k}$ — квадратная матрица, и для всех $1\leqslant i,j\leqslant k$ обозначим $M_{i}^{j}$ минор матрицы $A$, который получается вычёркиванием $i$-й строки и $j$-го столбца. Аналогично для $1\leqslant i,j,p,q\leqslant k$ обозначим $M_{i,j}^{p,q}$ минор, который получается из матрицы $A$ вычёркиванием $i$-й и $j$-й строк и $p$-го и $q$-го столбцов. Тогда

$\det(A)\cdot M_{1,k}^{1,k}=M_{1}^{1}\cdot M_{k}^{k}-M_{1}^{k}\cdot M_{k}^{1}.$

Литература

• C. L. Dodgson. Condensation of Determinants, Being a New and Brief Method for Computing their Arithmetical Values // Proceedings of the Royal Society of London. — 1866-1867. — Т. 15. — С. 150–155.
• А. Л. Новый метод вычисления определителей // Математическое просвещение. Вторая серия. — 1958. — Вып. 3. — С. 194.
• David Bressoud, Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, MAA Spectrum, Mathematical Associations of America, Washington, D.C., 1999.
• David Bressoud and Propp, James, How the alternating sign matrix conjecture was solved, Notices of the American Mathematical Society, 46 (1999), 637—646.
• D. Knuth (1996) Overlapping Pfaffians, Electronic Journal of Combinatorics, 3, no. 2.
• Mills, William H., Robbins, David P., and Rumsey, Howard, Jr., Proof of the Macdonald conjecture, Inventiones Mathematicae, 66 (1982), 73—87.
• Mills, William H., Robbins, David P., and Rumsey, Howard, Jr., Alternating sign matrices and descending plane partitions, Journal of Combinatorial Theory, Series A, 34 (1983), 340—359.
• Robbins, David P., The story of 1, 2, 7, 42, 429, 7436, …, The Mathematical Intelligencer, 13 (1991), 12—19.
• Doron Zeilberger, Dodgson’s determinant evaluation rule proved by two-timing men and women. Elec. J. Comb. 4 (1997).

Ссылки

• Weisstein, Eric W. Condensation (англ.) на сайте Wolfram MathWorld.