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

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Январь 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Позвольте быть квадратной матрицей, и для каждого обозначать матрицей, полученной в результате удаления -й строки и -го столбца. Точно так же для обозначается матрицей, которая получается в результате удаления -й и -ой строк и -го и -го столбцов.${\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}$

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

Мы следуем трактовке в книге Брессу; альтернативное комбинаторное доказательство см. в статье Зейльбергера. Обозначим (с точностью до знака, -й минор числа ) и определим матрицу как${\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}}$

Заметки [ править ]

Ссылки и дополнительная литература [ править ]

• Брессуд, Дэвид М. , Доказательства и подтверждения: история гипотезы о матрице переменных знаков , MAA Spectrum, Mathematical Association of America, Вашингтон, округ Колумбия, 1999.
• Брессуд, Дэвид М. и Пропп, Джеймс, Как была решена гипотеза о знакопеременной матрице , Уведомления Американского математического общества , 46 (1999), 637-646.
• Доджсон, К.Л. (1866–1867). «Конденсация детерминант, являющаяся новым и кратким методом вычисления их арифметических значений» (PDF) . Труды Лондонского королевского общества . 15 : 150–155.
• Кнут, Дональд , Перекрывающиеся пфаффианы , Электронный журнал комбинаторики , 3 вып. 2 (1996).
• Лоткин, Марк (1959). «Примечание о методах подрядчиков». Американский математический ежемесячник . 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 }$
• Зейлбергер, Дорон , детерминантное правило оценки Доджсона, подтвержденное двумя выборками мужчин и женщин , Электронный журнал комбинаторики , 4 вып. 2 (1997).

Внешние ссылки [ править ]

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