Формула Лейбница для определителей

Математическая формула

В алгебре формула Лейбница , названная в честь Готфрида Лейбница , выражает определитель квадратной матрицы через перестановки элементов матрицы. Если — матрица, где — запись в -й строке и -м столбце , то формула имеет вид ${\displaystyle A}$ ${\displaystyle n\times n}$ ${\displaystyle a_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle A}$

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

где — знаковая функция перестановок в группе перестановок , которая возвращает и для четных и нечетных перестановок соответственно . ${\displaystyle \operatorname {sgn} }$ ${\displaystyle S_{n}}$ ${\displaystyle +1}$ ${\displaystyle -1}$

Другая распространенная запись, используемая для формулы, — это символ Леви-Чивиты , использующий нотацию суммирования Эйнштейна , где она становится

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

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

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

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

Теорема. Существует ровно одна функция , которая является чередующейся полилинейной относительно столбцов и такая, что . ${\displaystyle F:M_{n}(\mathbb {K} )\rightarrow \mathbb {K} }$ ${\displaystyle F(I)=1}$

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

Уникальность: Пусть будет такой функцией, и пусть будет матрицей. Назовем -й столбец , т.е. , так что ${\displaystyle F}$ ${\displaystyle A=(a_{i}^{j})_{i=1,\dots ,n}^{j=1,\dots ,n}}$ ${\displaystyle n\times 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}\right).}$

Также пусть обозначает -й вектор-столбец единичной матрицы. ${\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 {\begin{aligned}F(A)&=F\left(\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}}\right)=\sum _{k_{1},\dots ,k_{n}=1}^{n}\left(\prod _{i=1}^{n}a_{k_{i}}^{i}\right)F\left(E^{k_{1}},\dots ,E^{k_{n}}\right).\end{aligned}}}$

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

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

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

${\displaystyle {\begin{aligned}F(A)&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\left(\prod _{i=1}^{n}a_{\sigma (i)}^{i}\right)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 F\left(I\right)=1}$

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

Многолинейный :

${\displaystyle {\begin{aligned}F(A^{1},\dots ,cA^{j},\dots )&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )ca_{\sigma (j)}^{j}\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\\&=c\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )a_{\sigma (j)}^{j}\prod _{i=1,i\neq 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}\right)\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\\&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\left(\left(b_{\sigma (j)}\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\right)+\left(a_{\sigma (j)}^{j}\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\right)\right)\\&=\left(\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )b_{\sigma (j)}\prod _{i=1,i\neq j}^{n}a_{\sigma (i)}^{i}\right)+\left(\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\prod _{i=1}^{n}a_{\sigma (i)}^{i}\right)\\&=F(A^{1},\dots ,b,\dots )+F(A^{1},\dots ,A^{j},\dots )\\\\\end{aligned}}}$

Попеременное :

${\displaystyle {\begin{aligned}F(\dots ,A^{j_{1}},\dots ,A^{j_{2}},\dots )&=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)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 {\begin{aligned}F(A)&=\sum _{\sigma \in S_{n},\sigma (j_{1})<\sigma (j_{2})}\left[\operatorname {sgn}(\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)a_{\sigma (j_{1})}^{j_{1}}a_{\sigma (j_{2})}^{j_{2}}+\operatorname {sgn}(\sigma ')\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma '(i)}^{i}\right)a_{\sigma '(j_{1})}^{j_{1}}a_{\sigma '(j_{2})}^{j_{2}}\right]\\&=\sum _{\sigma \in S_{n},\sigma (j_{1})<\sigma (j_{2})}\left[\operatorname {sgn}(\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)a_{\sigma (j_{1})}^{j_{1}}a_{\sigma (j_{2})}^{j_{2}}-\operatorname {sgn}(\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)a_{\sigma (j_{2})}^{j_{1}}a_{\sigma (j_{1})}^{j_{2}}\right]\\&=\sum _{\sigma \in S_{n},\sigma (j_{1})<\sigma (j_{2})}\operatorname {sgn}(\sigma )\left(\prod _{i=1,i\neq j_{1},i\neq j_{2}}^{n}a_{\sigma (i)}^{i}\right)\underbrace {\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}}}\right)} _{=0{\text{, if }}A^{j_{1}}=A^{j_{2}}}\\\\\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 {\begin{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} _{\{1\ldots n\}}}=\operatorname {sgn}(\operatorname {id} _{\{1\ldots n\}})=1\end{aligned}}}$

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

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

• Математический портал

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

Ссылки

• «Определитель», Энциклопедия математики , EMS Press , 2001 [1994]
• Трефетен, Ллойд Н.; Бау, Дэвид (1 июня 1997 г.). Численная линейная алгебра . SIAM . ISBN 978-0898713619.