Applied Linear Algebra - Packet 09

Packet 09

Matrices I: Reduction and Decomposition

A very important general method for understanding what matrices do when they act upon vectors is to transform them into matrices or products of matrices with standardized form. Each standardized form is designed to make certain aspects of matrix behavior very easy to see, or to make certain calculations that apply the matrix very easy to perform. Typically a matrix is converted to a standardized form using an algorithmic procedure that is run without intuitive or subjective assessment along the way, and the final result is studied afterwards.

In this packet we study a standardized form called ‘LU factorization’ that is produced using the technique of elimination. Given the LU factorization (or a refinement of part of it called row-echelon form or reduced row-echelon form), one can read off qualitative aspects of the matrix such as its rank, which is the dimension of its image subspace, as well as provide a basis for the image and a basis for the kernel, which is the subspace that is reduced to zero by the matrix action.

In addition to this qualitative information about the action of a matrix on some vectors, the LU factorization can be followed by another important technique called back-substitution. The combined process is typically used for inverting matrix equations such as these:

$$A𝐱=𝐛,AX=B.$$

The vector inverse of $𝐛$ under the action of $A$ is the vector $𝐱$ which $A$ sends to $𝐛$. The matrix inverse of $B$ under the action of $A$ is the matrix $X=A^{-1}B$ which is sent to $B$ by the action of $A$ multiplying it on the left. (In the second case, if $B=I_n$ is the identity, then we are just computing $X=A^{-1}$.) We will see below how the $LU$ factorization process followed by back-substitution allows us to find $𝐱$ or $X$.

LU factorization

An LU factorization of a matrix $A$ is simply a lower triangular matrix $L$ and an upper triangular matrix $U$ such that $A=LU$.

For example 1.

$$A=\left(\begin{array}{ccc}1& 2& 3\\ 2& 5& 10\\ 3& 2& -6\end{array}\right)=\left(\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 3& -4& 1\end{array}\right)\left(\begin{array}{ccc}1& 2& 3\\ 0& 1& 4\\ 0& 0& 1\end{array}\right)=LU$$

or 2.

$$A=\left(\begin{array}{ccccc}2& 4& -1& 5& -2\\ -4& -5& 3& -8& 1\\ 2& -5& -4& 1& 8\\ -6& 0& 7& -3& 1\end{array}\right)=\left(\begin{array}{cccc}1& 0& 0& 0\\ -2& 1& 0& 0\\ 1& -3& 1& 0\\ -3& 4& 2& 1\end{array}\right)\left(\begin{array}{ccccc}2& 4& -1& 5& -2\\ 0& 3& 1& 2& -3\\ 0& 0& 0& 2& 1\\ 0& 0& 0& 0& 5\end{array}\right)=LU.$$

Observe:

• In 1., both $L$ and $U$ have ones on the diagonal, and all matrices are square.
• In 2., $A$ and $U$ are not square, $L$ has ones on the diagonal, while $U$ has other values: $\mathrm{2,3,0,0}$.

We require the $L$ matrix to have ones on the diagonal, while the $U$ matrix may have other diagonal values.

A more general rule for $U$ called “row-echelon form” will be explained below; it is applicable when zeros on the diagonal crop up in the process; in essence it means the entries should be mashed “high and to the right.”

Keys to LU factorization

The principle of elimination is to use row-add matrices acting on the left in order to eliminate nonzero entries of $A$ that are below the main diagonal entries, clearing a column. These row-add matrices are then collected into a single lower-triangular matrix that combines the actions of all of them.

Creating columns: Observe first that we can combine row-add matrices which add from the same row into a single matrix having a single column of nonzero subdiagonal entries, for example:

$$\left(\begin{array}{cccc}1& 0& 0& 0\\ 2& 1& 0& 0\\ 3& 0& 1& 0\\ 4& 0& 0& 1\end{array}\right)=\left(\begin{array}{cccc}1& 0& 0& 0\\ 2& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 3& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 4& 0& 0& 1\end{array}\right).$$

The order in the product on the RHS does not matter!

Question 09-01

Order doesn’t matter when multiplying row-add matrices of the same column

Explain why (or prove algebraically that) order does not matter when multiplying row-add matrices with their nonzero subdiagonal entries lying in the same column. Explain this in general, not just for the $4\times 4$ matrix above.

Combining columns: Furthermore, we can break up any lower-triangular matrix $L$ into a product of single-column matrices like the one above:

$$L=\left(\begin{array}{cccc}1& 0& 0& 0\\ 2& 1& 0& 0\\ 3& 5& 1& 0\\ 4& 6& 7& 1\end{array}\right)=\left(\begin{array}{cccc}1& 0& 0& 0\\ 2& 1& 0& 0\\ 3& 0& 1& 0\\ 4& 0& 0& 1\end{array}\right)\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 5& 1& 0\\ 0& 6& 0& 1\end{array}\right)\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 7& 1\end{array}\right)=L_1\cdot L_2\cdot L_3.$$

Combining columns – order matters

The three factors in the RHS product cannot be reordered without changing the result!

By combining the above two factorizations, we can write any lower-triangular matrix $L$ (with ones on the diagonal) as a product of row-add matrices, and these row-add matrices can be grouped into single-column row-add combo matrices. If $L$ is lower-triangular with $n$ rows, and we write $L_i$ for the single-column combo with nonzeros in the $i^{\text{th}}$ column, then we have $L=L_1\cdot L_2\cdot \cdots \cdot L_{n-1}$. When you see $L_i$ you should think “single-column, row-add combo” and remember that the column of nonzeros lies below the main diagonal of ones.

Inverse of $L_i$: The last critical fact is that the inverse of any single-column row-add combo is the same matrix but with opposite signs on the subdiagonal entries:

$$\left(\begin{array}{cccc}1& 0& 0& 0\\ 2& 1& 0& 0\\ 3& 0& 1& 0\\ 4& 0& 0& 1\end{array}\right)\left(\begin{array}{cccc}1& 0& 0& 0\\ -2& 1& 0& 0\\ -3& 0& 1& 0\\ -4& 0& 0& 1\end{array}\right)=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right).$$

Computing LU factorizations

Here is the plan:

1. Postulate hypothetically that $A=LU=(L_1\cdots L_{n-1})U$, where $L_i$ are single-column row-add combos which combine to form the hypothetical $L$. We know $A$ and we seek $L$ and $U$.
2. Act upon $A$ and $LU$ on the left simultaneously by $L_1^{-1}$, then by $L_2^{-1}$, etc., through $L_{n-1}^{-1}$. We must invent $L_1^{-1}$, $L_2^{-1}$ etc. as we go along:
   1. Choose $L_1^{-1}$ such that $L_1^{-1}A$ has all zeros in the first column on the subdiagonal: In each nonzero subdiagonal entry of $L_1^{-1}$, put $\lambda$ such that row-add of the top entry into entry $2$ eliminates entry $2$, and so on to create the entire first column of $L_1^{-1}$ which acts to clear the first column of $A$.
   2. Continue with $L_2^{-1}$ chosen such that $L_2^{-1}(L_1^{-1}A)$ now has zeros in the first and second columns, and $L_2^{-1}$ has subdiagonal entries $\lambda$ in the second column.
   3. Continue through $L_{n-1}^{-1}$ and obtain $(L_1^{-1}\cdots L_{n-1}^{-1})A=U$. By flipping signs on $L_i$ for $i=1,\dots ,n-1$, we now know $L_i$ and simply combine the subdiagonal columns of all $L_i$ to create the whole $L$.
   4. Notice! The matrix $L_i$ is exactly the unique single-column row-add combo matrix which has $i^{\text{th}}$ column cleared by whatever clears the $i^{\text{th}}$ column of $A$. In other words, we cook up $L_i$ so that the same elimination works both on $A$ and on $L_i$, the difference being that $L_i$ has a $1$ at the top entry by definition, while the corresponding entry of $A$ may have other values.

In other words, we find the matrices $L_1,\dots ,L_{n-1}$ by backwards reasoning: row-add eliminations performed on $A$ should simultaneously effect eliminations on $L_1,\dots ,L_{n-1}$, converting them each to the identity matrix $I_n$. If this works, we know we have the $L_i$ ingredients inside the factorization $A=LU=(L_1\cdots L_{n-1})U$.

Example

Basic LU factorization

Problem: Show how to obtain the LU factorization:

$$A=\left(\begin{array}{cccc}2& -3& 5& -8\\ 4& -5& 11& -16\\ 6& -4& 17& -26\\ 8& -6& 5& -45\end{array}\right)=\left(\begin{array}{cccc}1& 0& 0& 0\\ 2& 1& 0& 0\\ 3& 5& 1& 0\\ 4& 6& 7& 1\end{array}\right)\left(\begin{array}{cccc}2& -3& 5& -8\\ 0& 1& 1& 0\\ 0& 0& -3& -2\\ 0& 0& 0& 1\end{array}\right)=LU$$

Solution: Full steps for the product multiplication showing $A=LU$ as above can be found here. Full steps for the reverse, factoring $A$ into $LU$, can be found here. (Click “Details” to show the steps.) We explain the latter details below. You are encouraged to use MatrixCalc.org to help you master the process, but remember that on the exams you must be able to run the process by hand.

Since $A$ is a $4\times 4$ matrix, we are looking for $L_1,L_2,L_3$ such that $A=(L_1{L}_2{L}_3)U$ and each $L_i$ is a single-column row-add combo matrix. Since the factorization is given to us, we know the answers should be:

$$L_1=\left(\begin{array}{cccc}1& 0& 0& 0\\ 2& 1& 0& 0\\ 3& 0& 1& 0\\ 4& 0& 0& 1\end{array}\right),L_2=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 5& 1& 0\\ 0& 6& 0& 1\end{array}\right),L_3=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 7& 1\end{array}\right).$$

Obtain these as follows. To eliminate the subdiagonal entries in the first column of $A$, we must add $-2$ times row $1$ into row $2$, then $-3$ times row $1$ into row $3$, and then $-4$ times row $1$ into row $4$.

To cook up $L_1$, we first place ones on the diagonal, zeros elsewhere (namely $I_4$). Then we arrange the first column so that it’s cleared by the same sequence of steps, except now we have $1$ in the first row whereas $A$ had $2$. Thus: $-2$ times $1$ added to $2$ gives $0$, then $-3$ times $1$ added to $3$ gives $0$, and $-4$ times $1$ added to $4$ gives $0$. The sequence $(\mathrm{1,2,3,4})$ is therefore appropriate for the first column in $L_2$, since it will be cleared by whatever row-adds clear the first column of $A$.

We have thus found $L_1$ as the matrix which is sent to $I_4$ by the action of the elimination process just described. This elimination process is represented by the action of the single-column row-add combo matrix:

$$L_1^{-1}=\left(\begin{array}{cccc}1& 0& 0& 0\\ -2& 1& 0& 0\\ -3& 0& 1& 0\\ -4& 0& 0& 1\end{array}\right)$$

and therefore $L_1^{-1}$ just given is the inverse of $L_1$ that we sought: since $L_1^{-1}{L}_1=I_4$.

After applying the process to $A$ and finding $L_1$, we proceed to find $L_2$, creating its column $1,-5,-6$ in order to clear the $\mathrm{5,6}$ from the second column of $L_1^{-1}A$:

$$L_1^{-1}A=\left(\begin{array}{cccc}1& 0& 0& 0\\ -2& 1& 0& 0\\ -3& 0& 1& 0\\ -4& 0& 0& 1\end{array}\right)\left(\begin{array}{cccc}2& -3& 5& -8\\ 4& -5& 11& -16\\ 6& -4& 17& -26\\ 8& -6& 5& -45\end{array}\right)=\left(\begin{array}{cccc}2& -3& 5& -8\\ 0& 1& 1& 0\\ 0& 5& 2& -2\\ 0& 6& -15& -13\end{array}\right)$$ $$L_2^{-1}(L_1^{-1}A)=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& -5& 1& 0\\ 0& -6& 0& 1\end{array}\right)\left(\begin{array}{cccc}2& -3& 5& -8\\ 0& 1& 1& 0\\ 0& 5& 2& -2\\ 0& 6& -15& -13\end{array}\right)=\left(\begin{array}{cccc}2& -3& 5& -8\\ 0& 1& 1& 0\\ 0& 0& -3& -2\\ 0& 0& -21& -13\end{array}\right).$$

Therefore

$$L_2=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 5& 1& 0\\ 0& 6& 0& 1\end{array}\right)={\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& -5& 1& 0\\ 0& -6& 0& 1\end{array}\right)}^{-1}$$

is the right choice for $L_2$, and we are almost finished. Observe that $-21=-3\cdot 7$. Thus:

$$L_3^{-1}(L_2^{-1}{L}_1^{-1}A)=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& -7& 1\end{array}\right)\left(\begin{array}{cccc}2& -3& 5& -8\\ 0& 1& 1& 0\\ 0& 0& -3& -2\\ 0& 0& -21& -13\end{array}\right)=\left(\begin{array}{cccc}2& -3& 5& -8\\ 0& 1& 1& 0\\ 0& 0& -3& -2\\ 0& 0& 0& 1\end{array}\right)$$

and so

$$L_3=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 7& 1\end{array}\right)={\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& -7& 1\end{array}\right)}^{-1}.$$

Question 09-02

Compute LU factorization

Find the LU factorization of the matrix $A=\left(\begin{array}{ccc}7& 1& 1\\ -28& 0& 5\\ 14& 14& 31\end{array}\right)$.

Exercise 09-01

Computing LU factorization

Find the LU factorization of $A=\left(\begin{array}{cc}0& 1\\ 0& 1\end{array}\right)$.

Exercise 09-02

Computing LU factorization

Find the LU factorization of $B=\left(\begin{array}{ccc}1& 0& 3\\ 0& 2& -8\\ 2& 14& -50\end{array}\right)$.

Exercise 09-03

Computing LU factorization

Find the LU factorization of $C=\left(\begin{array}{cccc}0& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 1& 0& 1\end{array}\right)$.

Pivoting

The algorithm presented above for LU factorization can fail down because of zeros. For example, consider $A$:

$$A=\left(\begin{array}{cccc}0& 1& 1& 0\\ 2& -3& 5& -8\\ 6& -4& 17& -26\\ 8& -6& 5& -45\end{array}\right).$$

We cannot even begin to eliminate $\mathrm{2,6,8}$ using row-add steps. In this situation, it is best to pivot to a different top row by using a row-swap permutation. The new top row is sometimes called the pivot row, and the new entry used to eliminate others by row-adding may be called the pivot entry or simply the pivot.

Write $P$ for the row-swap matrix that swaps rows $1$ and $2$. After pivoting, we have a new matrix:

$$PA=\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\left(\begin{array}{cccc}0& 1& 1& 0\\ 2& -3& 5& -8\\ 6& -4& 17& -26\\ 8& -6& 5& -45\end{array}\right)=\left(\begin{array}{cccc}2& -3& 5& -8\\ 0& 1& 1& 0\\ 6& -4& 17& -26\\ 8& -6& 5& -45\end{array}\right).$$

The new matrix has an LU factorization now:

$$\left(\begin{array}{cccc}2& -3& 5& -8\\ 0& 1& 1& 0\\ 6& -4& 17& -26\\ 8& -6& 5& -45\end{array}\right)=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 3& 5& 1& 0\\ 4& 6& 7& 1\end{array}\right)\left(\begin{array}{cccc}2& -3& 5& -8\\ 0& 1& 1& 0\\ 0& 0& -3& -2\\ 0& 0& 0& 1\end{array}\right).$$

It is appropriate to say that “$A$ has an LU factorization with pivots”, or to say that “we have a factorization $PA=LU$.” We do not say simply that “$A$ has an LU factorization” if pivots are required.

Every matrix $A$ has a factorization of the form $PA=LU$.

Numerical methods

For numerical stability, it is preferable to always pivot to the largest entry in a given column before performing elimination. This technique is called “partial pivoting.”

(“Complete pivoting” refers to a technique where elimination is performed to clear any uncleared column by choosing the largest remaining entry across the matrix. It is computationally expensive and therefore rarely used.)

The general procedure for computing $PA=LU$ factorizations is fairly complex because the natural algorithm interlaces elimination (using factors $L_i^{-1}$) with permutations for the pivots (using row-swap matrices $P_i$). You are not required to master this procedure for exams.

The general process of computing $U$ by successive elimination of terms with pivots, clearing out one column at a time, is called row reduction (see below). You are required to master row-reduction for exams.

The difference between row-reduction and the procedure for $PA=LU$ is that in the latter we do not keep track of $L_i$ and $P_i$ and do not calculate $L$ and $P$, we simply perform the row-add operations on $A$ until the $L$ factor inside $A$ is gone (by clearing columns) and the result is $U$.

Here is the theory for producing $PA=LU$ in general:

Factorization $PA=LU$

For $i=1,\dots ,n$, work through row $i$ of $A$:

1. Choose a row of $A$ to pivot into the first row, defining the corresponding row-swap matrix $P_1$. After swapping we have $P_{1}A$. (For numerical stability, choose the row of $A$ with largest entry in the first column; but in principle, can choose any row with nonzero entry in the first column.)
2. Construct $L_1^{-1}$ to eliminate entries in row $2$ and below, clearing column $1$ of $P_{1}A$. Obtain $L_1^{-1}{P}_{1}A$.
3. Proceed to row $2$: choose a pivot row and define row-swap $P_2$ and obtain $P_2{L}_1^{-1}{P}_{1}A$.
4. Construct $L_2^{-1}$ to clear column $2$ of $P_2{L}_1^{-1}{P}_{1}A$.
5. Repeat with $P_i$ a row-swap putting a chosen pivot from below row $i$ into row $i$.
6. Repeat with $L_i^{-1}$ clearing the $i^{\text{th}}$ column below the $i^{\text{th}}$ row.
7. End when $i=n$.

In this way we build a sequence:

$$L_{n-1}^{-1}{P}_{n-1}{L}_{n-2}^{-1}\dots P_2{L}_1^{-1}{P}_{1}A=U.$$

If we didn’t have all the $P_i$ matrices interlaced between the $L_i$’s, this would be $L_{n-1}^{-1}\dots L_1^{-1}A=U$, and therefore $A=L_1\dots L_{n}U$ as in the ordinary LU factorization. So what we want to do here is to extract the $P_i$’s out to the right and group them into $P$. This is the hardest part!

There is a trick we can use to make this happen. It turns out that $P_j{L}_i^{-1}{P}_j^{-1}$ (for $i<j$) is the same as $L_i^{-1}$, except that the nonzero stack of entries undergoes the row-swap of $P_j$. Using this fact, together with the fact that $P_j^{-1}=P_j$ because $P_j$ swaps two rows, we can rewrite our sequence in terms of other single-column matrices called $L_i^{\prime }$. For example, in the case $n=4$, we could write:

$$L_3^{\prime -1}=L_3,L_2^{\prime -1}=P_3{L}_2^{-1}{P}_3,L_1^{\prime -1}=P_3{P}_2{L}_1^{-1}{P}_2{P}_3.$$

From these definitions, it follows that

$$\left(L_3^{\prime -1}{L}_2^{\prime -1}{L}_1^{\prime -1}\right)\left(P_3{P}_2{P}_1\right)A=L_3^{-1}{P}_3{L}_2^{-1}{P}_2{L}_1^{-1}{P}_{1}A=U$$

and thus

$$\begin{array}{cc}\left(P_3{P}_2{P}_1\right)A& =\left(L_1^{\prime }{L}_2^{\prime }{L}_3^{\prime }\right)U\\ PA& =LU,\end{array}$$

where we define $P=P_3{P}_2{P}_1$ and $L=L_1^{\prime }{L}_2^{\prime }{L}_3^{\prime }$.

Here is a concise computational algorithm to perform these steps on a computer:

Algorithm on entries for $PA=LU$ factorization

Initialize: $P=L=I_n,U=A$. For $j=1$ to $n-1$ :

• Choose $i\ge j$ with maximum (or simply nonzero) $|u_{ij}|$. – That is: $i$ is the new pivot row index.
• Exchange $u_{j,j:n}\leftrightarrow u_{i,j:n}$. – That is: swap current row $j$ with new pivot row $i$ on future columns of $U$.
• Exchange $p_{j,:}\leftrightarrow p_{i,:}$. – That is: swap current row $j$ with new pivot row $i$ on all of $P$ to create $P_j{P}_{j-1}\cdots P_1$.
• Exchange ${\ell }_{j,1:j-1}\leftrightarrow {\ell }_{i,1:j-1}$. – That is: swap current row $j$ with new pivot row $i$ on the subdiagonal entries of $L$ to create $P_j{L}_1^{\prime }\cdots L_{j-1}^{\prime }{P}_j$.
• For $k=j+1$ to $n$ :
  • Set ${\ell }_{kj}=u_{kj}/u_{jj}$ – That is: write next subdiagonal stack of $L$: add terms to $P_j{L}_1^{\prime }\cdots L_{j-1}^{\prime }{P}_j$ to create $L_1^{\prime }\cdots L_j^{\prime }$.
  • Set $u_{k,j:n}=u_{k,j:n}-{\ell }_{kj}{u}_{j,j:n}$ – That is: clear subdiagonals of column $j$ of $U$ by row-adding.

To understand the step of setting ${\ell }_{kj}$ for $k>j$, it is useful to make the following observation:

$$(P_j{L}_1^{\prime }\cdots L_{j-1}^{\prime }{P}_j)L_j=L_1^{\prime }\cdots L_j^{\prime }.$$

This notation is a little misleading though, because $L_1^{\prime }$ on the RHS has subdiagonals permuted by $P_j$, whereas $L_1^{\prime }$ on the LHS does not. The factor $P_j{L}_1^{\prime }{P}_j$ will, though. Therefore, the meaning of $L_i^{\prime }$ changes at each step in the comments on the above algorithm.

Row-echelon form

When $U$ has a number of zeros cropping up, we can sometimes use pivoting to clear out more columns. For example, consider the matrices:

$$A=\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 2& 3& 4\\ 0& 0& 4& 5\\ 0& 0& 0& 1\end{array}\right),B=\left(\begin{array}{cccc}0& 2& 3& 4\\ 0& 0& 1& 0\\ 0& 0& 4& 5\\ 0& 0& 0& 1\end{array}\right),C=\left(\begin{array}{cccc}0& 2& 3& 4\\ 0& 0& 1& 0\\ 0& 0& 0& 5\\ 0& 0& 0& 0\end{array}\right).$$

Here $A$ is technically upper-triangular and satisfies the rules for $U$ in an LU factorization. However, it is possible to perform a pivot and obtain $B$, which can be further reduced by two elimination steps to obtain $C$.

The form of $C$ is called row-echelon form, or sometimes just echelon form. To be precise: in row-echelon form, the leading entry (left-most nonzero entry) in each row is somewhere to the right of the leading entries in the rows above, and rows of only zeros are at the bottom.

The combined process of creating $U$ as in LU decomposition and then continuing pivots and eliminations to put $U$ in row-echelon form is called row reduction.

• Row-echelon form for $U$ is very useful for inversion problems (see below). – For inversion problems, we will perform row reduction simultaneously on $A$ and on a vector $𝐛$ or matrix $B$ upon which we are inverting the action of $A$.
• Row-echelon form for $U$ is not needed for finding determinants (see below). – Indeed, row-echelon $U$ can only differ from other triangular $U$ when the determinant is zero.

Preimages and inversion

Recall the inversion problems we are interested in, namely solving for vector $𝐱$ or matrix $X$ in these equations:

$$A𝐱=𝐛,AX=B.$$

The LU factorization, and in particular the row reduction process yielding row-echelon form, is the perfect tool to solve these equations. Replacing $A$ with $LU$, we have:

$$LU𝐱=𝐛,LUX=B.$$

In the process of finding $LU$ we actually found $L^{-1}=L_n^{-1}\cdots L_1^{-1}$. Applying the $L^{-1}$ action to both sides:

$$U𝐱={𝐛}^{\prime },UX=B^{\prime }$$

where ${𝐛}^{\prime }=L^{-1}𝐛$ and $B^{\prime }=L^{-1}B$.

Now assume that $U$ is in row-echelon form. We can solve these equations for $𝐱$ and $X$ using the second fundamental technique of this packet, called back substitution.

Just as elimination is equivalent to inverting $L$, back substitution is equivalent to inverting $U$. Inverting $L$ with eliminations provides the row-echelon form, and inverting $U$ with back substitutions provides the reduced row-echelon form.

Reduced row-echelon form

Given $U$ in row-echelon form, it is also in reduced row-echelon form (RREF) when the leading nonzero entries in each row are ones, and any column with a leading one has all other entries equal to zero.

Back substitution is the process of applying row-scale and row-add matrix actions to convert a matrix in REF to a matrix in RREF. This is a continuation of “row reduction,” with a difference being that the matrices performing back substitution operations are not lower triangular, they are now upper triangular. Another difference is that we don’t have good reasons (in terms of applications) to record these back substitution matrices, we simply let them act on our matrix, or simultaneously on our matrix and vector (in the case of $A𝐱=𝐛$) or on our matrix and matrix (in the case of $AX=B$).

To find the RREF of a matrix in REF, we:

Computing reduced row-echelon form from row-echelon form

• Act by row-scale matrices to change the leading entries to ones.
• Act by more row-add matrices to eliminate the entries above leading ones.

Any RREF matrix can be written in terms of block submatrices:

$$\left(\begin{array}{cc}{I}_k& X\\ 0& 0\end{array}\right).$$

Here $I_k$ is the identity as a submatrix (the size of $k$ depends on how many zeros are in $U$), $X$ is some other submatrix, and $\begin{array}{cc}0& 0\end{array}$ are zeros filling out the rest of $U$.

Example

Back substitution: convert REF to RREF

$$\text{REF}\left(\begin{array}{cccc}0& 2& 3& 4\\ 0& 0& 1& 0\\ 0& 0& 0& 5\\ 0& 0& 0& 0\end{array}\right)\sim \left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 0\end{array}\right)\text{RREF}$$ $$\text{REF}\left(\begin{array}{ccccc}2& 4& -1& 5& -2\\ 0& 3& 1& 2& -3\\ 0& 0& 0& 2& 1\\ 0& 0& 0& 0& 5\end{array}\right)\sim \left(\begin{array}{ccccc}1& 2& -1/2& 5/2& -1\\ 0& 1& 1/3& 2/3& -1\\ 0& 0& 0& 1& 1/2\\ 0& 0& 0& 0& 1\end{array}\right)\sim \left(\begin{array}{ccccc}1& 0& -7/6& 0& 0\\ 0& 1& 1/3& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\end{array}\right)\text{RREF}$$

Exercise 09-04

Back substitution: convert REF to RREF

Convert $\left(\begin{array}{cccccc}1& -3& 0& -1& 0& -2\\ 0& 2& 0& 0& -8& 2\\ 0& 0& 0& 1& 9& 4\\ 0& 0& 0& 0& 0& 0\end{array}\right)$ from REF to RREF.

Preimage of a vector

The RREF of a matrix reveals the complete set of possible inverses (preimages) of a given vector.

Example

Inverting a vector using RREF

Consider the equation $A𝐱=𝐛$, with a row-reduced $A$:

$$\left(\begin{array}{cccc}1& 0& 0& -3\\ 0& 0& 1& 2\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right)=\left(\begin{array}{c}{b}_1\\ b_2\\ b_3\\ b_4\end{array}\right).$$

This matrix translates to the system of equations:

$$\begin{array}{cc}{x}_1-3x_4& =b_1,x_1=+3x_4+b_1\\ x_3+2x_4& =b_2,x_3=-2x_4+b_2\\ 0& =b_3\\ 0& =b_4\end{array}$$

There is a solution vector $𝐱$ provided $b_3=b_4=0$. If that is true, any $x_2$ and $x_4$ can be chosen, and $x_1,x_3$ are quickly found by solving the system. Given any choice of $x_2$ and $x_4$, there is only one possibility for each of $x_1,x_3$. Notice that the leading ones (also called pivots) are in columns $1$ and $3$, and $x_1$ and $x_3$ are determined. There are no pivots in columns $2$ and $4$, and $x_2$ and $x_4$ are free to take any value.

We can go farther and write the complete set of solutions $𝐱$ as the span of two vectors plus an offset, using values of $x_2$ and $x_4$ as the coefficients:

$$𝐱=\left(\begin{array}{c}3x_4+b_1\\ x_2\\ -2x_4+b_2\\ x_4\end{array}\right)=x_2\left(\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right)+x_4\left(\begin{array}{c}3\\ 0\\ -2\\ 1\end{array}\right)+\left(\begin{array}{c}{b}_1\\ 0\\ b_2\\ 0\end{array}\right)$$

so we could write, if you like: $𝐱\in ⟨\left(\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}3\\ 0\\ -2\\ 1\end{array}\right)⟩+\left(\begin{array}{c}{b}_1\\ 0\\ b_2\\ 0\end{array}\right)$.

If we wish to solve an equation $A𝐱=𝐛$ and $A$ is not yet in reduced row-echelon form, then we must convert $A$ to that form, while simultaneously applying the row reductions and pivots to the vector $𝐛$. (This means applying the same invertible transformations to both sides of the equation.) Row reduction is easily performed on $A$ and $𝐛$ simultaneously by combining them into the augmented matrix $\left(\begin{array}{cc}A& 𝐛\end{array}\right)$ and row reducing this instead. (This means: create a matrix by adding $𝐛$ as an additional column to $A$, and put a vertical line between them to demarcate the end of $A$.)

Example

Inverting a vector: row reduction of augmented matrix

Suppose we are trying to solve $A𝐱=𝐛$ with $A$ and $𝐛$ given by the following data:

$$A=\left(\begin{array}{ccccc}1& 6& 2& -5& -2\\ 0& 0& 2& -8& -1\\ 0& 0& 0& 0& 1\end{array}\right),𝐛=\left(\begin{array}{c}-4\\ 3\\ 7\end{array}\right).$$

Notice that $A$ is already in row-echelon form. So we create the augmented matrix and row-reduce it further to put $\left(\begin{array}{c}A|𝐛\end{array}\right)$ into RREF:

$$\begin{array}{cc}\left(\begin{array}{c}A|𝐛\end{array}\right)& =\left(\begin{array}{cccccc}1& 6& 2& -5& -2& -4\\ 0& 0& 2& -8& -1& 3\\ 0& 0& 0& 0& 1& 7\end{array}\right)\\ & \sim \left(\begin{array}{cccccc}1& 6& 0& 3& -1& -7\\ 0& 0& 2& -8& -1& 3\\ 0& 0& 0& 0& 1& 7\end{array}\right)\\ & \sim \left(\begin{array}{cccccc}1& 6& 0& 3& 0& 0\\ 0& 0& 1& -4& 0& 5\\ 0& 0& 0& 0& 1& 7\end{array}\right)\end{array}$$

and we discover that $x_2,x_4$ are free, $x_1=-6x_2-3x_4$ and $x_3=4x_4+5$ and $x_5=7$. The possible solutions for $𝐱$ are therefore:

$$𝐱=x_2\left(\begin{array}{c}-6\\ 1\\ 0\\ 0\\ 0\end{array}\right)+x_4\left(\begin{array}{c}-3\\ 0\\ 4\\ 1\\ 0\end{array}\right)+\left(\begin{array}{c}0\\ 0\\ 0\\ 0\\ 7\end{array}\right),x_2,x_4\in ℝ.$$

Solving linear systems

A linear system looks something like this:

$$\begin{array}{cc}{x}_1-2x_2+x_3& =0\\ 2x_2-8x_3& =8\\ 5x_1-5x_3& =10.\end{array}$$

This system is easily represented as the vector inversion problem of $A𝐱=𝐛$, with $𝐱=(x_1,x_2,x_3)$ and $\left(\begin{array}{cc}A& 𝐛\end{array}\right)$ given by:

$$\left(\begin{array}{cc}A& 𝐛\end{array}\right)=\left(\begin{array}{cccc}1& -2& 1& 0\\ 0& 2& -8& 8\\ 5& 0& -5& 10\end{array}\right)$$

The techniques of elimination and back substitution that we have learned for matrices correspond to the techniques of the same names that you already know for solving systems of equations.

Exercise 09-05

Comparing elimination and elimination

Explain (with some details in an example) how elimination for matrices (corresponding to multiplication by $L_i^{-1}$ for some single-column row-add combo matrix $L_i^{-1}$) is equivalent to elimination for a system of equations.

Hint: solve the above system using elimination and back substitution as in high school algebra, and then solve the same system as a vector preimage problem using row reduction to RREF of the augmented matrix. Write your solution steps in corresponding order so that you can match the corresponding steps between the two methods.

Preimage of a matrix

The technique for inverting a vector can be applied to find the preimage of a matrix simply by inverting the column vectors of that matrix. Namely, given the equation:

$$AX=B,$$

notice that if we write $X$ and $B$ in terms of their column vectors, we have:

$$\begin{array}{ccc}& A\left(\begin{array}{cccc}{𝐱}_1& {𝐱}_2& \dots & {𝐱}_n\end{array}\right)=\left(\begin{array}{cccc}{𝐛}_1& {𝐛}_2& \dots & {𝐛}_n\end{array}\right)& \text{<span class="tml-eqn"></span>}\\ & A{𝐱}_1={𝐛}_1,A{𝐱}_1={𝐛}_1,\dots ,A{𝐱}_n={𝐛}_n.& \text{<span class="tml-eqn"></span>}\end{array}$$

In principle, we can simply invert ${𝐛}_1,\dots ,{𝐛}_n$ one at a time, in sequence.

In practice, a much faster way to find $X$ is to write the augmented matrix $\left(\begin{array}{cc}A& B\end{array}\right)$ and row reduce this matrix.

The most important use of this technique is to find the inverse of an invertible matrix. Given $A$, the inverse $A^{-1}$ is found by computing the preimage of $I_n$ under the action of $A$, in other words by setting $B=I_n$ and row reducing the augmented matrix $\left(\begin{array}{cc}A& I_n\end{array}\right)$.

Example

Inverse of a $3\times 3$ matrix

Problem: Find the inverse $A^{-1}$ of the matrix $A=\left(\begin{array}{ccc}0& 1& 2\\ 1& 0& 3\\ 4& -3& 8\end{array}\right)$.

Solution: We row reduce the augmented matrix using pivots, eliminations, and back substitutions to put $A$ into RREF:

$$\begin{array}{cc}\left(\begin{array}{cccccc}0& 1& 2& 1& 0& 0\\ 1& 0& 3& 0& 1& 0\\ 4& -3& 8& 0& 0& 1\end{array}\right)& \sim \left(\begin{array}{cccccc}1& 0& 3& 0& 1& 0\\ 0& 1& 2& 1& 0& 0\\ 4& -3& 8& 0& 0& 1\end{array}\right)\\ \sim \left(\begin{array}{cccccc}1& 0& 3& 0& 1& 0\\ 0& 1& 2& 1& 0& 0\\ 0& -3& -4& 0& -4& 1\end{array}\right)& \sim \left(\begin{array}{cccccc}1& 0& 3& 0& 1& 0\\ 0& 1& 2& 1& 0& 0\\ 0& 0& 2& 3& -4& 1\end{array}\right)\\ \sim \left(\begin{array}{cccccc}1& 0& 3& 0& 1& 0\\ 0& 1& 2& 1& 0& 0\\ 0& 0& 1& 3/2& -2& 1/2\end{array}\right)& \sim \left(\begin{array}{cccccc}1& 0& 0& -9/2& 7& -3/2\\ 0& 1& 0& -2& 4& -1\\ 0& 0& 1& 3/2& -2& 1/2\end{array}\right).\end{array}$$

Therefore we have found $A^{-1}=\left(\begin{array}{ccc}-9/2& 7& -3/2\\ -2& 4& -1\\ 3/2& -2& 1/2\end{array}\right)$.

Determinants

Two facts about determinants allow us to use LU factorization to compute the determinant of any matrix:

Two determinant facts

• The determinant of any triangular matrix is equal to the product of its diagonal entries.
• The determinant is multiplicative: $\det AB=\det A\cdot \det B$.

If $A=LU$, then $\det A=\det L\cdot \det U$, and $\det L=1$ assuming it has only ones on the diagonal. So $\det A$ is the product of the diagonal entries of $U$.

If $PA=LU$, then $\det P\cdot \det A=\det L\cdot \det U$. It turns out that $\det P=\pm 1$. So $\det A=\mp \det U$ where again $\det U$ is the product of diagonal entries. The choice of sign is given by $\det P={(-1)}^k$ where $k$ is the number of non-trivial row-swaps that are composed to give $P$.

Problems due 20 Mar 2024 by 9:00am

Problem 09-01

Row reduction of a product

Suppose $A=BC$ and $B$ is invertible. Prove that any sequence of row reduction operations which reduces $B$ to $I_n$ will also reduce $A$ to $C$. Can you relate this fact to the LU decomposition?

Problem 09-02

LU factorization and solving $A𝐱=𝐛$

Compute the LU factorization of $A$:

$$A=\left(\begin{array}{cccc}1& -2& -4& -3\\ 2& -7& -7& -6\\ -1& 2& 6& 4\\ -4& -1& 9& 8\end{array}\right).$$

Use this to find the unique value of $𝐱$ that satisfies $A𝐱=𝐛$, where $𝐛=(\mathrm{1,7,0,3})$. (You should perform the elimination and back-substitution operations on the rows of $𝐛$ that are dictated by the LU decomposition of $A$.) Also: what is the determinant of $A$?

Problem 09-03

Inverse of $A$ using LU

Compute the inverse of $A$ from Problem 09-02 using the LU factorization computed in that problem, in other words by computing $U^{-1}{L}^{-1}$. Now compute $A^{-1}$ using the method at the end of the packet: perform row reduction on the augmented matrix $\left(\begin{array}{cc}A& I_4\end{array}\right)$. Which method do you like better?

Problem 09-04

Row reduction with pivoting

Perform row reduction with pivoting upon the matrix $A=\left(\begin{array}{cccc}2& 0& 0& 1\\ 4& 0& 0& 0\\ 4& 0& 3& 9\\ -6& 0& 24& 49\end{array}\right)$ in order to find all solutions $𝐱$ to the equation $A𝐱=𝐛$ with $𝐛=(\mathrm{1,1,1,1})$. (You can use the augmented matrix; no need to compute the full $PA=LU$ decomposition.)