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.

 
LoadingAdd to solve later

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 ↴


LoadingAdd to solve later

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