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

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

Общий метод

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

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

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

$b_{i,j}=\left|\begin{array}{cc}{a}_{i,j}& a_{i,j+1}\\ a_{i+1,j}& a_{i+1,j+1}\end{array}\right|,i,j=1\dots n-1.$

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

$c_{i,j}=\frac{\left|\begin{array}{cc}{b}_{i,j}& b_{i,j+1}\\ b_{i+1,j}& b_{i+1,j+1}\end{array}\right|}{a_{i+1,j+1}},i,j=1\dots n-2.$

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

Примеры

Без нулей

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

$\left|\begin{array}{cccc}-2& -1& -1& -4\\ -1& -2& -1& -6\\ -1& -1& 2& 4\\ 2& 1& -3& -8\end{array}\right|.$

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

$B=\left[\begin{array}{ccc}\left|\begin{array}{cc}-2& -1\\ -1& -2\end{array}\right|& \left|\begin{array}{cc}-1& -1\\ -2& -1\end{array}\right|& \left|\begin{array}{cc}-1& -4\\ -1& -6\end{array}\right|\\ \left|\begin{array}{cc}-1& -2\\ -1& -1\end{array}\right|& \left|\begin{array}{cc}-2& -1\\ -1& 2\end{array}\right|& \left|\begin{array}{cc}-1& -6\\ 2& 4\end{array}\right|\\ \left|\begin{array}{cc}-1& -1\\ 2& 1\end{array}\right|& \left|\begin{array}{cc}-1& 2\\ 1& -3\end{array}\right|& \left|\begin{array}{cc}2& 4\\ -3& -8\end{array}\right|\end{array}\right]=\left[\begin{array}{ccc}3& -1& 2\\ -1& -5& 8\\ 1& 1& -4\end{array}\right].$

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

$\left[\begin{array}{cc}\left|\begin{array}{cc}3& -1\\ -1& -5\end{array}\right|& \left|\begin{array}{cc}-1& 2\\ -5& 8\end{array}\right|\\ \left|\begin{array}{cc}-1& -5\\ 1& 1\end{array}\right|& \left|\begin{array}{cc}-5& 8\\ 1& -4\end{array}\right|\end{array}\right]=\left[\begin{array}{cc}-16& 2\\ 4& 12\end{array}\right].$

$C=\left[\begin{array}{cc}8& -2\\ -4& 6\end{array}\right].$

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

$\left[\begin{array}{cc}-16& 2\\ 4& 12\end{array}\right]$

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

$\left[\begin{array}{cc}-2& -1\\ -1& 2\end{array}\right].$

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

$\left[\begin{array}{c}\left|\begin{array}{cc}8& -2\\ -4& 6\end{array}\right|\end{array}\right]=\left[\begin{array}{c}40\end{array}\right].$

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

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

С нулями

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

$\left[\begin{array}{ccccc}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{array}\right]\to \left[\begin{array}{cccc}5& -5& -3& -1\\ -3& -3& -3& 3\\ 3& 3& 3& -1\\ -5& -3& -1& -5\end{array}\right]\to \left[\begin{array}{ccc}-30& 6& -12\\ 0& 0& 6\\ 6& -6& 8\end{array}\right].$

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

$\left[\begin{array}{ccccc}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{array}\right]\to \left[\begin{array}{cccc}-3& -3& -3& 3\\ 3& 3& 3& -1\\ -5& -3& -1& -5\\ 3& -5& 1& 1\end{array}\right]\to \left[\begin{array}{ccc}0& 0& 6\\ 6& -6& 8\\ -17& 8& -4\end{array}\right]\to \left[\begin{array}{cc}0& 12\\ 18& 40\end{array}\right]\to \left[\begin{array}{c}36\end{array}\right].$

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

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

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

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

Пусть $A=(m_{i,j}{)}_{i,j=1}^k$ — квадратная матрица, и для всех $1⩽i,j⩽k$ обозначим $M_i^j$ минор матрицы $A$, который получается вычёркиванием $i$-й строки и $j$-го столбца. Аналогично для $1⩽i,j,p,q⩽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.$

Литература

• Шаблон:Статья
• Шаблон:Статья
• 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).

Ссылки

• Шаблон:MathWorld