First, use Gauss’ method to reduce the linear system to echelon form.
Let row \(m\) be the bottom-most row that is not in the form \(0=0\text{,}\) it will have the form:
\begin{equation*}
a_{m,\ell_m} x_{\ell_m} + a_{m,\ell_m+1} x_{\ell_m+1} + \cdots + a_{m,n} x_n = 0
\end{equation*}
and since \(x_{\ell_m}\) is a leading variable \(a_{m,\ell_m} \neq 0\text{.}\) (Note: \(\ell\) means leading, so \(\ell_m\) means the column (variable \#) of the leading variable in the \(m\)th row.) Solving for \(x_{\ell_m}\text{:}\)
\begin{equation*}
x_{\ell_m} = -\frac{a_{m,\ell_m+1}}{a_{m,\ell_m}} x_{\ell_m+1} - \cdots
-\frac{a_{m,n}}{a_{m,\ell_m}} x_n
\end{equation*}
This equation shows how to write
\(x_{\ell_m}\) in terms of the free variables to the right of column
\(\ell_m\text{.}\) There may or may not be free variables. If there are not then it says that
\(x_{\ell_m}=0\text{.}\)
Next, in the induction proof, assume that some row \(t\leq m\text{,}\) can be written
\begin{equation*}
x_{\ell_t} = \text{linear combination of free variables}.\text{,}
\end{equation*}
then row \(t-1\) of the linear system in echelon form is:
\begin{equation*}
a_{t-1,\ell_{t-1}} x_{\ell_{t-1}} + a_{t-1,\ell_{t-1}+1} x_{\ell_{t-1}+1} + \cdots +
a_{t-1,n} x_n = 0
\end{equation*}
with \(a_{t-1,\ell_{t-1}} \neq 0\) and thus solve for \(x_{\ell_{t-1}}\) by subtracting all other terms and dividing through by \(a_{t-1,\ell_{t-1}}\text{.}\) Thus \(x_{\ell_{t-1}}\) is written as a linear combination of all variables to the right. For each leading variable on the right, replace it with its solution from back-substitution. Thus \(x_{\ell_{t-1}}\) can be written as
\begin{equation*}
x_{\ell_{t-1}} = \text{linear combination of free variables}
\end{equation*}
Inductively, each leading variable can be written in this form. The \(c_i\) in the statement of the lemma are the free variables and the vectors \(\vec{\beta}_i\) are coefficients of the free variable corresponding to \(c_i\) in each \(x_{\ell_i}\text{.}\)
