Формула Лейбница для определителей - Leibniz formula for determinants

В алгебра, то Формула Лейбница, названный в честь Готфрид Лейбниц, выражает детерминант из квадратная матрица в терминах перестановок матричных элементов. Если А является п×п матрица, где а_я,j это запись в яй ряд и j-й столбец А, формула

${displaystyle det(A)=sum _{ au in S_{n}}operatorname {sgn}( au )prod _{i=1}^{n}a_{i, au (i)}=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}a_{sigma (i),i},}$

где sgn - это функция знака из перестановки в группа перестановок S_п, который возвращает +1 и -1 для четные и нечетные перестановки, соответственно.

Еще одно распространенное обозначение, используемое для формулы, - это Символ Леви-Чивита и использует Обозначение суммирования Эйнштейна, где становится

${displaystyle det(A)=epsilon _{i_{1}cdots i_{n}}{a}_{1i_{1}}cdots {a}_{ni_{n}},}$

который может быть более знаком физикам.

Непосредственная оценка формулы Лейбница из определения требует ${displaystyle Omega (n!cdot n)}$ операций в целом, т. е. количество операций, асимптотически пропорциональных п факториал -потому что п! это номер заказа-п перестановки. Это непрактично сложно для больших п. Вместо этого определитель может быть вычислен в O (п³) операций путем формирования LU разложение ${displaystyle A=LU}$ (обычно через Гауссово исключение или аналогичные методы), и в этом случае ${displaystyle det A=(det L)(det U)}$ и определители треугольных матриц L и U являются просто продуктами их диагональных входов. (Однако в практических приложениях числовой линейной алгебры явное вычисление определителя требуется редко.) См., Например, Trefethen & Bau (1997).

Официальное заявление и доказательство

Теорема.Существует ровно одна функция

${displaystyle F:M_{n}(mathbb {K} )ightarrow mathbb {K} }$

который чередование полилинейный w.r.t. столбцы и такие, что ${displaystyle F(I)=1}$.

Доказательство.

Уникальность: Позволять ${displaystyle F}$ - такая функция, и пусть ${displaystyle A=(a_{i}^{j})_{i=1,dots ,n}^{j=1,dots ,n}}$ быть ${displaystyle n imes n}$ матрица. Вызов ${displaystyle A^{j}}$ то ${displaystyle j}$-й столбец ${displaystyle A}$, т.е. ${displaystyle A^{j}=(a_{i}^{j})_{i=1,dots ,n}}$, так что ${displaystyle A=left(A^{1},dots ,A^{n}ight).}$

Кроме того, пусть ${displaystyle E^{k}}$ обозначить ${displaystyle k}$-й вектор-столбец единичной матрицы.

Теперь каждый записывает ${displaystyle A^{j}}$с точки зрения ${displaystyle E^{k}}$, т.е.

${displaystyle A^{j}=sum _{k=1}^{n}a_{k}^{j}E^{k}}$.

В качестве ${displaystyle F}$ полилинейно,

${displaystyle {egin{aligned}F(A)&=Fleft(sum _{k_{1}=1}^{n}a_{k_{1}}^{1}E^{k_{1}},dots ,sum _{k_{n}=1}^{n}a_{k_{n}}^{n}E^{k_{n}}ight)&=sum _{k_{1},dots ,k_{n}=1}^{n}left(prod _{i=1}^{n}a_{k_{i}}^{i}ight)Fleft(E^{k_{1}},dots ,E^{k_{n}}ight).end{aligned}}}$

Из чередования следует, что любой член с повторяющимися индексами равен нулю. Таким образом, сумма может быть ограничена кортежами с неповторяющимися индексами, то есть перестановками:

${displaystyle F(A)=sum _{sigma in S_{n}}left(prod _{i=1}^{n}a_{sigma (i)}^{i}ight)F(E^{sigma (1)},dots ,E^{sigma (n)}).}$

Поскольку F чередуется, столбцы ${displaystyle E}$ можно поменять местами, пока он не станет идентификатором. В функция знака ${displaystyle operatorname {sgn}(sigma )}$ определяется для подсчета необходимого количества перестановок и учета результирующего изменения знака. В итоге получается:

${displaystyle {egin{aligned}F(A)&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(prod _{i=1}^{n}a_{sigma (i)}^{i}ight)F(I)&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}a_{sigma (i)}^{i}end{aligned}}}$

в качестве ${displaystyle F(I)}$ должен быть равен ${displaystyle 1}$.

Следовательно, никакая функция, кроме функции, определенной формулой Лейбница, не может быть полилинейной переменной функцией с ${displaystyle Fleft(Iight)=1}$.

Существование: Теперь покажем, что F, где F - функция, определенная формулой Лейбница, обладает этими тремя свойствами.

Полилинейный:

${displaystyle {egin{aligned}F(A^{1},dots ,cA^{j},dots )&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )ca_{sigma (j)}^{j}prod _{i=1,ieq j}^{n}a_{sigma (i)}^{i}&=csum _{sigma in S_{n}}operatorname {sgn}(sigma )a_{sigma (j)}^{j}prod _{i=1,ieq j}^{n}a_{sigma (i)}^{i}&=cF(A^{1},dots ,A^{j},dots )\F(A^{1},dots ,b+A^{j},dots )&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(b_{sigma (j)}+a_{sigma (j)}^{j}ight)prod _{i=1,ieq j}^{n}a_{sigma (i)}^{i}&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(left(b_{sigma (j)}prod _{i=1,ieq j}^{n}a_{sigma (i)}^{i}ight)+left(a_{sigma (j)}^{j}prod _{i=1,ieq j}^{n}a_{sigma (i)}^{i}ight)ight)&=left(sum _{sigma in S_{n}}operatorname {sgn}(sigma )b_{sigma (j)}prod _{i=1,ieq j}^{n}a_{sigma (i)}^{i}ight)+left(sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}a_{sigma (i)}^{i}ight)&=F(A^{1},dots ,b,dots )+F(A^{1},dots ,A^{j},dots )\end{aligned}}}$

Чередование:

${displaystyle {egin{aligned}F(dots ,A^{j_{1}},dots ,A^{j_{2}},dots )&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(prod _{i=1,ieq j_{1},ieq j_{2}}^{n}a_{sigma (i)}^{i}ight)a_{sigma (j_{1})}^{j_{1}}a_{sigma (j_{2})}^{j_{2}}end{aligned}}}$

Для любого ${displaystyle sigma in S_{n}}$ позволять ${displaystyle sigma '}$ быть набор, равный ${displaystyle sigma }$ с ${displaystyle j_{1}}$ и ${displaystyle j_{2}}$ индексы переключились.

${displaystyle {egin{aligned}F(A)&=sum _{sigma in S_{n},sigma (j_{1})<sigma (j_{2})}left[operatorname {sgn}(sigma )left(prod _{i=1,ieq j_{1},ieq j_{2}}^{n}a_{sigma (i)}^{i}ight)a_{sigma (j_{1})}^{j_{1}}a_{sigma (j_{2})}^{j_{2}}+operatorname {sgn}(sigma ')left(prod _{i=1,ieq j_{1},ieq j_{2}}^{n}a_{sigma '(i)}^{i}ight)a_{sigma '(j_{1})}^{j_{1}}a_{sigma '(j_{2})}^{j_{2}}ight]&=sum _{sigma in S_{n},sigma (j_{1})<sigma (j_{2})}left[operatorname {sgn}(sigma )left(prod _{i=1,ieq j_{1},ieq j_{2}}^{n}a_{sigma (i)}^{i}ight)a_{sigma (j_{1})}^{j_{1}}a_{sigma (j_{2})}^{j_{2}}-operatorname {sgn}(sigma )left(prod _{i=1,ieq j_{1},ieq j_{2}}^{n}a_{sigma (i)}^{i}ight)a_{sigma (j_{2})}^{j_{1}}a_{sigma (j_{1})}^{j_{2}}ight]&=sum _{sigma in S_{n},sigma (j_{1})<sigma (j_{2})}operatorname {sgn}(sigma )left(prod _{i=1,ieq j_{1},ieq j_{2}}^{n}a_{sigma (i)}^{i}ight)left(a_{sigma (j_{1})}^{j_{1}}a_{sigma (j_{2})}^{j_{2}}-a_{sigma (j_{1})}^{j_{2}}a_{sigma (j_{2})}^{j_{_{1}}}ight)\end{aligned}}}$

Таким образом, если ${displaystyle A^{j_{1}}=A^{j_{2}}}$ тогда ${displaystyle F(dots ,A^{j_{1}},dots ,A^{j_{2}},dots )=0}$.

Ну наконец то, ${displaystyle F(I)=1}$:

${displaystyle {egin{aligned}F(I)&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}I_{sigma (i)}^{i}=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}operatorname {delta } _{i,sigma (i)}&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )operatorname {delta } _{sigma ,operatorname {id} _{{1ldots n}}}=operatorname {sgn}(operatorname {id} _{{1ldots n}})=1end{aligned}}}$

Таким образом, единственные чередующиеся полилинейные функции с ${displaystyle F(I)=1}$ ограничены функцией, определенной формулой Лейбница, и на самом деле она также обладает этими тремя свойствами. Следовательно, определитель можно определить как единственную функцию

${displaystyle det :M_{n}(mathbb {K} )ightarrow mathbb {K} }$

с этими тремя свойствами.

Смотрите также

• Матрица
• Разложение Лапласа
• Правило Крамера

Рекомендации

• "Детерминант", Энциклопедия математики, EMS Press, 2001 [1994]
• Trefethen, Lloyd N .; Бау, Дэвид (1 июня 1997 г.). Числовая линейная алгебра. СИАМ. ISBN  978-0898713619.