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 ,
formula_1
where formula_2 is the entry of the th row and th column of , and formula_3 is the determinant of the submatrix obtained by removing the th row and the th column of .
The term formula_4 is called the cofactor of formula_2 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 formula_9 is an "n" × "n" matrix and formula_10 For clarity we also label the entries of formula_9 that compose its formula_12 minor matrix formula_13 as
formula_14 for formula_15
Consider the terms in the expansion of formula_16 that have formula_17 as a factor. Each has the form
for some permutation with formula_19, and a unique and evidently related permutation formula_20 which selects the same minor entries as . Similarly each choice of determines a corresponding i.e. the correspondence formula_21 is a bijection between formula_22 and formula_23
The explicit relation between formula_24 and formula_25 can be written as
where formula_27 is a temporary shorthand notation for a cycle formula_28.
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 formula_29 by formula_30 for formula_31 and formula_32. 
Then formula_33 is expressed as 
Now, the operation which apply formula_35 first and then apply formula_36 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 )
where formula_35 is temporary shorthand notation for formula_39.
the operation which apply formula_40 first and then apply formula_27 is 
above two are equal thus,
where formula_45 is the inverse of formula_46 which is formula_47.
Thus 
Since the two cycles can be written respectively as formula_49 and formula_50 transpositions,
And since the map formula_21 is bijective,
from which the result follows. Similarly, the result holds if the index of the outer summation was replaced with formula_54.
Laplace expansion of a determinant by complementary minors.
Laplaces 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 formula_56 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 formula_61 is the complementary set to formula_62.
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 formula_64 be an matrix and formula_65 the set of -element subsets of , formula_66 an element in it. Then the determinant of formula_9 can be expanded along the rows identified by formula_66 as follows:
where formula_70 is the sign of the permutation determined by formula_66 and formula_72, equal to formula_73, formula_74 the square minor of formula_9 obtained by deleting from formula_9 rows and columns with indices in formula_66 and formula_72 respectively, and formula_79 (called the complement of formula_74) defined to be formula_81 , formula_82 and formula_83 being the complement of formula_66 and formula_72 respectively.
This coincides with the theorem above when formula_86. 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 Laplace expansion recursively:
def determinant(M):
 # Base case of recursive function: 1x1 matrix
 if len(M) == 1: 
 return M[0][0]
 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:]]
 s = 1 if column % 2 == 0 else -1 
 total += s * element * determinant(K)
 return total