Alternative proofs of “length of linearly independent list is less than or equal to length of spanning list”

Question

I’m reading Linear Algebra Done Right by Sheldon Axler. Theorem 2.23 states that the length of a linearly independent list is always less than or equal to the length of a spanning list in a finite dimensional vector space. To prove this, Axler uses a process of inductively adding vectors from the basis to the spanning set, and then deleting elements of the spanning set from this list, so you’re left with a list that contains all elements of the basis and potentially some elements of the spanning set you started with.

Does anyone know of an alternative way of proving this fact? To me this seemed like a not completely intuitive process to prove something so simple.

Full description of proof here: Length of linearly independent list is less than or equal to length of spanning list

Answer 1

Sure: suppose $\mathbf{l}_1, \ldots, \mathbf{l}_n$ is any sequence of vectors and that $\mathbf{s}_1, \ldots, \mathbf{s}_m$ spans. Each $\mathbf{l}_j$ can be written as a linear combination of the $s_i$, so for each $j$ we may write $\mathbf{l}_j = \sum_i a_{ij} \mathbf{s}_i$ for scalars $a_{ij}$. The matrix $A = (a_{ij})$ is $m \times n$ and if $m < n$ there are more columns than rows ("more variables than equations") so there must be a non-zero solution $\mathbf{v}$ to $A \mathbf{x} = \mathbf{0}$. That means $\sum_j a_{ij}v_j = 0$ for all $i$, so $\sum_j v_j \mathbf{l}_j = \sum_j v_j \sum_{i}a_{ij}\mathbf{s}_i = \sum_i \left( \sum_j a_{ij}v_j \mathbf{l}_i \right) = \sum_i 0\cdot \mathbf{l}_i = \mathbf{0}$ and so the sequence $\mathbf{l}_1, \ldots, \mathbf{l}_n$ is linearly dependent.

Of course, you must somehow justify the statement that a homogeneous linear system with more variables than equations has a nonzero solution, or equivalently, that any $n+1$ vectors in $\mathbb{F}^n$ are linearly dependent. "Classically" if you want to avoid the swapping-in method of Axler you might do this by row reduction: show that doing row operations doesn't change the solution set of a linear system, then show that a system of this shape can be transformed by row ops to a form where it "obviously" has nonzero solutions. But really I don't agree that this result is "so simple" - it's a non-trivial theorem and so you should expect the proof to have non-trivial ideas in it.

Answer 2

The below proof corresponds to the explanation given by @egreg in the link the OP had provided.

---

Let $X$ be a vector space over some field $\mathbb{F}$. Let a list of vectors $x_1, \ldots, x_n \in X$ span $X$, that is, span$(x_1, \ldots, x_n) = X$. Also, suppose there is a list of vectors $y_1, \ldots, y_j \in X$ such that they are linearly independent. We wish to show $j \leq n$.

Since span$(x_1, \ldots, x_n) = X$, every vector in $X$ can be expressed as a linear combination of $x_1, \ldots, x_n$. In particular,

$$ y_1 = k_1x_1 + \cdots + k_nx_n $$

where $k_1, \ldots, k_n \in \mathbb{F}$ and $y_1 \neq 0$. We can rewrite this equation in the following way:

$$ x_1 = \left(\frac{1}{k_1}\right)y_1 + \left(-\frac{k_2}{k_1}\right)x_2 + \cdots + \left(-\frac{k_n}{k_1}\right)x_n $$

where $\frac{1}{k_1}, -\frac{k_2}{k_1}, \ldots, -\frac{k_n}{k_1} \in \mathbb{F}$. This shows that $x_1$ can be expressed as a linear combination of $y_1, x_2, \ldots, x_n$, which implies that we can replace $x_1$ in span$(x_1, \ldots, x_n)$ by $y_1$, that is,

$$ \text{span}(y_1, x_2, \ldots, x_n) = X $$

We are now in position to show $j \leq n$. We will do so by assuming instead that $j > n$, which will lead to a contradiction. Since if $j > n$, repeating the above process of expressing $y_i$ as a linear combination of each new span for $i = 2, \ldots, n$, we attain the list of vectors $y_1, \ldots, y_n$ which span $X$. This implies, without loss of generality,

$$ y_{n+1} = a_1y_1 + \cdots + a_ny_n $$

where $a_1, \ldots, a_n \in \mathbb{F}$ and $y_{n+1} \neq 0$. Adding the additive inverse of $y_{n+1}$ to both sides, we have:

\begin{align} 0 &= a_1y_1 + \cdots + a_ny_n - y_{n+1} \\ &= a_1y_1 + \cdots + a_ny_n - y_{n+1} + 0y_{n+2} + \cdots + 0y_j \end{align}

showing that the coefficient of $y_{n+1}$ is non-zero. But this contradicts that the list of vectors $y_1, \ldots, y_n, y_{n+1}, \ldots, y_j$ is linearly independent (since if $y_1, \ldots, y_n, y_{n+1}, \ldots, y_j$ is linearly independent, the coefficients $a_1, \ldots, a_n, a_{n+1}, \ldots, a_j$ in the equation $0 = a_1y_1 + \cdots + a_ny_n + a_{n+1}y_{n+1} + \cdots + a_jy_j$ must all equal zero).

Hence, we must have that $j \leq n$.

Answer 3

$ \newcommand{\span}{\operatorname{span}} $

This explanation requires the notion of a quotient vector space, which may or may not have been introduced. However, it does not require any unproven statements about dimension of quotient spaces. At its core, when you untangle Axler's proof and this one it's a similar idea, but hopefully this presentation gives a little additional insight.

I assume our working definition of a finite dimensional vector space $V$ is one that is spanned by a finite set of vectors, and the dimension $\dim V$ is the minimal size of a spanning set.

Lemma. Let $I\subset V$ be nonempty and linearly independent, and let $u\in V$ be nonzero. Then for some $v\in I$, $u\notin \span(I\backslash \{v\})$.

The proof of the lemma follows from the fact that if $u\in \span(I)$, it can be written as a unique linear combination $\sum_{v\in I}\lambda_v v$, so since $u\neq 0$, choose any $v\in I$ with $\lambda_v\neq 0$, and $u$ cannot be written as a linear combination of the other vectors in $I$ by uniqueness. (If $u\notin \span(I)$, we may choose any $v\in I$).

Now to prove the main result, we use induction on $\dim V$. If $\dim V=0$, then there are no nonzero vectors, so that every linearly independent set is empty, and the result is trivial.

If the result holds whenever $\dim V\leq k$, then suppose $\dim V=k+1$, so that $V=\span(S)$ with $|S|=k+1$. Then let $W=\span(u)$ for some nonzero $u\in S$, so that $$V/W=\span(\{u'+W\mid u'\in S\backslash \{u\}\}),$$ whereby $\dim(V/W)\leq k$.

Suppose $I\subset V$ is nonempty and independent. By the lemma, there is some $v\in I$ such that $u\notin \span(I\backslash \{v\})$. It follows that $W\cap \span(I\backslash \{v\}) =\{0\}$, and therefore $\{v'+W\mid v'\in I\backslash \{v\}\}$ is independent in $V/W$. Therefore by our inductive assumption we have $$|I\backslash\{v\}| = |\{v'+W\mid v'\in I\backslash \{v\}\}|\leq k,$$ so we conclude $|I|\leq k+1$.