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

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

$\det (A)=\sum _{\tau \in S_n}\mathrm{sgn}(\tau )\prod _{i=1}^n{a}_{i,\tau (i)}=\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{a}_{\sigma (i),i},$

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

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

$\det (A)={ϵ}_{i_1\cdots i_n}{a}_{1i_1}\cdots a_{n{i}_n}$.

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

Функция, определённая формулой Лейбница, является единственной Шаблон:Не переведено 5, обращающейся в единицу на единичной матрицеШаблон:Sfn. Таким образом, определитель может быть однозначно определён как знакопеременная мультилинейная функция, полилинейная относительно столбцов и строк, обращающаяся в единицу на единичной матрице.

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

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

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

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

Литература

• Шаблон:Из
• Шаблон:Книга
• Шаблон:Книга