The Laplace/Cofactor Expansion

June 17, 2009

The Laplace/Cofactor Expansion

Filed under: Algebra,Linear Algebra — cjohnson @ 3:22 pm

We’ve yet to describe a way to calculate determinants in any easy way; we’ve seen some nice properties, but still have to resort to writing a non-elementary matrix as a product of elementary matrices in order to calculate its determinant. What we want to do now is describe a recursive procedure for calculating a determinant by looking at determinants of submatrices. Let’s first agree to call the submatrix of $A$ with the $i$ -th row and $j$ -th column deleted the $i,j$ -minor of $A$ , which we’ll denote $\text{M}_{i,j}(A)$ . So, supposing

$\displaystyle A = \left[ \begin{array}{ccc} 2 & 3 & 5 \\ 7 & 9 & 11 \\ 13 & 17 & 19 \end{array}\right]$

if we delete the first row and second column we have

$\displaystyle \text{M}_{1,2}(A) = \left[ \begin{array}{cc} 7 & 11 \\ 13 & 19 \end{array} \right]$

Let’s also note that if the first row of $A$ is all zeros except for the first entry, the determinant of $A$ is simply the determinant of $\text{M}_{1,1}(A)$ multiplied by that first entry. That is,

To see this, first note that we can zero out the entries in the first column below the $a_{11}$ by performing a sequence of elementary row operations that don’t change the determinant. Now we clearly have

$\displaystyle \det \left[ \begin{array}{c|ccc} a_{11} & 0 & \cdots & 0 \\ \hline a_{21} & & & \\ \vdots & & \text{M}_{1,1}(A) & \\ a_{n1} & & & \end{array} \right] = a_{11} \det \left[ \begin{array}{c|ccc} 1 & 0 & \cdots & 0 \\ \hline 0 & & & \\ \vdots & & \text{M}_{1,1}(A) & \\ 0 & & & \end{array} \right]$

Supposing we can write $\text{M}_{1,1}(A)$ as a product of elementary matrices, $\text{M}_{1,1}(A) = E_1 \, E_2 \, ... \, E_m$ , to calculate its determinant, we can then obtain the matrix above by looking at the product

$\displaystyle \left[ \begin{array}{cc} 1 & 0 \\ 0 & E_1 \end{array} \right] \, \left[ \begin{array}{cc} 1 & 0 \\ 0 & E_2 \end{array} \right] \, \cdots \, \left[ \begin{array}{cc} 1 & 0 \\ 0 & E_m \end{array} \right]$

Each of these is then an elementary matrix whose determinant is the same as the determinant of the associated $E_i$ matrix, so we have our result.

Now, applying the linearity we discussed last time,

$\displaystyle \det \left[ \begin{array}{ccc} a_{11} & \cdots & a_{1n} \\ & R_2 & \\ & \vdots & \\ & R_n & \end{array} \right] = \det \left[ \begin{array}{ccccc} a_{11} & 0 & \cdots & 0 & 0 \\ & & R_2 & & \\ & & \vdots & & \\ & & R_n & & \end{array} \right] + \det \left[ \begin{array}{ccccc} 0 & a_{12} & 0 & \cdots & 0 \\ & & R_2 & & \\ & & \vdots & & \\ & & R_n & & \end{array} \right] + ... + \det \left[ \begin{array}{ccccc} 0 & 0 & \cdots & 0 & a_{1n} \\ & & R_2 & & \\ & & \vdots & & \\ & & R_n & & \end{array} \right]$

Notice that we can can zero out the elements in the first column below $a_{11}$ giving us

$\displaystyle \det \left[ \begin{array}{ccccc} a_{11} & 0 & \cdots & 0 & 0 \\ & & R_2 & & \\ & & \vdots & & \\ & & R_n & & \end{array} \right] = a_{11} \det \left( \text{M}_{11}(A) \right)$

In general, for the $j$ -th column, we want to do a series of column swaps bringing the $j$ -th column to the front of the matrix, but keeping the other columns in order. (For this reason a single column swap won’t work, since that permutes the remaining columns.) Each time we swap columns, the determinant is multiplied by -1. If we move the $j$ -th column to the left by swapping with column $j-1$ , then with column $j-2$ , and so on, we perform $j-1$ swaps. Thus

$\det \left[ \begin{array}{ccccc} \cdots & 0 & a_{1j} & 0 & \cdots \\ & & R_2 & & \\ & & \vdots & & \\ & & R_n & & \end{array} \right] = (-1)^{j-1} \det \left[ \begin{array}{c|ccc} a_{1j} & 0 & \cdots & 0 \\ \hline 0 & & & \\ \vdots & & \text{M}_{1,j}(A) & \\ 0 & & & \end{array} \right] = (-1)^{j-1} a_{1j} \det \left( \text{M}_{1,j}(A) \right)$

So in total we have

$\displaystyle \det(A) = \sum_{j=1}^n (-1)^{j-1} a_{1,j} \det \left( \text{M}_{1,j}(A) \right)$

We could also perform this expansion along another row, but we’d have to perform some row swaps to move that row to the top first. Supposing we decide to expand along the $i$ -th row, we’ll perform $i-1$ swaps, each time multiplying the determinant by -1. We’d multiply our result above, then by $(-1)^{i-1}$ . Distributing that across our sum though, we note that

$(-1)^{i-1} \, (-1)^{j-1} = (-1)^{i + j - 2} = (-1)^{i + j} \, (-1)^{-2} = (-1)^{i + j}$

So, if we expand along the $i$ -th row, our formula becomes

$\displaystyle \det(A) = \sum_{j=1} (-1)^{i+j} a_{i,j} \det \left( \text{M}_{i,j}(A) \right)$

Each term of the sum with the $a_{i,j}$ factor removed is called a cofactor; The $i,j$ -th cofactor, which we’ll denote $\text{cof}_{i,j}(A)$ is

$\displaystyle \text{cof}_{i,j}(A) = (-1)^{i+j} \det \left( \text{M}_{i,j}(A) \right)$

The procedure we’ve just described is known as the Laplace expansion (or cofactor expansion) for the determinant, and so now we have a more efficient way of calculating determinants. (Notice that we could expand along a column instead of a row: just repeat the above procedure on the transpose of the matrix.)

About these ads

Comments (3)

3 Comments »

Nice presentation. Congrats.

Comment by Nicolas Bourbaki Junior — June 18, 2009 @ 8:20 am | Reply
Hi, nice post. I’ll link your blog in mine.
Here is some little application of the Laplace expansion to compute the determinant of a block matrix.
http://watchmath.com/vlog/?p=87

Comment by watchmath — June 24, 2009 @ 2:39 pm | Reply
This site help me mostly ..
thank you for this post

sadi
http://www.sadi02.wordpress.com

Comment by sadi — July 30, 2009 @ 4:31 am | Reply