Leibniz formula for determinants

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 ${\displaystyle A}$ is an ${\displaystyle n\times n}$ matrix, where ${\displaystyle a_{ij}}$ is the entry in the ${\displaystyle i}$-th row and ${\displaystyle j}$-th column of ${\displaystyle A}$, the formula is

${\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 ${\displaystyle \operatorname {sgn} }$ is the sign function of permutations in the permutation group ${\displaystyle S_{n}}$, which returns ${\displaystyle +1}$ and ${\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

${\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 ${\displaystyle \Omega (n!\cdot n)}$ operations in general—that is, a number of operations asymptotically proportional to ${\displaystyle n}$ factorial—because ${\displaystyle n!}$ is the number of order-${\displaystyle n}$ permutations. This is impractically difficult for even relatively small ${\displaystyle n}$. Instead, the determinant can be evaluated in ${\displaystyle O(n^{3})}$ operations by forming the LU decomposition ${\displaystyle A=LU}$ (typically via Gaussian elimination or similar methods), in which case ${\displaystyle \det A=\det L\cdot \det U}$ and the determinants of the triangular matrices ${\displaystyle L}$ and ${\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 ${\displaystyle O(n^{3})}$ operations by reducing the problem to matrix multiplication, but most such algorithms are not practical.