Русская Википедия:Конденсация Доджсона
В математике, конденсация Доджсона — это метод вычисления определителей. Метод назван в честь его создателя Чарльза Доджсона (более известного как Льюис Кэрролл). Метод заключается в понижении порядка определителя специальным образом до порядка 1, единственный элемент которого и является искомым определителем.
Общий метод
Алгоритм может быть описан с помощью следующих четырёх этапов:
1. Пусть <math>A</math> — заданная квадратная матрица размера <math>n \times n</math>. Запишем матрицу <math>A</math> таким образом, чтобы она содержала только ненулевые элементы во внутренней части, то есть <math>a_{ij} \ne 0</math>, если <math>i, j \ne 1, n</math>. Это может быть сделано, например, с помощью операции добавления к строке матрицы некоторой другой строки, умноженной на некоторое число.
2. Запишем матрицу <math>B</math> размера <math>(n-1) \times (n-1)</math>, состоящую из миноров порядка 2 матрицы <math>A</math>. В явном виде:
- <math>
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>B</math>, запишем матрицу <math>C</math> размера <math>(n - 2) \times (n - 2)</math>, разделив соответствующие элементы полученной матрицы на внутренние элементы матрицы <math>A</math>:
- <math>
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>A = B</math> и <math>B = C</math>. Повторяем этап № 3 до тех пор, пока не получим матрицу порядка 1. Её единственный элемент и будет искомым определителем.
Примеры
Без нулей
Пусть необходимо вычислить определитель
- <math>
\begin{vmatrix}
-2 & -1 & -1 & -4 \\ -1 & -2 & -1 & -6 \\ -1 & -1 & 2 & 4 \\ 2 & 1 & -3 & -8
\end{vmatrix}. </math>
Составим матрицу <math>B</math> из миноров порядка 2:
- <math>
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>C</math>:
- <math>
\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>
C = \begin{bmatrix}
8 & -2 \\ -4 & 6
\end{bmatrix}. </math>
Элементы матрицы <math>C</math> мы получили, разделив элементы полученной матрицы
- <math>
\begin{bmatrix}
-16 & 2 \\ 4 & 12
\end{bmatrix} </math> на внутренние элементы матрицы <math>A</math>
- <math>
\begin{bmatrix}
-2 & -1 \\ -1 & 2
\end{bmatrix}. </math>
Повторяем этот процесс, пока не получим матрицу порядка 1:
- <math>
\begin{bmatrix}
\begin{vmatrix}
8 & -2 \\
-4 & 6
\end{vmatrix}
\end{bmatrix} = \begin{bmatrix}
40
\end{bmatrix}. </math> Делим на внутреннюю часть матрицы размера <math>3 \times 3</math>, то есть на <math>-5</math>, получаем <math>\begin{bmatrix} -8 \end{bmatrix}</math>.
<math>-8</math> и есть искомый определитель исходной матрицы.
С нулями
Запишем необходимые матрицы:
- <math>
\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>
\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>A = (m_{i,j})_{i,j=1}^k</math> — квадратная матрица, и для всех <math>1 \leqslant i, j \leqslant k</math> обозначим <math>M_i^j</math> минор матрицы <math>A</math>, который получается вычёркиванием <math>i</math>-й строки и <math>j</math>-го столбца. Аналогично для <math>1 \leqslant i, j, p, q \leqslant k</math> обозначим <math>M_{i,j}^{p,q}</math> минор, который получается из матрицы <math>A</math> вычёркиванием <math>i</math>-й и <math>j</math>-й строк и <math>p</math>-го и <math>q</math>-го столбцов. Тогда
- <math>\det(A) \cdot M_{1,k}^{1,k} = M_1^1 \cdot M_k^k - M_1^k\cdot M_k^1.</math>
Доказательство тождества Доджсона
Доказательство корректности конденсации Доджсона
Литература
- Шаблон:Статья
- Шаблон:Статья
- 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).
Ссылки
