Laplace expansion

From Wikipedia, the free encyclopedia
  (Redirected from Expansion by minors)
Jump to: navigation, search
This article is about the expansion of the determinant of a square matrix as a weighted sum of determinants of sub-matrices. For the expansion of an 1/r-potential using spherical harmonical functions, see Laplace expansion (potential).

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 square 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_{ij}\ = (-1)^{i+j} M_{ij}\,,

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:

 \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[edit]

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[edit]

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 τ ∈ Sn with \tau(i)=j, and a unique and evidently related permutation \sigma\in S_{n-1} which selects the same minor entries as \tau. Similarly each choice of \sigma determines a corresponding \tau, i.e. the correspondence \sigma\leftrightarrow\tau is a bijection between S_{n-1} and \{\tau\in S_n\colon\tau(i)=j\}. The permutation \tau can be derived from \sigma as follows.

Define \sigma'\in S_n by \sigma'(k) = \sigma(k) for 1 \le k \le n-1 and \sigma'(n) = n. Then \sgn\sigma'=\sgn\sigma and

\tau\,=(n,n-1,\ldots,i)\sigma'(j,j+1,\ldots,n)

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,

\sum_{\tau \in S_n\colon\tau(i)=j} \sgn \tau\,b_{1,\tau(1)} \cdots b_{n,\tau(n)}
= \sum_{\sigma \in S_{n-1}} (-1)^{i+j}\sgn\sigma\, b_{ij}
a_{1,\sigma(1)} \cdots a_{n-1,\sigma(n-1)}
=\ b_{ij} (-1)^{i+j} |M_{ij}|,

from which the result follows.

Laplace expansion of a determinant by complementary minors[edit]

Laplaces cofactor expansion can be generalised as follows.

Example[edit]

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 \left\{1,2,3,4\right\}, namely let S=\left\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\right\} be the aformentioned 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 complemenatary 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\}}
 {} = \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.

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.

Computational expense[edit]

The Laplace expansion is computationally inefficient for high dimension because for NxN matrices, the computational effort scales with N!. Therefore, the Laplace expansion is not suitable for large N. Using a decomposition into triangular matrices as in the LU decomposition, one can determine determinants with effort N3/3.[1]

References[edit]

  1. ^ Stoer Bulirsch: Introduction to Numerical Mathematics

See also[edit]

External links[edit]