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

Метод вычисления определителей

В математике конденсация Доджсона или метод контрактантов — это метод вычисления определителей квадратных матриц . Он назван в честь своего изобретателя Чарльза Лютвиджа Доджсона (более известного по своему псевдониму, как Льюис Кэрролл, популярный автор), который открыл его в 1866 году. ^[1] Метод в случае матрицы n  ×  n заключается в построении матрицы ( n  − 1) × ( n  − 1), ( n  − 2) × ( n  − 2) и так далее, заканчивая матрицей 1 × 1, которая имеет один элемент — определитель исходной матрицы.

Общий метод

Этот алгоритм можно описать в виде следующих четырех шагов:

1. Пусть A — заданная матрица n  ×  n . Расположите A так, чтобы внутри нее не было нулей. Явное определение внутренней части — все a _i,j с . Это можно сделать с помощью любой операции, которую можно было бы выполнить обычным образом, не меняя значения определителя, например, прибавив кратное одной строки к другой. ${\displaystyle i,j\neq 1,n}$
2. Создадим матрицу B размером ( n  − 1) × ( n  − 1), состоящую из определителей каждой подматрицы A размером 2 × 2. Явно запишем ${\displaystyle b_{i,j}={\begin{vmatrix}a_{i,j}&a_{i,j+1}\\a_{i+1,j}&a_{i+1,j+1}\end{vmatrix}}.}$
3. Используя эту матрицу ( n  − 1) × ( n  − 1), выполните шаг 2, чтобы получить матрицу C размером ( n  − 2) × ( n  − 2). Разделите каждый член в C на соответствующий член внутри A, поэтому . ${\displaystyle c_{i,j}={\begin{vmatrix}b_{i,j}&b_{i,j+1}\\b_{i+1,j}&b_{i+1,j+1}\end{vmatrix}}/a_{i+1,j+1}}$
4. Пусть A = B и B = C. Повторяйте шаг 3 по мере необходимости, пока не будет найдена матрица 1 × 1; ее единственным элементом является определитель.

Примеры

Без нулей

Хочется найти

${\displaystyle {\begin{vmatrix}-2&-1&-1&-4\\-1&-2&-1&-6\\-1&-1&2&4\\2&1&-3&-8\end{vmatrix}}.}$

Все внутренние элементы ненулевые, поэтому нет необходимости перестраивать матрицу.

Составляем матрицу из ее подматриц 2 × 2.

${\displaystyle {\begin{bmatrix}{\begin{vmatrix}-2&-1\\-1&-2\end{vmatrix}}&{\begin{vmatrix}-1&-1\\-2&-1\end{vmatrix}}&{\begin{vmatrix}-1&-4\\-1&-6\end{vmatrix}}\\\\{\begin{vmatrix}-1&-2\\-1&-1\end{vmatrix}}&{\begin{vmatrix}-2&-1\\-1&2\end{vmatrix}}&{\begin{vmatrix}-1&-6\\2&4\end{vmatrix}}\\\\{\begin{vmatrix}-1&-1\\2&1\end{vmatrix}}&{\begin{vmatrix}-1&2\\1&-3\end{vmatrix}}&{\begin{vmatrix}2&4\\-3&-8\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}3&-1&2\\-1&-5&8\\1&1&-4\end{bmatrix}}.}$

Затем находим еще одну матрицу определителей:

${\displaystyle {\begin{bmatrix}{\begin{vmatrix}3&-1\\-1&-5\end{vmatrix}}&{\begin{vmatrix}-1&2\\-5&8\end{vmatrix}}\\\\{\begin{vmatrix}-1&-5\\1&1\end{vmatrix}}&{\begin{vmatrix}-5&8\\1&-4\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}-16&2\\4&12\end{bmatrix}}.}$

Затем мы должны разделить каждый элемент на соответствующий элемент нашей исходной матрицы. Внутренность исходной матрицы равна , поэтому после деления мы получаем . Процесс нужно повторить, чтобы получить матрицу 1 × 1. Деление на внутренность матрицы 3 × 3, которая равна просто −5, дает и −8 действительно является определителем исходной матрицы. ${\displaystyle {\begin{bmatrix}-2&-1\\-1&2\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}8&-2\\-4&6\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}{\begin{vmatrix}8&-2\\-4&6\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}40\end{bmatrix}}.}$ ${\displaystyle {\begin{bmatrix}-8\end{bmatrix}}}$

С нулями

Проще говоря, выписываем матрицы:

${\displaystyle {\begin{bmatrix}2&-1&2&1&-3\\1&2&1&-1&2\\1&-1&-2&-1&-1\\2&1&-1&-2&-1\\1&-2&-1&-1&2\end{bmatrix}}\to {\begin{bmatrix}5&-5&-3&-1\\-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\end{bmatrix}}\to {\begin{bmatrix}-15&6&12\\0&0&6\\6&-6&8\end{bmatrix}}.}$

Здесь мы сталкиваемся с проблемой. Если мы продолжим процесс, то в конечном итоге будем делить на 0. Мы можем выполнить четыре обмена строк в исходной матрице, чтобы сохранить определитель, и повторить процесс, при этом большинство определителей будут вычислены заранее:

${\displaystyle {\begin{bmatrix}1&2&1&-1&2\\1&-1&-2&-1&-1\\2&1&-1&-2&-1\\1&-2&-1&-1&2\\2&-1&2&1&-3\end{bmatrix}}\to {\begin{bmatrix}-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\\3&-5&1&1\end{bmatrix}}\to {\begin{bmatrix}0&0&6\\6&-6&8\\-17&8&-4\end{bmatrix}}\to {\begin{bmatrix}0&12\\18&40\end{bmatrix}}\to {\begin{bmatrix}36\end{bmatrix}}.}$

Таким образом, мы приходим к определителю 36.

Тождество Деснанота–Якоби и доказательство корректности алгоритма конденсации

Доказательство того, что метод конденсации вычисляет определитель матрицы, если не встречается делений на ноль, основано на тождестве, известном как тождество Деснанота–Якоби (1841) или, в более общем смысле, тождество определителя Сильвестра (1851). ^[2]

Пусть будет квадратной матрицей, и для каждого обозначим через матрицу, которая получается путем удаления -й строки и -го столбца. Аналогично, для обозначим через матрицу, которая получается путем удаления -й и -й строк и -го и -го столбцов. ${\displaystyle M=(m_{i,j})_{i,j=1}^{k}}$ ${\displaystyle 1\leq i,j\leq k}$ ${\displaystyle M_{i}^{j}}$ ${\displaystyle M}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle 1\leq i,j,p,q\leq k}$ ${\displaystyle M_{i,j}^{p,q}}$ ${\displaystyle M}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle p}$ ${\displaystyle q}$

Тождество Деснанота–Якоби

${\displaystyle \det(M)\det(M_{1,k}^{1,k})=\det(M_{1}^{1})\det(M_{k}^{k})-\det(M_{1}^{k})\det(M_{k}^{1}).}$

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

Перепишите идентичность как

${\displaystyle \det(M)={\frac {\det(M_{1}^{1})\det(M_{k}^{k})-\det(M_{1}^{k})\det(M_{k}^{1})}{\det(M_{1,k}^{1,k})}}.}$

Теперь заметим, что по индукции следует, что при применении процедуры конденсации Доджсона к квадратной матрице порядка , матрица на -м этапе вычисления (где первый этап соответствует самой матрице ) состоит из всех связанных миноров порядка , где связанный минор является определителем связанного подблока смежных элементов . В частности, на последнем этапе получается матрица, содержащая единственный элемент, равный уникальному связанному минору порядка , а именно определитель . ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k=1}$ ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle k\times k}$ ${\displaystyle A}$ ${\displaystyle k=n}$ ${\displaystyle n}$ ${\displaystyle A}$

Доказательство тождества Деснанота-Якоби

Мы следуем изложению в книге « Доказательства и подтверждения: история гипотезы о матрице с чередующимися знаками» ^[3] ; альтернативное комбинаторное доказательство было дано в статье Дорона Зейлбергера ^[4] .

Обозначим (с точностью до знака, -й минор числа ) и определим матрицу как ${\displaystyle a_{i,j}=(-1)^{i+j}\det(M_{i}^{j})}$ ${\displaystyle (i,j)}$ ${\displaystyle M}$ ${\displaystyle k\times k}$ ${\displaystyle M'}$

${\displaystyle M'={\begin{pmatrix}a_{1,1}&0&0&0&\ldots &0&a_{k,1}\\a_{1,2}&1&0&0&\ldots &0&a_{k,2}\\a_{1,3}&0&1&0&\ldots &0&a_{k,3}\\a_{1,4}&0&0&1&\ldots &0&a_{k,4}\\\vdots &\vdots &\vdots &\vdots &&\vdots &\vdots \\a_{1,k-1}&0&0&0&\ldots &1&a_{k,k-1}\\a_{1,k}&0&0&0&\ldots &0&a_{k,k}\end{pmatrix}}.}$

(Обратите внимание, что первый и последний столбцы равны столбцам сопряженной матрицы ). Теперь тождество получается путем вычисления двумя способами. Во-первых, мы можем напрямую вычислить произведение матриц (используя простые свойства сопряженной матрицы или, в качестве альтернативы, используя формулу для разложения определителя матрицы в терминах строки или столбца), чтобы получить ${\displaystyle M'}$ ${\displaystyle A}$ ${\displaystyle \det(MM')}$ ${\displaystyle MM'}$

${\displaystyle MM'={\begin{pmatrix}\det(M)&m_{1,2}&m_{1,3}&\ldots &m_{1,k-1}&0\\0&m_{2,2}&m_{2,3}&\ldots &m_{2,k-1}&0\\0&m_{3,2}&m_{3,3}&\ldots &m_{3,k-1}&0\\\vdots &\vdots &\vdots &&\vdots &\vdots &\vdots \\0&m_{k-1,2}&m_{k-1,3}&\ldots &m_{k-1,k-1}&0\\0&m_{k,2}&m_{k,3}&\ldots &m_{k,k-1}&\det(M)\end{pmatrix}}}$

где мы используем для обозначения -го элемента матрицы . Определитель этой матрицы равен . Во-вторых, это равно произведению определителей, . Но очевидно, что тождество следует из приравнивания двух выражений, которые мы получили для , и деления на (это допускается, если рассматривать тождества как полиномиальные тождества над кольцом полиномов от неопределенных переменных ). ${\displaystyle m_{i,j}}$ ${\displaystyle (i,j)}$ ${\displaystyle M}$ ${\displaystyle \det(M)^{2}\cdot \det(M_{1,k}^{1,k})}$
${\displaystyle \det(M)\cdot \det(M')}$
${\displaystyle \det(M')=a_{1,1}a_{k,k}-a_{k,1}a_{1,k}=\det(M_{1}^{1})\det(M_{k}^{k})-\det(M_{1}^{k})\det(M_{k}^{1}),}$
${\displaystyle \det(MM')}$ ${\displaystyle \det(M)}$ ${\displaystyle k^{2}}$ ${\displaystyle (m_{i,j})_{i,j=1}^{k}}$

Ссылки

1. Доджсон, CL (1866–1867). «Конденсация определителей, как новый и краткий метод вычисления их арифметических значений» (PDF) . Труды Лондонского королевского общества . 15 : 150–155. Bibcode : 1866RSPS...15..150D.
2. Сильвестр, Джеймс Джозеф (1851). «О связи между младшими определителями линейно эквивалентных квадратичных функций». Philosophical Magazine . 1 : 295–305.
   Цитируется в Akritas, AG; Akritas, EK; Malaschonok, GI (1996). «Различные доказательства тождества (детерминанта) Сильвестра». Математика и компьютеры в моделировании . 42 (4–6): 585. doi :10.1016/S0378-4754(96)00035-3.
3. Брессо, Дэвид (1999). Доказательства и подтверждения: История гипотезы о матрице с чередующимися знаками . Cambridge University Press. ISBN 9781316582756.
4. Zeilberger, Doron. "Dodgson's Determinant-Evaluation Rule Proved by Two-Timing Men and Women". Electron. J. Comb . 4 (2): статья R22. doi : 10.37236/1337 . Получено 27 октября 2023 г.

Дальнейшее чтение

• Брессо, Дэвид М. и Пропп, Джеймс, Как была решена гипотеза матрицы чередующихся знаков, Notices of the American Mathematical Society , 46 (1999), 637-646.
• Кнут, Дональд , Перекрывающиеся Пфаффианы, Электронный журнал комбинаторики , 3 № 2 (1996).
• Лоткин, Марк (1959). «Заметка о методе контрактантов». The American Mathematical Monthly . 66 (6): 476–479. doi :10.2307/2310629. JSTOR  2310629.
• Миллс, Уильям Х., Роббинс, Дэвид П. и Рамси, Ховард-младший, Доказательство гипотезы Макдональда, Inventiones Mathematicae , 66 (1982), 73-87.
• Миллс, Уильям Х., Роббинс, Дэвид П. и Рамси, Ховард-младший, Матрицы с чередующимися знаками и нисходящие плоские разбиения, Журнал комбинаторной теории , Серия A , 34 (1983), 340-359.
• Роббинс, Дэвид П., История , The Mathematical Intelligencer , 13 (1991), 12-19. ${\displaystyle 1,2,7,42,429,7436,\cdots }$

Внешние ссылки

• Вайсштейн, Эрик В. «Конденсация Доджсона». MathWorld .