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

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

Общий метод

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

1. Пусть $~A$ — заданная квадратная матрица размера $n \times n$. Запишем матрицу $~A$ таким образом, чтобы она содержала только ненулевые элементы во внутренней части, то есть $a_{ij}\ne 0$, если $~i,j=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}, ~i,j=1 \ldots n-1$.
3. Применяя этап № 2 к матрице $~B$, запишем матрицу $~C$ размера $(n-2) \times (n-2)$, разделив соответствующие элементы полученной матрицы на внутренние элементы матрицы $~A$: $c_{i,j} = \dfrac{b_{i,j}}{a_{i + 1, j + 1}}, 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} \\ \\ \begin{vmatrix} -1 & -2 \\ -1 & -1 \end{vmatrix} & \begin{vmatrix} -2 & -1 \\ -1 & 2 \end{vmatrix} & \begin{vmatrix} -1 & -6 \\ 2 & 4 \end{vmatrix} \\ \\ \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} \\ \\ \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\le i, j\le k$ обозначим $M_i^j$ минор матрицы $~A$, который получается вычёркиванием $~i$-й строки и $~j$-го столбца. Аналогично для $1\le i, j, p,q\le 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 The Royal Society
• 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, \cdots$, 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).

Ссылки

• Dodgson Condensation на MathWorld.