18.4 Solution to HSLP using RREF

Types: N/A
Examples: N/A
Constructions: N/A
Generalizations: 18.3 Homogenous Linear System

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

Solution to

A \cdot \vec{x} = \vec{0}

using

RREF

Let $A \in R^{m \times n}$ be a "given" matrix and suppose $U = RREF (A)$ . Then, for an $\vec{x} \in R^{n}$ we have

A \cdot \vec{x} = \vec{0} ⟺ U \cdot \vec{x} = \vec{0} .

\begin{proof}
Let $A \in R^{m \times n}$ . Suppose $U = RREF (A)$ . To prove this biconditional theorem, we need to show:

If $A \cdot \vec{x} = \vec{0}$ , then $U \cdot \vec{x} = \vec{0}$ .
If $U \cdot \vec{x} = \vec{0}$ , then $A \cdot \vec{x} = \vec{0}$ .

To start, recall our algorithm for creating $RREF (A)$ . By construction of 17.3 Reduced Row Echelon Form matrix $U$ , there exists a sequence of elementary matrices $E_{1}, E_{2}, \dots, E_{t} \in R^{m \times m}$ such that

E_{t} \cdot E_{t - 1} \dots E_{2} \cdot E_{1} \cdot A = U

for some $t \in N$ . Moreover, each elementary matrix $E_{j}$ can either be written as a 9.8 Shear Matrix, 9.9 Dilation Matrix, or 9.10 Transposition Matrix (AKA permutation matrix), for $1 \leq j \leq t$ . Because each of these matrices is nonsingular, then the $m \times m$ matrix

E = E_{t} \cdot E_{t - 1} \dots E_{2} \cdot E_{1}

is nonsingular. This follows from the fact that any product of nonsingular matrices is also nonsingular.

Let's prove condition 1 of this proof, the forward direction.

\begin{aligned} A \cdot \vec{x} = \vec{0} & ⟹ & E \cdot A \cdot \vec{x} & = E \cdot \vec{0} \\ ⟹ & U \cdot \vec{x} & = \vec{0} \end{aligned}

The final line follows since for $E \cdot \vec{0} = \vec{0}$ for any $E \in R^{m \times m}$ . Now, let's prove condition 2, the backwards direction.

\begin{aligned} U \cdot \vec{x} = \vec{0} & ⟹ (E \cdot A) \cdot \vec{x} & = E \cdot \vec{0} \\ ⟹ E \cdot (A \cdot \vec{x}) & = \vec{0} \\ ⟹ A \cdot \vec{x} & = \vec{0} \end{aligned}

The final line results from the fact that if $E \in R^{m \times m}$ is nonsingular, then we know $E \cdot \vec{y} = \vec{0}$ iff $\vec{y} = \vec{0}$ . In this case, we set $\vec{y} = A \cdot \vec{x}$ . With this, we have finished our proof in both directions, both of which hold true.

\end{proof}