# On the induction argument of the "many paths to a basis" theorem

I'm trying to make practical sense of the induction argument of the following famous theorem on the dimension of a finite-dimensional vector space.

Theorem Let $$n$$ be a positive integer. If $$V$$ is a vector space containing two lists of vectors $$x_1,\ldots,x_n$$ and $$y_1,\ldots,y_n$$ of the same length $$n$$, such that

(1) $$x_1,\ldots,x_n$$ generate $$V$$, and

(2) $$y_1,\ldots,y_n$$ are independent,

then both lists are bases of $$V$$.

Update: For your convenience I've updated the post adding the full proof.

In the proof below, $$\theta$$ denotes the zero vector of $$V$$.

Proof. We have to show that list (1) is independent and list (2) is generating. The proof is by induction on $$n$$. Let $$F$$ be the field of scalars.

Suppose $$n=1$$. By assumption, $$V = Fx_1$$ and $$y_1\neq \theta$$. Say $$y_1 = c x_1$$. Since $$y_1$$ is nonzero, both $$c$$ and $$x_1$$ are non zero. From $$x_1\neq\theta$$ we see that the list $$x_1$$ is independent. Since every vector is a multiple of $$x_1 = c^{-1}y_1$$, and therefore of $$y_1$$ the list $$y_1$$ is generating.

Let $$n\geq 2$$ and assume that the statement in the theorem is true for lists of length $$n-1$$.

We assert first that $$x_1,\ldots,x_n$$ are independent. Assume to the contrary that this list is linearly dependent, i.e. one of the $$x_i$$ is a linear combination of the others. Suppose, for illustration, that $$x_n$$ is a linear combination of $$x_1,\ldots,x_{n-1}$$. It follows that the list $$x_1,\ldots,x_{n-1}$$ generates $$V$$; for, its linear span includes $$x_n$$ as well as $$x_1,\ldots,x_{n-1}$$, so it must be all of $$V$$ by (1). Since the list $$y_1,\ldots,y_{n-1}$$ is independent by (2), it follows from the induction hypothesis that $$y_1,\ldots,y_{n-1}$$ generate $$V$$. In particular, $$y_n$$ is a linear combination of $$y_1,\ldots, y_{n-1}$$, contradicting (2). The contradiction shows that $$x_1,\ldots,x_{n}$$ is independent, as asserted.

The proof that $$y_1,\ldots, y_n$$ are generating will be accomplished by invoking the induction hypothesis in a suitable quotient space $$V/M$$; the first step is to construct an appropriate linear subspace $$M$$. Express $$y_n$$ as a linear combination of $$x_1,\ldots,x_n$$, say $$y_n = c_1x_1+\cdots+c_nx_n.$$ Since $$y_n\neq \theta$$, one of the coefficients $$c_i$$ must be nonzero; rearranging the $$x_i$$, we can suppose that $$c_n\neq 0$$. It follows that $$x_n = (-c_1/c_n)x_1+\cdots+(-c_{n-1}/c_n)x_{n-1}+(1/c_n)y_n,$$ thus the linear span of the list $$x_1,\ldots,x_{n-1},y_n$$ includes all of the vectors $$x_1,\ldots,x_n$$; in view of (1) we conclude that $$(*)\,\,\,\, x_1,\ldots,x_{n-1},y_n\,\,\text{generate } V.$$ Let $$M = Fy_n$$ and let $$Q:V\to V/M$$ be the quotient mapping. Then $$(3)\,\,\,\ Qx_1,\ldots,Qx_{n-1}\text{ generate } V/M$$

(by (*)) and $$(4)\,\,\,\ Qy_1,\ldots,Qy_{n-1}\text{ are independent}$$ (by (2)), so by the induction hypothesis, both the lists (3) and (4) are bases of $$V/M$$. In particular, the list (4) is generating for $$V/M$$; since $$M$$ is generated by $$y_n$$, it follows (from another result not shown here) that $$y_1,\ldots,y_n$$ generate $$V$$.

Q.E.D.

I'm stuck at the induction step (in bold). I do understand that the assumption is a necessary logical step which is given for truth without questioning, in order to show that what follows is true.

My question is:

if $$V$$ has basis $$x_1,\ldots,x_{n-1}$$, how can it also have (a larger) basis $$x_{1},\ldots,x_{n}$$?

• All bases of a vector space have the same number of elements. Aug 21, 2022 at 17:35
• Indeed a good question. The whole theorem is sort-of quantified with $(\forall V, V\text{ is a vector space})$... You assume that the statement is valid for $n-1$ for all vector spaces and then you prove it again for $n$, for all vector spaces. In the inductive step where you try to prove it for a vector space $V$ and number $n$, you will most likely apply the statement for the number $n-1$ to some other vector space, not $V$. (Perhaps it will be the span of $x_1,x_2,\ldots,x_{n-1}$.)
– user700480
Aug 21, 2022 at 17:41
• @JoséCarlosSantos yep $n$ is indeed unique. Aug 21, 2022 at 18:42
• You say yourself that the proof switches to "a quotient vector space". Maybe that is the space for which they use the statement with $n-1$ ?
– user700480
Aug 21, 2022 at 22:09
• @StinkingBishop no, the quotient vector space argument is used only for (2); see the updated post with the full (long!!) proof. Aug 22, 2022 at 21:38

It's not really clear from the statement of the theorem which sentence is proved by induction, I agree.

Consider this one: let $$n \in \mathbb{N}$$. Let us denote by $$P_n$$ the sentence:

for all vector space $$V$$, for all $$n$$-tuples $$(x_1,\cdots,x_n)$$ and $$(y_1,\cdots,y_n)$$ of vectors in $$V$$ such that the $$x_i$$'s generate $$V$$ and the $$y_j$$'s are linearly independent, then both are bases of $$V$$.

Now, let $$V$$ be a vector space, and $$n \in \mathbb{N}$$. Let us denote by $$Q_n$$ the sentence: for all $$n$$-tuples $$(x_1,\cdots,x_n)$$ and $$(y_1,\cdots,y_n)$$ of vectors in $$V$$ such that the $$x_i$$'s generate $$V$$ and the $$y_j$$'s are linearly independent, then both are bases.

Then $$\forall n\in \mathbb{N},\ P_n$$ can certainly be proved by induction, following the proof of your book, perhaps by making some things a bit more precise. The assertion $$\forall n\in \mathbb{N},\ Q_n$$ is also true, but for other reasons. Indeed, if $$\dim V = n$$ then $$Q_n$$ is a particular case of $$P_n$$, so is true. However, if $$\dim V \neq n$$, then $$Q_n$$ is of the form $$\forall x \in \emptyset,\ blahblah$$ which is obviously true and is not relevant to vector spaces.

• @Plop (2) would be still vacuously true for any $n$ in any vector space. If $n$ is not the dimension, then antescedent (existence of such $x_1,\ldots,x_n,y_1,\ldots,y_n$) is always false.
– user700480
Aug 21, 2022 at 22:13
• Oh. You’re right…
– Plop
Aug 21, 2022 at 22:15
• see the updated post with the full proof of (1) and (2). again, thinking of a general different $V$ each time seems a bit odd. Could previous $V's$ be linear subsets of the current $V$, as is suggested in another answer? Aug 22, 2022 at 21:49

if $$V$$ has basis $$x_1,\ldots,x_{n-1}$$, how can it also have (a larger) basis $$x_{1},\ldots,x_{n}$$

The $$V$$s aren't the same in each step. You should take $$V'$$ to be a subset of $$V$$, and take $$x_1,\ldots,x_{n-1}$$ and $$y_1,\ldots,y_{n-1}$$ to both be lists of vectors within $$V'$$, where $$x_1,\ldots,x_{n-1}$$ generate $$V'$$, and $$y_1,\ldots,y_{n-1}$$ are independent, and both are bases of $$V'$$ (this is a weaker version of the induction hypothesis, as the induction speaks of all possible lists of size $$n-1$$, not just for a particular subset of $$V$$). Then augment each by arbitrary $$x_{n}$$ and $$y_{n}$$, respectively, with $$x_1,\ldots,x_{n}$$ generating $$V$$, and $$y_1,\ldots,y_{n}$$ independent, and prove that these augmented lists are both bases of $$V$$.

• Thanks. Yes, it seems that V at n-1 must be a subset of the current V, as also others seem to suggest. Aug 22, 2022 at 22:29