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

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

Общий методПравить

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

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

2. Запишем матрицу $B$$B$  размера $(n-<!--\; -\; -->1)\times <!--\; \times \; -->(n-<!--\; -\; -->1)$$(n-1)\times (n-1)$ , состоящую из миноров порядка 2 матрицы $A$$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$$B$ , запишем матрицу $C$$C$  размера $(n-<!--\; -\; -->2)\times <!--\; \times \; -->(n-<!--\; -\; -->2)$$(n-2)\times (n-2)$ , разделив соответствующие элементы полученной матрицы на внутренние элементы матрицы $A$$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$$A=B$  и $B=C$$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$$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$$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$$C$  мы получили, разделив элементы полученной матрицы

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

на внутренние элементы матрицы $A$$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 <!--\; \times \; -->3$$3 \times 3$ , то есть на $-<!--\; -\; -->5$$-5$ , получаем $\left[\begin{array}{c}-<!--\; -\; -->8\end{array}\right]$${\begin{bmatrix}-8\end{bmatrix}}$ .

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

$det(A)\cdot <!--\; \cdot \; -->M_{1,k}^{1,k}=M_1^1\cdot <!--\; \cdot \; -->M_k^k-<!--\; -\; -->M_1^k\cdot <!--\; \cdot \; -->M_k^1.$$\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.