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} \definecolor{indigo}{rgb}{.8, 0, .6} \def\ihat{\hat{\mmlToken{mi}[mathvariant="bold"]{ı}}} \def\jhat{\hat{\mmlToken{mi}[mathvariant="bold"]{ȷ}}} \def\khat{\hat{\mathsf{k}}} \def\tombstone{\unicode{x220E}} \def\contradiction{\unicode{x2A33}} \def\textregistered{^{\unicode{xAE}}} \def\trademark{^{\texttrademark}} $$
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.
- 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.
- 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
- upper triangular form,
- row echelon form or
- 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 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¶
Now we are ready to study the rest of Dr. Strang's video on 
Elementary Matrices. You should start at 19:04 minutes into the video.
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¶
$$ 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
Example 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:
- all of the columns of $A$ are pivot columns
- The homogeneous linear system $A\mathbf{x} = 0$ has a unique solution
- $A$ is a nonsingular matrix
- $A$ is a non-degenerate matrix
- $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
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:
- $A$ has a free column
- The homogeneous linear system $A\mathbf{x} = 0$ has a infinitely many solutions
- $A$ is a singular matrix
- $A$ is a degenerate matrix
- $A$ is not an invertible matrix
- $A$ is not row equivalent to $I$
- The reduced row echelon form of $A$ is a matrix with free columns
- $A$ cannot be factored into a product of elementary matrices
2.4.7 The CR Decomposition¶
We will spend a considerable portion of our time in this course factoring matrices into products of simpler matrices.
Definition¶
Factorization
Using algebra to decompose an algebraic expression into a product of simpler factors can reveal important properties of the original expression.
In naive algebra, one factors a polynomial into a product of linear factors. Sometimes a linear factor can have a multiplicity great that one.
Example 4¶
(a) Since the linear factor $x-1$ are both factors of $x^2 - 2x + 1$. The linear factor $x-1$ has multiplicity 2.
$$ x^2 - 2x + 1 = (x-1)^2 $$
(b) The linear factor $x+2$ are all three factors of $x^3 + 6x^2 + 12x + 8$. The linear factor $x+2$ has multiplicity 3.
$$ x^3 + 6x^2 + 12x + 8 = (x+2)^3 $$
(c) The linear factor $x+1$ is a factor of multiplicity two for $x^3 $.
$$ 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 shed light on the more complex product matrix.
Definition¶
Rank Factorization
Rank Factorization of a matrix $A$ factors the matrix into two matrices $C$ and $R$.
- Matrix $C$ is made of the pivot columns of matrix $A$ in the order they appear in $A$, and
- Matrix $R$ satisfies $A=CR$.
Rank Factorization
Exercise 1¶
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*} $$
2.4.8 The LU Decomposition¶
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 Gauss-Jordan 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 $$
Factoring a Matrix into A=LU
We will accomplish this task using only type III elementary row operations¶
Notice that the method that Dr.Strang and I recommend computing the $LU$ decomposition requires the use of only type III elementary 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.
One avoids type II row operations to ensure that the diagonal elements of the lower triangular factor are ones.
Example 5¶
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 an type III elementary matrix.
$$ 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} $$
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*} \mathbf{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{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*} $$
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{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*} $$
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{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 computations,
Step 5¶
$$ \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.
Exercise 2¶
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.9 Properties of LU Factorization¶
The LU factorization utilizes only type III elementary row operations to ensure that the factorization satisfies the definition. $L$ must be a lower triangular matrix with only ones in its diagonal. The construction of the LU factorization reveals that it has seven important properties
Properties of LU Factorization¶
- A row operation may be performed on a matrix by multiplying it by an elementary matrix.
- An elementary matrix is invertible and its inverse is an elementary matrix.
- A matrix is nonsingular if and only if it is a product (composition) of elementary matrices.
- An $n\times n$ matrix $A$ has an LU factorization if and only if it can be reduced to upper triangular form with no type I row operations.
- If $A=LU$, then $L$ is nonsingular.
- Any matrix, it's upper triangular form, row echelon form, and reduced row echelon form are row equivalent.
- Any two matrices with the same reduced row echelon form are row equivalent.
Proof of Property 3¶
$\Rightarrow$ Suppose that matrix $A$ is nonsingular. This means that $A$ is square and all of its columns are pivot columns. Thus the reduced row echelon form of matrix $A$ has $n$ pivots with pivot values of 1. The reduced row echelon form of matrix $A$ must be the $n\times n$ identity $I_n$. This means that there is a finite sequence of type I, type II, and type III row operations that reduces matrix $A$ to $I_n$. Let $k>0$ be the number of row operations required to reduce $A$ to $I_n$. Each row operation can be applied to matrix $A$ by multiplying $A$ by an elementary matrix. Hence
$$ E_1\,E_2\cdots E_k\,A = I_n $$
Here each $E_j$ is the elementary matrix that applies the $j^{\text{th}}$ row operation to matrix $A$. Since elementary matrices are nonsingular, and their inverses are elmentary matrices,
$$ A = E_k^{-1}\cdots E_2^{-1}\,E_1^{-1}\,I_n = E_k^{-1}\cdots E_2^{-1}\,E_1^{-1} $$
Therefore $A$ is a product of elementary matrices.
$\Leftarrow$ Suppose that $n\times n$ matrix $A = E_1\,E_2\cdots E_k$ is a product of elementary matrices. As elementary matrices are invertible, define
$$ B = E_k^{-1}\cdots E_2^{-1}\,E_1^{-1} $$
Matrix $B$ has the property that
$$ \begin{align*} AB &= \left( E_1\,E_2\cdots E_k \right)\,\left( E_k^{-1}\cdots E_2^{-1}\,E_1^{-1} \right) \\ \\ &= E_1\,E_2\cdots \left( E_k\,E_k^{-1}\right)\cdots E_2^{-1}\,E_1^{-1} \\ \\ &= E_1\,E_2\cdots \left( I_n \right)\cdots E_2^{-1}\,E_1^{-1} \\ \\ &= E_1\,E_2\cdots \left( E_{k-1}\,E_{k-1}^{-1} \right) \cdots E_2^{-1}\,E_1^{-1} \\ \\ &\ddots \\ \\ &= E_1\left( E_2\,E_2^{-1} \right) E_1^{-1} \\ \\ &= E_1\,E_1^{-1} = I_n \end{align*} $$
Hence $B = A^{-1}$, and since $A$ is invertible, it is nonsingular. $\tombstone$
Exercise 3¶
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} = I_2 $$
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 = EI_2 = AI_2 $$
Notice that $E=A$ is not lower triangular.
2.4.10 Gaussian Elimination with Partial Pivoting¶
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 computationally stable we will utilize type I 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. Permutation matrices have some important properties.
Undoing exchanging row $i$ and $j$ is accomplished by exchanging them again. Hence $P^2 = P\,P = I$. Thus elementary permutation matrices are involutions. The elementary matrix that represents exchanging row $i$ and row $j$ is an identity matrix with the rows exchanged. For example,
$$ P = \begin{bmatrix}\ 1\ &\ 0\ &\ 0\ &\ 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 1\ \\ \ 0\ &\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ &\ 0\ \end{bmatrix} \qquad I = \begin{bmatrix}\ 1\ &\ 0\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ &\ 0\ \\ \ 0\ &\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 1\ \end{bmatrix} $$
Notice that exchanging rows 2 and 4 are equal exchanging columns 2 and 4. Likewise an elementary permutation matrix that exchanges row $i$ and row $j$, also exchanges column $i$ and column $j$. Hence every elementary permutation matrix is symmetric.
Elementary Permutation Matrices¶
Elementary permutation matrices are symmetric involutions. Hence
$$ P^{-1} = P = P^T $$
A composition of type I row operations, or a product of elementary permutation matrices is still a permutation matrix since it simply re-orders the rows of the matrix. However such a composition is not elementary.
Permutation Matrix¶
A permutation matrix is a product of a finite number (k>0) of elementary permutation matrices.
$$ P = P_1\cdots P_k $$
The transpose of a permutation matrix is its inverse.
$$ P^{-1} = P^T $$
Proof that $P^T = P^{-1}$¶
This is a consequence of computing the transpose of a matrix product.
$$ \begin{align*} P\,P^T &= \left( P_1\cdots P_k \right)\left( P_1\cdots P_k \right)^T \\ \\ &= \left( P_1\cdots P_k \right)\left(P_k^T\cdots P_1^T\right) \\ \\ &= P_1\cdots\left( P_kP_k^T \right)\cdots P_1^T \\ \\ &= P_1\cdots\left( I \right)\cdots P_1^T \\ &\ddots \\ &= P_1\,P_1^T = I \end{align*} $$
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}. $$
Example 6¶
Solve $A\mathbf{x}=\mathbf{b}$, where $A = \begin{bmatrix}\ \ 1\ &\ \ 3\ & \ \ 4\ &\ \ 3\ \\ \ \ 2\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \\ -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \end{bmatrix}$, and $\mathbf{b} = \begin{bmatrix}\ \ 0\ \\ \ \ 8\ \\ -16\ \\ \ \ 8\ \end{bmatrix}$.
The element of the first column of matrix $A$ is the third column. Our first step is to use a type I row operation, or permutation matrix
$$ \begin{align*} PA = \begin{bmatrix}\ 0\ &\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ &\ 0\ \\ \ 1\ &\ 0\ &\ 0\ &\ 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 1\ \end{bmatrix}\begin{bmatrix}\ \ 1\ &\ \ 3\ & \ \ 4\ &\ \ 3\ \\ \ \ 2\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \\ -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \end{bmatrix} = \begin{bmatrix} -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 2\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \\\ \ 1\ &\ \ 3\ & \ \ 4\ &\ \ 3\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \end{bmatrix} \end{align*} $$
Now perform row operations on $PA$.
$$ \begin{align*} \begin{bmatrix} -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 2\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \\ \ \ 1\ &\ \ 3\ & \ \ 4\ &\ \ 3\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \end{bmatrix}\begin{array}{l} \\ R_2+\frac{2}{3}R_1 \\ R_3+\frac{1}{3}R_1 \\ \\ \end{array} &\rightarrow \begin{bmatrix} -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 0\ &\ \ 2\ &\ \ 2\ &\ \ \frac{7}{3}\ \\ \ \ 0\ &\ \ 2\ & \ \ 2\ &\ \ \frac{11}{3}\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \end{bmatrix} \end{align*} $$
The largest element of column two in rows two-thru-four is row 4. So permute rows 2 and 4. This also permutes the row operations above!
$$ \begin{align*} P = \begin{bmatrix}\ 1\ &\ 0\ &\ 0\ &\ 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 1\ \\ \ 0\ &\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ &\ 0\ \end{bmatrix}\begin{bmatrix}\ 0\ &\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ &\ 0\ \\ \ 1\ &\ 0\ &\ 0\ &\ 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 1\ \end{bmatrix} &= \begin{bmatrix}\ 0\ &\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 1\ \\ \ 1\ &\ 0\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ &\ 0\ \end{bmatrix} \\ \\ \begin{bmatrix} -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \\ \ \ 0\ &\ \ 2\ & \ \ 2\ &\ \ \frac{11}{3}\ \\ \ \ 0\ &\ \ 2\ &\ \ 2\ &\ \ \frac{7}{3}\ \end{bmatrix}\begin{array}{l} \\ \\ R_3-\frac{1}{2}R_2 \\ R_4-\frac{1}{2}R_2 \\ \end{array} &\rightarrow \begin{bmatrix} -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \\ \ \ 0\ &\ \ 0\ & \ \ 0\ &\ \ \frac{14}{3}\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ \frac{10}{3}\ \end{bmatrix} = U \\ \\ L &= \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 0\ \\ -\frac{1}{3}\ &\ \ \frac{1}{2}\ &\ \ 1\ &\ \ 0\ \\ -\frac{2}{3}\ \ &\ \ \frac{1}{2}\ &\ \ 0\ &\ \ 1\ \end{bmatrix} \end{align*} $$
Check
$$ \begin{align*} PA = \begin{bmatrix}\ 0\ &\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 1\ \\ \ 1\ &\ 0\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ &\ 0\ \end{bmatrix}\begin{bmatrix}\ \ 1\ &\ \ 3\ & \ \ 4\ &\ \ 3\ \\ \ \ 2\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \\ -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \end{bmatrix} &= \begin{bmatrix} -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \\ \ \ 1\ &\ \ 3\ & \ \ 4\ &\ \ 3\ \\ \ \ 2\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \end{bmatrix} \\ \\ LU = \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 0\ \\ -\frac{1}{3}\ &\ \ \frac{1}{2}\ &\ \ 1\ &\ \ 0\ \\ -\frac{2}{3}\ \ &\ \ \frac{1}{2}\ &\ \ 0\ &\ \ 1\ \end{bmatrix}\begin{bmatrix} -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \\ \ \ 0\ &\ \ 0\ & \ \ 0\ &\ \ \frac{14}{3}\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ \frac{10}{3}\ \end{bmatrix} &= \begin{bmatrix} -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \\ \ \ 1\ &\ \ 3\ & \ \ 4\ &\ \ 3\ \\ \ \ 2\ &\ \ 4\ &\ \ 6\ &\ \ 1\ \end{bmatrix}\ {\color{green}\Large{\checkmark}} \end{align*} $$
Next we perform some computations
$$ \begin{align*} A\mathbf{x} &= \mathbf{b} \\ \\ PLU\mathbf{x} &= \mathbf{b} \\ \\ U\mathbf{x} &= L^{-1}P^T\mathbf{b} \\ \\ \begin{bmatrix} -3\ & -3\ & -6\ &\ \ 2\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2\ \\ \ \ 0\ &\ \ 0\ & \ \ 0\ &\ \ \frac{14}{3}\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ \frac{10}{3}\ \end{bmatrix}\mathbf{x} &= \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 0\ \\ -\frac{1}{3}\ &\ \ \frac{1}{2}\ &\ \ 1\ &\ \ 0\ \\ -\frac{2}{3}\ \ &\ \ \frac{1}{2}\ &\ \ 0\ &\ \ 1\ \end{bmatrix}^{-1}\begin{bmatrix}\ 0\ &\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 1\ \\ \ 1\ &\ 0\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ &\ 0\ \end{bmatrix}^T\begin{bmatrix}\ \ 0\ \\ \ \ 8\ \\ -16\ \\ \ \ 8\ \end{bmatrix} \\ \\ &= \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 0\ \\ \ \ \frac{1}{3}\ & -\frac{1}{2}\ &\ \ 1\ &\ \ 0\ \\ \ \ \frac{2}{3}\ \ & -\frac{1}{2}\ &\ \ 0\ &\ \ 1\ \end{bmatrix}\begin{bmatrix}\ 0\ &\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 1\ \\ \ 1\ &\ 0\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ &\ 0\ \end{bmatrix}\begin{bmatrix}\ \ 0\ \\ \ \ 8\ \\ -16\ \\ \ \ 8\ \end{bmatrix} \\ \\ &= \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 0\ \\ \ \ \frac{1}{3}\ & -\frac{1}{2}\ &\ \ 1\ &\ \ 0\ \\ \ \ \frac{2}{3}\ \ & -\frac{1}{2}\ &\ \ 0\ &\ \ 1\ \end{bmatrix}\begin{bmatrix} -16\ \\ \ \ 8\ \\ \ \ 0\ \\ \ \ 8\ \end{bmatrix} = \begin{bmatrix} -16\ \\ \ \ 8\ \\ -\frac{28}{3}\ \\ -\frac{20}{3}\ \end{bmatrix} \\ \\ \begin{bmatrix} -3\ & -3\ & -6\ &\ \ 2 & | & -16\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2 & | & 8\ \\ \ \ 0\ &\ \ 0\ & \ \ 0\ &\ \ \frac{14}{3} & | & -\frac{28}{3}\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ \frac{10}{3} & | & -\frac{20}{3}\ \end{bmatrix}\begin{array}{l} \\ \\ 3R_3/14 \\ 3R_4/10 \end{array} &\rightarrow \begin{bmatrix} -3\ & -3\ & -6\ &\ \ 2 & | & -16\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -2 & | & 8\ \\ \ \ 0\ &\ \ 0\ & \ \ 0\ &\ \ 1 & | & -2\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 1 & | & -2\ \end{bmatrix}\begin{array}{l} R_1-2R_3 \\ R_2+2R_3 \\ \\ R_4-R_3 \end{array} \\ \\ \rightarrow \begin{bmatrix} -3\ & -3\ & -6\ &\ \ 0 & | & -12\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ &\ \ 0 & | &\ \ 4\ \\ \ \ 0\ &\ \ 0\ & \ \ 0\ &\ \ 1 & | & -2\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0 & | &\ \ 0\ \end{bmatrix}\begin{array}{l} -R_1/3 \\ R_2/4 \\ \\ \\ \end{array} &\rightarrow \begin{bmatrix}\ \ 1\ &\ \ 1\ &\ \ 2\ &\ \ 0 & | &\ \ 4\ \\ \ \ 0\ &\ \ 1\ &\ \ 1\ &\ \ 0 & | &\ \ 1\ \\ \ \ 0\ &\ \ 0\ & \ \ 0\ &\ \ 1 & | & -2\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0 & | &\ \ 0\ \end{bmatrix}\begin{array}{l} R_1-R_2 \\ \\ \\ \\ \end{array} \\ \\ \rightarrow \begin{bmatrix}\ \ 1\ &\ \ 0\ &\ \ 1\ &\ \ 0 & | &\ \ 3\ \\ \ \ 0\ &\ \ 1\ &\ \ 1\ &\ \ 0 & | &\ \ 1\ \\ \ \ 0\ &\ \ 0\ & \ \ 0\ &\ \ 1 & | & -2\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0 & | &\ \ 0\ \end{bmatrix} \\ \\ x_4 &= -2 \\ x_3 &= s\in\mathbb{R} \\ x_2 + s &= 1 \\ x_2 &= 1 - s \\ x_1 + s &= 3 \\ x_1 &= 3 - s \\ \\ \mathbf{x} = \begin{bmatrix} 3-s \\ 1-s \\ s \\ -2 \end{bmatrix} &= s\begin{bmatrix} -1\ \\ -1\ \\ \ \ 1\ \\ \ \ 0\ \end{bmatrix} + \begin{bmatrix}\ 3\ \\ \ 1\ \\ \ 0\ \\ -2\ \end{bmatrix} \end{align*} $$
2.4.11 Exercises¶
Exercise 4¶
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 5¶
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} \\ \\ 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} \\ \\ \\ 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 6¶
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$.
