Laplace expansion

Examples

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 any one of its rows or columns. For instance, an expansion along the first row yields:

: \begin{align} |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} \[5pt] & = 1 \cdot (-3) - 2 \cdot (-6) + 3 \cdot (-3) = 0. \end{align}

Laplace expansion along the second column yields the same result:

: \begin{align} |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} \[5pt] & = -2 \cdot (-6) + 5 \cdot (-12) - 8 \cdot (-6) = 0. \end{align}

It is easy to verify 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.

Proof

Suppose B is an n × n matrix and i,j\in{1,2,\dots,n}. For clarity we also label the entries of B that compose its i,j minor matrix M_{ij} as

(a_{st}) for 1 \le s,t \le 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 τ ∈ Sn with \tau(i)=j, and a unique and evidently related permutation \sigma\in S_{n-1} which selects the same minor entries as τ. Similarly each choice of σ determines a corresponding τ i.e. the correspondence \sigma\leftrightarrow\tau is a bijection between S_{n-1} and {\tau\in S_n\colon\tau(i)=j}. Using Cauchy's two-line notation, the explicit relation between \tau and \sigma can be written as : \sigma = \begin{pmatrix} 1 & 2 & \cdots & i & \cdots & n-1 \ (\leftarrow)_j ( \tau(1) ) & (\leftarrow)_j ( \tau(2) ) & \cdots & (\leftarrow)_j ( \tau(i+1) ) & \cdots & (\leftarrow)_j ( \tau(n) ) \end{pmatrix} where (\leftarrow)_j is a temporary shorthand notation for a cycle (n,n-1,\cdots,j+1,j). This operation decrements all indices larger than j so that every index fits in the set {1,2,...,n-1}

The permutation τ can be derived from σ as follows. Define \sigma'\in S_n by \sigma'(k) = \sigma(k) for 1 \le k \le n-1 and \sigma'(n) = n. Then \sigma' is expressed as : \sigma' = \begin{pmatrix} 1 & 2 & \cdots & i & \cdots & n-1 & n \ (\leftarrow)_j ( \tau(1) ) & (\leftarrow)_j ( \tau(2) ) & \cdots & (\leftarrow)_j ( \tau(i+1) ) & \cdots & (\leftarrow)_j ( \tau(n) ) & n\end{pmatrix} Now, the operation which apply (\leftarrow)_i first and then apply \sigma' is (Notice applying A before B is equivalent to applying inverse of A to the upper row of B in two-line notation) : \sigma' (\leftarrow)_i = \begin{pmatrix} 1 & 2 & \cdots & i+1 & \cdots & n & i \ (\leftarrow)_j ( \tau(1) ) & (\leftarrow)_j ( \tau(2) ) & \cdots & (\leftarrow)_j ( \tau(i+1) ) & \cdots & (\leftarrow)_j ( \tau(n) ) & n \end{pmatrix} where (\leftarrow)_i is temporary shorthand notation for (n,n-1,\cdots,i+1,i).

the operation which applies \tau first and then applies (\leftarrow)_j is : (\leftarrow)_j \tau = \begin{pmatrix} 1 & 2 & \cdots & i & \cdots & n-1 & n \ (\leftarrow)_j ( \tau(1) ) & (\leftarrow)_j ( \tau(2) ) & \cdots & n & \cdots & (\leftarrow)_j ( \tau(n-1) ) & (\leftarrow)_j ( \tau(n) ) \end{pmatrix} above two are equal thus, : (\leftarrow)_j \tau = \sigma' (\leftarrow)_i : \tau = (\rightarrow)_j \sigma' (\leftarrow)_i where (\rightarrow)_j is the inverse of (\leftarrow)_j which is (j,j+1,\cdots,n).

Thus : \tau,=(j,j+1,\ldots,n)\sigma'(n,n-1,\ldots,i) 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 \sigma\leftrightarrow\tau is bijective,

:\begin{align} \sum_{i=1}^n\sum_{\tau \in S_n:\tau(i)=j} \sgn \tau,b_{1,\tau(1)} \cdots b_{n,\tau(n)} &= \sum_{i=1}^{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)}\ &= \sum_{i=1}^{n}b_{ij}(-1)^{i+j} \sum_{\sigma \in S_{n-1}} \sgn\sigma, a_{1,\sigma(1)} \cdots a_{n-1,\sigma(n-1)}\ &= \sum_{i=1}^{n} b_{ij} (-1)^{i+j} M_{ij} \end{align}

from which the result follows. Similarly, the result holds if the index of the outer summation was replaced with j.

Laplace expansion of a determinant by complementary minors

Laplace's cofactor expansion can be generalised as follows.

Example

Consider the matrix : A = \begin{bmatrix} 1 & 2 & 3 & 4 \ 5 & 6 & 7 & 8 \ 9 & 10 & 11 & 12 \ 13 & 14 & 15 & 16 \end{bmatrix}. The determinant of this matrix can be computed by using the Laplace's cofactor expansion along the first two rows as follows. Firstly note that there are 6 sets of two distinct numbers in {1, 2, 3, 4}, namely let S=\left{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}\right} be the aforementioned set.

By defining the complementary cofactors to be : b_{{j,k}}=\begin{vmatrix} a_{1j} & a_{1k} \ a_{2j} & a_{2k} \end{vmatrix}, : c_{{p,q}}=\begin{vmatrix} a_{3p} & a_{3q} \ a_{4p} & a_{4q} \end{vmatrix}, and the sign of their permutation to be : \varepsilon^{{j,k},{p,q}} = \sgn\begin{bmatrix} 1 & 2 & 3 & 4 \ j & k & p & q \end{bmatrix}, \text{ where } p\neq j,q\neq k.

The determinant of A can be written out as

: |A| = \sum_{H \in S} \varepsilon^{H,H^\prime}b_{H}c_{H^\prime}, where H^{\prime} is the complementary set to H .

In our explicit example this gives us

:\begin{align} |A| &= b_{{1,2}}c_{{3,4}} -b_{{1,3}}c_{{2,4}} +b_{{1,4}}c_{{2,3}}+b_{{2,3}}c_{{1,4}} -b_{{2,4}}c_{{1,3}} +b_{{3,4}}c_{{1,2}} \[5pt] &= \begin{vmatrix} 1 & 2 \ 5 & 6 \end{vmatrix} \cdot \begin{vmatrix} 11 & 12 \ 15 & 16 \end{vmatrix}

• \begin{vmatrix} 1 & 3 \ 5 & 7 \end{vmatrix} \cdot \begin{vmatrix} 10 & 12 \ 14 & 16 \end{vmatrix}

• \begin{vmatrix} 1 & 4 \ 5 & 8 \end{vmatrix} \cdot \begin{vmatrix} 10 & 11 \ 14 & 15 \end{vmatrix}
• \begin{vmatrix} 2 & 3 \ 6 & 7 \end{vmatrix} \cdot \begin{vmatrix} 9 & 12 \ 13 & 16 \end{vmatrix}

• \begin{vmatrix} 2 & 4 \ 6 & 8 \end{vmatrix} \cdot \begin{vmatrix} 9 & 11 \ 13 & 15 \end{vmatrix}

• \begin{vmatrix} 3 & 4 \ 7 & 8 \end{vmatrix} \cdot \begin{vmatrix} 9 & 10 \ 13 & 14 \end{vmatrix}\[5pt] &= -4 \cdot (-4) -(-8) \cdot (-8) +(-12) \cdot (-4) +(-4) \cdot (-12) -(-8) \cdot (-8) +(-4) \cdot (-4)\[5pt] &= 16 - 64 + 48 + 48 - 64 + 16 = 0. \end{align}

As above, it is easy to verify 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.

General statement

Let B=[b_{ij}] be an n × n matrix and S the set of k-element subsets of , H an element in it. Then the determinant of B can be expanded along the k rows identified by H as follows: :|B| = \sum_{L\in S} \varepsilon^{H,L} b_{H,L} c_{H,L}

where \varepsilon^{H,L} is the sign of the permutation determined by H and L, equal to (-1)^{\left(\sum_{h\in H}h\right) + \left(\sum_{\ell\in L}\ell\right)}, b_{H,L} the square minor of B obtained by deleting from B rows and columns with indices in H and L respectively, and c_{H,L} (called the complement of b_{H,L}) defined to be b_{H',L'} , H' and L' being the complement of H and L respectively.

This coincides with the theorem above when k=1. The same thing holds for any fixed k columns.

Computational expense

The Laplace expansion is computationally inefficient for high-dimension matrices, with a time complexity in big O notation of O(n!). Alternatively, using a decomposition into triangular matrices as in the LU decomposition can yield determinants with a time complexity of O(n3). The following Python code implements the Laplace expansion:

def determinant(M):
    # Base case of recursive function: 1x1 matrix
    if len(M) == 1:
        return M[0][0]

    total = 0
    for column, element in enumerate(M[0]):
        # Exclude first row and current column.
        K = [x[:column] + x[column + 1 :] for x in M[1:]]
        s = 1 if column % 2 == 0 else -1
        total += s * element * determinant(K)
    return total

References

• David Poole: Linear Algebra. A Modern Introduction. Cengage Learning 2005, , pp. 265–267 ()
• Harvey E. Rose: Linear Algebra. A Pure Mathematical Approach. Springer 2002, , pp. 57–60 ()

de:Determinante#Laplacescher Entwicklungssatz

References

1. (1949). "Elementary problem 834". American Mathematical Society.
2. Stoer Bulirsch: Introduction to Numerical Mathematics