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

Формула Лейбница — выражение для определителя квадратной матрицы $A=(a_{i,j})$$A=(a_{i,j})$ размера $n\times <!--\; \times \; -->n$$n\times n$ через перестановки её элементов:

$det(A)=\underset{\mathrm{\tau <!--\; \tau \; -->}\in <!--\; \in \; -->S_n}{\sum <!--\; \sum \; -->}\mathrm{sgn}<!--\; \; -->(\mathrm{\tau <!--\; \tau \; -->})\underset{i=1}{\overset{n}{\prod <!--\; \prod \; -->}}{a}_{i,\mathrm{\tau <!--\; \tau \; -->}(i)}=\underset{\mathrm{\sigma <!--\; \sigma \; -->}\in <!--\; \in \; -->S_n}{\sum <!--\; \sum \; -->}\mathrm{sgn}<!--\; \; -->(\mathrm{\sigma <!--\; \sigma \; -->})\underset{i=1}{\overset{n}{\prod <!--\; \prod \; -->}}{a}_{\mathrm{\sigma <!--\; \sigma \; -->}(i),i},$$\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},$

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

С использованием символа Леви-Чивиты и соглашений о суммировании Эйнштейна:

$det(A)={\mathrm{ϵ<!--\; ϵ\; -->}}_{i_1\cdots <!--\; \cdots \; -->i_n}{a}_{1i_1}\cdots <!--\; \cdots \; -->a_{n{i}_n}$$\det(A)=\epsilon _{i_{1}\cdots i_{n}}{a}_{1i_{1}}\cdots {a}_{ni_{n}}$.

Названа в честь Готфрида Лейбница, который ввёл понятие определителя и способ его вычисления в 1678 году.

Единственная знакопеременная мультилинейная функция^[en], обращающаяся в единицу на единичной матрице — это функция, определённая формулой Лейбница; таким образом, определитель может быть однозначно определён как знакопеременная мультилинейная функция, полилинейная относительно столбцов, обращающаяся в единицу на единичной матрице.

Вычислительная сложностьПравить

Прямое вычисление по формуле Лейбница требует в общем случае $\mathrm{\Omega <!--\; \Omega \; -->}(n!\cdot <!--\; \cdot \; -->n)$$\Omega (n!\cdot n)$  операций, то есть, число операций асимптотически пропорционально факториалу $n$$n$  (числу упорядоченных перестановок из $n$$n$  элементов). Для больших $n$$n$  определитель можно вычислить за $O(n^3)$$O(n^{3})$  операций путём формирования LU-разложения $A=LU$$A=LU$  (обычно получаемого с помощью метода Гаусса или аналогичных методов), и в этом случае $detA=(detL)(detU)$$\det A=(\det L)(\det U)$ , а определители треугольных матриц $L$$L$  и $U$$U$  равняются произведениям диагональных элементов матриц. (В практических приложениях вычислительной линейной алгебры, однако, явное вычисление определителя используется редко).

Смотрите такжеПравить

• Дифференцирование поисковой функции
• Формула Лейбница (производной произведения)

ЛитератураПравить

• Определитель — статья из Математической энциклопедии. Д. И. Супруненко
• Lloyd N. Trefethen, David Bau. Numerical Linear Algebra. — SIAM, 1997. — ISBN 978-0898713619.
• Serge Lang. Linear Algebra. — Springer-Verlag, 2004. — (Undergraduate texts in mathematic). — ISBN 0-387-96412-6.