Leibniz formula for determinants

From Wikipedia, the free encyclopedia

In algebra, the Leibniz formula expresses the determinant of a square matrix $A = (a_{ij})_{i,j = 1, \dots, n}$ in terms of permutations of the matrix' elements. Named in honor of Gottfried Leibniz, the formula is

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

for an n×n matrix, where sgn is the sign function of permutations in the permutation group S_n, which returns +1 and –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)=\epsilon^{i_1\cdots i_n}{A}_{1i_1}\cdots {A}_{ni_n},$

which may be more familiar to physicists.

[edit] Formal statement and proof

Theorem. There exists exactly one function

$F : \mathfrak M_n (\mathbb K) \longrightarrow \mathbb K$

which is alternate multilinear w.r.t. columns and such that $F (I) = 1$ .

Proof.

Uniqueness: Let $F$ be such a function, and let $A = (a_i^j)_{i = 1, \dots, n}^{j = 1, \dots , n}$ be an $n \times n$ matrix. Call $A j$ the $j$ -th column of $A$ , i.e. $A^j = (a_i^j)_{i = 1, \dots , n}$ , so that $A = \left(A^1, \dots, A^n\right).$

Also, let $E k$ denote the $k$ -th column vector of the identity matrix.

Now one writes each of the $A j$ 's in terms of the $E k$ , i.e.

$A^j = \sum_{k = 1}^n a_k^j E^k$ .

As $F$ is multilinear, one has

$\begin{align} F(A)& = F\left(\sum_{k_1 = 1}^n a_{k_1}^1 E^{k_1}, A^2, \dots, A^n\right)\\ & = \sum_{k_1 = 1}^n a_{k_1}^1 F\left(E^{k_1}, A^2, \dots, A^n\right)\\ & = \sum_{k_1 = 1}^n a_{k_1}^1 \sum_{k_2 = 1}^n a_{k_2}^1 F\left(E^{k_1}, E^{k_2}, A^3, \dots, A^n\right)\\ & = \sum_{k_1, k_2 = 1}^n \left(\prod_{i = 1}^2 a_{k_i}^i\right) F\left(E^{k_1}, E^{k_2}, A^3, \dots, A^n\right)\\ & = \cdots\\ & = \sum_{k_1, \dots, k_n = 1}^n \left(\prod_{i = 1}^n a_{k_i}^i\right) F\left(E^{k_1}, \dots, E^{k_n}\right). \end{align}$

From alternation, it follows that if $k 1 = k 2$ then

$\begin{align}\\ F\left(\dots,E^{k_1},\dots,E^{k_2},\dots\right) &= -F\left(\dots,E^{k_2},\dots,E^{k_1},\dots\right)\\ F\left(\dots,E^{k_1},\dots,E^{k_2},\dots\right) &= -F\left(\dots,E^{k_1},\dots,E^{k_2},\dots\right)\\ F\left(\dots,E^{k_1},\dots,E^{k_2},\dots\right) &= 0 \end{align}$

As the above sum takes into account all the possible choices of ordered $n$ -tuples $\left(k_1, \dots , k_n\right)$ , and because $k_{i_1} = k_{i_2}$ implies that F is zero, the sum can be reduced from all tuples to permutations as

$\sum_{\sigma \in \mathfrak S_n} \prod_{i = 1}^n a_{\sigma(i)}^i F((E^{\sigma(1)}, \dots , E^{\sigma(n)})).$

Now one rearranges the columns of $\left(E^{\sigma(1)}, \dots, E^{\sigma(n)}\right)$ so that it becomes the identity matrix; the number of columns that need to be exchanged is exactly $sgn(σ)$ . Hence, thanks to alternance, one finally gets

$\begin{align} F(A)& = \sum_{\sigma \in \mathfrak S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i)}^i F(I)\\ & = \sum_{\sigma \in \mathfrak S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i)}^i \end{align}$

as $F (I)$ is required to be equal to $1$ .

Therefore no function besides the function defined by the Leibniz Formula is a multilinear alternating function with $F\left(I\right)=1$ .

Existence: We now show that F, where F is the function defined by the Leibniz formula, has these three properties.

Multilinear:

$\begin{align} F(A^0, \dots, c*A^j, \dots) & = \sum_{\sigma \in \mathfrak S_n} \sgn(\sigma) * c * a_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\ & = c*\sum_{\sigma \in \mathfrak S_n} \sgn(\sigma) * a_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\ &=c*F(A^0, \dots, A^j, \dots)\\ \\ F(A^0, \dots, b+A^j, \dots) & = \sum_{\sigma \in \mathfrak S_n} \sgn(\sigma) * \left(b + a_{\sigma(j)}^j\right)\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\ & = \sum_{\sigma \in \mathfrak S_n} \sgn(\sigma) * \left(\left(b\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\right) + \left(a_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\right)\right)\\ & = \left(\sum_{\sigma \in \mathfrak S_n} \sgn(\sigma) * b\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\right) + \left(\sum_{\sigma \in \mathfrak S_n} \sgn(\sigma) * \prod_{i = 1}^n a_{\sigma(i)}^i\right)\\ &= F(A^0, \dots, b, \dots) + F(A^0, \dots, A^j, \dots)\\ \\ \end{align}$

Alternating:

$\begin{align} F(\dots, A^{j_1}, \dots, A^{j_2}, \dots) & = \sum_{\sigma \in \mathfrak S_n} \sgn(\sigma) \left(\prod_{i = 1, i \neq j_1, i\neq j_2}^n a_{\sigma(i)}^i\right)*a_{\sigma(j_1)}^{j_1}*a_{\sigma(j_2)}^{j_2}\\ \end{align}$

Now let $ω$ be the tuple equal to $σ$ with the $j 1$ and $j 2$ indices switched. It follows from the definition of $sgn$ that $sgn(σ) = - s g n (ω)$ .

$\begin{align}\\ F(\dots, A^{j_1}, \dots, A^{j_2}, \dots) & = \sum_{\omega \in \mathfrak S_n} -\sgn(\omega) \left(\prod_{i = 1, i \neq j_1, i\neq j_2}^n a_{\omega(i)}^i\right)*a_{\omega(j_1)}^{j_1}*a_{\omega(j_2)}^{j_2}\\ & = -F(\dots, A^{j_2}, \dots, A^{j_1}, \dots)\\ \\ \end{align}$

Finally, $F (I) = 1$ :

$\begin{align}\\ F(I) & = \sum_{\sigma \in \mathfrak S_n} \sgn(\sigma) \prod_{i = 1}^n I_{\sigma(i)}^i\\ & = \sum_{\sigma = (1,2,\dots,n)} \prod_{i = 1}^n I_{i}^i\\ & = 1 \end{align}$

Thus the only functions which are multilinear alternating with $F (I) = 1$ are restricted to the function defined by the Leibniz formula, and it in fact also has these three properties. Hence the determinant can be defined as the only function

$\det : \mathfrak M_n (\mathbb K) \longrightarrow \mathbb K$

with these 3 properties.

Leibniz formula for determinants

From Wikipedia, the free encyclopedia

[edit] Formal statement and proof

Views

Personal tools

Navigation

Search

Interaction

Toolbox