# Systems of linear equations: What did the author mean?

EDIT: Since even after putting up a bounty I didn't get as much as a comment in two days I completely rewrote my question in hope to make it more accesible and get some good answers.

Consider the system in echelon form (the fat "X" denotes some sums):

This gives rise to a map $$\phi:\mathbb{R}^s\rightarrow L\subseteq \mathbb{R}^n,$$ where $s$ is the number of free variables for this system, that assign to every value of the free variable a solution ($L$ is the solution set).

The author of lecture notes from where I copied the above continues saying, that this map is surjectiv, "which can be proved directly, but the proof is messy. We can show it in a more elegant fashion using the theory which we will learn later, since in particular we have to show that the number $r$ does not depend on our way of arriving at the above system, but only on the original system".

Up to the point of introducing this system, the concepts of "vector space", "rank" and "subspace" were not yet discussed. It was only showed that - we can bring every arbitrary system via row operations to a system of the above form - that row transformations don't change the solution. - that we can solve the above system by substituting backwards (if all the $b_{r+1},\ldots,b_n$ are $0$).

My question is: Why does the proof that $\phi$ is surjective require "later theory" ? I believe it can be proven in a straightforward way (and using only what we have uptil now), that every map $\phi$ that we obtain be transforming a solvable system into a system of the above form is surjective (of course we don't know at this point, if we transform a system in two different ways to a system of the above form, whether for their associated maps $$\phi:\mathbb{R}^s\rightarrow L\subseteq \mathbb{R}^n \ \text{and} \ \phi:\mathbb{R}^{s'}\rightarrow L\subseteq \mathbb{R}^n$$we have $s=s'$ or $s\neq s'$. This is an essential point, I believe; with "later theory" it also follows that indeed $s=s'$, but we don't need that for surjectivity, nor that $r$ doesn't on the way we arrive from some system to the above system - in contrast to what the author said.)

(I assume I got so few comments because in the earlier version it wasn't clear, what I was asking. Now I hope it's more clear!)

-
Yes, it's intuitively clear, but intuition messes up sometimes. The easiest way to see why this is difficult is to try and articulate such a proof yourself. Can you really prove that varying the free variables gives all the solutions? – EuYu Feb 21 '13 at 23:05
@EuYu Assume there is a solution, that isn't reached by varying the free variables. We distinguish two cases: An entry of the solution vector that corresponds to a 1) nonfree variable 2) free variable in the above system can't be reached by varying the free variables . In the first case, since the solution vector must satisfy the above system, all of those entries of the solution vector that correspond to the nonfree variables in the above system must be of the $\frac{1}{p_j}(b_j-\sum_{i=p_j}^{n})$. This is the same form the nonfree variables have, when we vary the free variables. [...] – temo Feb 22 '13 at 10:27
The only way that the value of such an entry can't be obtained by varying the free variables is, if the free variables come from a larger set of values. But that obviously can't be the case, since all the free variables live in $\mathbb{R}^s$. The second case is trivial. Thus we have obtained a contradiction in both cases, so the free variables should indeed give all the solutions. Now either this proof is flawed (if so: where is the error?) or I was right and it really isn't necessary for additional theoretical machinery to prove this result. – temo Feb 22 '13 at 10:33
The above proof I don't find at all satisfying. I am not sure what you mean by $p_j$ or $b_j$, but why must the free variables live in $\mathbb{R}^s$? Assuming that there are $s$ free-variables is same as assuming the rank-nullity theorem, which is the classical way to prove this result. Is it not possible for a solution to have less or more free-variables? Different free-variables? By the way, I don't really think the proof is difficult, but rather mechanical and unenlightening. There is nothing new to be gained in going through a tedious proof at this point. – EuYu Feb 22 '13 at 16:24
@EuYu Well I can read what the free variables are off of the above system (note that what I proved was for the above fixed system; the $p_j$ and $b_j$ are also referring to it, although its true that I forgot to write $x_i$ on the right of the sum). So I know that there are $s$ free, real variables for this fixed system. And for this fixed system the above shows, that the fixed parametrisation $\phi:\mathbb{R}^s\rightarrow L$ is surjective. Since there seem to be unclear points, I'm going to expand my proof: What I showed above was actually just a step. The rest goes like this: [...] – temo Feb 25 '13 at 13:01

You are right that the author exaggerates the difficulty of proving that the map $\phi$ is surjective to the set $L$ of solutions, but your argument (in the comments) is not very clear, so I'll clarify it here.
The main point is that the system in echelon form is equivalent to the original system, so that the two have the same solution set $L$; this is implicit in the kind of transformations allowed to reach echelon form (no restrictions can be arbitrarily added or forgotten). So we just need to consider the echelon form system by itself.
The essence of the definition of $\phi$ is that it uses the equations of the system to deduce the values of all variables from the values of the free variables among them. Therefore $\phi(x_1,\ldots,x_s)\in L$ for all $(x_1,\ldots,x_s)\in\Bbb R^s$: one always gets a solution, whatever values one takes for the free variables. But we also know that $\phi$ did not change the values of the free variables themselves, so that if $i_1,\ldots,i_s\in\{1,\ldots,n\}$ are the positions of the free variables and $\pi:\Bbb R^n\to\Bbb R^s$ is the map extracting the values at those positions, so $\pi(x_1,\ldots,x_n)=(x_{i_1},\ldots,x_{i_s})$, then $\pi(\phi(x_1,\ldots,x_s))=(x_1,\ldots,x_s)$ (if we solve all variables from the free ones, but then forget those variables that aren't free, we just get back the values we started with). And finally we know that there was no choice in finding the non-free variables, since each one was deduced using an equation of the system from either the values of the free variables alone (for the first one solved) or from the values of the free variables and previously solved values of non-free variables. This means that two solutions that have the same values for the free variables must be identical (the first non-free variable where they differ would contradict the fact that they are both solutions); in formula, for $(x_1,\ldots,x_n),(y_1,\ldots,y_n)\in L$ the condition $\pi(x_1,\ldots,x_n)=\pi(y_1,\ldots,y_n)$ (agreement on the free variables) implies $(x_1,\ldots,x_n)=(y_1,\ldots,y_n)$ (agreement everywhere).
Now one easily argues surjectivity of $\phi$. Let $(x_1,\ldots,x_n)\in L$ be any solution, and put $(y_1,\ldots,y_n)=\phi(\pi(x_1,\ldots,x_n))=\phi(x_{i_1},\ldots,x_{i_s})$. Then on one hand $(y_1,\ldots,y_n)$ is in the image of $\phi$, and therefore in $L$ ($\phi$ only produces solutions), and on the other hand $\pi(y_1,\ldots,y_n)=\pi(\phi(\pi(x_1,\ldots,x_n)))=\pi(x_1,\ldots,x_n)$. But we just saw that this implies $(x_1,\ldots,x_n)=(y_1,\ldots,y_n)$, and in particular $(x_1,\ldots,x_n)$ is (also) in the image of $\phi$. Stated without formulas: given any solution, we can extract from it the values of the free variables and construct from them using $\phi$ values for all the non-free variables; but since this is the only way to extend those values to a solution, we must have gotten back to our original solution.