Открыть главное меню

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

СсылкиПравить