Wichita State University Logo

Math 511: Linear Algebra

2.4 Elementary Matrices

2.4.1 Elementary Row Operations¶

$$ \require{color} \definecolor{brightblue}{rgb}{.267, .298, .812} \definecolor{darkblue}{rgb}{0.0, 0.0, 1.0} \definecolor{palepink}{rgb}{1, .73, .8} \definecolor{softmagenta}{rgb}{.99,.34,.86} \definecolor{blueviolet}{rgb}{.537,.192,.937} \definecolor{jonquil}{rgb}{.949,.792,.098} \definecolor{shockingpink}{rgb}{1, 0, .741} \definecolor{royalblue}{rgb}{0, .341, .914} \definecolor{alien}{rgb}{.529,.914,.067} \definecolor{crimson}{rgb}{1, .094, .271} \def\ihat{\mathbf{\hat{\unicode{x0131}}}} \def\jhat{\mathbf{\hat{\unicode{x0237}}}} \def\khat{\mathrm{\hat{k}}} \def\tombstone{\unicode{x220E}} \def\contradiction{\unicode{x2A33}} $$

Recall from Section 1.2 that there are three elementary row operations one may perform on a matrix or augmented matrix.

Elementary Row Operations¶

  • Type I Interchange two rows

    • Interchanging two rows corresponds to interchanging two of the equations in the system of equations represented by the matrix.


  • Type II Multiply a row by a nonzero real number

    • Multiplying a row by a nonzero real number corresponds to multiplying both sides of one of the equations by the nonzero real number.



  • Type III Replace a row by the sum of the row and a multiple of another row.

    • Replacing a row by the sum of the row and a multiple of another row corresponds to adding a multiple of one equation to another.

These are the row operations we have been performing on a matrix or augmented matrix to obtain a row-equivalent matrix. The most important row-equivalent matrices are

  1. upper triangular form,
  2. row echelon form or
  3. reduced row echelon form.

The matrix one obtains from an elementary row operation is not equal to the original matrix. By equivalent we mean that the new linear system, matrix or augmented matrix has the same set of solutions.

2.4.2 Vector-Matrix Multiplication¶

We already discussed the definition of vector-matrix multiplication. The product of an $m\times n$ matrix $A$ on the left by an $1\times m$ matrix computes a linear combination of the rows of matrix $A$.

$$ \begin{align*} \mathbf{y}^TA &= \begin{bmatrix} y_1 & y_2 & y_3 & \dots & y_m \end{bmatrix}\begin{bmatrix} \mathbf{a}^1 \\ \mathbf{a}^2 \\ \mathbf{a}^3 \\ \vdots \\ \mathbf{a}^m \end{bmatrix} \\ \\ &= y_1\mathbf{a}^1 + y_2\mathbf{a}^2 + y_3\mathbf{a}^3 + \cdots + y_m\mathbf{a}^m = \displaystyle\sum_{k=1}^m y_k\mathbf{a}^k \\ \\ &= y_k\mathbf{a}^k \\ \end{align*} $$

Example 2.4.1¶

$$ \begin{align*} \begin{bmatrix} 1 & 2 & -1 \end{bmatrix}\begin{bmatrix} 1 & 2 & 3 \\ 0 & 2 & 1 \\ 2 & 1 & 0 \end{bmatrix} &= 1\cdot\begin{bmatrix} 1 & 2 & 3 \end{bmatrix} + 2\begin{bmatrix} 0 & 2 & 1 \end{bmatrix} + (-1)\cdot\begin{bmatrix} 2 & 1 & 0 \end{bmatrix} \\ \\ &= \begin{bmatrix} 1 & 2 & 3 \end{bmatrix} + \begin{bmatrix} 0 & 4 & 2 \end{bmatrix} - \begin{bmatrix} 2 & 1 & 0 \end{bmatrix} \\ \\ &= \begin{bmatrix} -1 & 5 & 5 \end{bmatrix} \end{align*} $$

Using symbols we write,

$$ y^TA = \begin{bmatrix} 1 & 2 & -1 \end{bmatrix}\begin{bmatrix} \mathbf{a}^1 \\ \mathbf{a}^2 \\ \mathbf{a}^3 \end{bmatrix} = \left[ 1\cdot\mathbf{a}^1 + 2\cdot\mathbf{a}^2 + (-1)\cdot\mathbf{a}^3 \right] = \mathbf{a}^1 + 2\mathbf{a}^2 - \mathbf{a}^3 $$

Similarly, given a linear combination of the rows of matrix $A$ one can deduce the row vector one multiplied by $A$ to obtain the specified linear combination. For example, given $4\times 3$ matrix $A$ and the linear combination $\mathbf{a}^1 - \mathbf{a}^2 + 2\mathbf{a}^3$

$$ \mathbf{a}^1 - \mathbf{a}^2 + 2\mathbf{a}^3 = 1\cdot\mathbf{a}^1 + (-1)\cdot\mathbf{a}^2 + 2\cdot\mathbf{a}^3 + 0\cdot\mathbf{a}^4 = \begin{bmatrix} 1 & -1 & 2 & 0 \end{bmatrix}A $$

Given a $3\times 4$ matrix $A$ and the linear combination $2\mathbf{a}^1 + 7\mathbf{a}^3$
$$ 2\mathbf{a}^1 + 7\mathbf{a}^3 = \begin{bmatrix} 2 & 0 & 7 \end{bmatrix}A $$

2.4.3 Type $\mathrm{I}$ Elementary Matrices¶

To perform a type $\mathrm{I}$ elementary row operation on an $n\times n$ matrix $A$, we need an $n\times n$ matrix $E$ that interchanges two rows of matrix $A$.

Example 2.4.2¶

$$ A = \begin{bmatrix} \ \ 2 & \ \ 2 & 3 \\ -1 & -2 & 0 \\ \ \ 1 & \ \ 4 & 3 \end{bmatrix} = \begin{bmatrix} \mathbf{a}^1 \\ \mathbf{a}^2 \\ \mathbf{a}^3 \end{bmatrix}, $$

let us interchange row 1 and row 3. We want the result to be

$$ \begin{bmatrix} \ \ 1 & \ \ 4 & 3 \\ -1 & -2 & 0 \\ \ \ 2 & \ \ 2 & 3 \end{bmatrix} = \begin{bmatrix} \mathbf{a}^3 \\ \mathbf{a}^2 \\ \mathbf{a}^1 \end{bmatrix} $$

These are very elementary linear combinations. We want the first row of our result to be

$$ \mathbf{a}^3 = 0\mathbf{a}^1 + 0\mathbf{a}^2 + \mathbf{a}^3 = \begin{bmatrix} 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} \ \ 2 & \ \ 2 & 3 \\ -1 & -2 & 0 \\ \ \ 1 & \ \ 4 & 3 \end{bmatrix}. $$

We want the second row of our result to be

$$ \mathbf{a}^2 = 0\mathbf{a}^1 + \mathbf{a}^2 + 0\mathbf{a}^3 = \begin{bmatrix} 0 & 1 & 0 \end{bmatrix}\begin{bmatrix} \ \ 2 & \ \ 2 & 3 \\ -1 & -2 & 0 \\ \ \ 1 & \ \ 4 & 3 \end{bmatrix}. $$

And we want the third row of our result to be

$$ \mathbf{a}^1 = \mathbf{a}^1 + 0\mathbf{a}^2 + 0\mathbf{a}^3 = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix}\begin{bmatrix} \ \ 2 & \ \ 2 & 3 \\ -1 & -2 & 0 \\ \ \ 1 & \ \ 4 & 3 \end{bmatrix}. $$

So we have

$$ \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}\begin{bmatrix} \ \ 2 & \ \ 2 & 3 \\ -1 & -2 & 0 \\ \ \ 1 & \ \ 4 & 3 \end{bmatrix} = \begin{bmatrix} \ \ 1 & \ \ 4 & 3 \\ -1 & -2 & 0 \\ \ \ 2 & \ \ 2 & 3 \end{bmatrix}. $$

The matrix $P = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}$ is called a Type $\mathrm{I}$ Elementary Matrix. The affect of multiplying this matrix times a $3\times n$ matrix will result in a new matrix with the $1^{\text{st}}$ and $3^{\text{rd}}$ rows interchanged.

This matrix is said to permute the rows of a $3\times 3$ matrix. This type of square matrix is also called a elementary permutation matrix. Notice that this elementary matrix is a square matrix. Notice also that the linear transformation it performs is to exchange the components of a $3\times 1$ vector.

$$ P\begin{bmatrix} x \\ y \\ z \end{bmatrix} = \begin{bmatrix} z \\ y \\ x \end{bmatrix} $$

The inverse of interchanging two rows of a matrix is to interchange them again, as that returns each to its original position. This means the linear transformation represented by an elementary permutation matrix or type $\mathrm{I}$ elementary matrix is an involution,

$$ P^2 = PP = I. $$

Any matrix that is equal to its own inverse is called an involutory matrix.

A permutation matrix exchanges any number of pairs of rows of the matrix it is multiplied. For example the permutation matrix

$$P = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} $$
interchanges the $1^{\text{st}}$ and $3^{\text{rd}}$ rows followed by interchanging the $1^{\text{st}}$ and $2^{\text{nd}}$ rows. You can check that this matrix is not involutory. The inverse of matrix $P$ is $P^T$. Verify that $PP^T = P^TP = I$. Matrices whose inverse is equal to its transpose are called orthogonal matrices.

  • Elementary permutation matrices are orthogonal, involutory, and symmetric.

  • All permutation matrices are orthogonal matrices.

2.4.4 Type $\mathrm{II}$ Elementary Matrices¶

To perform an type $\mathrm{II}$ elementary row operation we want to multiply one row by a nonzero real number (scalar) and leave all of the other rows unchanged. Given matrix

Examples 2.4.3¶

$$ A = \begin{bmatrix} \ \ 1 & \ \ 4 & 3 \\ -2 & -4 & 0 \\ \ \ 2 & \ \ 2 & 0 \end{bmatrix}, $$

we might want to multiply the second row by $-\frac{1}{2}$. The type $\mathrm{II}$ elementary matrix that performs this operation is the matrix

$$ E = \begin{bmatrix} 1 & \ \ 0 & 0 \\ 0 & -\frac{1}{2} & 0 \\ 0 & \ \ 0 & 1 \end{bmatrix} $$

We verify this is true by performing the multiplication

$$ EA = \begin{bmatrix} 1 & \ \ 0 & 0 \\ 0 & -\frac{1}{2} & 0 \\ 0 & \ \ 0 & 1 \end{bmatrix}\begin{bmatrix} \ \ 1 & \ \ 4 & 3 \\ -2 & -4 & 0 \\ \ \ 2 & \ \ 2 & 0 \end{bmatrix} = \begin{bmatrix} \ \mathbf{a}^1 + \ 0\mathbf{a}^2 + 0\mathbf{a}^3 \\ 0\mathbf{a}^1 - \frac{1}{2}\mathbf{a}^2 + 0\mathbf{a}^3 \\ 0\mathbf{a}^1 + \ 0\mathbf{a}^2 + \ \mathbf{a}^3 \end{bmatrix} = \begin{bmatrix} 1 & 4 & 3 \\ 1 & 2 & 0 \\ 2 & 2 & 0 \end{bmatrix}. $$

Type $\mathrm{II}$ elementary matrices are invertible and their inverses are obtained by multiplying the same row by the multiplicative inverse of the nonzero scalar. In example 2.4.3

$$ E^{-1} = \begin{bmatrix} 1 & \ \ 0 & 0 \\ 0 & -2 & 0 \\ 0 & \ \ 0 & 1 \end{bmatrix}. $$

2.4.5 Type $\mathrm{III}$ Elementary Matrices¶

A type $\mathrm{III}$ elementary matrix results in replacing one row by adding a multiple of another to it. For example if we want to reduce matrix

$$ A = \begin{bmatrix} 1 & 4 & 3 \\ 1 & 2 & 0 \\ 2 & 2 & 0 \end{bmatrix} $$

by subtracting two times row 1 from row 3, we would multiply matrix $A$ by the elementary matrix

$$ E = \begin{bmatrix} \ \ 1 & 0 & 0 \\ \ \ 0 & 1 & 0 \\ -2 & 0 & 1 \end{bmatrix}. $$

The product

$$ EA = \begin{bmatrix} \ \ 1 & 0 & 0 \\ \ \ 0 & 1 & 0 \\ -2 & 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 4 & 3 \\ 1 & 2 & 0 \\ 2 & 2 & 0 \end{bmatrix} = \begin{bmatrix} \ \ \ \ \ \ \ \ \mathbf{a}^1 + 0\mathbf{a}^2 + 0\mathbf{a}^3 \\ \ \ \ \ \ \ 0\mathbf{a}^1 + \ \mathbf{a}^2 + 0\mathbf{a}^3 \\ (-2)\mathbf{a}^1 + 0\mathbf{a}^2 + \mathbf{a}^3 \end{bmatrix} = \begin{bmatrix} \mathbf{a}^1 \\ \mathbf{a}^2 \\ -2\mathbf{a}^1 + \mathbf{a}^3 \end{bmatrix} = \begin{bmatrix} 1 & \ \ 4 & \ \ 3 \\ 1 & \ \ 2 & \ \ 0 \\ 0 & -6 & -6 \end{bmatrix}. $$

Notice that like type $\mathrm{I}$ and $\mathrm{II}$ elementary matrices, type $\mathrm{III}$ elementary matrices are invertible. The inverse of subtracting two times row 1 from row 3 is to add two times row 1 to row 3,

$$ E^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 1 \end{bmatrix}. $$

2.4.6 Row Equivalent Matrices¶

Definition¶

If one multiplies a finite number of $n\times n$ elementary matrices by an $n\times n$ matrix $A$, the product

$$ B = E_1E_2E_3\cdots E_kA $$

is called a row equivalent matrix. We say that $\mathbf{B}$ is row equivalent to $\mathbf{A}$. Notice that since all of these elementary matrices are invertible we have that

$$ E_k^{-1}\cdots E_3^{-1}E_2^{-1}E_1^{-1}B = A $$

so $\mathbf{A}$ is row equivalent to $\mathbf{B}$.

We can add to our list

Theorem 2.4.1¶

If A is an $n\times n$ matrix, all of the following conditions are equivalent:

  1. all of the columns of $A$ are pivot columns
  2. The homogeneous linear system $A\mathbf{x} = 0$ has a unique solution
  3. $A$ is a nonsingular matrix
  4. $A$ is a non-degenerate matrix
  5. $A$ is an invertible matrix
  6. $A$ is row equivalent to $I$
  7. The reduced row echelon form of $A$ is $I$
  8. $A$ is the product of elementary matrices

Throughout this course we will continue adding to this list. Similarly,

Corollary 2.4.2¶

If A is an $n\times n$ matrix, all of the following conditions are equivalent:

  1. $A$ has a free column
  2. The homogeneous linear system $A\mathbf{x} = 0$ has a infinitely many solutions
  3. $A$ is a singular matrix
  4. $A$ is a degenerate matrix
  5. $A$ is not an invertible matrix
  6. $A$ is not row equivalent to $I$
  7. The reduced row echelon form of $A$ is a matrix with free columns
  8. $A$ cannot be factored into a product of elementary matrices

2.4.7 The LU Decomposition¶

Recall that our first method for factoring a matrix into a product of two simpler matrices is the factoring $A=CR$, where matrix $C$ has just the pivot columns of matrix $A$ and matrix $R$ is the reduced row echelon form of matrix $A$ with any rows of zeros removed.

Column-Rank Factorization video Column-Rank Factorization

Our second method of factoring a matrix into simpler matrices is the LU Decomposition; we will factor matrix $A$ into a product of a lower triangular matrix, $L$ and an upper triangular matrix $U$.

Dr. Strang video factoring a matrix into A=LU Factoring a Matrix into A=LU

The notes below cover the LU Decomposition however, if you still want more information on the factoring method Dr. Strang and I cover this method the same way. It can be useful to hear the same explanation from another person.

2.4.8 Computing the LU Decomposition¶

We will accomplish this task using only type III elementary row operations¶

Notice that computing the $LU$ decomposition is another application of using row operations to reduce a matrix into a simpler form. In this application we reduce a matrix into upper triangular form $U$ using only type III elementary row operations.

Example 1¶

Perform the $LU$ decomposition of matrix $A = \begin{bmatrix} 2 & 1 & 1 \\ 6 & 4 & 5 \\ 4 & 1 & 3 \end{bmatrix}$.

$$\begin{align*} A &= \begin{bmatrix} 2 & 1 & 1 \\ {\color{purple} 6} & 4 & 5 \\ 4 & 1 & 3 \end{bmatrix}\ \begin{array}{l} \\ R_2 - 3R_1 \\ \\ \end{array} \\ \\ E_{21}A &= \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\,\begin{bmatrix} 2 & 1 & 1 \\ {\color{purple} 6} & 4 & 5 \\ 4 & 1 & 3 \end{bmatrix} = \begin{bmatrix} 2 & 1 & 1 \\ {\color{purple} 0} & 1 & 2 \\ 4 & 1 & 3 \end{bmatrix} \end{align*}$$

The main difference here is that we are performing the type III row operations with an type III elementary matrix. In this case we use the type III elementary matrix

$$\mathbf{E}_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$
We call the matrix $E_{21}$ because our goal, like any other method that reduces the matrix, is to obtain a zero in position $(2,1)$ of the resulting equivalent matrix. The next step is to use a type III row operation to obtain a zero in position $(3,1)$, so we will name the type III elementary matrix $E_{31}$.

$$\begin{align*} E_{21}A &= \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ {\color{purple} 4} & 1 & 3 \end{bmatrix}\ \begin{array}{l} \\ \\ R_3-2R_1 \end{array} \\ \\ E_{31}E_{21}A &= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \end{bmatrix}\,\begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ {\color{purple} 4} & 1 & 3 \end{bmatrix} = \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ {\color{purple} 0} & -1 & 1 \end{bmatrix} \end{align*}$$
The third step is to use the pivot in position $(2,2)$ to get a zero in position $(3,2)$

$$\begin{align*} E_{31}E_{21}A &= \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & {\color{purple}{-1}} & 1 \end{bmatrix}\ \begin{array}{l} \\ \\ R_3+R_2 \end{array} \\ \\ E_{32}E_{31}E_{21}A &= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}\,\begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & {\color{purple}{-1}} & 1 \end{bmatrix} = \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & {\color{purple}{0}} & 3 \end{bmatrix} = U \\ \end{align*}$$
Notice that matrix $U$ is our upper triangular form of matrix $A$. Now using matrix algebra we perform the following steps,

$$\begin{align*} E_{32}E_{31}E_{21}A &= U \\ \\ E_{32}^{-1}E_{32}E_{31}E_{21}A &= E_{32}^{-1}U \\ \\ IE_{31}E_{21}A &= E_{32}^{-1}U \\ \\ E_{31}^{-1}E_{31}E_{21}A &= E_{31}^{-1}E_{32}^{-1}U \\ \\ E_{21}A &= E_{31}^{-1}E_{32}^{-1}U \\ \\ E_{21}^{-1}E_{21}A &= E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U \\ \\ A &= E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U \end{align*} $$



Since we were clever enough to use only type III elementary row operations, we compute each inverse using the inverse type III elementary row operations

$$\begin{align*} E_{21}^{-1} &= \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\ \begin{array}{l} \ \\ R_2 + 3R_1 \\ \ \end{array} \\ \\ E_{31}^{-1} &= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 1 \end{bmatrix}\ \begin{array}{l} \\ \\ R_3 + 2R_1 \end{array} \\ \\ E_{32}^{-1} &= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix}\ \begin{array}{l} \\ \\ R_3 - R_2 \end{array} \end{align*}$$

Furthermore, because we are clever enough to use only type III elementary row operations, the product of these matrices is both lower triangular and the elements of the lower triangle are simple to determine,

$$ L = E_{21}^{-1}E_{31}^{-1}E_{32}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & -1 & 1 \end{bmatrix} $$

You should check for yourself that,

$$ A = \begin{bmatrix} 2 & 1 & 1 \\ 6 & 4 & 5 \\ 4 & 1 & 3 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & -1 & 1 \end{bmatrix}\,\begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 3 \end{bmatrix} = LU. $$

Why do we factor a matrix into a product of a lower triangular matrix and an upper triangular matrix?¶

This makes solving the equation $A\mathbf{x} = \mathbf{b}$ easier. In modeling applications of all kinds we read data from a measuring device, $\mathbf{b}$, and we want to compute the result of the mathematical model based on this input. If $A$ is invertible we compute the inverse before the measurements start and compute

$$ \mathbf{x} = A^{-1}\mathbf{b}.$$
However, in most cases the matrix $A$ is very large and generally not invertible. If we compute instead the factors $L$ and $U$, then we use the following algebra

$$\begin{align*} A\mathbf{x} &= \mathbf{b} \\ \\ LU\mathbf{x} &= \mathbf{b} \\ \\ U\mathbf{x} &= L^{-1}\mathbf{b} \end{align*}$$
Remember that matrix $L$ is a product of type III elementary matrices, so it is invertible, even though upper triangular matrix $U$ might not be. When we obtain the input $\mathbf{b}$ we solve the equation

$$U\mathbf{x} = L^{-1}\mathbf{b}.$$
This is much simpler because the matrix $U$ is already in upper triangular form. Solve the system only involves backward substitution. A simple computer algorithm can perform the backward substitution and obtain the result $\mathbf{x}$ quickly and accurately.


2.4.9 Exercise¶

Exercise 1¶

Solve the equation $A\mathbf{x} = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}$ using the $LU$-decomposition from the previous example.


Solution

$$ \begin{align*} A\mathbf{x} &= \begin{bmatrix}\ \ 2\ &\ \ 1\ &\ \ 1\ \\ \ \ 6\ &\ \ 4\ &\ \ 5\ \\ \ \ 4\ &\ \ 1\ &\ \ 3\ \end{bmatrix}\mathbf{x} = \begin{bmatrix}\ \ 1\ \\ \ \ 2\ \\ \ \ 3\ \end{bmatrix} \\ \\ LU\mathbf{x} &= \begin{bmatrix}\ \ 1\ \\ \ \ 2\ \\ \ \ 3\ \end{bmatrix} \\ \\ U\mathbf{x} &= L^{-1}\begin{bmatrix}\ \ 1\ \\ \ \ 2\ \\ \ \ 3\ \end{bmatrix} \end{align*} $$
Remember that we compute $L^{-1}$ as a product.
$$ \begin{align*} L^{-1} &= E_{32}E_{31}E_{21} \\ \\ &= \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 1\ \end{bmatrix}\,\begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ \\ -2\ &\ \ 0\ &\ \ 1\ \end{bmatrix}\,\begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ \\ -3\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ \end{bmatrix} \\ \\ &= \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 1\ \end{bmatrix}\,\begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ \\ -3\ &\ \ 1\ &\ \ 0\ \\ -2\ &\ \ 0\ &\ \ 1\ \end{bmatrix} = \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ \\ -3\ &\ \ 1\ &\ \ 0\ \\ -5\ &\ \ 1\ &\ \ 1\ \end{bmatrix} \\ \\ U\mathbf{x} &= \begin{bmatrix}\ \ 2\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ &\ \ 2\ \\ \ \ 0\ &\ \ 0\ &\ \ 3\ \end{bmatrix}\mathbf{x} = \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ \\ -3\ &\ \ 1\ &\ \ 0\ \\ -5\ &\ \ 1\ &\ \ 1\ \end{bmatrix}\,\begin{bmatrix}\ \ 1\ \\ \ \ 2\ \\ \ \ 3\ \end{bmatrix} = L^{-1}\mathbf{b} \\ \\ \begin{bmatrix}\ \ 2\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ &\ \ 2\ \\ \ \ 0\ &\ \ 0\ &\ \ 3\ \end{bmatrix}\mathbf{x} &= \begin{bmatrix}\ \ 1\ \\ -1\ \\ \ \ 0\ \end{bmatrix} \end{align*} $$
Since we can now use backward substitution,
$$ \begin{align*} 3x_3 &= 0 &\qquad x_2 + 2(0) &= -1 &\qquad 2x_1 - 1 + 0 &= 1 \\ \\ x_3 &= 0 &\qquad x_2 &= -1 &\qquad 2x_1 &= 2 \\ \\ & &\qquad & &\qquad x_1 &= 1 \end{align*} $$
Our solution is $\mathbf{x} = \begin{bmatrix} \ \ 1\ \\ -1\ \\ \ \ 0\ \end{bmatrix}$.

2.4.10 Transposes, Permutations and Spaces $\mathbb{R}^n$¶

There is no video from Grant Sanderson on these topics. If you have any questions about the material covered in this video be sure to ask about it in our Discussion Forum

Video covering Transposes, Permutations, and spaces R^n Factoring a Matrix into A=LU

We discussed transpose in the previous sections. Dr. Strang is showing how to use permutation matrices, transposes, and begin our discussion of subspaces of $\mathbb{R}^n$. He uses a much older notation that we both do now. Remember the elements of matrix use the lower-case version of the same capital letter used to name the matrix.

$$ A = [a_{ij}] $$

The transpose exchanges the row indices and the column indices. We would write today

$$ A^T = [a_{ji}] $$

2.4.11 Gaussian Elimination¶

Gaussian Elimination and $LU$-decomposition may not always be possible when matrix $A$ is a singular matrix and zeros appear in the next pivot position we want to use. In practical terms, computer programs encounter trouble when using a pivot that is close to zero. To make our elimination work for singular matrices and computationally stable we will utilize type I elementary row operations and type III elementary row operations to permute rows so that the pivot in matrix $U$ is the largest nonzero value possible from the rows available.

The product of the row exchanges is a permutation matrix $P$. This may not be a elementary permutation matrix because it may be a product of several permutations. The resulting factorization becomes


$$ PA = LU $$
where permutation matrix $P$ exchanges the rows necessary to make the computation of $L$ and $U$ most accurate and makes sure that the diagonal elements of matrix $L$ has no zeros.

We will learn in Chapter 5 that a permutation matrix is orthogonal. That means that


$$ P^{-1} = P^T $$
This gives that


$$ \begin{align*} PA &= LU \\ \\ P^{-1}PA &= P^{-1}LU = P^TLU \\ \\ A &= P^TLU \end{align*} $$
If we realize that the transpose of a permutation matrix is a permutation matrix, then we often think of $P^T$ as our permutation matrix in our factorization. That means most textbooks will write the factorization called



Gaussian Elimination with Partial Pivoting¶


$$ A = PLU $$
where $P$ is a permutation matrix, $L$ is lower triangular and $U$ is upper triangular. In this case we can solve the equation $A\mathbf{x}=\mathbf{b}$ for many input vectors $\mathbf{b}$
$$ \begin{align*} A\mathbf{x} &= \mathbf{b} \\ \\ PLU\mathbf{x} &= \mathbf{b} \\ \\ U\mathbf{x} &= L^{-1}P^T\mathbf{b} \\ \end{align*} $$
For each input vector $\mathbf{b}$ we can solve the system $A\mathbf{x}=\mathbf{b}$ by using backward substitution to solve
$$ U\mathbf{x} = L^{-1}P^T\mathbf{b}. $$

2.4.12 CR Decomposition Exercise¶

Exercise 1¶

Place the matrix $A$ into reduced row echelon form. Consider the matrix

$$ A = \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 4 & \ \ 3 \\ \ \ 2 & \ \ 4 & \ \ 6 & \ \ 1 \\ -3 & -3 & -6 & \ \ 2 \\ \ \ 0 & \ \ 4 & \ \ 4 & -2 \end{bmatrix} $$


View Solution
$$\begin{align*} B &= \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 4 & \ \ 3 \\ \ \ 2 & \ \ 4 & \ \ 6 & \ \ 1 \\ -3 & -3 & -6 & \ \ 2 \\ \ \ 0 & \ \ 4 & \ \ 4 & -2 \end{bmatrix} \begin{matrix} \\ -2R_1 + R_2 \\ \ \ 3R_1 + R_3 \\ \\ \end{matrix} \\ \\ &= \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 4 & \ \ 3 \\ \ \ 0 & -2 & -2 & -5 \\ \ \ 0 & \ \ 6 & \ \ 6 & \ 11 \\ \ \ 0 & \ \ 4 & \ \ 4 & -2 \end{bmatrix} \begin{matrix} \\ \\ \ \ 3R_2 + R_3 \\ \ \ 2R_2 + R_4 \\ \end{matrix} \\ \\ &= \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 4 & \ \ \ 3 \\ \ \ 0 & -2 & -2 & -5 \\ \ \ 0 & \ \ 0 & \ \ 0 & -4 \\ \ \ 0 & \ \ 0 & \ \ 0 & -12 \end{bmatrix} \begin{matrix} \\ \\ \\ -3R_3 + R_4 \\ \end{matrix} \\ \\ &= \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 4 & \ \ \ 3 \\ \ \ 0 & -2 & -2 & -5 \\ \ \ 0 & \ \ 0 & \ \ 0 & -4 \\ \ \ 0 & \ \ 0 & \ \ 0 & -12 \end{bmatrix} \begin{matrix} \\ \\ \\ -3R_3 + R_4 \\ \end{matrix} \\ \\ &= \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 4 & \ \ \ 3 \\ \ \ 0 & -2 & -2 & -5 \\ \ \ 0 & \ \ 0 & \ \ 0 & -4 \\ \ \ 0 & \ \ 0 & \ \ 0 & \ \ 0 \end{bmatrix} \begin{matrix} -\frac{1}{2}R_2 \\ -\frac{1}{4}R_3 \\ \end{matrix} \\ \\ &= \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 4 & \ \ \ 3 \\ \ \ 0 & \ \ 1 & \ \ 1 & \ \ \frac{5}{2} \\ \ \ 0 & \ \ 0 & \ \ 0 & \ \ 1 \\ \ \ 0 & \ \ 0 & \ \ 0 & \ \ 0 \end{bmatrix} \end{align*}$$
The matrix $B$ is currently in row echelon form. We use backward substitution to find the reduced row echelon form.
$$\begin{align*} B &= \begin{bmatrix} 1 & 3 & 4 & 3 \\ 0 & 1 & 1 & \frac{5}{2} \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{array}{l} -3R_3 + R_1 \\ -\frac{5}{2} R_3 + R_2 \\ \\ \\ \end{array} \\ \\ &= \begin{bmatrix} 1 & 3 & 4 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{array}{l} -3R_2 + R_1 \\ \\ \\ \\ \end{array} \\ \\ &= \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align*}$$
$B$ is now the reduced row echelon form of $A$.

After completing Exercise 1, we have that

$$ B = \begin{bmatrix} 1 & 0 & \color{#9900FF}1 & 0 \\ 0 & 1 & \color{#9900FF}1 & 0 \\ 0 & 0 & \color{#9900FF}0 & 1 \\ 0 & 0 & \color{#9900FF}0 & 0 \end{bmatrix}. $$
Note that the third column of $B$ does not contain a pivot. This means that the third column is not a pivot column. Because it is not a pivot column, that means the corresponding (third) column of $A$ is linearly dependent on its other columns.

$$ A = \begin{bmatrix} \ \ 1 & \ \ 3 & \color{#9900FF}{\ \ 4} & \ \ 3 \\ \ \ 2 & \ \ 4 & \color{#9900FF}{\ \ 6} & \ \ 1 \\ -3 & -3 & \color{#9900FF}{-6} & \ \ 2 \\ \ \ 0 & \ \ 4 & \color{#9900FF}{\ \ 4} & -2 \end{bmatrix} $$
With matrices $A$ and $B$, we are close to being able to form the rank factorization of matrix $A$. This factorization lets us take a matrix $A\in\mathbb{R}^{m\times n}$ of rank $r$ and decompose it into a product

$$ A = CR $$
where $C$ is a matrix of the pivot columns of $A$ and $R$ is a matrix of a nonzero rows from the reduced row echelon form of $A$. Setting

$$ C = \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 3 \\ \ \ 2 & \ \ 4 & \ \ 1 \\ -3 & -3 & \ \ 2 \\ \ \ 0 & \ \ 4 & -2 \end{bmatrix} $$
and

$$ R = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}, $$
we have that

$$ \begin{align*} A &= CR \\ \\ \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 4 & \ \ 3 \\ \ \ 2 & \ \ 4 & \ \ 6 & \ \ 1 \\ -3 & -3 & -6 & \ \ 2 \\ \ \ 0 & \ \ 4 & \ \ 4 & -2 \end{bmatrix} &= \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 3 \\ \ \ 2 & \ \ 4 & \ \ 1 \\ -3 & -3 & \ \ 2 \\ \ \ 0 & \ \ 4 & -2 \end{bmatrix} \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \end{align*} $$





Exercise 2¶

Use matrix multiplication to verify that $A = CR$.


View Solution
This is easily shown by partitioning the matrix $R$ into its columns.
$$ \begin{align*} A &= CR \\ \\ &= \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 3 \\ \ \ 2 & \ \ 4 & \ \ 1 \\ -3 & -3 & \ \ 2 \\ \ \ 0 & \ \ 4 & -2 \end{bmatrix} \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \\ \\ &= \begin{bmatrix} \color{#9900FF}{\ \ 1} & \color{#006666}{\ \ 3} & \color{#0066CC}{\ \ 3} \\ \color{#9900FF}{\ \ 2} & \color{#006666}{\ \ 4} & \color{#0066CC}{\ \ 1} \\ \color{#9900FF}{-3} & \color{#006666}{-3} & \color{#0066CC}{\ \ 2} \\ \color{#9900FF}{\ \ 0} & \color{#006666}{\ \ 4} & \color{#0066CC}{-2} \end{bmatrix}\left[\begin{array}{c|c|c|c} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right] \\ \\ &= \left[\begin{array}{c|c|c|c} \color{#9900FF}{\ \ 1} & \color{#006666}{\ \ 3} & \color{#9900FF}{\ \ 1} + \color{#006666}{\ \ 3} & \color{#0066CC}{\ \ 3} \\ \color{#9900FF}{\ \ 2} & \color{#006666}{\ \ 4} & \color{#9900FF}{\ \ 2} + \color{#006666}{\ \ 4} & \color{#0066CC}{\ \ 1} \\ \color{#9900FF}{-3} & \color{#006666}{-3} & \color{#9900FF}{-3} + \color{#006666}{-3} & \color{#0066CC}{\ \ 2} \\ \color{#9900FF}{\ \ 0} & \color{#006666}{\ \ 4} & \color{#9900FF}{\ \ 0} + \color{#006666}{\ \ 4} & \color{#0066CC}{-2} \end{array}\right] \\ \\ &= \begin{bmatrix} \ \ 1 & \ \ 3 & \ \ 4 & \ \ 3 \\ \ \ 2 & \ \ 4 & \ \ 6 & \ \ 1 \\ -3 & -3 & -6 & \ \ 2 \\ \ \ 0 & \ \ 4 & \ \ 4 & -2 \end{bmatrix} \color{#9900FF}{\Huge \quad\checkmark} \end{align*} $$

Your use of this self-initiated mediated course material is subject to our An international nonprofit organization that empowers people to grow and sustain the thriving commons of shared knowledge and culture. Creative Commons License 4.0