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

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

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

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