5
$\begingroup$

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}$?

$\endgroup$
5
  • 2
    $\begingroup$ All bases of a vector space have the same number of elements. $\endgroup$ Aug 21, 2022 at 17:35
  • 3
    $\begingroup$ 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}$.) $\endgroup$
    – user700480
    Aug 21, 2022 at 17:41
  • $\begingroup$ @JoséCarlosSantos yep $n$ is indeed unique. $\endgroup$
    – utobi
    Aug 21, 2022 at 18:42
  • 1
    $\begingroup$ 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$ ? $\endgroup$
    – user700480
    Aug 21, 2022 at 22:09
  • $\begingroup$ @StinkingBishop no, the quotient vector space argument is used only for (2); see the updated post with the full (long!!) proof. $\endgroup$
    – utobi
    Aug 22, 2022 at 21:38

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ @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. $\endgroup$
    – user700480
    Aug 21, 2022 at 22:13
  • $\begingroup$ Oh. You’re right… $\endgroup$
    – Plop
    Aug 21, 2022 at 22:15
  • $\begingroup$ 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? $\endgroup$
    – utobi
    Aug 22, 2022 at 21:49
1
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .