Types: N/A
Examples: 12.2.1 Nonsingular Matrix to Model Gravity
Constructions: N/A
Generalizations: N/A

Properties: N/A
Sufficiencies: N/A
Questions: N/A

Backwards Substitution: Upper-Triangular

U \vec{x} = \vec{y}

Let $U \vec{x} = \vec{y}$ be a given linear-systems problem with 8.9 Upper-Triangular Matrix $U \in R^{n \times n}$ and $\vec{y} \in R^{n}$ . If entries of $U$ , $u_{i i} \neq 0$ for all $i \in {1, 2, \dots, n}$ , then our linear-system problem has a unique solution. This solution can be found using the backward substitution algorithm:

\begin{aligned} x_{n} & = \frac{y_{n}}{u_{n n}} \\ x_{i} & = \frac{1}{u_{i i}} (y_{i} - \sum_{j = i + 1}^{n} u_{i j} x_{j}) \end{aligned}

where $i = (n - 1), (n - 2), \dots, 2, 1$ .

\begin{proof}
Let $n = 5$ and consider

[\begin{matrix} u_{11} & u_{12} & u_{13} & u_{14} & u_{15} \\ 0 & u_{22} & u_{23} & u_{24} & u_{25} \\ 0 & 0 & u_{33} & u_{34} & u_{35} \\ 0 & 0 & 0 & u_{44} & u_{45} \\ 0 & 0 & 0 & 0 & u_{55} \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{matrix}] = [\begin{matrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ y_{5} \end{matrix}]

Note that $u_{i i} \neq 0$ for all $i \in [5)$ .

Step 0

Let's start at the bottom entry of the matrix.

\begin{aligned} {Entry}_{5} (U \vec{x}) & = y_{5} \\ ⟹ [{Row}_{5} (U)]_{1 \times 5} [\vec{x}]_{5 \times 1} & = y_{5} \\ = [\begin{array}{c} 0 & 0 & 0 & 0 & u_{55} \end{array}] [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{array}] \\ ⟹ u_{55} \cdot x_{5} & = y_{5} \\ ⟹ x_{5} & = \frac{y_{5}}{u_{55}} \end{aligned}

From this, we can work "backwards" up the matrix. In our next step, we will substitute in our value we get for $x_{5}$ .

Step 1

Because we solved for a value of $x_{5}$ in our last step, we can substitute it in when solving for $x_{4}$ .

\begin{aligned} ⟹ {Entry}_{4} (U \cdot \vec{x}) & = y_{4} \\ ⟹ {Row}_{4} (U) \cdot \vec{x} & = y_{4} \\ ⟹ [\begin{array}{c} 0 & 0 & 0 & u_{44} & u_{45} \end{array}] [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{array}] & = y_{4} \\ ⟹ u_{44} \cdot x_{4} + u_{45} \cdot x_{5} & = y_{4} \\ ⟹ u_{44} \cdot x_{4} & = y_{4} - u_{45} x_{5} \\ ⟹ x_{4} & = \frac{1}{u_{44}} (y_{4} - u_{45} x_{5}) \end{aligned}

Step 2

We continue our algorithm by solving for $x_{3}$ .

\begin{aligned} ⟹ {Entry}_{3} (U \cdot \vec{x}) & = y_{3} \\ ⟹ {Row}_{3} (U) \cdot \vec{x} & = y_{3} \\ ⟹ [\begin{array}{c} 0 & 0 & u_{33} & u_{34} & u_{35} \end{array}] [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{array}] & = y_{3} \\ ⟹ u_{33} x_{3} + u_{34} x_{4} + u_{35} x_{5} & = y_{3} \\ ⟹ x_{3} & = \frac{1}{u_{33}} (y_{3} - u_{34} x_{4} - u_{35} x_{5}) \end{aligned}

Can we generalize this?

⟹ x_{3} = \frac{1}{u_{33}} (y_{3} - \sum_{k = 4}^{5} u_{3 k} \cdot x_{k})

Let's look back at $x_{4}$ from Step 1. Can we generalize that too?

\begin{aligned} x_{4} & = \frac{1}{u_{44}} (y_{4} - u_{45} x_{5}) \\ = \frac{1}{u_{44}} (y_{4} - \sum_{k = 5}^{5} u_{4 k} \cdot x_{k}) \end{aligned}

Step 3

Can we intuit what our final entries will look like based on the pattern we've been seeing? Let's find $x_{2}$ first.

\begin{aligned} {Entry}_{2} (U \cdot \vec{x}) & = y_{2} \\ x_{2} & = \frac{1}{u_{22}} (y_{2} - \sum_{k = 3}^{5} u_{2 k} \cdot x_{k}) \\ ⟺ {Row}_{2} (U) \cdot \vec{x} = y_{2} \\ ⟹ [\begin{array}{c} 0 & u_{22} & u_{23} & u_{24} & u_{25} \end{array}] [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{array}] = y_{2} \\ ⟹ u_{22} x_{2} + u_{23} x_{3} + u_{24} x_{4} + u_{25} x_{5} = y_{2} \\ ⟹ x_{2} = \frac{1}{u_{22}} (y_{2} - u_{23} x_{3} - u_{24} x_{4} - u_{25} x_{5}) \end{aligned}

Therefore, to get our final entry,

\begin{aligned} x_{1} & = \frac{1}{u_{11}} (y_{1} - \sum_{k = 2}^{5} u_{1 k} x_{k}) \end{aligned}

\end{proof}