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

Общий метод

править

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

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

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

 

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

 

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

Примеры

править

Без нулей

править

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

 

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

 

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

 
 

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

 

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

 

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

 

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

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

С нулями

править

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

 

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

 

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

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

править

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

править

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

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

 

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

править

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

править

Литература

править
  • 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).

Ссылки

править