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

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

$\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}$

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

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

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

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

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

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

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

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

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

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

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

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

Как $F$ является полилинейным, имеет место

${\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}}$

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

$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 чередуется, столбцы $E$ можно менять местами, пока он не станет тождественным. Знаковая функция $\operatorname {sgn}(\sigma )$ определяется для подсчета количества необходимых свопов и учета результирующего изменения знака. Наконец-то получается:

${\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}}$

как $F(I)$ обязан быть равен $1$.

Поэтому никакая функция, кроме функции, определяемой формулой Лейбница, не может быть полилинейной знакопеременной функцией с $F\left(I\right)=1$.

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

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

${\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}}$

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

${\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}}$

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

${\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}}$

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

Окончательно, $F(I)=1$:

${\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}}$

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

См. также

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

Ссылки

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