An Inquiry-Based Introduction to Linear Algebra and Applications

Subsection Introduction

This section is different than others in that it contains mainly proofs of previously stated results and only a little new material. Consequently, there is no application attached to this section.

We have seen that an important property of the determinant is that it provides an easy criteria for the invertibility of a matrix. As a result, we obtained an algebraic method for finding the eigenvalues of a matrix, using the characteristic equation. In this section, we will investigate other properties of the determinant related to how elementary row operations change the determinant. These properties of the determinant will help us evaluate the determinant in a more efficient way compared to using the cofactor expansion method, which is computationally intensive for large \(n\) values due to it being a recursive method. Finally, we will derive a geometrical interpretation of the determinant.

Subsection Elementary Row Operations and Their Effects on the Determinant

In Preview Activity 22.1, we conjectured how elementary row operations affect the determinant of a matrix. In the following activity, we prove how the determinant changes when a row is multiplied by a constant using the cofactor expansion definition of the determinant.

Your work in Activity 22.2 proves the first part of the following theorem on how elementary row operations change the determinant of a matrix.

In the next section, we will use elementary matrices to prove the last two properties of Theorem 22.1.

Subsection Elementary Matrices

As we saw in Preview Activity 22.1, elementary row operations can be achieved by multiplication by elementary matrices.

The following elementary matrices correspond, respectively, to an elementary row operation which swaps rows 2 and 4; an elementary row operation which multiplies the third row by 5; and an elementary row operation which adds four times the third row to the first row on any \(4\times 4\) matrix:

To obtain an elementary matrix corresponding an elementary row operation, we simply perform the elementary row operation on the identity matrix. For example, \(E_1\) above is obtained by swapping rows 2 and 4 of the identity matrix.

With the use of elementary matrices, we can now prove the result about how the determinant is affected by elementary row operations. We first rewrite Theorem 22.1 in terms of elementary matrices:

As a corollary of this theorem, we can prove the multiplicativity of determinants:

We can use the multiplicative property of the determinant and the determinants of elementary matrices to calculate the determinant of a matrix in a more efficient way than using the cofactor expansion. The next activity provides an example.

Your work in Activity 22.3 provides an efficient method for calculating the determinant. If \(A\) is a square matrix, we use row operations given by elementary matrices \(E_1\text{,}\) \(E_2\text{,}\) \(\ldots\text{,}\) \(E_k\) to row reduce \(A\) to row echelon form \(R\text{.}\) That is

We know \(\det(E_i)\) for each \(i\text{,}\) and since \(R\) is a triangular matrix we can find its determinant. Then

In other words, if we keep track of how the row operations affect the determinant, we can calculate the determinant of a matrix \(A\) using row operations.

Subsection Geometric Interpretation of the Determinant

Determinants have interesting and useful applications from a geometric perspective. To understand the geometric interpretation of the determinant of an \(n\times n\) matrix \(A\text{,}\) we consider the image of the unit square under the transformation \(T(\vx)=A\vx\) and see how its area changes based on \(A\text{.}\)

It can be shown that for all \(2\times 2\) matrices a similar relationship holds.

There is a similar geometric interpretation of the determinant of a \(3\times 3\) matrix in terms of volume.

The sign of \(\det(A)\) can be interpreted in terms of the orientation of the column vectors of \(A\text{.}\) See the project in Section 17 for details.

Subsection An Explicit Formula for the Inverse and Cramer's Rule

In Section 10 we found the inverse \(A^{-1}\) using row reduction of the matrix obtained by augmenting \(A\) with \(I_n\text{.}\) However, in theoretical applications, having an explicit formula for \(A^{-1}\) can be handy. Such an explicit formula provides us with an algebraic expression for \(A^{-1}\) in terms of the entries of \(A\text{.}\) A consequence of the formula we develop is Cramer's Rule, which can be used to provide formulas that give solutions to certain linear systems.

We begin with an interesting connection between a square matrix and the matrix of its cofactors that we explore in the next activity.

The result of Activity 22.6 is rather surprising, but it is valid in general. That is, if \(A = [a_{ij}]\) is an invertible \(n \times n\) matrix and \(C_{ij}\) is the \((i,j)\) cofactor of \(A\text{,}\) then \(A \ \adj(A)=\det(A) I_n\text{.}\) In other words, \(A \left(\frac{\adj(A)}{\det(A)}\right) = I_n\) and so

This gives us another formulation of the inverse of a matrix. To see why \(A \ \adj(A) = \det(A) I_n\text{,}\) we use the row-column version of the matrix product to find the \(ij\)th entry of \(A \ \adj(A)\) as indicated by the shaded row and column

Thus the \(ij\)th entry of \(A \ \adj(A)\) is

Notice that if \(i=j\text{,}\) then expression (22.4) is the cofactor expansion of \(A\) along the \(i\)th row. So the \(ii\)th entry of \(A \ \adj(A)\) is \(\det(A)\text{.}\) It remains to show that the \(ij\)th entry of \(A \ \adj(A)\) is 0 when \(i \neq j\text{.}\)

When \(i \neq j\text{,}\) the expression (22.4) is the cofactor expansion of the matrix

along the \(j\)th row. This matrix is the one obtained by replacing the \(j\)th row of \(A\) with the \(i\)th row of \(A\text{.}\) Since this matrix has two identical rows, it is not row equivalent to the identity matrix and is therefore not invertible. Thus, when \(i \neq j\) expression (22.4) is 0. This makes \(A \ \adj(A) = \det(A) I_n\text{.}\)

One consequence of the formula \(A^{-1} = \frac{1}{\det(A)} \adj(A)\) is Cramer's rule, which describes the solution to the equation \(A \vx = \vb\text{.}\)

The result from Activity 22.7 may seem a bit strange, but turns out to be true in general. The result is called Cramer's Rule.

To see why Cramer's Rule works in general, let \(A\) be an \(n \times n\) invertible matrix and \(\vb = [b_1 \ b_2 \ \cdots \ b_n]^{\tr}\text{.}\) The solution to \(A \vx = \vb\) is

Expanding the product gives us

The expression

is the cofactor expansion of the matrix

along the \(j\)th column, giving us the formula in Cramer's Rule.

Cramer's Rule is not a computationally efficient method. To find a solution to a linear system of \(n\) equations in \(n\) unknowns using Cramer's Rule requires calculating \(n+1\) determinants of \(n \times n\) matrices — quite inefficient when \(n\) is 3 or greater. Our standard method of solving systems using Gaussian elimination is much more efficient. However, Cramer's Rule does provide a formula for the solution to \(A \vx = \vb\) as long as \(A\) is invertible.

Subsection The Determinant of the Transpose

In this section we establish the fact that the determinant of a square matrix is the same as the determinant of its transpose.

The result is easily verified for \(2 \times 2\) matrices, so we will proceed by induction and assume that the determinant of the transpose of any \((n-1) \times (n-1)\) matrix is the same as the determinant of its transpose. Suppose \(A = [a_{ij}]\) is an \(n \times n\) matrix. By definition,

and

Note that the only terms in either determinant that contains \(a_{11}\) is \(a_{11}C_{11}\text{.}\) This term is the same in both determinants, so we proceed to examine other elements. Let us consider all terms in the cofactor expansion for \(\det(A^{\tr})\) that contain \(a_{i1}a_{1j}\text{.}\) The only summand that contains \(a_{i1}\) is \(a_{i1}C_{i1}\text{.}\) Letting \(A_{ij}\) be the sub-matrix of \(A\) obtained by deleting the \(i\)th row and \(j\)th column, we see that \(a_{i1}C_{i1} = (-1)^{i+1}a_{i1}\det(A_{i1})\text{.}\) Now let's examine the sub-matrix \(A_{i1}\text{:}\)

When we expand along the first row to calculate \(\det(A_{i1})\text{,}\) the only term that will involve \(a_{1j}\) is

where \(A_{ik,jm}\) denotes the sub-matrix of \(A\) obtained by deleting rows \(i\) and \(k\) and columns \(j\) and \(m\) from \(A\text{.}\) So the term that contains \(a_{i1}a_{1j}\) in the cofactor expansion for \(\det(A^{\tr})\) is

Now we examine the cofactor expansion for \(\det(A)\) to find the terms that contain \(a_{i1}a_{1j}\text{.}\) The quantity \(a_{1j}\) only appears in the cofactor expansion as

Now let's examine the sub-matrix \(A_{1j}\text{:}\)

Here is where we use the induction hypothesis. Since \(A_{1j}\) is an \((n-1) \times (n-1)\) matrix, its determinant can be found with a cofactor expansion down the first column. The only term in this cofactor expansion that will involve \(a_{i1}\) is

So the term that contains \(a_{i1}a_{1j}\) in the cofactor expansion for \(\det(A)\) is

Since the quantities in (22.5) and (22.6) are equal, we conclude that the terms in the two cofactor expansions are the same and

Subsection Row Swaps and Determinants

In this section we determine the effect of row swaps to the determinant. Let \(E_{rs}\) be the elementary matrix that swaps rows \(r\) and \(s\) in the \(n \times n\) matrix \(A=[a_{ij}]\text{.}\) Applying \(E_{12}\) to a \(2 \times 2\) matrix \(A = \left[ \begin{array}{cc} a \amp b \\ c \amp d \end{array} \right]\text{,}\) we see that

So swapping rows in a \(2 \times 2\) matrix multiplies the determinant by \(-1\text{.}\) Suppose that row swapping on any \((n-1) \times (n-1)\) matrix multiplies the determinant by \(-1\) (in other words, we are proving our statement by mathematical induction). Now suppose \(A\) is an \(n \times n\) matrix and let \(B = [b_{ij}] = E_{rs}A\text{.}\) We first consider the case that \(s = r+1\) — that we swap adjacent rows. We consider two cases, \(r > 1\) and \(r = 1\text{.}\) First let us suppose that \(r > 1\text{.}\) Let \(C_{ij}\) be the \((i,j)\) cofactor of \(A\) and \(C'_{ij}\) the \((i,j)\) cofactor of \(B\text{.}\) We have

and

Since \(r > 1\text{,}\)it follows that \(a_{1j} = b_{1j}\) for every \(j\text{.}\) For each \(j\) the sub-matrix \(B_{1j}\) obtained from \(B\) by deleting the \(i\)th row and \(j\)th column is the same matrix as obtained from \(A_{ij}\) by swapping rows \(r\) and \(s\text{.}\) So by our induction hypothesis, we have \(C'_{1j} = -C_{1j}\) for each \(j\text{.}\) Then

Now we consider the case where \(r=1\text{,}\) where \(B\) is the matrix obtained from \(A\) by swapping the first and second rows. Here we will use the fact that \(\det(A) = \det(A^{\tr})\) which allows us to calculate \(\det(A)\) and \(\det(B)\) with the cofactor expansions down the first column. In this case we have

and

For each \(i \geq 3\text{,}\) the sub-matrix \(B_{i1}\) is just \(A_{i1}\) with rows 1 and 2 swapped. So we have \(C'_{i1} = -C_{i1}\) by our induction hypothesis. Since we swapped rows 1 and 2, we have \(B_{21} = A_{11}\) and \(B_{11} = A_{21}\text{.}\) Thus,

and

Putting this all together gives us

So we have shown that if \(B\) is obtained from \(A\) by interchanging two adjacent rows, then \(\det(B) = -\det(A)\text{.}\) Now we consider the general case. Suppose \(B\) is obtained from \(A\) by interchanging rows \(r\) and \(s\text{,}\) with \(r \lt s\text{.}\) We can perform this single row interchange through a sequence of adjacent row interchanges. First we swap rows \(r\) and \(r+1\text{,}\) then rows \(r+1\) and \(r+2\text{,}\) and continue until we swap rows \(s-1\) and \(s\text{.}\) This places the original row \(r\) into the row \(s\) position, and the process involved \(s-r\) adjacent row interchanges. Each of these interchanges multiplies the determinant by a factor of \(-1\text{.}\) At the end of this sequence of row swaps, the original row \(s\) is now row \(s-1\text{.}\) So it will take one fewer adjacent row interchanges to move this row to be row \(r\text{.}\) This sequence of \((s-r)+(s-r-1) = 2(s-r-1)-1\) row interchanges produces the matrix \(B\text{.}\) Thus,

and interchanging any two rows multiplies the determinant by \(-1\text{.}\)

Subsection Cofactor Expansions

We have stated that the determinant of a matrix can be calculated by using a cofactor expansion along any row or column. We use the result that swapping rows introduces a factor of \(-1\) in the determinant to verify that result in this section. Note that in proving that \(\det(A^{\tr}) = \det(A)\text{,}\) we have already shown that the cofactor expansion along the first column is the same as the cofactor expansion along the first row. If we can prove that the cofactor expansion along any row is the same, then the fact that \(\det(A^{\tr}) = \det(A)\) will imply that the cofactor expansion along any column is the same as well.

Now we demonstrate that the cofactor expansions along the first row and the \(i\)th row are the same. Let \(A = [a_{ij}]\) be an \(n \times n\) matrix. The cofactor expansion of \(A\) along the first row is

and the cofactor expansion along the \(i\)th row is

Let \(B\) be the matrix obtained by swapping row \(i\) with previous rows so that row \(i\) becomes the first row and the order of the remaining rows is preserved.

Then

So, letting \(C'_{ij}\) be the \((i,j)\) cofactor of \(B\) we have

Notice that for each \(j\) we have \(B_{1j} = A_{ij}\text{.}\) So

Subsection The LU Factorization of a Matrix

There are many instances where we have a number of systems to solve of the form \(A \vx = \vb\text{,}\) all with the same coefficient matrix. The system may evolve over time so that we do not know the constant vectors \(\vb\) in the system all at once, but only determine them as time progresses. Each time we obtain a new vector \(\vb\text{,}\) we have to apply the same row operations to reduce the coefficient matrix to solve the new system. This is time repetitive and time consuming. Instead, we can keep track of the row operations in one row reduction and save ourselves a significant amount of time. One way of doing this is the \(LU\)-factorization (or decomposition).

To illustrate, suppose we can write the matrix \(A\) as a product \(A = LU\text{,}\) where

Let \(\vb = [3 \ 1 \ 1 \ 3]^{\tr}\) and \(\vx = [x_1 \ x_2 \ x_3 \ x_4]^{\tr}\text{,}\) and consider the linear system \(A \vx = \vb\text{.}\) If \(A \vx = \vb\text{,}\) then \(LU \vx = \vb\text{.}\) We can solve this system without applying row operations as follows. Let \(U\vx = \vz\text{,}\) where \(\vz = [z_1 \ z_2 \ z_3 \ z_4]^{\tr}\text{.}\) We can solve \(L\vz = \vb\) by using forward substitution.

The equation \(L \vz = \vb\) is equivalent to the system

The first equation shows that \(z_1=3\text{.}\) Substituting into the second equation gives us \(z_2 = 4\text{.}\) Using this information in the third equation yields \(z_3 = -3\text{,}\) and then the fourth equation shows that \(z_4 = 0\text{.}\) To return to the original system, since \(U\vx = \vz\text{,}\) we now solve this system to find the solution vector \(\vx\text{.}\) In this case, since \(U\) is upper triangular, we use back substitution. The equation \(U\vx = \vz\) is equivalent to the system

Note that the third column of \(U\) is not a pivot column, so \(x_3\) is a free variable. The last equation shows that \(x_4=-1\text{.}\) Substituting into the second equation and solving for \(x_2\) yields \(x_2 = 2-3x_3\text{.}\) The first equation then gives us \(x_1 = 3-x_3\text{.}\) So the general solution

to \(A \vx = \vb\) can be found through \(L\) and \(U\) via forward and backward substitution. If we can find a factorization of a matrix \(A\) into a lower triangular matrix \(L\) and an upper triangular matrix \(U\text{,}\) then \(A= LU\) is called an \(LU\)-factorization or \(LU\)-decomposition.

We can use elementary matrices to obtain a factorization of certain matrices into products of lower triangular (the “L” in LU) and upper triangular (the “U” in LU) matrices. We illustrate with an example. Let

Our goal is to find an upper triangular matrix \(U\) and a lower triangular matrix \(L\) so that \(A = LU\text{.}\) We begin by row reducing \(A\) to an upper triangular matrix, keeping track of the elementary matrices used to perform the row operations. We start by replacing the entries below the \((1,1)\) entry in \(A\) with zeros. The elementary matrices that perform these operations are

and

We next zero out the entries below the \((2,2)\) entry as

where

The product \(E_3E_2E_1A\) is an upper triangular matrix \(U\text{.}\) So we have

and

where

is a lower triangular matrix \(L\text{.}\) So we have decomposed the matrix \(A\) into a product \(A = LU\text{,}\) where \(L\) is lower triangular and \(U\) is upper triangular. Since every matrix is row equivalent to a matrix in row echelon form, we can always find an upper triangular matrix \(U\) in this way. However, we may not always obtain a corresponding lower triangular matrix, as the next example illustrates.

Suppose we change the problem slightly and consider the matrix

Using the same elementary matrices \(E_1\text{,}\) \(E_2\text{,}\) and \(E_3\) as earlier, we have

To reduce \(B\) to row-echelon form now requires a row interchange. Letting

brings us to

So in this case we have \(U = E_4E_3E_2E_1B\text{,}\) but

is not lower triangular. The difference in this latter example is that we needed a row swap to obtain the upper triangular form.

Subsection Examples

What follows are worked examples that use the concepts from this section.

Subsection Summary

• The elementary row operations have the following effects on the determinant:

  • If we multiply a row of a matrix by a constant \(k\text{,}\) then the determinant is multiplied by \(k\text{.}\)

  • If we swap two rows of a matrix, then the determinant changes sign.

  • If we add a multiple of a row of a matrix to another, the determinant does not change.

• Each of the elementary row operations can be achieved by multiplication by elementary matrices. To obtain the elementary matrix corresponding to an elementary row operation, we perform the operation on the identity matrix.

• Let \(A\) be an \(n\times n\) invertible matrix. For any \(\vb\) in \(\R^n\text{,}\) the solution \(\vx\) of \(A\vx=\vb\) has entries

  \begin{equation*} x_i =\frac{\det(A_i(\vb))}{\det(A)} \end{equation*}

  where \(A_i(\vb)\) represents the matrix formed by replacing \(i\)th column of \(A\) with \(\vb\text{.}\)

• Let \(A\) be an invertible \(n\times n\) matrix. Then

  \begin{equation*} A^{-1} = \frac{1}{\det(A)} \text{ adj } A \end{equation*}

  where the \(\text{ adj } A\) matrix, the adjugate of \(A\), is defined as the matrix whose \(ij\)-th entry is \(C_{ji}\text{,}\) the \(ji\)-th cofactor of \(A\text{.}\)

• For a \(2\times 2\) matrix \(A\text{,}\) the area of the image of the unit square under the transformation \(T(\vx)=A\vx\) is equal to \(|\det(A)|\text{,}\) which is also equal to the area of the parallelogram defined by the columns of \(A\text{.}\)

• For a \(3\times 3\) matrix \(A\text{,}\) the volume of the image of the unit cube under the transformation \(T(\vx)=A\vx\) is equal to \(|\det(A)|\text{,}\) which is also equal to the volume of the parallelepiped defined by the columns of \(A\text{.}\)

• An \(LU\) factorization of a square matrix \(A\) consists of a lower triangular matrix \(L\) and an upper triangular matrix \(U\) so that \(A = LU\text{.}\)

• A square matrix \(A\) has an \(LU\) factorization if we can use row operations without row interchanges to row reduce \(A\) to an upper triangular matrix \(U\text{.}\) In this situation the elementary matrices that perform the row operations produce a lower triangular matrix \(L\) so that \(A = LU\text{.}\) If \(A\) cannot be reduced to an upper triangular matrix \(U\) without row interchanges, then we can factor \(A\) in the form \(PLU\text{,}\) where \(L\) is a lower triangular matrix, \(U\) is an upper triangular matrix, and \(P\) is obtained from the identity matrix by appropriate row interchanges.

• There are many instances where we have a number of systems to solve of the form \(A \vx = \vb\text{,}\) all with the same coefficient matrix but where the vectors \(\vb\) can change. With an \(LU\) factorization, we can keep track of the row operations in one row reduction and save ourselves a significant amount of time when solving these systems.