Формула Лейбніца для визначників

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Формула Лейбніца виражає визначник квадратної матриці

A = (a_{ij})_{i,j = 1, \dots, n}

через перестановки елементів матриці. Для n×n матриці формула така

\det(A) = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i), i},

де sgn — парність перестановки у групі перестановок Sn, яка повертає +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(n3) дій, використовуючи LU розклад матриці A = LU (зазвичай через метод Гауса або подібний), в цьому випадку \det A = (\det L) (\det U) а визначники трикутних матриць L і U є просто добутками їх діагональних елементів. (Однак, у практичному застосуванні чисельної лінійної алгебри, явний розрахунок визначника необхідний рідко.)