18.2 Example of Template for Complete Solutions

Types: N/A
Examples: N/A
Constructions: N/A
Generalizations: N/A

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

Template for Complete Solutions for Toy GLSP

Recall the general linear-systems problem from 17.6 Toy GLSP.

{[\begin{matrix} - 3 & 6 & - 1 & 1 & - 7 \\ 1 & - 2 & 2 & 3 & - 1 \\ 2 & - 4 & 5 & 8 & - 4 \end{matrix}]}_{3 \times 5} {[\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x 5 \end{matrix}]}_{5 \times 1} = {[\begin{matrix} - 13 \\ 6 \\ 13 \end{matrix}]}_{3 \times 1}

Recall that we have already transformed our GLSP into 17.3 Reduced Row Echelon Form via multiplication on the left by elementary matrices.

{[\begin{matrix} 1 & - 2 & 0 & - 1 & 3 \\ 0 & 0 & 1 & 2 & - 2 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}]}_{3 \times 5} {[\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{matrix}]}_{5 \times 1} = {[\begin{matrix} 4 \\ 1 \\ 0 \end{matrix}]}_{3 \times 1}

How can we use reduced row echelon form to find our particular solution and trivial solution?

\vec{x} = \vec{p} + \vec{z}

\begin{proof}[Solution.]
Let's start by looking for our particular solution $\vec{p}$ . The columns with a leading entry of $1$ are pivot columns. All columns that do not meet this criteria are nonpivot columns.

U = {[\begin{array}{ccccc} \overset{pivot col. 1}{1} & - 2 & \overset{pivot col. 2}{0} & - 1 & 3 \\ 0 & 0 & 1 & 2 & - 2 \\ 0 & \underset{nonpivot col. 1}{0} & 0 & \underset{nonpivot col. 2}{0} & \underset{nonpivot col. 3}{0} \end{array}]}_{3 \times 5}

We need to find the values of $\vec{x}$ when multiplied with $A$ on the right that produce our resulting vector $\vec{y}$ .

{[\begin{array}{ccccc} 1 & - 2 & 0 & - 1 & 3 \\ 0 & 0 & 1 & 2 & - 2 \\ 0 & 0 & 0 & 0 & 0 \end{array}]}_{3 \times 5} {[\begin{matrix}  \end{matrix}]}_{5 \times 1} = {[\begin{matrix} 4 \\ 1 \\ 0 \end{matrix}]}_{3 \times 1}

We can rewrite $\vec{y}$ as a linear combination of our pivot columns.

[\begin{matrix} 4 \\ 1 \\ 0 \end{matrix}] = [\begin{matrix} 4 \\ 0 \\ 0 \end{matrix}] + [\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}] = 4 [\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}] + 1 [\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}]

Therefore, we need:

4 of the first pivot column
0 of the first nonpivot column
1 of the second pivot column
0 of the second nonpivot column
0 of the third nonpivot column

Mathematically, we write

{[\begin{array}{ccccc} 1 & - 2 & 0 & - 1 & 3 \\ 0 & 0 & 1 & 2 & - 2 \\ 0 & 0 & 0 & 0 & 0 \end{array}]}_{3 \times 5} {[\begin{matrix} 4 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix}]}_{5 \times 1} = {[\begin{matrix} 4 \\ 1 \\ 0 \end{matrix}]}_{3 \times 1}

& The number of pivot columns is hidden in our right hand side vector $\vec{y}$ .

Now, we need to find the vectors that second $U$ to 0. In other words, how do we find the trivial solution?

Before continuing, let

$r$ be the number of pivot columns of the matrix $U$ .
$f$ be the number of nonpivot columns of matrix $U$ .

In our example, we see that $r = 2$ and $f = 3$ .

Claim

Each nonpivot column can be written as a linear combination of previous pivot columns.

For our matrix $U$ , we can say that column 2 is a linear combination of column 1. Let's look first at nonpivot column 1.

\begin{aligned} [U (:, 2)]_{3 \times 1} = [\begin{array}{c} - 2 \\ 0 \\ 0 \end{array}] = - 2 \cdot [\begin{array}{c} 1 \\ 0 \\ 0 \end{array}] & = - 2 \cdot [U (:, 1)]_{3 \times 1} \\ ⟹ - 2 \cdot U (:, 1) & = 1 \cdot U (:, 2) \\ ⟹ 2 \cdot U (:, 1) + 1 \cdot U (:, 2) & = \vec{0} \\ ⟹ 2 [\begin{array}{c} 1 \\ 0 \\ 0 \end{array}] + 1 [\begin{array}{c} - 2 \\ 0 \\ 0 \end{array}] & = [\begin{array}{c} 0 \\ 0 \\ 0 \end{array}] \end{aligned}

Can we get a special solution using this equation?

We can use this equation to a special trivial solution associated with nonpivot column 1. Formally, we are constructing a vector ${\vec{z}}_{1} \in R^{5}$ that encodes the linear dependence relations in the columns of $U$ .

Therefore,

U \cdot {\vec{z}}_{1} = {[\begin{matrix} 1 & - 2 & 0 & - 1 & 3 \\ 0 & 0 & 1 & 2 & - 2 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}]}_{3 \times 5} {[\begin{matrix} 2 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}]}_{5 \times 1} = [\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}], with {\vec{z}}_{1} = [\begin{matrix} 2 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}] .

We can move on to the next pivot column.

U (:, 4) = [\begin{matrix} - 1 \\ 2 \\ 0 \end{matrix}] = - 1 [\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}] + 2 [\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}] = - 1 \cdot U (:, 1) + 2 \cdot U (:, 3)

Again, let's use 04 Vector Arithmetic to set the right-hand side of the equation to zero so we can find our trivial solution.

\begin{aligned} ⟹ U (:, 4) + 1 \cdot U (:, 1) - 2 \cdot U (:, 3) & = \vec{0} \\ ⟹ 1 [\begin{array}{c} - 1 \\ 2 \\ 0 \end{array}] + 1 [\begin{array}{c} 1 \\ 0 \\ 0 \end{array}] - 2 [\begin{array}{c} 0 \\ 1 \\ 0 \end{array}] & = \vec{0} \end{aligned}

From our linear combination, we can construct ${\vec{z}}_{2} \in R^{5}$ such that

U \cdot {\vec{z}}_{2} = [\begin{matrix} 1 & - 2 & 0 & - 1 & 3 \\ 0 & 0 & 1 & 2 & - 2 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}] [\begin{matrix} 1 \\ 0 \\ - 2 \\ 1 \\ 0 \end{matrix}] = [\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}], with {\vec{z}}_{2} = [\begin{matrix} 1 \\ 0 \\ - 2 \\ 1 \\ 0 \end{matrix}]

Finally, we can rewrite our last nonpivot column as

U (:, 5) = [\begin{matrix} 3 \\ - 2 \\ 0 \end{matrix}] = 3 [\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}] - 2 [\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}] = 3 \cdot U (:, 1) - 2 \cdot U (:, 3)

Once again, set the right side to zero using vector arithmetic.

- 3 \cdot U (:, 1) + 2 \cdot U (:, 3) + 1 \cdot U (:, 5) = - 3 [\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}] + 2 [\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}] + 1 [\begin{matrix} 3 \\ - 2 \\ 0 \end{matrix}]

Pulling out our scalars, we can construct ${\vec{z}}_{3} \in R^{5}$ such that

U \cdot {\vec{z}}_{3} = [\begin{matrix} 1 & - 2 & 0 & - 1 & 3 \\ 0 & 0 & 1 & 2 & - 2 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}] [\begin{matrix} - 3 \\ 0 \\ 2 \\ 0 \\ 1 \end{matrix}] = [\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}], with {\vec{z}}_{3} = [\begin{matrix} - 3 \\ 0 \\ 2 \\ 0 \\ 1 \end{matrix}]

We now have three 6.7 Linearly Independent Vectors to the linear-systems problem

U \cdot \vec{x} = 0

provided by ${\vec{z}}_{1}, {\vec{z}}_{2}, {\vec{z}}_{3}$ as well one particular solution given by

\vec{p} = [\begin{matrix} 4 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix}] .

Combining these using our 18.1 Template for Complete Solutions to GLSP, we see that

\begin{aligned} U \cdot \vec{x} & = U [\vec{p} + \vec{z}] \\ = U [\vec{p} + c_{1} {\vec{z}}_{1} + c_{2} {\vec{z}}_{2} + c_{3} {\vec{z}}_{3}] \\ = U \vec{p} + U (c_{1} {\vec{z}}_{1}) + U (c_{2} {\vec{z}}_{2}) + U (c_{3} {\vec{z}}_{3}) \\ = \vec{y} + c_{1} \cdot U {\vec{z}}_{1} + c_{2} U {\vec{z}}_{2} + c_{3} U {\vec{z}}_{3} \\ = \vec{y} + c_{1} \cdot \vec{0} + c_{2} \cdot \vec{0} + c_{3} \cdot \vec{0} \\ = \vec{y} + 0 \\ = \vec{y} \end{aligned}

To conclude, we say that our final solution is our particular solution plus any linear combination of our trivial solutions.

\vec{x} = [\begin{matrix} 4 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix}] + c_{1} [\begin{matrix} 2 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}] + c_{2} [\begin{matrix} 1 \\ 2 \\ - 2 \\ 1 \\ 0 \end{matrix}] + c_{3} [\begin{matrix} - 3 \\ 0 \\ 2 \\ 0 \\ 1 \end{matrix}]

\end{proof}