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

Linear algebra problems and solutions

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.

 
FavoriteLoadingAdd to solve later

Sponsored Links

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 ↴


FavoriteLoadingAdd to solve later

Sponsored Links

More from my site

You may also like...

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

Leave a Reply

Your email address will not be published. Required fields are marked *

More in Linear Algebra
Linear algebra problems and solutions
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