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

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

Общий метод

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

  1. Пусть A - заданная матрица размера n  ×  n . Расположите A так, чтобы внутри не было нулей. Явным определением интерьера будет все a i, j с . Это можно сделать, используя любую операцию, которую обычно можно выполнить без изменения значения определителя, например, добавление нескольких строк из одной строки в другую.
  2. Создайте  матрицу B  размером ( n - 1) × ( n - 1), состоящую из определителей каждой подматрицы 2 × 2 матрицы A. Явно запишем
  3. Используя эту  матрицу ( n  - 1) × ( n - 1), выполните шаг 2, чтобы получить  матрицу C. ( n  - 2) × ( n - 2). Разделите каждый член в C на соответствующий член внутри A, чтобы .
  4. Пусть A = B и B = C. При необходимости повторяйте шаг 3, пока не будет найдена матрица 1 × 1; его единственная запись - определитель.

Примеры

Без нулей

Один хочет найти

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

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

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

Затем мы должны разделить каждый элемент на соответствующий элемент нашей исходной матрицы. Внутри матрица оригинальная , поэтому после деления получим . Процесс необходимо повторить, чтобы получить матрицу 1 × 1. Деление на внутреннюю часть матрицы 3 × 3, которая равна −5, дает, и −8 действительно является определителем исходной матрицы.

С нулями

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

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

Следовательно, мы приходим к определителю 36.

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

Доказательство того, что метод уплотнения вычисляет определитель матрицы, если деления на ноль не встречаются, основано на тождестве, известном как тождество Деснанота-Якоби (1841) или, в более общем смысле, тождество детерминанта Сильвестра (1851).

Позвольте быть квадратной матрицей, и для каждого обозначать матрицей, полученной в результате удаления -й строки и -го столбца. Аналогично, for , обозначается матрицей, полученной в результате удаления -й и -й строк и -го и -го столбцов.

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

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

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

Теперь заметим, что по индукции следует, что при применении процедуры уплотнения Доджсона к квадратной матрице порядка матрица на -м этапе вычисления (где первый этап соответствует самой матрице ) состоит из всех связанных миноров порядка of , где связанный минор - определитель связного подблока смежных записей . В частности, на последнем этапе получается матрица, содержащая единственный элемент, равный единственному связному минору порядка , а именно определителю .

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

Мы следуем лечению в книге Брессу; для альтернативного комбинаторного доказательства см. статью Зейльбергера. Обозначим (с точностью до знака, -й минор числа ) и определим матрицу как


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


где мы используем для обозначения -й записи . Определитель этой матрицы . Во-вторых, это равно произведению определителей . Но очевидно, что тождество следует из приравнивания двух полученных нами выражений и деления на (это допустимо, если рассматривать тождества как полиномиальные тождества над кольцом многочленов от неопределенных переменных ).


Ноты

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

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