Why Too Many Vectors Must Be Dependent

Why a Finite Basis Sets a Limit

A basis is a list that both spans a vector space and is linearly independent. If a vector space has a basis with \(n\) vectors, it is natural to ask whether a longer list in that space can also be independent. The exchange lemma gives a way to answer: a new vector can replace a suitable vector in a spanning basis without losing the basis property. Repeating this replacement shows that after \(n\) independent insertions, no further vector can be added while preserving independence.

We work over a scalar field \(\mathbb{F}\), which may be \(\mathbb{R}\) or \(\mathbb{C}\). A list \((\mathbf{b}_1,\dots,\mathbf{b}_n)\) in a vector space \(V\) is a basis if it spans \(V\) and is linearly independent. It spans \(V\) when every vector in \(V\) is a linear combination of its entries. It is linearly independent when the equation \(c_1\mathbf{b}_1+\cdots+c_n\mathbf{b}_n=\mathbf{0}\) forces every coefficient \(c_i\) to be zero. The number \(n\) here is the length of the particular basis we are using.

The result below concerns lists, not just sets: each position in a list has its own coefficient, even if some entries happen to be equal. It also requires a finite basis. The replacement argument works because there are only finitely many basis vectors to exchange.

The Exchange Lemma

Proof. First, the replacement list spans \(V\). Since \(a_k\ne0\), rearranging the expression for \(\mathbf{w}\) gives \(\mathbf{b}_k=\frac{1}{a_k}\bigl(\mathbf{w}-\sum_{i\ne k}a_i\mathbf{b}_i\bigr)\). Thus the omitted vector \(\mathbf{b}_k\) is a linear combination of the replacement list. Every vector in \(V\) was already a linear combination of the original basis, so it is also a linear combination of the replacement list. To prove independence, suppose \(c\mathbf{w}+\sum_{i\ne k}c_i\mathbf{b}_i=\mathbf{0}\). Substituting the expression for \(\mathbf{w}\), the coefficient of \(\mathbf{b}_k\) in this combination of the original basis is \(ca_k\). Independence of the original basis forces \(ca_k=0\), so \(c=0\) because \(a_k\ne0\). The remaining equation is \(\sum_{i\ne k}c_i\mathbf{b}_i=\mathbf{0}\), and independence of the original basis forces every \(c_i=0\). The replacement list is both spanning and independent, so it is a basis. \(\square\)

The condition \(a_k\ne0\) matters: the vector being inserted must have a nonzero coefficient on the basis vector being removed. When there is more than one such coefficient, any corresponding basis vector can be replaced. The lemma does not say that an arbitrary basis vector can be removed.

Too Many Vectors Must Be Dependent

Proof. If \(n=0\), the empty basis spans \(V\), so \(V=\{\mathbf{0}\}\). Since \(p>0\), the list contains at least one vector, and every vector in it is \(\mathbf{0}\). Giving one entry coefficient \(1\) and all other entries coefficient \(0\) produces a nontrivial relation. Now suppose \(n\ge1\), and start with a basis \((\mathbf{b}_1,\dots,\mathbf{b}_n)\). We process \(\mathbf{v}_1,\dots,\mathbf{v}_n\) in order. At stage \(j\), either the first \(j\) vectors are already dependent, or the current basis has the form \((\mathbf{v}_1,\dots,\mathbf{v}_{j-1},\mathbf{c}_j,\dots,\mathbf{c}_n)\), where the \(\mathbf{c}_i\) are the basis vectors not yet replaced. This holds initially, before processing any vectors, because the current basis is the original one.

If \(\mathbf{v}_j\) lies in \(\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_{j-1}\}\), it is a linear combination of the preceding vectors. Moving that combination to one side gives a nontrivial relation among the first \(j\) vectors: the coefficient on \(\mathbf{v}_j\) is \(1\). For \(j=1\), the span of the empty list is \(\{\mathbf{0}\}\), so this case means \(\mathbf{v}_1=\mathbf{0}\), which is also a nontrivial dependence relation.

Otherwise, express \(\mathbf{v}_j\) as a linear combination of the current basis. At least one coefficient on \(\mathbf{c}_j,\dots,\mathbf{c}_n\) must be nonzero. If all those coefficients were zero, the expression would put \(\mathbf{v}_j\) in the span of \(\mathbf{v}_1,\dots,\mathbf{v}_{j-1}\), contrary to this case. The exchange lemma therefore lets us replace a \(\mathbf{c}_i\) with nonzero coefficient by \(\mathbf{v}_j\). The resulting list is again a basis, and the stage condition holds for \(j+1\).

Consequently, either a dependence has been found by stage \(n\), or the resulting basis contains \(\mathbf{v}_1,\dots,\mathbf{v}_n\). In the latter case, \(p>n\) ensures that \(\mathbf{v}_{n+1}\) exists. It is a linear combination of the basis vectors, so subtracting that combination from \(\mathbf{v}_{n+1}\) gives a relation among \(\mathbf{v}_1,\dots,\mathbf{v}_{n+1}\) with coefficient \(1\) on \(\mathbf{v}_{n+1}\). In either case, the first \(n+1\) entries have a nontrivial relation. Giving every later entry coefficient \(0\) makes this a nontrivial relation for the full list, so the full list is dependent. \(\square\)

The proof is a controlled replacement process. At each stage, either the new vector is already made from vectors previously inserted, giving a dependence relation immediately, or it can replace one of the original basis vectors that remain. Once \(n\) vectors have been inserted without a dependence relation, the list already contains a basis, so the next vector is forced to be a combination of those vectors.

Worked Examples in \(\mathbb{R}^n\)

What the Theorem Does—and Does Not—Say

The theorem guarantees the existence of a nontrivial relation; it does not identify in advance which vectors will have nonzero coefficients in that relation. In particular, the relation need not use every entry of the list. In the five-vector example, the last vector has coefficient zero. This is still enough to establish dependence because the other coefficients are not all zero.

A common mistake is to test only whether pairs of vectors are scalar multiples. For instance, \(\begin{bmatrix}1\\0\end{bmatrix}\), \(\begin{bmatrix}0\\1\end{bmatrix}\), and \(\begin{bmatrix}1\\1\end{bmatrix}\) in \(\mathbb{R}^2\) have no pair in which one vector is a scalar multiple of the other. It would be wrong to conclude that the three-vector list is independent: the first two add to the third, so \(\begin{bmatrix}1\\0\end{bmatrix}+\begin{bmatrix}0\\1\end{bmatrix}-\begin{bmatrix}1\\1\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\). Pairwise checks do not rule out a relation involving three or more vectors.

There is a related error in applying the exchange lemma. Starting with the basis \((\mathbf{e}_1,\mathbf{e}_2)\) of \(\mathbb{R}^2\), let \(\mathbf{w}=2\mathbf{e}_1\). A wrong exchange would remove \(\mathbf{e}_2\), claiming that \((\mathbf{e}_1,\mathbf{w})\) is a basis. But \(\mathbf{w}\) has coefficient \(0\) on \(\mathbf{e}_2\), and the proposed list is dependent because \(\mathbf{w}-2\mathbf{e}_1=\mathbf{0}\); it also cannot span \(\mathbf{e}_2\). The correction is to remove \(\mathbf{e}_1\), whose coefficient in \(\mathbf{w}\) is \(2\ne0\). The exchange lemma then gives the basis \((\mathbf{w},\mathbf{e}_2)\).

The conclusion here is specifically about lists longer than a finite basis. It does not settle whether a shorter list can span; that is a different question. For the result proved here, the essential steps are to track which basis vectors remain available for exchange, check that a replacement coefficient is nonzero, and keep the full list—not merely a set of distinct vectors—in view.