- Конденсация Доджсона
-
В математике, конденсация Доджсона — это метод вычисления определителей. Метод назван в честь его создателя Чарльза Доджсона (более известного, как Льюис Кэррол). Метод заключается в понижении порядка определителя специальным образом до порядка 1, единственный элемент которого и является искомым определителем.
Содержание
Общий метод
Алгоритм может быть описан с помощью следующих четырёх этапов:
- Пусть — заданная квадратная матрица размера . Запишем матрицу таким образом, чтобы она содержала только ненулевые элементы во внутренней части, то есть , если . Это может быть сделано, например, с помощью операции добавления к строке определителя некоторой другой строки, умноженной на некоторое число.
- Запишем матрицу размера , состоящую из миноров порядка 2 матрицы . В явном виде — .
- Применяя этап № 2 к матрице , запишем матрицу размера , разделив соответствующие элементы полученной матрицы на внутренние элементы матрицы : .
- Пусть и . Повторяем этап № 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).
Ссылки
Категория:- Определители
Wikimedia Foundation. 2010.