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

Sponsored Links

Contents

We give two proofs. The essential ideas behind those two proofs are the same.

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 ↴

Sponsored Links

### 1 Response

1. 10/02/2017

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

##### Three Linearly Independent Vectors in $\R^3$ Form a Basis. Three Vectors Spanning $\R^3$ Form a Basis.

Let $B=\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$ be a set of three-dimensional vectors in $\R^3$. (a) Prove that if the set $B$ is...

Close