Mathematics Prelims

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,

\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(\text{M}_{1,1}(A)\right)

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

3 Comments »

  1. Nice presentation. Congrats.

    Comment by Nicolas Bourbaki Junior — June 18, 2009 @ 8:20 am | Reply

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

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


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: