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

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

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

Общий метод

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

1. Пусть A — заданная матрица размера n  ×  n . Расположите А так, чтобы внутри него не было нулей. Явным определением интерьера будет все a _i,j с . Это можно сделать, используя любую операцию, которую обычно можно выполнить без изменения значения определителя, например добавление кратного числа одной строки к другой. ${\displaystyle i,j\neq 1,n}$
2. Создайте ( n  − 1) × ( n  − 1) матрицу B, состоящую из определителей каждой подматрицы 2 × 2 матрицы A. Явно запишем ${\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})}}.}$

Теперь заметим, что по индукции следует, что при применении процедуры конденсации Доджсона к квадратной матрице порядка матрица на --м этапе вычислений (где первый этап соответствует самой матрице ) состоит из всех связных миноров порядка of , где связный минор является определителем связного подблока соседних записей . В частности, на последнем этапе получают матрицу, содержащую единственный элемент, равный уникальному связному минору порядка , а именно определитель . ${\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. Бибкод : 1866RSPS...15..150D.
2. Сильвестр, Джеймс Джозеф (1851). «О связи между минорными определителями линейно эквивалентных квадратичных функций». Философский журнал . 1 : 295–305.
   Цитируется в Akritas, AG; Акритас, ЕК; Малащонок, Г.И. (1996). «Различные доказательства (определяющей) личности Сильвестра». Математика и компьютеры в моделировании . 42 (4–6): 585. doi : 10.1016/S0378-4754(96)00035-3.
3. Брессуд, Дэвид (1999). Доказательства и подтверждения: история гипотезы о матрице чередующихся знаков . Издательство Кембриджского университета. ISBN 9781316582756.
4. Зейлбергер, Дорон. «Правило детерминантной оценки Доджсона, доказанное двукратными мужчинами и женщинами». Электрон. Дж. Комб . 4 (2): статья R22. дои : 10.37236/1337 . Проверено 27 октября 2023 г.

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

• Брессуд, Дэвид М. и Пропп, Джеймс, Как была решена гипотеза о матрице чередующихся знаков, Уведомления Американского математического общества , 46 (1999), 637-646.
• Кнут, Дональд , Перекрывающиеся пфаффианы, Электронный журнал комбинаторики , 3 вып. 2 (1996).
• Лоткин, Марк (1959). «Примечание о методе подрядчиков». Американский математический ежемесячник . 66 (6): 476–479. дои : 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 }$

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

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