In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression for the determinant |B| of an n × n matrix B that is a weighted sum of the determinants of n sub-matrices of B, each of size (n−1) × (n−1). 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.
The i, j cofactor of B is the scalar Cij defined by
C i j = ( − 1 ) i + j M i j , where Mij is the i, j minor matrix of B, that is, the determinant of the (n − 1) × (n − 1) matrix that results from deleting the i-th row and the j-th column of B.
Then the Laplace expansion is given by the following
Theorem. Suppose
B = [
bij] is an
n ×
n matrix and fix any
i,
j ∈ {1, 2, ...,
n}.
Then its determinant |B| is given by:
| B | = b i 1 C i 1 + b i 2 C i 2 + ⋯ + b i n C i n = b 1 j C 1 j + b 2 j C 2 j + ⋯ + b n j C n j = ∑ j ′ = 1 n b i j ′ C i j ′ = ∑ i ′ = 1 n b i ′ j C i ′ j Consider the matrix
B = [ 1 2 3 4 5 6 7 8 9 ] . 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:
| B | = 1 ⋅ | 5 6 8 9 | − 2 ⋅ | 4 6 7 9 | + 3 ⋅ | 4 5 7 8 | Laplace expansion along the second column yields the same result:
| B | = − 2 ⋅ | 4 6 7 9 | + 5 ⋅ | 1 3 7 9 | − 8 ⋅ | 1 3 4 6 | 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.
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 i j as
( a s t ) for 1 ≤ s , t ≤ n − 1.
Consider the terms in the expansion of | B | that have b i j as a factor. Each has the form
sgn τ b 1 , τ ( 1 ) ⋯ b i , j ⋯ b n , τ ( n ) = sgn τ b i j a 1 , σ ( 1 ) ⋯ a n − 1 , σ ( n − 1 ) for some permutation τ ∈ Sn 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 explicit relation between τ and σ can be written as
σ = ( 1 2 ⋯ i ⋯ n − 1 τ ( 1 ) ( ← ) j τ ( 2 ) ( ← ) j ⋯ τ ( i + 1 ) ( ← ) j ⋯ τ ( n ) ( ← ) j ) where ( ← ) j is a temporary shorthand notation for a cycle ( n , n − 1 , ⋯ , j + 1 , j ) . This operation decrements all indexes which is larger than j so that every indexes fit in the set {1,2,...,n-1}
The permutation τ can be derived from σ as follows. Define σ ′ ∈ S n by σ ′ ( k ) = σ ( k ) for 1 ≤ k ≤ n − 1 and σ ′ ( n ) = n . Then σ ′ is expressed as
σ ′ = ( 1 2 ⋯ i ⋯ n − 1 n τ ( 1 ) ( ← ) j τ ( 2 ) ( ← ) j ⋯ τ ( i + 1 ) ( ← ) j ⋯ τ ( n ) ( ← ) j n ) Now, the operation which apply ( ← ) i first and then apply σ ′ is (Notice applying A before B is equivalent to applying inverse of A to the upper row of B in Cauchy's two-line notation )
σ ′ ( ← ) i = ( 1 2 ⋯ i + 1 ⋯ n i τ ( 1 ) ( ← ) j τ ( 2 ) ( ← ) j ⋯ τ ( i + 1 ) ( ← ) j ⋯ τ ( n ) ( ← ) j n ) where ( ← ) i is temporary shorthand notation for ( n , n − 1 , ⋯ , i + 1 , i ) .
the operation which apply τ first and then apply ( ← ) j is
( ← ) j τ = ( 1 2 ⋯ i ⋯ n − 1 n τ ( 1 ) ( ← ) j τ ( 2 ) ( ← ) j ⋯ n ⋯ τ ( n − 1 ) ( ← ) j τ ( n ) ( ← ) j ) above two are equal thus,
( ← ) j τ = σ ′ ( ← ) i τ = ( → ) j σ ′ ( ← ) i where ( → ) j is the inverse of ( ← ) j which is ( j , j + 1 , ⋯ , n ) .
Thus
τ = ( j , j + 1 , … , n ) σ ′ ( n , n − 1 , … , i ) Since the two cycles can be written respectively as n − i and n − j transpositions,
sgn τ = ( − 1 ) 2 n − ( i + j ) sgn σ ′ = ( − 1 ) i + j sgn σ . And since the map σ ↔ τ is bijective,
∑ τ ∈ S n : τ ( i ) = j sgn τ b 1 , τ ( 1 ) ⋯ b n , τ ( n ) = ∑ σ ∈ S n − 1 ( − 1 ) i + j sgn σ b i j a 1 , σ ( 1 ) ⋯ a n − 1 , σ ( n − 1 ) = b i j ( − 1 ) i + j | M i j | from which the result follows.
Laplaces cofactor expansion can be generalised as follows.
Consider the matrix
A = [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ] . 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 = { { 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 3 } , { 2 , 4 } , { 3 , 4 } } be the aforementioned set.
By defining the complementary cofactors to be
b { j , k } = | a 1 j a 1 k a 2 j a 2 k | ,
c { j , k } = | a 3 j a 3 k a 4 j a 4 k | ,
and the sign of their permutation to be
ε { i , j } , { p , q } = sgn [ 1 2 3 4 i j p q ] .
The determinant of A can be written out as
| A | = ∑ H ∈ S ε H , H ′ b H c H ′ , where H ′ is the complementary set to H .
In our explicit example this gives us
| 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 } = | 1 2 5 6 | ⋅ | 11 12 15 16 | − | 1 3 5 7 | ⋅ | 10 12 14 16 | + | 1 4 5 8 | ⋅ | 10 11 14 15 | + | 2 3 6 7 | ⋅ | 9 12 13 16 | − | 2 4 6 8 | ⋅ | 9 11 13 15 | + | 3 4 7 8 | ⋅ | 9 10 13 14 | = − 4 ⋅ ( − 4 ) − ( − 8 ) ⋅ ( − 8 ) + ( − 12 ) ⋅ ( − 4 ) + ( − 4 ) ⋅ ( − 12 ) − ( − 8 ) ⋅ ( − 8 ) + ( − 4 ) ⋅ ( − 4 ) = 16 − 64 + 48 + 48 − 64 + 16 = 0. 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.
Let B = [ b i j ] be an n × n matrix and S the set of k-element subsets of {1, 2, ... , n}, H an element in it. Then the determinant of B can be expanded along the k rows identified by H as follows:
| B | = ∑ L ∈ S ε H , L b H , L c H , L where ε H , L is the sign of the permutation determined by H and L , equal to ( − 1 ) ( ∑ h ∈ H h ) + ( ∑ ℓ ∈ L ℓ ) , 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.
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 ( n 3 ) .
