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
)
.
