Prove that $n+1$ vectors in $\mathbb{R}^n$ cannot be linearly independent

Question

I was looking for a short snazzy proof on the following statement:

n+1 vectors in $\mathbb{R}^n$ cannot be linearly independent

A student of mine asked this today morning and I couldn't come up with a proof solely from the definition of linear independence.

From a higher level perspective, I explained that if I put the vectors in a matrix then if the only null space entry is the zero vector, then the vectors are independent but since we have one extra column than row and that the row and column rank are equal, there is no way we can have $n+1$ as the rank of the matrix and hence from Rank-Nullity theorem, the dimension of the Nullspace is at least one which implies that there is a combination of the vectors where not all the scalar multiples in the definition are 0 but yet we get a zero as the linear combination. The student hasn't completely learnt the fundamental subspaces yet so I am not sure he grasped what I was saying.

Is there a cleaner proof?

EDIT: I am stunned how many beautiful answers I got with so much diversity.

Answer 1

Let denote $(e_1,\ldots,e_n)$ the standard basis of $\mathbb R^n$ and suppose that $(f_1,\ldots,f_{n+1})$ a set of linearly independent vectors. We can write $$f_1=\sum_{k=1}^n a_k e_k$$ and since $f_1\ne 0$ there's $a_k\ne 0$ and WLOG suppose $a_1\neq0$ so $$e_1=\frac{1}{a_1}\left(f_1-\sum_{k=2}^n a_k e_k\right)$$ hence we see that $(f_1,e_2,\ldots,e_n)$ spans $\mathbb R^n$.

Now repeat $n$ times the same method (induction) and we find that $(f_1,\ldots,f_{n})$ spans $\mathbb R^n$ so the vectors $f_{n+1}$ is a linear combination of the other vectors $f_i$ which is a contradiction.

If the induction step was not obvious, consider the following:

Since we have established that $(f_1,e_2,\ldots,e_n)$ spans $\mathbb R^n$, write

$$f_2=b_1f_1+\sum_{k=2}^n b_k e_k$$

Since $f_2\neq0$, there's at least one $b_l\neq0$. Also note that not all $(b_2,b_3,\ldots,b_n)$ can be zero because otherwise it would imply that $f_2=b_1f_1$ contradicting the assumed linear independence of $(f_1,\ldots,f_{n+1})$. So we can take $b_l\neq0$ where $l\geq 2$. WLOG suppose $b_3\neq0$. Now,

$$e_3=\frac{1}{b_3}\left(f_2-b_1f_1-b_2e_2-\sum_{k=4}^n b_k e_k\right)$$

From this we see that, $(f_1,e_2,f_2,e_4,\ldots,e_n)$ spans $\mathbb R^n$, where we replaced $e_3$ with $f_2$. The assumed linear independence of the $f_i$'s means that we can repeat this process to replaces all the $e_i$'s.

Answer 2

You can prove the following, directly.

Let $V$ have dimension $n$, and let $\{w_1,\ldots,w_r\}$ be a set of linearly independent vectors in $V$. Then $r\leq n$.

P Let $\{v_1,\ldots,v_n\}$ be a basis for $V$. Write for each $i=1,2,\ldots,r$

$$w_i=\sum_{j=1}^n {\alpha_{ij}}v_j$$

Consider the homogeneous system of $n$ equations and $r$ unknowns, $1\leq j\leq n$. $$\sum_{i=1}^r a_{ij}x_i=0$$

and suppose we have a solution $\{\omega_1,\ldots,\omega_r\}$. This means that $$\begin{align}\sum_{i=1}^r\omega_i w_i&=\sum_{i=1}^r\omega_i\sum_{j=1}^na_{ij}v_j\\&=\sum_{j=1}^n\left(\sum_{i=1}^r a_{ij}\omega_i\right)v_j=0\end{align}$$

thus by linear independence we must have $\omega_i=0, i=1,\ldots, r$. It follows that the homogeneous system admits only the trivial solution, so we must have $r\leq n$. Thus any set of $k>n$ vectors must be linearly dependent. This rests on the fact that any homogeneous system with more equations than unknowns must admit a nontrivial solution, which is something (I guess) most of (us) students are aware of.

Answer 3

Essentially the same: Let $n\in\mathbb N_0$ be minimal such that there are $v_0,\ldots,v_n\in F^n$ that are linearly independent. Then clearly $n>0$ as the only choice of $v_0\in F^0$ is linearly dependent. Let $\pi_n(v)$ denote the $n$th component of vector $v$. If we have $\pi_n(v_i)=0$ for all $i$, we can in fact view the vectors as elements of $F^{n-1}$, where they are still independent, contradicting minimality of $n$. Therefore, at least one vector, wlog. $v_n$, has nonzero $n$th component. Let $w_i=v_i-\frac{\pi_n(v_i)}{\pi_n(v_n)}v_n$ for $0\le i<n$. Then $\pi_n(w_i)=0$ and hence we can view the $w_i$ as elements of $F^{n-1}$. By minimality of $n$, the vectors $w_0,\ldots,w_{n-1}\in F^{n-1}$ are linearly dependent, hence $\sum c_iw_i=0$ with nontrivial $c_i\in F$. Then $$ \sum_{i=0}^{n-1}c_iv_i-\left(\sum_{i=0}^{n-1}\frac{c_i\pi_n(v_i)}{\pi_n(v_n)}\right)v_n=0$$ contradiciton.

Answer 4

Take your idea: you put the $n+1$ vectors as rows of a matrix, so you get an $(n+1) \times n$ matrix.

Now, do Gaussian elimination. You get a zero row. That zero row is a nontrivial linear combination of the rows of your matrix.

Thus, linear dependence.

It may help to first say some words about the rowspace of this matrix being the same as the span of your $n+1$ vectors, or somesuch.

Answer 5

More as a private exercise than to answer this particular question, I've tried to write a proof of the main facts leading to the definition of dimension, using only the basic definitions of linear combination, span, linear dependence, spanning set, and basis; apart from that I assume only some intuitively (and formally) obvious facts as that a subset of a linear independent set is linearly independent. I work in finitely generated vector spaces, but since I don't know the existence of bases at the outset, I cannot limit myself to spaces $\Bbb R^n$.

I know that the Steinitz exchange lemma achieves this, doing everything in one fell swoop, but I think the resulting inductive proof is somewhat technical, and I would like to avoid vagueness such as "up to reordering" and "without loss of generality". I've tried to achieve this by splitting out different levels of detail, which leads to avoiding equations almost altogether. Nonetheless I'm somewhat dissatisfied with my formulation, especially of the final proof which looks harder on paper than it did in my imagination.

One must of course at some point use invertibility of nonzero scalars; to get that out of the way, I start with a simple lemma about linear dependence. Then comes a proposition that constructs bases, explicitly, but without concern for counting elements. The latter is done in the final theorem, which is really just a commentary on the construction in the proposition.

I talk mostly about families of vectors rather than about sets, because everything depends in an essential way on the ordering implied by the indices (and because multiple occurrences of the same vector are not excluded); however I use set builder notation for convenience, which is not really consistent with that point of view. I think that the proposition below can be generalised to the infinite dimensional situation using families of vectors indexed by a well-ordered set, but for the theorem would doubt that it can be done.

For the record, all this requires no commutativity, and works painlessly for finitely generated (say) right modules over a division ring. I would expect this to be true for any proof of these matters, if carefully written.

Lemma. If some linear relation between members of a set $X$ of vectors involves some vector $v\in X$ with nonzero coefficient$~c_v$, then $v$ is a linear combination of the remaining vectors: $\def\Span{\operatorname{Span}}v\in\Span(X-\{v\})$.

Write the relation $\sum_{x\in X}c_xx=0$ as $c_vv=-\sum_{x\in X-\{v\}}c_xx$; now multiply by $c_v^{-1}$ (using that $c_v\neq0$).

Proposition. If $S=\{f_1,\ldots,f_k\}$ is a linearly independent family of vectors in$~V$, and $T=\{g_1,\ldots,g_l\}$ is a family of vectors spanning$~V$, then $V$ has a basis $S\cup C$, where $$C=\{\,g_i\mid\,g_i\notin\Span(S\cup\{g_1,\ldots,g_{i-1}\})\}\subseteq T.$$

For $0\leq i\leq l$, put $X_i=S\cup\{g_1,\ldots,g_i\}$ and $X_i'=S\cup(\{g_1,\ldots,g_i\}\cap C)$; we show by induction on $i$ that the set $X_i'$ is a linearly independent family spanning$~\Span(X_i)$ (in other words a basis of that subspace); the instance $i=l$ gives the proposition since $\Span(X_l)\supseteq\Span(T)=V$. For $i=0$ this holds by the linear independence of $S$. For $i>0$ one distinguishes cases $g_i\notin C$ and $g_i\in C$, both of which are easy. For $g_i\notin C$ one uses that adding to $X_{i-1}$ the vector $g_i$ already in its span does not change that span. For $g_i\in C$ one uses adding the same vector $g_i$ to two sets $X_{i-1},X_{i-1}'$ with the same span keeps their span the same, while $g_i\notin\Span(X_{i-1})=\Span(X_{i-1}')$ ensures that the independent family $X_{i-1}'$ remains independent after adding$~g_i$ (the contrapositive of the lemma says that any linear relation involves only $X_{i-1}'$, and so is trivial).

Now, for any independent family$~S$ and spanning family$~T$, denote by $C(S,T)$ the set $C$ of the proposition, and by $E(S,T)$ the basis $S\cup C(S,T)=S\cup C$ of the proposition. We get in particular, for any space admitting a finite spanning set$~T$ (finitely generated space), a basis $E(\emptyset,T)$ of$~V$. On the other hand for any basis $B$ of$~V$ one has $E(B,T)=B$, since $C=\emptyset$ in the proposition. We can now show that dimension is well defined in the case of finitely generated spaces.

Theorem. For any $S,T$ as above, the basis $E(S,T)$ has the same number of elements as $E(\emptyset,T)$.

Proof is by induction on the size of$~S$, the case $S=\emptyset$ being trivial. So consider $S=\{f_1,\ldots,f_k\}$ with $k>0$, and assuming the result holds for $S^-=\{f_1,\ldots,f_{k-1}\}$. From the definition it is clear that $C(S,T)\subseteq C(S^-,T)$, and we must show that the complement $C(S^-,T)\setminus C(S,T)$ contains exactly one element. Since $E(S^-,T)$ is a basis of$~V$, there is a unique expression of $f_k$ as linear combination$~L$ of its elements. That combination involves some element of$~C(S^-,T)$ with nonzero coefficient, because the family$~S$ is linearly independent. If $i$ is maximal such that $g_i\in C(S^-,T)$ appears with nonzero coefficient in$~L$, then by the lemma $g_i\in\Span(f_1,\ldots,f_k,g_1,\ldots,g_{i-1})$, and therefore $g_i\in C(S^-,T)\setminus C(S,T)$. Conversely if $g_j\in C(S^-,T)\setminus C(S,T)$ then $g_j\in\Span(\{f_1,\ldots,f_k,g_1,\ldots,g_{j-1}\}\cap E(S,T))$ and the linear combination witnessing this must involve $f_k$ with nonzero coefficient (because of $g_j\in C(S^-,T)$); by the lemma and the uniqueness of the expression$~L$ for $f_k$ this forces $j=i$, completing the proof.

Answer 6

If there are $n+1$ linearly independent vectors in a vector space $V$, then $\operatorname {dim}V\ge n+1$.

But, as is well-known, $\operatorname {dim}\Bbb R^n=n$.

The result follows.

(Perhaps see Hurewicz and Wallman's classic Dimension Theory.)