Underdetermined system has infinitely many solutions

Question

To prove that there can be at most n linearly independent vectors in R^n, I have to show, that a matrix equation $$ A_{n \times (n +1)}x=b $$ has infinitely many solutions. I have been looking for a proof for that but so far most of the proofs rely on some kind of other "obvious" result or intuition. For example some simply state that a system with more variables than equations has infinitely many solutions. Even though obvious, I can't prove this result.

So could someone please present an exact proof? Without simply stating that for sure the matrix can be transformed to some kind of other form etc?

Answer 1

$A$ corresponds to a linear map $T_A: \Bbb R^{n+1} \to \Bbb R^n$.

By one of the fundamental theorems on linear maps (see here e.g.):

$$n+1 = \dim(\Bbb R^{n+1}) = \dim(\operatorname{Im}(T_A)) + \dim(\operatorname{Ker}(T_A))$$

As $\dim(\operatorname{Im}(T_A)) \le \dim(\Bbb R^n)=n$ it follows that $\dim(\operatorname{Ker}(T_A)) \ge 1$ and it follows that if $Ax=b$ has one solution $x_0$ it has infinitely many solutions $x_0 + y$, where $y \in \operatorname{Ker}(T_A)$ and there are infinitely many such $y$ as the dimension is positive and $\Bbb R$ is infinite. It is perfectly possible that there is no solution as well. So $0$ or infinitely many solutions whenever the dimension of the domain exceeds that of the codomain.

Answer 2

This proof is lifted from "Linear Algebra and It's Applications" by David C. Lay

Let $A=[v_1...v_p]$ where each column is condensed into vectors of dimension $n$, then $A$ is $n \times p$, and the equation $Ax=0$ corresponds to a system of $n$ equations in $p$ unknowns. If $p>n$, there are more variables than equations, there must be be a free variable*. Hence $Ax=0$ has a nontrivial solution and the columns of $A$ are linearly dependent.

*You can see this statement is true: When a matrix is transformed into it's row reduced echelon form (which is always possible: see here), each row must contain a pivot point (basic variable) or be completely composed of zeros (free variable). The number of pivot points can never exceed the number of columns (because each column can only have, at most, one pivot point), so naturally, if the rows exceed the number of columns there must be a free variable.