# Laplace expansion

(Redirected from Expansion by minors)
Jump to navigation Jump to search

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

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

where Mij is the i, j minor 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:

{\displaystyle {\begin{aligned}|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{aligned}}}

## Examples

Consider the matrix

${\displaystyle 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:

${\displaystyle |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}}}$
${\displaystyle {}=1\cdot (-3)-2\cdot (-6)+3\cdot (-3)=0.}$

Laplace expansion along the second column yields the same result:

${\displaystyle |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}}}$
${\displaystyle {}=-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 ${\displaystyle B}$ is an n × n matrix and ${\displaystyle i,j\in \{1,2,\dots ,n\}.}$ For clarity we also label the entries of ${\displaystyle B}$ that compose its ${\displaystyle i,j}$ minor matrix ${\displaystyle M_{ij}}$ as

${\displaystyle (a_{st})}$ for ${\displaystyle 1\leq s,t\leq n-1.}$

Consider the terms in the expansion of ${\displaystyle |B|}$ that have ${\displaystyle b_{ij}}$ as a factor. Each has the form

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

for some permutation τSn with ${\displaystyle \tau (i)=j}$, and a unique and evidently related permutation ${\displaystyle \sigma \in S_{n-1}}$ which selects the same minor entries as τ. Similarly each choice of σ determines a corresponding τ i.e. the correspondence ${\displaystyle \sigma \leftrightarrow \tau }$ is a bijection between ${\displaystyle S_{n-1}}$ and ${\displaystyle \{\tau \in S_{n}\colon \tau (i)=j\}.}$ The explicit relation between ${\displaystyle \tau }$ and ${\displaystyle \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 indices larger than j so that every index fit in the set {1,2,...,n-1}

The permutation τ can be derived from σ as follows. Define ${\displaystyle \sigma '\in S_{n}}$ by ${\displaystyle \sigma '(k)=\sigma (k)}$ for ${\displaystyle 1\leq k\leq n-1}$ and ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle n-i}$ and ${\displaystyle n-j}$ transpositions,

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

And since the map ${\displaystyle \sigma \leftrightarrow \tau }$ is bijective,

{\displaystyle {\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

${\displaystyle 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 ${\displaystyle 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

${\displaystyle b_{\{j,k\}}={\begin{vmatrix}a_{1j}&a_{1k}\\a_{2j}&a_{2k}\end{vmatrix}}}$,
${\displaystyle c_{\{p,q\}}={\begin{vmatrix}a_{3p}&a_{3q}\\a_{4p}&a_{4q}\end{vmatrix}}}$,

and the sign of their permutation to be

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

The determinant of A can be written out as

${\displaystyle |A|=\sum _{H\in S}\varepsilon ^{H,H^{\prime }}b_{H}c_{H^{\prime }},}$

where ${\displaystyle H^{\prime }}$ is the complementary set to ${\displaystyle H}$.

In our explicit example this gives us

{\displaystyle {\begin{aligned}|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{aligned}}}

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 ${\displaystyle B=[b_{ij}]}$ be an n × n matrix and ${\displaystyle S}$ the set of k-element subsets of {1, 2, ... , n}, ${\displaystyle H}$ an element in it. Then the determinant of ${\displaystyle B}$ can be expanded along the k rows identified by ${\displaystyle H}$ as follows:

${\displaystyle |B|=\sum _{L\in S}\varepsilon ^{H,L}b_{H,L}c_{H,L}}$

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

This coincides with the theorem above when ${\displaystyle 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 ${\displaystyle O(n!)}$. Alternatively, using a decomposition into triangular matrices as in the LU decomposition can yield determinants with a time complexity of ${\displaystyle O(n^{3})}$.[1]

## References

1. ^ Stoer Bulirsch: Introduction to Numerical Mathematics