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.

enter image description here

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.

  • $\begingroup$ You should not denote the columns by the name of the unknowns. $\endgroup$ – Bernard May 27 '18 at 8:28
  • 2
    $\begingroup$ 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... $\endgroup$ – 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}}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.