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

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

Общий метод

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

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

Примеры

Без нулей

Человек желает найти

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

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

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

{\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}}.

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

{\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}}.

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

С нулями

Просто записав матрицы:

{\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. Мы можем выполнить четыре замены строк в исходной матрице, чтобы сохранить определитель, и повторить процесс, при этом большая часть определителей будет рассчитана заранее:

{\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]

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

Личность Денано-Якоби

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

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

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

\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})}}.

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

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

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

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

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}}.

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

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}}

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

Ссылки

^ Доджсон, К.Л. (1866–1867). «Конденсация определителей: новый и краткий метод вычисления их арифметических значений» (PDF) . Труды Лондонского королевского общества . 15 : 150–155. Бибкод : 1866RSPS...15..150D .
^ Сильвестр, Джеймс Джозеф (1851). «О связи между минорными определителями линейно эквивалентных квадратичных функций». Философский журнал . 1 : 295–305.
Цитируется в Акритас, АГ; Акритас, ЕК; Малащонок, Г.И. (1996). «Различные доказательства (определяющей) личности Сильвестра». Математика и компьютеры в моделировании . 42 (4–6): 585. doi : 10.1016/S0378-4754(96)00035-3 .
^ Брессуд, Дэвид (1999). Доказательства и подтверждения: история гипотезы о матрице чередующихся знаков . Издательство Кембриджского университета. ISBN 9781316582756 .
^ Зейлбергер, Дорон. «Правило детерминантной оценки Доджсона, доказанное двукратными мужчинами и женщинами» . Электрон. Дж. Комб . 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.
Роббинс, Дэвид П., История $1,2,7,42,429,7436,\cdots$ , The Mathematical Intelligencer , 13 (1991), 12–19.

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

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

[1] Доджсон, К.Л. (1866–1867). «Конденсация определителей: новый и краткий метод вычисления их арифметических значений» (PDF) . Труды Лондонского королевского общества . 15 : 150–155. Бибкод : 1866RSPS...15..150D .

[2] Сильвестр, Джеймс Джозеф (1851). «О связи между минорными определителями линейно эквивалентных квадратичных функций». Философский журнал . 1 : 295–305.
Цитируется в Акритас, АГ; Акритас, ЕК; Малащонок, Г.И. (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 г.

[1]

[2]

[3]

[4]