# 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. Add to solve later

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\\
\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\\
\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

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 […]

This site uses Akismet to reduce spam. Learn how your comment data is processed.

###### More in Linear Algebra ##### 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