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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В математике, конденсация Доджсона — это метод вычисления определителей. Метод назван в честь его создателя Чарльза Доджсона (более известного, как Льюис Кэррол). Метод заключается в понижении порядка определителя специальным образом до порядка 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}=\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).

Ссылки[править | править вики-текст]