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 equality
where is the entry of the th row and th column of, and 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 is the equality
The coefficient of in the above sum is called the cofactor of 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

Suppose is an n × n matrix and For clarity we also label the entries of that compose its minor matrix as
for
Consider the terms in the expansion of that have as a factor. Each has the form
for some permutation with, and a unique and evidently related permutation which selects the same minor entries as. Similarly each choice of determines a corresponding i.e. the correspondence is a bijection between and
Using Cauchy's two-line notation, the explicit relation between and can be written as
where is a temporary shorthand notation for a cycle.
This operation decrements all indices larger than j so that every index fits in the set
The permutation can be derived from as follows.
Define by for and.
Then is expressed as
Now, the operation which apply first and then apply is
where is temporary shorthand notation for.
the operation which applies first and then applies is
above two are equal thus,
where is the inverse of which is.
Thus
Since the two cycles can be written respectively as and transpositions,
And since the map is bijective,
from which the result follows. Similarly, the result holds if the index of the outer summation was replaced with.

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 namely let 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
where is the complementary set to.
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

Let be an matrix and the set of -element subsets of, an element in it. Then the determinant of can be expanded along the rows identified by as follows:
where is the sign of the permutation determined by and, equal to, the square minor of obtained by deleting from rows and columns with indices in and respectively, and defined to be, and being the complement of and respectively.
This coincides with the theorem above when. The same thing holds for any fixed columns.

Computational expense

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:

def determinant:
# Base case of recursive function: 1x1 matrix
if len 1:
return M
total = 0
for column, element in enumerate:
# Exclude first row and current column.
K = + x for x in M[1:
s = 1 if column % 2 0 else -1
total += s * element * determinant
return total