Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты.(Январь 2019) (Узнайте, как и когда удалить этот шаблон сообщения)
В математика, Конденсация Доджсона или же метод подрядчиков это метод вычисления детерминанты из квадратные матрицы. Он назван в честь своего изобретателя, Чарльз Лютвидж Доджсон (более известный под своим псевдонимом, как популярный автор Льюис Кэрролл). Метод в случае п × п матрица предназначена для построения (п − 1) × (п - 1) матрица, (п − 2) × (п - 2) и так далее, заканчивая матрицей 1 × 1, которая имеет один элемент, определитель исходной матрицы.
Этот алгоритм можно описать следующими четырьмя шагами:
Пусть A - данное п × п матрица. Расположите A так, чтобы внутри не было нулей. Явное определение интерьера было бы всего лишья, j с . Это можно сделать, используя любую операцию, которую обычно можно выполнить без изменения значения определителя, например, добавление нескольких строк из одной строки в другую.
Создать (п − 1) × (п - 1) матрица B, состоящая из определителей каждой подматрицы 2 × 2 матрицы A. Явно запишем
Используя это (п − 1) × (п - 1) матрицу, выполните шаг 2, чтобы получить (п − 2) × (п - 2) матрица C. Разделите каждый член в C на соответствующий член внутри A так, чтобы .
Пусть A = B и B = C. При необходимости повторяйте шаг 3, пока не будет найдена матрица 1 × 1; его единственная запись - определитель.
Примеры
Без нулей
Один хочет найти
Все внутренние элементы ненулевые, поэтому нет необходимости переупорядочивать матрицу.
Составим матрицу его подматриц размером 2 × 2.
Затем мы находим другую матрицу определителей:
Затем мы должны разделить каждый элемент на соответствующий элемент нашей исходной матрицы. Внутренняя часть исходной матрицы, поэтому после деления получаем. Процесс необходимо повторить, чтобы получить матрицу 1 × 1.Деление на внутреннюю часть матрицы 3 × 3, которая равна −5, дает и −8 действительно является определителем исходной матрицы.
С нулями
Просто выписываем матрицы:
Здесь у нас проблемы. Если мы продолжим процесс, мы, в конечном итоге, разделим на 0. Мы можем выполнить четыре обмена строками в исходной матрице, чтобы сохранить определитель, и повторить процесс, предварительно вычислив большинство определителей:
Следовательно, мы приходим к определителю 36.
Тождество Деснано – Якоби и доказательство корректности алгоритма уплотнения
Доказательство того, что метод уплотнения вычисляет определитель матрицы, если деления на ноль не встречаются, основано на тождестве, известном как Тождество Деснанота – Якоби (1841) или, в более общем смысле, Сильвестр детерминантная личность (1851).[1]
Позволять - квадратная матрица, и для каждого , обозначим через матрица, которая получается из удалив -й ряд и -й столбец. Аналогично для, обозначим через матрица, которая получается из удалив -й и -й ряды и -й и -й столбец.
Тождество Деснанота – Якоби
Доказательство правильности конденсации Доджсона
Перепишите тождество как
Заметим теперь, что по индукции следует, что при применении процедуры конденсации Доджсона к квадратной матрице порядка , матрица в -й этап вычисления (где первый этап соответствует матрице сам) состоит из всех связанные несовершеннолетние порядка из , где связный минор - определитель связного подблок смежных записей . В частности, на последнем этапе , получается матрица, содержащая единственный элемент, равный единственному связному минору порядка , а именно определитель .
Доказательство тождества Деснано-Якоби.
Мы следуем лечению в книге Брессу; альтернативное комбинаторное доказательство см. в статье Зейльбергера. (до подписи -й минор ), и определим матрица к
(Обратите внимание, что первый и последний столбцы равны таковым из сопряженная матрица из ). Идентичность теперь получается путем вычисления двумя способами. Во-первых, мы можем напрямую вычислить матричное произведение (используя простые свойства сопряженной матрицы или, альтернативно, используя формулу для разложения определителя матрицы в терминах строки или столбца), чтобы прийти к
где мы используем для обозначения -я запись . Определитель этой матрицы равен . Во-вторых, это равно произведению определителей, . Но ясно поэтому тождество следует из приравнивания двух полученных нами выражений для и разделив на (это допустимо, если рассматривать тождества как полиномиальные тождества над кольцом многочленов в неопределенные переменные ).
Примечания
^Сильвестр, Джеймс Джозеф (1851). «О связи между минорными определителями линейно эквивалентных квадратичных функций». Философский журнал. 1: 295–305. Цитируется в Акритас, А.Г .; Akritas, E.K .; Малащонок, Г. И. (1996). «Различные доказательства (детерминантной) личности Сильвестра». Математика и компьютеры в моделировании. 42 (4–6): 585. Дои:10.1016 / S0378-4754 (96) 00035-3.
Ссылки и дополнительная литература
Брессуд, Дэвид М., Доказательства и подтверждения: история гипотезы о матрице переменных знаков, MAA Spectrum, Математические ассоциации Америки, Вашингтон, округ Колумбия, 1999.
Лоткин, Марк (1959). «Примечание о методах подрядчиков». Американский математический ежемесячник. 66 (6): 476–479. Дои:10.2307/2310629. JSTOR2310629.
Миллс, Уильям Х., Роббинс, Дэвид П. и Рамси Ховард-младший, Доказательство гипотезы Макдональда, Inventiones Mathematicae, 66 (1982), 73-87.
Миллс, Уильям Х., Роббинс, Дэвид П. и Рамси, Ховард младший, Матрицы чередующихся знаков и нисходящие плоские разбиения. Журнал комбинаторной теории, серия А, 34 (1983), 340-359.
Роббинс, Дэвид П., История , Математический интеллект, 13 (1991), 12-19.