4

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...

Greenonline
  • 204
Rummelluff
  • 489
  • You've given a proof. (1) It's homogeneous, so it has at least one solution. (2) it's underdetermined, so it has zero or infinitely many. (3) Because we know it has at least one solution, it cannot have zero, and so by 2, it must have infinitely many. There's really nothing left to prove. – John Hughes Oct 31 '14 at 05:23
  • Yes, but I only "know" that, i am not able to prove, that an underdetermined system of linear equations can never only have one solution... How can i prove that mathematically? – Rummelluff Oct 31 '14 at 05:29
  • 1
    So when you said you "knew" item 2, you meant that you believed it, but do not have a proof? Perhaps you can phrase your question in the form of a question, and then someone can answer it. – John Hughes Oct 31 '14 at 05:31
  • I've edited the question – Rummelluff Oct 31 '14 at 05:34

1 Answers1

4

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.

Marc van Leeuwen
  • 115,048