Homework Help: Proof about system of linear equations in echelon form

1. May 28, 2015

s3a

1. The problem statement, all variables and given/known data
Problem:
Consider a system of linear equations in echelon form with r equations and n unknowns.

Prove the following.:

(i) If r = n, then the system has a unique solution.

(ii) If r < n, then we can arbitrarily assign values to the n - r free variables and solve uniquely for the r pivot variables, obtaining a solution of the system.

Solution:
(i) Suppose r = n. Then we have a square system AX = B where the matrix A of coefficient sis (upper) triangular with nonzero diagonal elements. Thus, A is invertible. By Theorem 3.10, the system has a unique solution.

(ii) Assigning values to the n - r free variables yields a triangular system in the pivot variables, which, by (i), has a unique solution.

Statement of Theorem 3.10:
Suppose the field K is infinite. Then the system AX = B has: (a) a unique solution, (b) no solution, or (c) an infinite number of solutions.

2. Relevant equations
There is a theorem (that I found online) which states than an upper triangular matrix is invertible if and only if all of its diagonal elements are non zero.

3. The attempt at a solution
I understand the solution for part (i) up until and including "Thus, A is invertible.", but I don't get the part that says "By Theorem 3.10, the system has a unique solution.". How does one come to that conclusion from Theorem 3.10? In other words, how does one determine from Theorem 3.10 that the system has a unique solution as opposed to having no solution or an infinite number of solutions? I'm not asking for a general way to justify determining that the system has a unique solution; I'm asking for a way to justify that the system has a unique solution by specifically using Theorem 3.10.

If something I said is unclear, let me know.

Any help in understanding the solution of this proof would be greatly appreciated!

2. May 29, 2015

Ray Vickson

You don't need Theorem 3.10; in fact, appealing to the theorem without knowing what it means or where it comes from seems to me to be counterproductive. It is much more revealing to recall why we bother with echelon forms in the first place: they make solving the equations a snap.

For example, suppose your echelon form is
$$\begin{array}{ccc|c} 1 & 2 & 3 & 4\\ 0 & 1 & 2 & 15 \\ 0 & 0 & 1 & 6 \end{array}$$
This is just a shorthand form for the system of equations
$$\begin{array}{ccccccc} x_1 & +& 2 x_2 & + &3x_3 & = & 4\\ & & x_2 & + & 2x_3 & =& 1 5 \\ & & & & x_3 & =& 6 \end{array}$$
which has an obviously unique solution: first, $x_3 = 6$, then put that value into the second equation and get the value of $x_2 = 15 - 2x_3 = 15 - 12 = 3$. Then put the now-known values of $x_2, x_3$ into the first equation; that gives you a unique value for $x_1$.

It works in exactly the same way for the general case of r = n.

3. Jun 2, 2015

s3a

Thanks for the response, and I get the intuition (i.e., what you said), but I not only want to know how to express it formally (as if I had to prove it on an exam), but I actually do care about appealing to Theorem 3.10 (because when I see something that I don't get in my books, I don't like to move on ).

So, could you please help me understand my book's proof (which makes use of Theorem 3.10)?

Last edited: Jun 2, 2015
4. Jun 2, 2015

Staff: Mentor

Here's the augmented matrix that Ray showed. The 3 x 3 matrix at the left is in echelon form, and r (number of equations, or number of rows) = n (number of variables, or number of columns in matrix A).
$$\begin{array}{ccc|c} 1 & 2 & 3 & 4\\ 0 & 1 & 2 & 15 \\ 0 & 0 & 1 & 6 \end{array}$$
Pretty clearly this matrix equation has a unique solution - you can solve for z, then for y, and finally for x.The unique solution represents a single point in R3.

Now suppose we ended up with this augmented matrix, which is in echelon form.
$$\begin{array}{ccc|c} 1 & 2 & 3 & 4\\ 0 & 1 & 2 & 15 \\ 0 & 0 & 0 & 0 \end{array}$$
Here r < n (i.e., there are two rows with nonzero leading entries, so we can arbitrarily assign values to the n - r = 3 - 2 = 1 free variable, and solve for the r = 2 pivot variables in terms of the free variable. Since the free variable can take on any value, there are an infinite number of solutions.
Geometrically, the solution space is a line in R3, produced by all three planes intersecting in a line..

Last, suppose we ended with this augmented matrix, which is almost identical to the previous one, except for the nonzero value in the bottom row.
$$\begin{array}{ccc|c} 1 & 2 & 3 & 4\\ 0 & 1 & 2 & 15 \\ 0 & 0 & 0 & 2 \end{array}$$
Again, we have r < n, but this time the last row means that the third equation is 0x + 0y + 0z = 2, which has no solution at all, no matter what we choose for x, y, or z. The system of equations that this matrix represents is inconsistent.

Geometrically, we could have a number of situations that cause this, including two of the planes being parallel, or all three being parallel. It's possible that each pair of planes intersect (in a line), but there is no point that is on all three planes.

5. Jun 3, 2015

Ray Vickson

If the solution you wrote is the book's, then I don't understand it. Theorem 3.10 makes no mention of matrix inverses, so I don't see how that comes into the solution at all. In fact, the only proofs I have seen of theorems like 3.10 START from the echelon form, then go through manipulations like I did (and like Mark 44 did) and thereby PROVE the theorem as output from that reasoning process (not as input). There may be other, completely different proofs of Theorem 3.10 that I have never seen (it would not surprise me), but the usual presentation is exactly backwards from the one you seem to want. So, I am unable to help you.

I suggest you go to the library and check out another book on the subject; it may present an alternative point of view that clarifies these issues for you.