In algebra, the Leibniz formula, named in honor of Gottfried Leibniz, expresses the determinant of a square matrix in terms of permutations of the matrix elements. If A {\displaystyle A} is an n × n {\displaystyle n\times n} matrix, where a i j {\displaystyle a_{ij}} is the entry in the i {\displaystyle i} -th row and j {\displaystyle j} -th column of A {\displaystyle A} , the formula is
det ( A ) = ∑ τ ∈ S n sgn ( τ ) ∏ i = 1 n a i τ ( i ) = ∑ σ ∈ S n sgn ( σ ) ∏ i = 1 n a σ ( i ) i {\displaystyle \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}}
where sgn {\displaystyle \operatorname {sgn} } is the sign function of permutations in the permutation group S n {\displaystyle S_{n}} , which returns + 1 {\displaystyle +1} and − 1 {\displaystyle -1} for even and odd permutations, respectively. Another common notation used for the formula is in terms of the Levi-Civita symbol and makes use of the Einstein summation notation, where it becomes
det ( A ) = ϵ i 1 ⋯ i n a 1 i 1 ⋯ a n i n , {\displaystyle \det(A)=\epsilon _{i_{1}\cdots i_{n}}{a}_{1i_{1}}\cdots {a}_{ni_{n}},}
which may be more familiar to physicists. Directly evaluating the Leibniz formula from the definition requires Ω ( n ! ⋅ n ) {\displaystyle \Omega (n!\cdot n)} operations in general—that is, a number of operations asymptotically proportional to n {\displaystyle n} factorial—because n ! {\displaystyle n!} is the number of order- n {\displaystyle n} permutations. This is impractically difficult for even relatively small n {\displaystyle n} . Instead, the determinant can be evaluated in O ( n 3 ) {\displaystyle O(n^{3})} operations by forming the LU decomposition A = L U {\displaystyle A=LU} (typically via Gaussian elimination or similar methods), in which case det A = det L ⋅ det U {\displaystyle \det A=\det L\cdot \det U} and the determinants of the triangular matrices L {\displaystyle L} and U {\displaystyle U} are simply the products of their diagonal entries. (In practical applications of numerical linear algebra, however, explicit computation of the determinant is rarely required.) See, for example, Trefethen & Bau (1997). The determinant can also be evaluated in fewer than O ( n 3 ) {\displaystyle O(n^{3})} operations by reducing the problem to matrix multiplication, but most such algorithms are not practical.
… excerpt ends here. Continue reading the full article.
