# Linear Algebra - proof of infinite solutions to the system Ax=b

I submit the complete proof of a theorem and i would like to ask a specific numeric example and further clarification on the proof because i do not understand some parts of it. The proof comes from book: Linear Algebra step by step, by Singh.

Theorem: Let $Ax=b$ a consistent non-homogeneous linear system, $b$ is not zero. R is the rref, $n=$ number of unknown variables, $r=$ rows. If $r < n$ then $Ax=b$ has an infinite number of solutions.

proof: We are given that the number of non-zero rows (equations) $r$ is less than the number of unknowns $n$. Consider the reduced row echelon form R with r non-zero rows. This means there are exactly $r$ leading $1$’s. Why? Because R is in reduced row echelon form which means any non-zero row has a leading 1. Every column of R cannot have a leading $1$ because you would need $n$ leading $1$’s but there are only $r$ which is less than $n$. Therefore there must be a column call it $x_j$ which has no leading one.

If the $j$-th ( $x_j$ ) column has only zero entries then we can let $x_j = t$ where $t$ is any real number. The solutions are: $x_1=s_1,x_2=s_2,....x_{j-1}=s_{j-1}, x_j=t,.....x_n=s_n,\;t\in \Bbb R$. Hence our infinite solution set is: $\mathbf S = \{s_1,s_2,....t,,...,x_n=s_n\mid t\in \Bbb R\}$. We have an infinite number of solutions to $Ax = b$.

If there is a non-zero entry in the $j$-th column then at least one of unknowns must be written in terms of $x_j$ . Let the unknown $x_j$ be $t$ where t is any real number. This means that at least one of the other unknowns can be written in terms of $t$. Thus we have infinite number of solutions.

The last two paragraphs I do not fully understand, Hopefully a numeric example could help clarify the description of the last two paragraphs.

• You should not denote the columns by the name of the unknowns. – Bernard May 27 '18 at 8:28
• please check the book. I copied all the symbols as is. It is not my proof, complain to the author of the book. i merely try to learn... – DontAskTheEye May 27 '18 at 8:47

The two paragraphs in question shouldn't really be considered as separate cases.

Here's a simple example: $$\begin{bmatrix} 1 & 0 & 0 & a \\ 0 & 1 & 0 & b \\ 0 & 0 & 1 & c \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\x_4 \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix}$$

Letting $x_4 = t$ range, we have the infinite set of solutions

$$x_1 = b_1 - at$$ $$x_2 = b_2 - bt$$ $$x_3 = b_3 - ct$$ $$x_4 = t$$

In general, suppose you have $A\vec{x} = \vec{b}$ with $A$ an $m \times n$ matrix in reduced-row-echelon form with nonzero rows and $m < n$. Denote the entries of $A$ by $a_{ij}$.

Let $i_1, \ldots i_m$ be the indices of the columns containing leading ones, and $j_1, \ldots, j_{n-m}$ be indices of the remaining columns. We let the $x_{j_1}, \ldots x_{j_{n-m}}$ range as $t_{j_1}, \ldots, t_{j_{n-m}}$.

By expanding the matrix multiplication we find the infinite set of solutions

$$x_{i_1} = b_1 - \sum_{k=1}^{n-m} a_{1 j_{k}} t_{j_k}$$ $$\vdots$$ $$x_{i_m} = b_m - \sum_{k=1}^{n-m} a_{m j_{k}} t_{j_k}$$ $$x_{j_1} = t_{j_1}$$ $$\vdots$$ $$x_{j_{n-m}} = t_{j_{n-m}}$$