4.2: Triangular systems - Math 124 Course Notes

Upper triangular systems¶

Consider

\begin{aligned}3x-2y&=8,\\2y&=4.\end{aligned}

The second equation gives $y=2$ . Substitute into the first: $3x-4=8$ , so $x=4$ . In matrix form,

\begin{bmatrix}3&-2\\0&2\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} =\begin{bmatrix}8\\4\end{bmatrix}.

The zero in the bottom-left position is doing useful work: the last equation contains only the last variable.

For example,

U=\begin{bmatrix}2&-1&4\\0&3&5\\0&0&-2\end{bmatrix},\qquad L=\begin{bmatrix}2&0&0\\-1&3&0\\3&1&-2\end{bmatrix}

are upper and lower triangular, respectively. Entries on the other side of the diagonal are allowed to be zero too. A diagonal matrix is both upper and lower triangular.

Back substitution¶

For an upper triangular system with nonzero diagonal entries, we start at the bottom and work upward. This is called back substitution.

Let’s solve

\begin{bmatrix}4&-2&2\\0&3&-1\\0&0&5\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix} =\begin{bmatrix}6\\3\\15\end{bmatrix}.

Writing out the equations makes the order clear:

\begin{aligned}4x_1-2x_2+2x_3&=6,\\3x_2-x_3&=3,\\5x_3&=15.\end{aligned}

The last equation gives $x_3=3$ . The second then gives $3x_2-3=3$ , so $x_2=2$ . Finally,

4x_1-2(2)+2(3)=6\quad\Longrightarrow\quad x_1=1.

Thus $\vec x=\begin{bmatrix}1\\2\\3\end{bmatrix}$ . Check it by multiplying the original matrix by this vector.

Forward substitution¶

For a lower triangular system, the direction reverses. Consider

\begin{bmatrix}2&0&0\\-1&3&0\\3&1&-2\end{bmatrix}\begin{bmatrix}x\\y\\z\end{bmatrix} =\begin{bmatrix}4\\7\\1\end{bmatrix}.

This time the first equation contains only one variable:

\begin{aligned}2x=4&\quad\Longrightarrow\quad x=2,\\ -x+3y=7&\quad\Longrightarrow\quad -2+3y=7\quad\Longrightarrow\quad y=3,\\ 3x+y-2z=1&\quad\Longrightarrow\quad6+3-2z=1\quad\Longrightarrow\quad z=4. \end{aligned}

The solution is $\begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}2\\3\\4\end{bmatrix}$ .

Activity 1

Rewrite each system as a matrix equation, then solve it. Identify whether you use forward or back substitution.

$2x+y=7$ , $y=3$ .
$2x=2$ , $2x+3y=8$ , $x-y+2z=5$ .
$2x-y+z=4$ , $3y+2z=7$ , $z=2$ .

Check each solution in all of its original equations.

Solution

1. The matrix equation is

\begin{bmatrix}2&1\\0&1\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}7\\3\end{bmatrix}.

Use back substitution: $y=3$ , then $2x+3=7$ , so $x=2$ . The solution is $\begin{bmatrix}2\\3\end{bmatrix}$ . Checking gives $2(2)+3=7$ and $3=3$ .

2. The matrix equation is

\begin{bmatrix}2&0&0\\2&3&0\\1&-1&2\end{bmatrix}\begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}2\\8\\5\end{bmatrix}.

Use forward substitution: $2x=2$ gives $x=1$ ; $2+3y=8$ gives $y=2$ ; and $1-2+2z=5$ gives $z=3$ . The solution is $\begin{bmatrix}1\\2\\3\end{bmatrix}$ . Checking gives $2(1)=2$ , $2(1)+3(2)=8$ , and $1-2+2(3)=5$ .

3. The matrix equation is

\begin{bmatrix}2&-1&1\\0&3&2\\0&0&1\end{bmatrix}\begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}4\\7\\2\end{bmatrix}.

Use back substitution: $z=2$ , then $3y+4=7$ gives $y=1$ , and $2x-1+2=4$ gives $x=\frac32$ . The solution is $\begin{bmatrix}3/2\\1\\2\end{bmatrix}$ . Checking gives $2(3/2)-1+2=4$ , $3(1)+2(2)=7$ , and $2=2$ .

Why the diagonal matters¶

At each step, we divide by a diagonal entry. The diagonal entries don’t need to be 1, but they do need to be nonzero for this procedure to determine one new variable at every step.

For instance,

\begin{bmatrix}2&1\\0&0\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} =\begin{bmatrix}7\\3\end{bmatrix}

has a last equation $0=3$ , so it has no solution. Replacing the right-hand side by $\begin{bmatrix}7\\0\end{bmatrix}$ gives $0=0$ instead. Then $y$ is unrestricted, and $x=(7-y)/2$ gives infinitely many solutions.

We’ll study these possibilities in Chapter 4.5. For now, our triangular solves will have nonzero diagonal entries.

Activity 2

Give a $3\times3$ matrix that is upper triangular but not lower triangular.
What must a matrix look like if it is both upper and lower triangular?
Explain why a triangular system with all diagonal entries nonzero has exactly one solution for every right-hand side.

Solution

1. One example is

\begin{bmatrix}1&2&0\\0&3&4\\0&0&5\end{bmatrix}.

Every entry below the diagonal is zero, so it is upper triangular. The nonzero entries above the diagonal mean it is not lower triangular.

2. It must be diagonal: being upper triangular forces all entries below the diagonal to be zero, and being lower triangular forces all entries above it to be zero. Diagonal entries may be zero or nonzero.

3. For an upper triangular system, the last equation determines the last variable uniquely because its coefficient is nonzero. After substituting that value into the preceding equation, the next variable is uniquely determined for the same reason. Continuing upward determines all variables, with no choices or contradictions. A lower triangular system works the same way from top to bottom. Thus every right-hand side gives exactly one solution.