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 (or minors) of B, each of size (n − 1) × (n − 1). The Laplace expansion is of didactic interest for its simplicity and as one of several ways to view and compute the determinant. For large matrices, it quickly becomes inefficient to compute when compared to methods using matrix decomposition.

Calculation of the determinant by Laplace expansion utilizes the cofactor and the minor. The i, j cofactor of the matrix B is the scalar C_ij defined by

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

where M_ij 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=[b_{ij}]

is an

n\times n

matrix and choose any fixed

i,j\in \{1,2...n\}

. Suppose

i^{'}

is a fixed choice of

i\in \{1,2...n\}

. Then its determinant

\left|B\right|=\det(B)

is given by:

{\begin{aligned}\det(B)&=\left[(-1)^{i^{'}+1}b_{i^{'}1}\det(M_{i^{'}1})\right]+\left[(-1)^{i^{'}+2}b_{i^{'}2}\det(M_{i^{'}2})\right]\cdots +\left[(-1)^{i^{'}+n}b_{1n}\det(M_{i^{'}n})\right]\\&=\sum _{j=1}^{n}(-1)^{i^{'}+j}b_{i^{'}j}\det(M_{i^{'}j})\\\end{aligned}}

where

\det(M_{ij})

is the minor of element

B_{ij}

, i.e. the determinant of the submatrix

M_{ij}

formed by removing the

i^{th}

row and the

j^{th}

column of matrix

B

.

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{aligned}|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{aligned}}

Laplace expansion along the second column yields the same result:

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

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\leq s,t\leq n-1.$

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

\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 $τ \in 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

\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 $(\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 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\leq k\leq n-1$ and $\sigma '(n)=n$ . Then $\sigma '$ is expressed as

\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 $(\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 Cauchy's two-line notation )

\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 $(\leftarrow )_{i}$ is temporary shorthand notation for $(n,n-1,\cdots ,i+1,i)$ .

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

(\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,

(\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,

\operatorname {sgn} \tau \,=(-1)^{2n-(i+j)}\operatorname {sgn} \sigma '\,=(-1)^{i+j}\operatorname {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 _{i=1}^{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)}\\&=\sum _{i=1}^{n}b_{ij}(-1)^{i+j}\sum _{\sigma \in S_{n-1}}\operatorname {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{aligned}}

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

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_{\{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\}}={\mbox{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{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\}}\\[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{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 $B=[b_{ij}]$ be an $n \times 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 $O (n 3)$ .[1] The following Python code implements Laplace expansion recursively:

def determinant(M):
    # Base case of recursive function: 2x2 matrix (such that det(M) = ad - cb)
    if len(M) == 2:
        return (M[0][0] * M[1][1]) - (M[0][1] * M[1][0])
    else:
        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:]]
            # Given that the element is in row 1, sign is negative if index is odd.
            if column % 2 == 0:
                total += element * determinant(K)
            else:
                total -= element * determinant(K)
        return total

References

Stoer Bulirsch: Introduction to Numerical Mathematics

David Poole: Linear Algebra. A Modern Introduction. Cengage Learning 2005, ISBN 0-534-99845-3, pp. 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, pp. 57–60 (restricted online copy, p. 57, at Google Books)

External links

Laplace expansion in C (in Portuguese)
Laplace expansion in Java (in Portuguese)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Stoer Bulirsch: Introduction to Numerical Mathematics