Laplace expansion

Feb 19

Laplace expansion

The Laplace expansion is a formula for calculating determinants that is calculationally more efficient than the Leibniz formula but less efficient than the decomposition into triangular matrices. See if you like the proof below or the one that heavily relies on permutations.

In fact, we have already dealt with the Laplace expansion when we said that $\det A$ is a linear function of column $A^{(j)}:$

(1) $\det A=\sum_{i=1}^na_{ij}l_{ji}.$

Our task is to analyze the coefficients $l_{ji}.$ They will be identified as determinants of certain submatrices of $A,$ up to the sign.

Special case

For simplicity, let us start with $j=1:$

(2) $\det A=a_{11}l_{11}+...+a_{n1}l_{1n}.$

Definition. For any $a_{ij},$ denote $A_{ij}$ the matrix resulting from $A$ after deleting row $i$ and column $j.$ $A_{ij}$ is of size $(n-1)\times (n-1).$ Its determinant $\det A_{ij}=M_{ij}$ is called $(i,j)$ -minor.

Step 1. We want to show that $l_{11}=M_{11}.$ By the cross-out rule $l_{11}$ depends only on the elements of $A_{11}.$ When studying $l_{11},$ we can assume without loss of generality that

$a_{11}=1,$ $a_{21}=...=a_{n1}=0.$

Then (2) becomes $\det A=l_{11}.$ This allows us to assert that $l_{11}$ satisfies Axioms 1-3:

1) $l_{11}$ is a homogeneous function of any row of $A_{11}$ because $\det A$ has this property,

2) Adding one of the rows of $A_{11}$ to another row does not change $l_{11}$ because $\det A$ stays the same, and

3) If $A_{11}=I_{(n-1)\times (n-1)},$ then $A=I_{n\times n}$ and $l_{11}=\det I=1.$

Since, again, $l_{11}$ is a function of elements of $A_{11}$ only, it follows that

(3) $l_{11}=\det A_{11}=M_{11}.$

Step 2. To analyze $l_{12},$ as above, we can assume that

$a_{21}=1,$ $a_{11}=a_{31}=...=a_{n1}=0.$

(2) becomes $\det A=l_{12}.$ Here $A=(u_2,A^{(2)},...,A^{(n)})$ where $u_2$ is the second unit column-vector and $A^{(2)},...,A^{(n)}$ are columns of $A.$ Let $\tilde{A}$ be the result of permuting the first and second rows of $A.$ This permutation changes the sign of $\det A$ and does not change $l_{12}$ (the matrix $A_{12}$ for $A$ is the same as $A_{11}$ for $\tilde{A}$ ). Hence,

(4) $\det \tilde{A}=-\det A=-l_{12}.$

For $\tilde{A},$ $l_{11}$ is the same as $l_{11}$ for $A$ in Step 1, so (3) and (4) imply $l_{12}=-M_{12}.$

Step $i.$ We can assume that

$a_{i1}=1,$ $a_{11}=...=a_{i-1,1}=a_{i+1,1}=a_{n1}=0.$

(2) becomes $\det A=l_{1i},$ where $A=(u_i,A^{(2)},...,A^{(n)})$ and $u_{i}$ is the $i$ -th unit column-vector. As in Step 2, we can reduce this case to Step 1. Permute rows $i$ and $i-1,$ then permute rows $i-1$ and $i-2$ and so on. In total we need $i-1$ permutations leading to $i-1$ changes in sign. Instead of (4) we get

$\det \tilde{A}=(-1)^{i-1}\det A=(-1)^{i-1}l_{1i},$

where $\tilde{A}$ is the result of $i-1$ permutations. The element in the upper left corner of $\tilde{A}$ is 1 and therefore $l_{1i}$ is the same as $l_{11}$ for $A$ in Step 1. The conclusion is that

(5) $l_{1i}=(-1)^{i-1}M_{1i}.$

General case

To consider (1), we reduce the case of the $j$ -th column to the case of the first column. For this, we permute columns $j$ and $j-1,$ then columns $j-1$ and $j-2$ and so on. In total we need $j-1$ permutations. Denoting the new matrix $\tilde{A},$ we have $\det \tilde{A}=(-1)^{j-1}\det A.$ To $\det \tilde{A}$ we can apply what we know about (2). This will lead to multiplying (5) by $(-1)^{j-1}.$ The result is

$l_{ji}=(-1)^{i-1+j-1}M_{ji}=(-1)^{i+j}M_{ji}.$

Thus we have derived the Laplace expansion:

Theorem. For $j=1,...,n$ one has an expansion by column

$\det A=\sum_{i=1}^na_{ij}(-1)^{i+j}M_{ji}.$

The meaning of this expansion is that the calculation of the determinant of $A$ is reduced to the calculation of the determinants of matrices of lower dimension. Instead of expansions by column, one can use expansions by row, whichever is convenient. The expression $(-1)^{i+j}M_{ji}$ is called a cofactor of the element $a_{ij}.$