Laplace expansion

From Mathematics wiki

Jump to: navigation, search

The Laplace expansion is an algorithm for calculating the determinant of a square n\times n\, matrix A\, by first calculating the determinants of n\, (n-1)\times(n-1)\, submatrices of A\,.

Let a_{ij}\, be the (n-1)\times(n-1)\, matrix obtained by deleting the i^{th}\, row and j^{th}\, column of A\,. Then we may fix any row i\, and expand the determinant along that row

\det A = \sum_{j=1}^n A_{ij} (-1)^{i+j}\det a_{ij}\,,

and since the determinant of the transpose of a matrix is equal to the determinant of the matrix, we may alternatively fix any column j\, and expand the determinant along that column

\det A = \sum_{i=1}^n A_{ij} (-1)^{i+j}\det a_{ij}\,.

The algorithm terminates because the determinant of a 1\times 1\, matrix is equal to the only element of that matrix.

Defining m_{ij} = \det a_{ij}\, to be the minors of A\,, and C_{ij} = (-1)^{i+j} m_{ij}\, to be the cofactors of A\,, these formulas are alternatively written as

\det A = \sum_{j=1}^n A_{ij} C_{ij}\,,

or

\det A = \sum_{i=1}^n A_{ij} C_{ij}\,.

Furthermore, consider the product A C^T\,. The i,i\, entry is equal to \det A\,, while the i,k\neq i\, entry is the Laplace expansion of the determinant of a matrix with two identical rows, and is therefore 0\,. Thus, calling C^T = adj(A)\, the adjugate,

A \,adj(A) = (\det A) I\,,

where I\, is the identity. The Laplace expansion therefore gives one way of calculating the inverse of a matrix.

Proof

Recall that the determinant of a square n\times n\, matrix A\, is given by

\det A \equiv \sum_{\pi} (-1)^{I(\pi)} \prod_{i=1}^n A_{i \pi(i)}\,,

where \pi \in S_n\, is some permutation of (1,2,3...,n)\,, i.e., an element of the permutation group S_n\,, and I(\pi)\,, called the inversion number of \pi\,, the number of pairwise exchanges needed on \pi\, to obtain (1,2,3...,n)\,. I.e., \sgn(\pi) \equiv (-1)^{I(\pi)}\, is 1\, if \pi\, is an even permutation of (1,2,3...)\, and -1\, otherwise.

The element A_{ij}\, appears in the sum in terms of the form

(-1)^{I(\pi)} A_{i \pi(i)} \prod_{k\neq i} A_{k \pi(k)}\,

where \pi(i) = j\,, i.e., appears as

(-1)^{I(\pi)} A_{i j} \prod_{k\neq i} A_{k \pi(k)}\,,

or

(-1)^{I(\pi)} A_{i j} \prod_{k=1}^{n-1} (a_{ij})_{k \sigma(k)}\,,

where a_{ij}\, is the (n-1)\times(n-1)\, matrix obtained by deleting the i^{th}\, row and j^{th}\, column of A\,, and \sigma \in S_{n-1}\, is a related permutation of (1,2,3...,n-1)\,. Define \pi' \in S_n\, to be the permutation \pi'(k) = \sigma(k)\, for k = 1...n-1\, and \pi'(n) = n\,, i.e., it leaves the last element unchanged, so that I(\pi') = I(\sigma)\,. Now \pi'\, was obtained from \pi\, as follows

\pi' = (1,2,3, ...j-2, j-1, n, j , j+1, j+2,..., n-2, n-1) \circ \pi \circ (1,2,3, ..., i+1, i+2, ...,n, i)\,.

so

(-1)^{I(\sigma)} = (-1)^{I(\pi')} = (-1)^{n-i + (n-j)} (-1)^{I(\pi)} = (-1)^{i+j} (-1)^{I(\pi)}\,,

so that

\sum_{\pi, \pi(i)=j} (-1)^{I(\pi)} A_{i j} \prod_{k=1}^{n-1} (a_{ij})_{k \sigma(k)}\, = A_{ij} (-1)^{i+j} \sum_{\sigma} (-1)^{I(\sigma)} \prod_{k=1}^{n-1} (a_{ij})_{k \sigma(k)}\,
= A_{ij} (-1)^{i+j}\det a_{ij}\,,

while

\det A\, = \prod_{i=1}^n \sum_{\pi} (-1)^{I(\pi)} A_{i \pi(i)}\,,
= \prod_{i=1}^n \sum_{j=1}^n \sum_{\pi, \pi(i)=j} (-1)^{I(\pi)} A_{i \pi(i)}\,,
= \sum_{j=1}^n \sum_{\pi, \pi(i)=j} (-1)^{I(\pi)} A_{i\pi(i)}\prod_{k\neq i}^n A_{k \pi(k)}\,,
= \sum_{j=1}^n \sum_{\pi, \pi(i)=j} (-1)^{I(\pi)} A_{i j} \prod_{k=1}^{n-1} (a_{ij})_{k \sigma(k)}\,,
= \sum_{j=1}^n A_{ij} (-1)^{i+j}\det a_{ij}\,.

References

This article incorporates material from Laplace expansion on Wikipedia, which is licensed under the GFDL. [1]

This article incorporates material from Laplace expansion on PlanetMath, which is licensed under the GFDL. [2]

  1. ↑ Laplace expansion, from Wikipedia, The free encyclopedia; Retrieved April 4, 2007.
  2. ↑ Laplace expansion, from PlanetMath; Retrieved April 4, 2007.
Retrieved from "http://www.mathematics.thetangentbundle.net/wiki/Linear_algebra/Laplace_expansion"
Personal tools