23
Feb 19

Laplace expansion




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}.

Leave a Reply

You must be logged in to post a comment.