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

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

Общий метод

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

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

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

[math]\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. }[/math]

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

[math]\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. }[/math]

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

Примеры

Без нулей

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

[math]\displaystyle{ \begin{vmatrix} -2 & -1 & -1 & -4 \\ -1 & -2 & -1 & -6 \\ -1 & -1 & 2 & 4 \\ 2 & 1 & -3 & -8 \end{vmatrix}. }[/math]

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

[math]\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}. }[/math]

Составим матрицу [math]\displaystyle{ C }[/math]:

[math]\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}. }[/math]

[math]\displaystyle{ C = \begin{bmatrix} 8 & -2 \\ -4 & 6 \end{bmatrix}. }[/math]

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

[math]\displaystyle{ \begin{bmatrix} -16 & 2 \\ 4 & 12 \end{bmatrix} }[/math]

на внутренние элементы матрицы [math]\displaystyle{ A }[/math]

[math]\displaystyle{ \begin{bmatrix} -2 & -1 \\ -1 & 2 \end{bmatrix}. }[/math]

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

[math]\displaystyle{ \begin{bmatrix} \begin{vmatrix} 8 & -2 \\ -4 & 6 \end{vmatrix} \end{bmatrix} = \begin{bmatrix} 40 \end{bmatrix}. }[/math]

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

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

С нулями

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

[math]\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}. }[/math]

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

[math]\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}. }[/math]

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

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

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

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

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

[math]\displaystyle{ \det(A) \cdot M_{1,k}^{1,k} = M_1^1 \cdot M_k^k - M_1^k\cdot M_k^1. }[/math]

Литература

• 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.