Laplace expansion

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 C_ij defined by

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

where M_ij 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 = [b_ij] is an n × n matrix and fix any i, j ∈ {1, 2, ..., n}.

Then its determinant |B| is given by:

$\begin{align} |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} \\ & = \sum_{j'=1}^{n} b_{ij'} C_{ij'} = \sum_{i'=1}^{n} b_{i'j} C_{i'j} \end{align}$

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:

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

Laplace expansion along the second column yields the same result:

$|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 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 τ ∈ S_n 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\}.$ The explicit relation between $\tau$ and $\sigma$ can be written as

${\displaystyle \sigma ={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1\\\tau (1)(\leftarrow )_{j}&\tau (2)(\leftarrow )_{j}&\cdots &\tau (i+1)(\leftarrow )_{j}&\cdots &\tau (n)(\leftarrow )_{j}\end{pmatrix}}}$

where ${\displaystyle (\leftarrow )_{j}}$ is a temporary shorthand notation for a cycle ${\displaystyle (n,n-1,\cdots ,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 $\sigma'\in S_n$ by $\sigma'(k) = \sigma(k)$ for $1 \le k \le n-1$ and $\sigma'(n) = n$. Then ${\displaystyle \sigma '}$ is expressed as

${\displaystyle \sigma '={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1&n\\\tau (1)(\leftarrow )_{j}&\tau (2)(\leftarrow )_{j}&\cdots &\tau (i+1)(\leftarrow )_{j}&\cdots &\tau (n)(\leftarrow )_{j}&n\end{pmatrix}}}$

Now, the operation which apply ${\displaystyle (\leftarrow )_{i}}$ first and then apply ${\displaystyle \sigma '}$ 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 )

${\displaystyle \sigma '(\leftarrow )_{i}={\begin{pmatrix}1&2&\cdots &i+1&\cdots &n&i\\\tau (1)(\leftarrow )_{j}&\tau (2)(\leftarrow )_{j}&\cdots &\tau (i+1)(\leftarrow )_{j}&\cdots &\tau (n)(\leftarrow )_{j}&n\end{pmatrix}}}$

where ${\displaystyle (\leftarrow )_{i}}$ is temporary shorthand notation for ${\displaystyle (n,n-1,\cdots ,i+1,i)}$.

the operation which apply $\tau$ first and then apply ${\displaystyle (\leftarrow )_{j}}$ is

${\displaystyle (\leftarrow )_{j}\tau ={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1&n\\\tau (1)(\leftarrow )_{j}&\tau (2)(\leftarrow )_{j}&\cdots &n&\cdots &\tau (n-1)(\leftarrow )_{j}&\tau (n)(\leftarrow )_{j}\end{pmatrix}}}$

above two are equal thus,

${\displaystyle (\leftarrow )_{j}\tau =\sigma '(\leftarrow )_{i}}$

${\displaystyle \tau =(\rightarrow )_{j}\sigma '(\leftarrow )_{i}}$

where ${\displaystyle (\rightarrow )_{j}}$ is the inverse of ${\displaystyle (\leftarrow )_{j}}$ which is ${\displaystyle (j,j+1,\cdots ,n)}$.

Thus

${\displaystyle \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{aligned}\sum _{{\tau \in S_{n}:\tau (i)=j}}\operatorname{sgn} \tau \,b_{{1,\tau (1)}}\cdots b_{{n,\tau (n)}}&=\sum _{{\sigma \in S_{{n-1}}}}(-1)^{{i+j}}\operatorname{sgn} \sigma \,b_{{ij}}a_{{1,\sigma (1)}}\cdots a_{{n-1,\sigma (n-1)}}\\&=b_{{ij}}(-1)^{{i+j}}\left|M_{{ij}}\right|\end{aligned}}$

from which the result follows.

Laplace expansion of a determinant by complementary minors

Laplaces 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_{\{j,k\}}=\begin{vmatrix} a_{3j} & a_{3k} \\ a_{4j} & a_{4k} \end{vmatrix}$,

and the sign of their permutation to be

$\varepsilon^{\{i,j\},\{p,q\}}=\mbox{sgn}\begin{bmatrix} 1 & 2 & 3 & 4 \\ i & j & p & q \end{bmatrix}$.

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\}} \\ &= \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}\\ &= -4 \cdot (-4) -(-8) \cdot (-8) +(-12) \cdot (-4) +(-4) \cdot (-12) -(-8) \cdot (-8) +(-4) \cdot (-4)\\ &= 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 {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| = \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 ${\displaystyle O\left({\frac {n^{3}}{3}}\right)}$.^[1]

See also

• Leibniz formula for determinants

References

1. Stoer Bulirsch: Introduction to Numerical Mathematics

• David Poole: Linear Algebra. A Modern Introduction. Cengage Learning 2005, ISBN 0-534-99845-3, p. 265-267 (restricted online copy, p. 265, at Google Books)
• Harvey E. Rose: Linear Algebra. A Pure Mathematical Approach. Springer 2002, ISBN 3-7643-6905-1, p. 57-60 (restricted online copy, p. 57, at Google Books)

External links

• Laplace expansion at PlanetMath