Wikipedia / Laplace expansion
Wikipedia / Laplace expansion
In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression of the determinant of an -matrix as a weighted sum of minors, which are the determinants of some -submatrices of . Specifically, for every , the Laplace expansion along the th row is the entry of the th row and th column of is the determinant of the submatrix obtained by removing the th row and the th column of . Similarly, the Laplace expansion along the th column (Each identity implies the other, since the determinants of both a matrix and its transpose are the same.)
in the above sum is called the cofactor in .
The Laplace expansion is often useful in proofs, as in, for example, allowing recursion on the size of matrices. It is also 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 Gaussian elimination.
Examples
Consider the matrix
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:
Laplace expansion along the second column yields the same result:
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
is an n × n as
as a factor. Each has the form
for some permutation which selects the same minor entries as . Similarly each choice of determines a corresponding is a bijection Using Cauchy's two-line notation can be written as
is a temporary shorthand notation for a cycle. This operation decrements all indices larger than j so that every index fits in the set {1,2,...,n-1}
The permutation can be derived from is expressed as
is (Notice applying A before B is equivalent to applying inverse of A to the upper row of B in two-line notation)
.
is
above two are equal thus,
.
Thus
Since the two cycles transpositions,
is bijective,
.
Laplace expansion of a determinant by complementary minors
Laplace's cofactor expansion can be generalised as follows.
Example
Consider the matrix
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 be the aforementioned set.
By defining the complementary cofactors to be
and the sign of their permutation to be
The determinant of A can be written out as
.
In our explicit example this gives us
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
be an the set of -element subsets of can be expanded along the as follows:
respectively.
. The same thing holds for any fixed columns.
Computational complexity
The Laplace expansion is computationally inefficient for high-dimension matrices, with a time complexity in big O notation of . Alternatively, using a decomposition into triangular matrices as in the LU decomposition can yield determinants with a time complexity of . The following Python code implements the Laplace expansion:
See also
Rule of Sarrus determinants
References
David Poole: Linear Algebra. A Modern Introduction. Cengage Learning 2005, , pp.265–267 ()
Harvey E. Rose: Linear Algebra. A Pure Mathematical Approach. Springer 2002, , pp.57–60 ()