Laplace expansion

From Wikipedia, the free encyclopedia

In linear algebra, the Laplace expansion of the determinant of an n × n square matrix B expresses the determinant |B| as a sum of n determinants of (n-1) × (n-1) sub-matrices of B. There are 2n such expressions, one for each row and column of B. The Laplace expansion is of theoretical interest as one of several ways to view the determinant, as well as of practical use in determinant computation.

Define the i,j minor matrix M_ij of B as the (n-1) × (n-1) matrix that results from deleting the i-th row and the j-th column of B, and the i,j cofactor of B as

$C_{ij}\ = (-1)^{i+j} |M_{ij}|.$

Then the Laplace expansion is given by the following

Theorem Suppose B = (b_ij) is an n × n matrix and i,j ∈ {1, 2, ...,n}. Then the determinant

$\|B\|\$	$= b_{i1} C_{i1} + b_{i2} C_{i2} + \cdots + b_{in} C_{in}$
	$= b_{1j} C_{1j} + b_{2j} C_{2j} + \cdots + b_{nj} C_{nj}.$

[edit] Example

Consider the matrix

$B = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}.$

The determinant of this matrix can be computed by using the Laplace expansion along the first row:

$|B| = 1 \cdot \begin{vmatrix} 5 & 6 \\ 8 & 9 \end{vmatrix} - 2 \cdot \begin{vmatrix} 4 & 6 \\ 7 & 9 \end{vmatrix} + 3 \cdot \begin{vmatrix} 4 & 5 \\ 7 & 8 \end{vmatrix}$

${} = 1 \cdot (-3) - 2 \cdot (-6) + 3 \cdot (-3) = 0.$

Alternatively, Laplace expansion along the second column yields

$|B| = -2 \cdot \begin{vmatrix} 4 & 6 \\ 7 & 9 \end{vmatrix} + 5 \cdot \begin{vmatrix} 1 & 3 \\ 7 & 9 \end{vmatrix} - 8 \cdot \begin{vmatrix} 1 & 3 \\ 4 & 6 \end{vmatrix}$

${} = -2 \cdot (-6) + 5 \cdot (-12) - 8 \cdot (-6) = 0.$

It is easy to see that the result is correct: the matrix is singular because the sum of its first and third column is twice the second column, and hence its determinant is zero.

[edit] Proof of the Laplace expansion

Suppose B is an n × n matrix and i,j ∈ {1, 2, ..., n}. For clarity we also label the entries of B that compose its i,j minor matrix M_ij as (a_st) for 1 ≤ s,t ≤ n-1.

Consider the terms in the expansion of |B| that have b_ij as a factor. Each has the form

$\sgn \tau\,b_{1,\tau(1)} \cdots b_{i,j} \cdots b_{n,\tau(n)} = \sgn \tau\,b_{ij} a_{1,\sigma(1)} \cdots a_{n-1,\sigma(n-1)}$

for some permutation τ ∈ S_n with τ(i) = j, and a unique and evidently related permutation σ ∈ S_n-1 which selects the same minor entries as τ. Similarly each choice of σ determines a corresponding τ, i.e. the correspondence σ ↔ τ is a bijection between S_n-1 and {τ ∈ S_n : τ(i) = j}. The permutation τ can be derived from σ as follows.

Define σ' ∈ S_n by σ'(k) = σ(k) for 1 ≤ k ≤ n-1 and σ'(n) = n. Then sgn σ' = sgn σ and

$\tau\,= (n,n-1,\ldots,i)\,\sigma'\,(j,j+1,\ldots,n).$

Since the two cycles can be written respectively as n-i and n-j transpositions,

$\sgn\tau\,= (-1)^{2n-(i+j)} \sgn\sigma'\,= (-1)^{i+j} \sgn\sigma.$

And since the map σ ↔ τ is bijective,

$\sum_{\tau \in S_n:\tau(i)=j}$	$\sgn \tau\,b_{1,\tau(1)} \cdots b_{n,\tau(n)}$
	$= \sum_{\sigma \in S_{n-1}} (-1)^{i+j}\sgn\sigma\, b_{ij} a_{1,\sigma(1)} \cdots a_{n-1,\sigma(n-1)}$
	$=\ b_{ij} (-1)^{i+j} \|M_{ij}\|,$