Конденсация Доджсона

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

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

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

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

${\displaystyle 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 к матрице ${\displaystyle B}$, запишем матрицу ${\displaystyle C}$ размера ${\displaystyle (n-2)\times (n-2)}$, разделив соответствующие элементы полученной матрицы на внутренние элементы матрицы ${\displaystyle A}$:

${\displaystyle 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. Пусть ${\displaystyle A=B}$ и ${\displaystyle B=C}$. Повторяем этап № 3 до тех пор, пока не получим матрицу порядка 1. Её единственный элемент и будет искомым определителем.

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

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

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

${\displaystyle 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}}.}$

Составим матрицу ${\displaystyle C}$:

${\displaystyle {\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}}.}$

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

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

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

на внутренние элементы матрицы ${\displaystyle A}$

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

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

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

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

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

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

${\displaystyle {\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. Однако мы можем переставить строки исходной матрицы и повторить процесс:

${\displaystyle {\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.

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

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

${\displaystyle \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.