# If there are More Vectors Than a Spanning Set, then Vectors are Linearly Dependent

## Problem 576

Let $V$ be a subspace of $\R^n$.

Suppose that

\[S=\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\}\]
is a spanning set for $V$.

Prove that any set of $m+1$ or more vectors in $V$ is linearly dependent.

Contents

The second proofs uses matrix equations to organize clutter of a system of linear equations.

## Proof 1.

Consider the set $T=\{\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_k\}$ of $k$ vectors in the subspace $V$, where $k\geq m+1$.

We prove that the set $T$ is linearly dependent.

Consider the linear combination

\[x_1\mathbf{u}_1+x_2\mathbf{u}_2+\cdots+x_k \mathbf{u}_k=\mathbf{0}, \tag{*}\]
where $\mathbf{0}$ is the zero vector of $\R^n$.

Our goal is to find a nonzero solution $x_1, x_2, \dots, x_n$ of this equation.

As $S$ is a spanning set for $V$, each vector $\mathbf{v}_i$ in $T$ can be written as a linear combination of vectors in $S$.

So we have

\begin{align*}

\mathbf{u}_1&=a_{11}\mathbf{v}_1+a_{21}\mathbf{v}_2+\cdots +a_{m1}\mathbf{v}_m\\

\mathbf{u}_2&=a_{12}\mathbf{v}_1+a_{22}\mathbf{v}_2+\cdots +a_{m2}\mathbf{v}_m\\

\vdots &\qquad \vdots\\

\mathbf{u}_k&=a_{1k}\mathbf{v}_1+a_{2k}\mathbf{v}_2+\cdots +a_{mk}\mathbf{v}_m.\\

\end{align*}

Here $a_{ij} \in \R$ for $1\leq i \leq m$, $1\leq j \leq k$.

Using these linear combination, the equation (*) can be written as

\begin{align*}

x_1(a_{11}\mathbf{v}_1+a_{21}\mathbf{v}_2+\cdots +a_{m1}\mathbf{v}_m)+x_2(a_{12}\mathbf{v}_1+a_{22}\mathbf{v}_2+\cdots +a_{m2}\mathbf{v}_m)\\

+\cdots+x_k(a_{1k}\mathbf{v}_1+a_{2k}\mathbf{v}_2+\cdots +a_{mk}\mathbf{v}_m)=\mathbf{0}.

\end{align*}

Rearranging terms, we obtain

\begin{align*}

&(a_{11}x_1+a_{12}x_2+\cdots+a_{1k} x_k)\mathbf{v}_1+(a_{21}x_1+a_{22}x_2+\cdots+a_{2k} x_k)\mathbf{v}_2\\

+&\dots+(a_{m1}x_1+a_{m2}x_2+\cdots+a_{mk} x_k)\mathbf{v}_m=\mathbf{0}. \tag{**}\\

\end{align*}

Now it suffices to find a nonzero $x_1, \dots x_k$ such that the coefficients of $\mathbf{v}_1, \dots, \mathbf{v}_m$ in (**) are all zero.

Thus, we need to find a nonzero solution of the following system.

\begin{align*}

a_{11}x_1+a_{12}x_2+\cdots+a_{1k} x_k&=0\\

a_{21}x_1+a_{22}x_2+\cdots+a_{2k} x_k&=0\\

\vdots &\\

a_{m1}x_1+a_{m2}x_2+\cdots+a_{mk} x_k&=0.

\end{align*}

Observe that this is a $m\times k$ homogeneous system and as $m+1\leq k$, there are more variables than equations.

Hence this homogeneous system has infinitely many solutions, in particular, it has a nonzero solution $x_1, \dots, x_k$.

Hence the equation (**) and, equivalently, the equation (*) has a nonzero solution $x_1, \dots, x_k$.

Therefore the set $T$ is linearly dependent. This completes the proof.

## Proof 2.

Let $T=\{\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_k\}$ be the set of $k$ vectors in the subspace $V$, where $k\geq m+1$.

We want to show that $T$ is linearly dependent.

This is equivalent to finding a nonzero solution $x_1, \dots, x_k$ of the equation

\[x_1\mathbf{u}_1+x_2\mathbf{u}_2+\cdots+x_k \mathbf{u}_k=\mathbf{0}.\]
The equation can be written as

\[U\mathbf{x}=\mathbf{0}, \tag{***}\]
where

\[U=[\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_k] \text{ and } \mathbf{x}=\begin{bmatrix}

x_1 \\

x_2 \\

\vdots \\

x_k

\end{bmatrix}.\]
Note that $U$ is an $n \times k$ matrix.

Since the subspace $V$ is spanned by the set $S=\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\}$, we have

\begin{align*}

\mathbf{u}_1&=a_{11}\mathbf{v}_1+a_{21}\mathbf{v}_2+\cdots +a_{m1}\mathbf{v}_m\\

\mathbf{u}_2&=a_{12}\mathbf{v}_1+a_{22}\mathbf{v}_2+\cdots +a_{m2}\mathbf{v}_m\\

\vdots &\qquad \vdots\\

\mathbf{u}_k&=a_{1k}\mathbf{v}_1+a_{2k}\mathbf{v}_2+\cdots +a_{mk}\mathbf{v}_m.\\

\end{align*}

Let $V=[\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m]$ be the $n\times m$ matrix whose column vectors are $\mathbf{v}_1, \dots, \mathbf{v}_m$.

Then the above linear combinations can be expressed as

\[V\begin{bmatrix}

a_{11} \\

a_{21} \\

\vdots \\

a_{m1}

\end{bmatrix}=\mathbf{u}_1, V\begin{bmatrix}

a_{12} \\

a_{22} \\

\vdots \\

a_{m2}

\end{bmatrix}=\mathbf{u}_2, \dots, V\begin{bmatrix}

a_{1k} \\

a_{2k} \\

\vdots \\

a_{mk}

\end{bmatrix}=\mathbf{u}_k. \]

Combining these into one matrix equation, we obtain

\[VA=U,\]
where

Every Basis of a Subspace Has the Same Number of Vectors \[A=\begin{bmatrix}

a_{1 1} & a_{1 2} & \cdots & a_{1 k} \\

a_{2 1} & a_{2 2} & \cdots & a_{2 k} \\

\vdots & \vdots & \ddots & \vdots \\

a_{m 1} & a_{m 2} & \cdots & a_{m k}

\end{bmatrix}.\]

Thus, the equation (***) becomes

\[VA\mathbf{x}=\mathbf{0}.\]
Note that $A$ is an $m\times k$ matrix with $k >m$.

So the homogeneous system $A\mathbf{x}=\mathbf{0}$ has a nonzero solution $\mathbf{x}=\mathbf{x}_0$ since there are more variables than equations.

Hence we have $VA\mathbf{x}_0=V\mathbf{0}=\mathbf{0}$, and the equation (***) has a nonzero solution $\mathbf{x}_0$.

Thus we conclude that the set $T$ is linearly dependent, which completes the proof.

## Related Question.

As an application of this problem, you may want to prove the following problem.

**Problem**.

Let $V$ be a subspace of $\R^n$.

Suppose that $B=\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_k\}$ is a basis of the subspace $V$.

Prove that every basis of $V$ consists of $k$ vectors in $V$.

The proof of this problem is given in the post ↴

Add to solve later

## 1 Response

[…] For a proof of this fact, see the post ↴ If there are More Vectors Than a Spanning Set, then Vectors are Linearly Dependent […]