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

Формула Лейбница — выражение для определителя квадратной матрицы размера через перестановки её элементов:

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

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

.

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

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

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

Прямое вычисление по формуле Лейбница требует в общем случае   операций, то есть число операций асимптотически пропорционально факториалу   (числу упорядоченных перестановок из   элементов. Для больших   определитель можно вычислить за   операций путём формирования LU-разложения   (обычно получаемого с помощью исключений Гаусса или аналогичных методов), и в этом случае  , а определители треугольных матриц   и   — произведения диагональных элементов матриц. (В практических приложениях вычислительной линейной алгебры, однако, явное вычисление определителя используется редко[2]).

ПримечанияПравить

  1. Lang, 2004, с. 148 Theorem 2.3.
  2. Trefethen & Bau, 1997.

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