# 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

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 ↴

### More from my site

• Can We Reduce the Number of Vectors in a Spanning Set? Suppose that a set of vectors $S_1=\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$ is a spanning set of a subspace $V$ in $\R^3$. Is it possible that $S_2=\{\mathbf{v}_1\}$ is a spanning set for $V$?   Solution. Yes, in general, $S_2$ can be a spanning set. As an […]
• The Subset Consisting of the Zero Vector is a Subspace and its Dimension is Zero Let $V$ be a subset of the vector space $\R^n$ consisting only of the zero vector of $\R^n$. Namely $V=\{\mathbf{0}\}$. Then prove that $V$ is a subspace of $\R^n$.   Proof. To prove that $V=\{\mathbf{0}\}$ is a subspace of $\R^n$, we check the following subspace […]
• Every Basis of a Subspace Has the Same Number of Vectors 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$.   Hint. You may use the following fact: Fact. If […]
• Row Equivalent Matrix, Bases for the Null Space, Range, and Row Space of a Matrix Let $A=\begin{bmatrix} 1 & 1 & 2 \\ 2 &2 &4 \\ 2 & 3 & 5 \end{bmatrix}.$ (a) Find a matrix $B$ in reduced row echelon form such that $B$ is row equivalent to the matrix $A$. (b) Find a basis for the null space of $A$. (c) Find a basis for the range of $A$ that […]
• The Subspace of Linear Combinations whose Sums of Coefficients are zero Let $V$ be a vector space over a scalar field $K$. Let $\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_k$ be vectors in $V$ and consider the subset $W=\{a_1\mathbf{v}_1+a_2\mathbf{v}_2+\cdots+ a_k\mathbf{v}_k \mid a_1, a_2, \dots, a_k \in K \text{ and } […] • Linear Independent Vectors and the Vector Space Spanned By Them Let V be a vector space over a field K. Let \mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_n be linearly independent vectors in V. Let U be the subspace of V spanned by these vectors, that is, U=\Span \{\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_n\}. Let […] • Does an Extra Vector Change the Span? Suppose that a set of vectors S_1=\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\} is a spanning set of a subspace V in \R^5. If \mathbf{v}_4 is another vector in V, then is the set \[S_2=\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3, \mathbf{v}_4\}$ still a spanning set for […]
• Find a Spanning Set for the Vector Space of Skew-Symmetric Matrices Let $W$ be the set of $3\times 3$ skew-symmetric matrices. Show that $W$ is a subspace of the vector space $V$ of all $3\times 3$ matrices. Then, exhibit a spanning set for $W$.   Proof. To prove that $W$ is a subspace of $V$, the $3\times 3$ zero matrix […]

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