Underdetermined homogeneous system of linear equations has always infinitely many solutions I want to prove that an underdetermined homogeneous system of linear equations always has infinitely many solutions.
I know that a homogenous system of linear equations always has the trivial solution (0,0,...,0). I also know that an underdetermined system of linear equations can only have zero or infinitely many solutions, but I can not prove that. 
So because the underdetermined homogeneous system of linear equations always has the trivial solution, it must have infinitely many solutions. But as I said, I am not able to prove, that an underdetermined system of linear equations can never only have one solution...
It is "clear" why this has to be the case, because you can determine one variable in expression of another, so you can create infinitely many solutions. But how can I prove that mathematically?
I mustn't use matrices or anything like that...
 A: An underdetermined system is one in which there are more unknowns than equations. You can use induction on the number $n$ of unknowns; since there is always at most one of them, the base case $n=0$ is vacuously true.
Consider the final unknown $x_n$. If its coefficient in all equations is $0$, then one can give it an arbitrary value, and let all other unknowns be$~0$, to get infinitely many solutions (this is where homogeneity is used). Otherwise single out one equation in which $x_n$ has a nonzero coefficient. Use it to express $x_n$ as a linear combination of the other unknowns. Substitute this expression for $x_n$ into the remaining equations (this is equivalent to eliminating $x_n$ from the other equations by Gauss's method). The remaining equations form an underdetermined system: one less equation (the one singled out) and one less unknown ($x_n$); so by induction it has infinitely many solutions (for the remaining unknowns). For each of these solutions, build one that also gives $x_n$ by using the expression as linear combination of the other unknowns. One easily checks that this gives solutions of the original system.
