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

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

1. Пусть  — заданная квадратная матрица размера . Запишем матрицу таким образом, чтобы она содержала только ненулевые элементы во внутренней части, то есть , если . Это может быть сделано, например, с помощью операции добавления к строке матрицы некоторой другой строки, умноженной на некоторое число, отличное от нуля.

2. Запишем матрицу размера , состоящую из миноров порядка 2 матрицы . В явном виде:

3. Применяя этап № 2 к матрице , запишем матрицу размера , разделив соответствующие элементы полученной матрицы на внутренние элементы матрицы :

4. Пусть и . Повторяем этап № 3 до тех пор, пока не получим матрицу порядка 1. Её единственный элемент и будет искомым определителем.

Примеры

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

Составим матрицу из миноров порядка 2:

Составим матрицу :

Элементы матрицы мы получили, разделив элементы полученной матрицы

на внутренние элементы матрицы

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

Делим на внутреннюю часть матрицы размера , то есть на , получаем .

и есть искомый определитель исходной матрицы.

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

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

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

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

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

Пусть  — квадратная матрица, и для всех обозначим минор матрицы , который получается вычёркиванием -й строки и -го столбца. Аналогично для обозначим минор, который получается из матрицы вычёркиванием -й и -й строк и -го и -го столбцов. Тогда

Доказательство тождества Доджсона

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

Литература

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

Ссылки

Категория:Определители