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

  • Can We Reduce the Number of Vectors in a Spanning Set?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 ZeroThe 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 VectorsEvery 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 MatrixRow 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 zeroThe 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 ThemLinear 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?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 MatricesFind 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 […]

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