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
- Type II Multiply a row by a nonzero real number
- Type III Replace a row by the sum of the row and a multiple of another row.
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
- upper triangular form,
- row echelon form, and
- 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.
Video Lecture 1: Elementary Matrices.¶
Now we are ready to study the rest of Dr. Strang's video at 19:04 minutes into the video.
Elementary MatricesTo 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 1 - Permuting Rows¶
$$ 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} $$
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 effect 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 an 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} $$
Definition¶
Permutation Matrix (Type I Elementary Matrix)
Let $\mathbf{e}_1$, $\dots$, $\mathbf{e}_n$ be the $n$ elementary basis vectors for $\mathbb{R}^n$, and let $(i_1,\dots,i_n)$ be a permutation of the integers $1$, $\dots$, $n$ (For example, $(6, 3, 5, 1, 2, 4)$ is a permutation of the first six positive integers).
Define $P = \begin{bmatrix}\ \mathbf{e}_{i_1}^T\ \\ \ \vdots\ \\ \ \mathbf{e}_{i_n}^T\ \end{bmatrix}$. If $A$ is an $n\times p$ matrix, then $PA = \begin{bmatrix}\ \mathbf{a}^{i_1}\ \\ \ \vdots\ \\ \ \mathbf{a}^{i_n}\ \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.
Definition¶
Involution
Any non-singular matrix $P$ with the property
$$ P^2 = PP = I. $$
is called an involution.
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$.
Definition¶
Orthogonal Matrix
A non-singular matrix $Q$ whose inverse is equal to its transpose, $Q^TQ = QQ^T = I$ is called an orthogonal matrix.
Elementary permutation matrices permute exactly one pair of rows. Thus not all permutation matrices are elementary.
Theorem 1¶
Properties of Elementary Permutation Matrices
Elementary permutation matrices are involutory, orthogonal, and symmetric.
Exercise 1 - Prove Theorem 1¶
View Solution
Let $P$ be an $n\times n$ elementary permutation matrix. Suppose that matrix $P$ swaps row $j$ with row $k$, $1\le j < k\le n$. Each row of $P$ is the transpose of an elementary basis vector. The $i^{\text{th}}$ row of matrix $P$ is given by: $$ \mathbf{p}^i = \left\{ \begin{array}{ccc} \mathbf{e}_i^T & \text{ if } & i\neq j,k \\ \mathbf{e}_k^T & \text{ if } & i=j \\ \mathbf{e}_j^T & \text{ if } & i=k \end{array} \right. $$ If $A$ is an $n\times p$ matrix, the $i^{\text{th}}$ row of $PA$ is given by $$ (PA)^i = \left\{ \begin{array}{ccc} \mathbf{a}_i^T & \text{ if } & i\neq j,k \\ \mathbf{a}_k^T & \text{ if } & i=j \\ \mathbf{a}_j^T & \text{ if } & i=k \end{array} \right. $$ Squaring matrix $P$ swaps rows $j$ and $k$ again so that $$ (P^2)^i = \left\{ \begin{array}{ccc} \mathbf{e}_i^T & \text{ if } & i\neq j,k \\ \mathbf{e}_j^T & \text{ if } & i=j \\ \mathbf{e}_k^T & \text{ if } & i=k \end{array} \right. $$ Hence $P^2=I$ and matrix $P$ is involutory.$P^T$ has the property that columns $j$ and $k$ have been swapped. That is, $$ (\mathbf{p}^T)_i = \left\{ \begin{array}{ccc} \mathbf{e}_i & \text{ if } & i\neq j,k \\ \mathbf{e}_k & \text{ if } & i=j \\ \mathbf{e}_j & \text{ if } & i=k \end{array} \right. $$ Using the inner product version of matrix multiplication, $$ \mathbf{p}^r(\mathbf{p}^T)_s = \left\{ \begin{array}{ccc} 0 = \mathbf{e}^r\mathbf{e}_s & \text{ if } & r\neq s \\ 1 = \mathbf{e}^i\mathbf{e}_i & \text{ if } & r=s=i\neq j,k \\ 1 = \mathbf{e}^j\mathbf{e}_j & \text{ if } & r=s=j \\ 1 = \mathbf{e}^k\mathbf{e}_k & \text{ if } & r=s=k \end{array} \right. = \left\{ \begin{array}{ccc} 0 & \text{ if } & r\neq s \\ 1 & \text{ if } & r=s \end{array} \right. $$ Hence $PP^T = \left[ \delta_{rs} \right] = I_n$, and matrix $P$ is orthogonal.
$P^{-1} = P$ since $P$ is involutory, and $P^{-1} = P^T$ since $P$ is orthogonal, therefore $P = P^{-1} = P^T$ and $P$ is symmetric.
To perform a 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
Example 2 - Scaling Rows¶
$$ 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}. $$
Definition¶
Type II Elementary Matrix
A Type II Elementary Matrix, $E$, is a diagonal matrix. Exactly one diagonal entry is a nonzero scalar value, and all other diagonal entries are equal to one.
Theorem 2¶
Properties of Type II Elementary Matrices
Type II elementary matrices are non-singular, diagonal, and symmetric.
Exercise 2 - Prove Theorem 2¶
View Solution
Let $E$ be a $n\times n$ type II elementary matrix with $1\le k\le n$, $e_{kk} = \alpha$, $\alpha\neq 0$, and $e_{ii}=1$ when $i\neq k$. By definition $E$ is a diagonal matrix, and therefore symmetric. $E^{-1}=E$, except for value $e_{kk}$, the $k^{\text{th}}$ diagonal element of the inverse matrix is $\alpha^{-1} = \frac{1}{\alpha}$. Thus $E$ is invertible, and hence non-singular. $\blacksquare$Definition¶
Type III Elementary Matrix
Like type II elementary matrices, a type $\mathrm{III}$ elementary matrix, $E$, differs from an identity matrix in one row only. The elements of this one row describe a linear combination of the rows of an $n\times p$ matrix $A$ in the product $EA$. The linear combination consists of a nonzero scalar multiplication of one other row added to the modified row.
Multiplying matrix $A$ by $E$ on the left results in replacing one row of matrix $A$ with a multiple of one other row of matrix $A$ added to it.
Example 3 - Type III Row Operation¶
$$ 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}. $$
Type III Elementary matrices are not required to be lower triangular. However in Gaussian Elimination, one eliminates the pivot from all rows beneath the pivot. This results in lower triangular type III elementary matrices.
Once the matrix is in row echelon form, Jordan elimination, removes pivot variables from rows above the pivot. Hence these type III elementary matrices will be upper triangular.
Theorem 3¶
Properties of Type III Elementary Matrices
Type III elementary matrices matrices are non-singular.
Exercise 3 - Prove Theorem 3¶
View Solution
If $E$ is an $n\times n$, type III elementary matrix, and $A$ is an $n\times p$ matrix. Then product matrix $EA$ differs from matrix $A$ in only one row. This row has a nonzero scalar multiple $\alpha$ times another row of matrix $A$ added to it. As the scaled row remains unchanged, _subtracting_ the same scalar multiple of this row to the modified row will undo the modification. Hence type III elementary matrices are non-singular.Definition¶
Row Equivalent Matrices
If one multiplies a finite number of $n\times n$ elementary matrices by an $n\times p$ 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 of properties of non-singular matrices.
Theorem 4¶
If A is an $n\times n$ matrix, all of the following conditions are equivalent:
- $A$ is a nonsingular matrix (non-degenerate)
- all of the columns of $A$ are pivot columns
- The homogeneous linear system $A\mathbf{x} = 0$ has a unique solution
- $A$ is an invertible matrix
- $A$ is row equivalent to $I$
- The reduced row echelon form of $A$ is $I$
- $A$ is the product of elementary matrices
We will continue adding to this list throughout this course. Similarly,
Corollary 5¶
If A is an $n\times n$ matrix, all of the following conditions are equivalent:
- $A$ is a singular matrix (degenerate)
- $A$ has a free column
- The homogeneous linear system $A\mathbf{x} = 0$ has infinitely many solutions
- $A$ is not an invertible matrix
- $A$ is not row equivalent to $I$
- The reduced row echelon form of $A$ is not $I$
- $A$ cannot be factored into a product of elementary matrices
In pre-calculus algebra, one factors a polynomial into a product of linear factors. Sometimes a linear factor can have a multiplicity greater than one.
Example 4 - Factoring Polynomials¶
(a) Linear factor $x-1$ is a factor of $x^2 - 2x + 1$ with multiplicity 2.
$$ x^2 - 2x + 1 = (x-1)^2 $$
(b) Linear factor $x+2$ is a factor of $x^3 + 6x^2 + 12x + 8$ with multiplicity 3.
$$ x^3 + 6x^2 + 12x + 8 = (x+2)^3 $$
(c) Linear factor $x+1$ is a factor of $x^3 - x^2 - 5x - 3$ with multiplicity 2.
$$ x^3 - x^2 - 5x - 3 = (x+1)^2(x-3) $$
Matrices can often be factored into simpler and easier to understand matrices. These factors each provide insight into the more complex product matrices. We will spend a considerable portion of our time in this course factoring matrices into products of simpler matrices.
Definition¶
Rank
The Rank of $m\times n$ matrix $A$ is the number of pivot columns of matrix $A$. The rank is denoted rank$(A)$.
Video Lecture 2: Column-Rank Factorization.¶
Column-Rank FactorizationDefinition¶
Column-Rank Factorization
Column-Rank Factorization or CR Factorization decomposes an $m\times n$ matrix $A$ into two factors
$$A = CR.$$
Let $r= \textrm{rank}(A)$. Then $m\times r$ matrix $C$ consists of the pivot columns of matrix $A$, and $r\times n$ matrix $R$ consists of the nonzero rows of the reduced row echelon form of matrix $A$.
Matrix $C$ contains each of the pivot columns of matrix $A$ in the order they appear in $A$.
Each column of matrix $R$ describes the linear combination of the columns of $C$ required to produce the corresponding column of $A$. Hence for $1\le j\le n$,
$$\mathbf{a}_j = C\mathbf{r}_j$$
Exercise 4 - Compute the CR Factorization¶
Compute the rank factorization of matrix $B = \begin{bmatrix}\ \ 1\ & -4\ & -4\ &\ \ 2\ \\ \ \ 0\ &\ \ 3\ &\ \ 1\ & -2\ \\ -5\ & -2\ & -3\ & -11\ \\ -2\ &\ \ 0\ &\ \ 2\ & -2\ \end{bmatrix}$
Solution
$$ \begin{align*} B = \begin{bmatrix}\ \ {\color{darkblue}1}\ & -4\ & -4\ &\ \ 2\ \\ \ \ 0\ &\ \ 3\ &\ \ 1\ & -2\ \\ -5\ & -2\ & -3\ & -11\ \\ -2\ &\ \ 0\ &\ \ 2\ & -2\ \end{bmatrix}\begin{array}{l} \\ \\ R_3+5R_1 \\ R_4+2R_1 \end{array} &\rightarrow \begin{bmatrix}\ \ {\color{darkblue}1}\ & -4\ & -4\ &\ \ 2\ \\ \ \ 0\ &\ \ 3\ &\ \ 1\ & -2\ \\ \ \ 0\ & -22\ & -23\ & -1\ \\ \ \ 0\ & -8\ & -6\ &\ \ 2\ \end{bmatrix}\begin{array}{l} \\ \\ R_3+7R_2 \\ R_4+3R_2 \end{array} \rightarrow \begin{bmatrix}\ \ {\color{darkblue}1}\ & -4\ & -4\ &\ \ 2\ \\ \ \ 0\ &\ \ 3\ &\ \ 1\ & -2\ \\ \ \ 0\ & -1\ & -16\ & -15\ \\ \ \ 0\ &\ \ 1\ & -3\ & -4\ \end{bmatrix}\begin{array}{l} \\ R_4 \\ \\ R_2 \end{array} \\ \\ &\rightarrow \begin{bmatrix}\ \ {\color{darkblue}1}\ & -4\ & -4\ &\ \ 2\ \\ \ \ 0\ &\ \ {\color{darkblue}1}\ & -3\ & -4\ \\ \ \ 0\ & -1\ & -16\ & -15\ \\ \ \ 0\ &\ \ 3\ &\ \ 1\ & -2\ \end{bmatrix}\begin{array}{l} \\ \\ R_3+R_2 \\ R_4-3R_2 \end{array} \rightarrow \begin{bmatrix}\ \ {\color{darkblue}1}\ & -4\ & -4\ &\ \ 2\ \\ \ \ 0\ &\ \ {\color{darkblue}1}\ & -3\ & -4\ \\ \ \ 0\ &\ \ 0\ & -19\ & -19\ \\ \ \ 0\ &\ \ 0\ &\ \ 10\ &\ \ 10\ \end{bmatrix}\begin{array}{l} \\ \\ R_3/(-19) \\ R_4/10 \end{array} \\ \\ &\rightarrow \begin{bmatrix}\ \ {\color{darkblue}1}\ & -4\ & -4\ &\ \ 2\ \\ \ \ 0\ &\ \ {\color{darkblue}1}\ & -3\ & -4\ \\ \ \ 0\ &\ \ 0\ &\ \ {\color{darkblue}1}\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 1\ \end{bmatrix}\begin{array}{l} R_1+4R_3 \\ R_2+3R_3 \\ \\ R_4-R_3 \end{array} \rightarrow \begin{bmatrix}\ \ {\color{darkblue}1}\ & -4\ &\ \ 0\ &\ \ 6\ \\ \ \ 0\ &\ \ {\color{darkblue}1}\ &\ \ 0\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ {\color{darkblue}1}\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{bmatrix}\begin{array}{l} R_1+4R_2 \\ \\ \\ \\ \end{array} \\ \\ &\rightarrow \begin{bmatrix}\ \ {\color{darkblue}1}\ &\ \ 0\ &\ \ 0\ &\ \ 2\ \\ \ \ 0\ &\ \ {\color{darkblue}1}\ &\ \ 0\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ {\color{darkblue}1}\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{bmatrix} \\ \\ C &= \begin{bmatrix}\ \ 1\ & -4\ & -4\ \\ \ \ 0\ &\ \ 3\ &\ \ 1\ \\ -5\ & -2\ & -3\ \\ -2\ &\ \ 0\ &\ \ 2\ \end{bmatrix} \qquad R = \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ &\ \ 2\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 1\ \end{bmatrix} \end{align*} $$Our second method of factoring a matrix into simpler matrices is the LU Decomposition. The LU factorization is very widely used. We shall see that like CR Factorization, Gaussian elimination and LU decomposition are closely related processes.
Definition¶
LU Decomposition
The LU Decomposition of matrix $A$ factors the matrix into a product of
- a lower triangular matrix $L$ whose diagonal elements have the value one, and
- an upper triangular matrix $U$ so that
$$ A = LU $$
Video Lecture 3: Factoring a Matrix into LU.¶
Factoring a Matrix into A=LUNotice that the method that Dr.Strang and I recommend computing the $LU$ decomposition requires the use of only type III row operations.
One avoids the use of permutations (type I row operations) so that lower triangular and upper triangular factors are produced by the process of Gaussian elimination.
One avoids type II row operations to ensure that the diagonal elements of the lower triangular factor are ones.
Restricting your work to type III row operations simplifies the process in order to promote conceptual understanding over arithmetic inscrutability.
There are other methods of obtaining the LU Factorization. Computers use an algorithm called Gaussian Elimination with Partial Pivoting.
Example 5 - LU Factorization¶
Perform the $LU$ decomposition of matrix $A = \begin{bmatrix} 2 & 1 & 1 \\ 6 & 4 & 5 \\ 4 & 1 & 3 \end{bmatrix}$.
Step 1¶
We start by identifying the pivot in position $a_{11}=2$ and use a type III row operation to obtain a zero in position $a_{21}$. The main difference here is that we are performing the type III row operations with a type III elementary matrix.
$$ A = \begin{bmatrix} 2 & 1 & 1 \\ {\color{blueviolet} 6} & 4 & 5 \\ 4 & 1 & 3 \end{bmatrix}\ \begin{array}{l} \\ R_2 - 3R_1 \\ \\ \end{array} $$
We call the elementary matrix that performs this type III row operation $E_{21}$ because the purpose of the type III row operation is to obtain a zero in position $a_{21}$.
$$ \begin{align*} E_{21} &= \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ \\ -3\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ \end{bmatrix} \\ \\ E_{21}A &= \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ \\ -3\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ \end{bmatrix}\,\begin{bmatrix} 2 & 1 & 1 \\ {\color{blueviolet} 6} & 4 & 5 \\ 4 & 1 & 3 \end{bmatrix} = \begin{bmatrix} 2 & 1 & 1 \\ {\color{blueviolet} 0} & 1 & 2 \\ 4 & 1 & 3 \end{bmatrix} \end{align*} $$
Step 2¶
Use a type III row operation to obtain a zero in position $a_{31}$. The type III elementary matrix is designated $E_{31}$.
$$ \begin{align*} E_{21}A &= \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ {\color{blueviolet} 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{blueviolet} 4} & 1 & 3 \end{bmatrix} = \begin{bmatrix}\ \ 2\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ &\ \ 2\ \\ \ \ {\color{blueviolet} 0} & -1\ &\ \ 1\ \end{bmatrix} \end{align*} $$
Step 3¶
Utilize the pivot in position $a_{22}$ to get a zero in position $a_{32}$ using elementary matrix $E_{32}$
$$ \begin{align*} E_{31}E_{21}A &= \begin{bmatrix}\ \ 2\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ &\ \ 2\ \\ \ \ 0\ & {\color{blueviolet}{-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{blueviolet}{-1}}\ &\ \ 1\ \end{bmatrix} = \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & {\color{blueviolet}{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 computations,
Step 4¶
$$ \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. $$
Example 6 - Solving a Factored Linear System¶
Factoring $A = LU$ before solving the equation $A\mathbf{x} = \mathbf{b}$ provides an easier method for finding the solution. 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. 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. Solving the upper triangular system
$$ U\mathbf{x} = L^{-1}\mathbf{b} $$
requires only backward substitution.
Exercise 5 - Solve using LU Factorization¶
Solve the equation $A\mathbf{x} = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}$ using the $LU$-decomposition of matrix $A$ from example 5.
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}$.
Exercise 6 - No LU Factorization¶
Show that matrix $A = \begin{bmatrix}\ 0\ &\ 1\ \\ \ 1\ &\ 0\ \end{bmatrix}$ has no LU decomposition.
Solution
The only elementary operation that reduces $A$ to upper triangular form is a type I row operation, $E = A$.$$ EA = AA = \begin{bmatrix}\ 0\ &\ 1\ \\ \ 1\ &\ 0\ \end{bmatrix}\begin{bmatrix}\ 0\ &\ 1\ \\ \ 1\ &\ 0\ \end{bmatrix} = \begin{bmatrix}\ 1\ &\ 0\ \\ \ 0\ &\ 1\ \end{bmatrix} = U $$
Since a type I row operation is required, there is no lower triangular matrix $L$ such that $A = LU$. In fact the upper triangular form of $A$ is $I_2$.
$$ A = AI_2 $$
Notice that $A$ is not lower triangular. Notice that matrix $A$ is non-singular and row-equivalent to the identity. However it cannot be factored into lower-triangular and upper-triangular matrices.
Exercise 7 - Complete LU Factorization¶
Compute the LU factorization of $A = \begin{bmatrix}\ \ 1\ & -2\ \\ \ \ 3\ &\ \ 4\ \end{bmatrix}$. List the elementary matrices used to reduce $A$ to upper triangular form.
Solution
$$ \begin{align*} \begin{bmatrix}\ \ 1\ & -2\ \\ \ \ 3\ &\ \ 4\ \end{bmatrix}\begin{array}{l} \\ R_2{\color{red}-3}R_1 \end{array} &\rightarrow \begin{bmatrix}\ \ 1\ & -2\ \\ \ \ 0\ &\ 10\ \end{bmatrix} = U \\ \\ E_{21} &= \begin{bmatrix}\ \ 1\ &\ \ 0\ \\ {\color{red}-3}\ &\ \ 1\ \end{bmatrix} \\ \\ L &= \begin{bmatrix}\ \ 1\ &\ \ 0\ \\ \ \ {\color{darkblue}3}\ &\ \ 1\ \end{bmatrix} \\ \\ A = LU &= \begin{bmatrix}\ \ 1\ &\ \ 0\ \\ \ \ {\color{darkblue}3}\ &\ \ 1\ \end{bmatrix}\begin{bmatrix}\ \ 1\ & -2\ \\ \ \ 0\ &\ 10\ \end{bmatrix} \end{align*} $$Exercise 8 - Complete LU Factorization¶
Compute the LU factorization of $A = \begin{bmatrix}\ \ 2\ & -1\ &\ \ 2\ \\ \ \ 2\ &\ \ 1\ & -4\ \\ \ \ 2\ & -3\ & -2\ \end{bmatrix}$. List the elementary matrices used to reduce $A$ to upper triangular form.
Solution
$$ \begin{align*} \begin{bmatrix}\ \ 2\ & -1\ &\ \ 2\ \\ \ \ 2\ &\ \ 1\ & -4\ \\ \ \ 2\ & -3\ & -2\ \end{bmatrix}\begin{array}{l} \\ \\ R_2+({\color{red} -1})R_1 \\ R_3+({\color{red} -1})R_1 \end{array} &\rightarrow \begin{bmatrix}\ \ 2\ & -1\ &\ \ 2\ \\ \ \ 0\ &\ \ 2\ & -6\ \\ \ \ 0\ & -2\ & -4\ \end{bmatrix}\begin{array}{l} \\ \\ \\ R_3+({\color{red} 1})R_2 \end{array} \rightarrow \begin{bmatrix}\ \ 2\ & -1\ &\ \ 2\ \\ \ \ 0\ &\ \ 2\ & -6\ \\ \ \ 0\ &\ \ 0\ & -10\ \end{bmatrix} = U \\ \\ \\ E_{21} &= \begin{bmatrix}\ 1\ &\ \ 0\ &\ \ 0\ \\ {\color{red}-1}\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ \end{bmatrix} \\ E_{31} &= \begin{bmatrix}\ 1\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ \\ {\color{red}-1}\ &\ \ 0\ &\ \ 1\ \end{bmatrix} \\ E_{32} &= \begin{bmatrix}\ 1\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ \\ \ \ 0\ &\ \ {\color{red}1}\ &\ \ 1\ \end{bmatrix} \\ \\ L &= \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ \\ \ \ {\color{darkblue}1}\ &\ \ 1\ &\ \ 0\ \\ \ \ {\color{darkblue}1}\ & {\color{darkblue}-1}\ &\ \ 1\ \end{bmatrix} \\ \\ A = LU &= \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ \\ \ \ {\color{darkblue}1}\ &\ \ 1\ &\ \ 0\ \\ \ \ {\color{darkblue}1}\ & {\color{darkblue}-1}\ &\ \ 1\ \end{bmatrix}\begin{bmatrix}\ \ 2\ & -1\ &\ \ 2\ \\ \ \ 0\ &\ \ 2\ & -6\ \\ \ \ 0\ &\ \ 0\ & -10\ \end{bmatrix} \end{align*} $$Exercise 9 - Prove¶
Show that if $A$, $B$, and $C$ are $n\times n$ matrices, $A$ is row equivalent to $B$, and $B$ is row equivalent to $C$, then $A$ is row equivalent to $C$.
Solution
If $A$, $B$, and $C$ are $n\times n$ matrices, $A$ is row equivalent to $B$, and $B$ is row equivalent to $C$, then there is a sequence of $k>0$ elementary matrices $E_1$, $E_2$, $\dots$, $E_k$, and another $\ell$ elementary matrices $F_1$, $F_2$, $\dots$, $F_{\ell}$ so that$$ A = E_1\,E_2\dots E_k\,B, \qquad\text{and}\qquad B = F_1\,F_2\dots F_{\ell}\,C $$
Hence
$$ A = E_1\,E_2\dots E_k\,B = E_1\,E_2\dots E_k\,F_1\,F_2\dots F_{\ell}\,C $$
Therefore matrix $A$ is row equivalent to $C$.
Exercise 10 - Prove¶
Prove that the inverse of a non-singular, lower triangular matrix is lower triangular.
