Ch04 Vector Spaces

4.3 Lineary Independent Sets; Bases

An indexed set of vectors $\left\{ \textbf{v}_1, \cdots, \textbf{v}_p \right\}$ in $V$ is said to be linearly independent if the vector equation

$$c_1 \textbf{v}_1 + c_2 \textbf{v}_2 + \cdots + c_p \textbf{v}_p = \textbf{0} \tag{1}$$

has only the trivial solution, $c_1=0, \cdots, c_p=0$.

The set $\left\{ \textbf{v}_1, \cdots, \textbf{v}_p \right\}$ is said to be linearly dependent if (1) has a nontrivial solution, i.e., if there are some weights, $c_1, \cdots, c_p$, not all zero, such that (1) holds.

In such a case, (1) is called a linear dependence relation among $\textbf{v}_1, \cdots, \textbf{v}_p$.

Theorem 4:

An indexed set $\left\{ \textbf{v}_1, \cdots, \textbf{v}_p \right\}$ of two or more vectors, with $\textbf{v}_1 \ne \textbf{0}$, is linearly dependent if and only if some $\textbf{v}_j$ (with $j>1$) is a linear combination of the preceding vectors, $\textbf{v}_1, \cdots, \textbf{v}_{j-1}$.

Definition: Basis

Let $H$ be a subspace of a vector space $V$. An indexed set of vectors $B=\left\{ \textbf{b}_1, \cdots, \textbf{b}_p \right\}$ in $V$ is a basis for $H$ if

• (i) $B$ is a linearly independent set, and
• (ii) The subspace spanned by $B$ coincides with $H$; that is, $H=\text{Span }\left\{ \textbf{b}_1, \cdots, \textbf{b}_p \right\}$.

The definition of a basis applies to the case when $H=V$, because any vector space is a subspace of itself.

Thus a basis of $V$ is a linearly independent set that spans $V$.

When $H \ne V$, condition (ii) includes the requirement that each of the vectors $\textbf{b}_1, \cdots, \textbf{b}_p$ must belong to $H$, because Span $\left\{ \textbf{b}_1, \cdots, \textbf{b}_p \right\}$ contains $\textbf{b}_1, \cdots, \textbf{b}_p$.

Standard Basis

Let $\textbf{e}_1, \cdots, \textbf{e}_n$ be the columns of the $n \times n$ matrix, $I_n$.

That is, $$\textbf{e}_1 = \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \textbf{e}_2 = \begin{bmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{bmatrix}, \cdots, \textbf{e}_n = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{bmatrix}$$

The set $\left\{ \textbf{e}_1, \cdots, \textbf{e}_n \right \}$ is called the standard basis for $\mathbb{R}^n$.

See the following figure.

Theorem 5: The Spanning Set Theorem

Let $S=\left\{ \textbf{v}_1, \cdots, \textbf{v}_p \right\}$ be a set in $V$, and let $H=\text{Span }\left\{ \textbf{v}_1, \cdots, \textbf{v}_p \right\}$.

• (a) If one of the vectors in $S$—say, $\textbf{v}_k$—is a linear combination of the remaining vectors in $S$, then the set formed from $S$ by removing $\textbf{v}_k$ still spans $H$.
• (b) If $H\ne\left\{ \textbf{0} \right\}$, some subset of $S$ is a basis for $H$.

Proof:

a.

By rearranging the list of vectors in $S$, if necessary, we may suppose that $\textbf{v}_p$ is a linear combination of $\textbf{v}_1, \cdots, \textbf{v}_p$ —say,

$$\textbf{v}_p = a_1 \textbf{v}_1 + \cdots + a_{p-1}\textbf{v}_{p-1} \tag{3}$$

Given any $\textbf{x}$ in $H$, we may write

$$\textbf{x} = c_1 \textbf{v}_1 + \cdots + c_{p-1}\textbf{v}_{p-1} + c_p\textbf{v}_p \tag{4}$$

for suitable scalars $c_1, \cdots, c_p$.

Substituting the expression for $\textbf{v}_p$ from (3) into (4), it is easy to see that $\textbf{x}$ is a linear combination $\textbf{v}_1, \cdots, \textbf{v}_p$

Thus $\left\{ \textbf{v}_1, \cdots, \textbf{v}_p \right\}$ spans $H$, because $\textbf{x}$ was an arbitrary element of $H$.

b.

If the original spanning set $S$ is linearly independent, then it is already a basis for $H$.

• Otherwise, one of the vectors in $S$ depends on the others and can be deleted, by part (a).
• So long as there are two or more vectors in the spanning set, we can repeat this process until the spanning set is linearly independent and hence is a basis for $H$.
• If the spanning set is eventually reduced to one vector, that vector will be nonzero (and hence linearly independent) because $H \ne \left\{ \textbf{0} \right\}$.

Exampel 7

Let $\textbf{v}_1 = \begin{bmatrix} 0 \\ 2 \\ -1 \end{bmatrix}, \textbf{v}_2 = \begin{bmatrix} 2 \\ 2 \\ 0 \end{bmatrix}, \textbf{v}_3 = \begin{bmatrix} 6 \\ 16 \\ -5 \end{bmatrix}$ and $H = \text{Span }\left\{ \textbf{v}_1, \textbf{v}_2, \textbf{v}_3 \right \}$. Note that $\textbf{v}_3 = 5\textbf{v}_1+3\textbf{v}_2$, and show that Span $\left\{\textbf{v}_1, \textbf{v}_2, \textbf{v}_3\right\}$ = Span $\left\{\textbf{v}_1, \textbf{v}_2 \right\}$. Then find a basis for the subsapce $H$.

Solution

Every vector in $\text{Span }\left\{ \textbf{v}_1,\textbf{v}_2 \right\}$ belongs to $H$ because

$$c_1 \textbf{v}_1 + c_2 \textbf{v}_2 = c_1 \textbf{v}_1 +c_2 \textbf{v}_2 + 0 \textbf{v}_3$$

• Now let $\textbf{x}$ be any vector in $H$—say

$$\textbf{x} = c_1 \textbf{v}_1 + c_2 \textbf{v}_2 + c_3 \textbf{v}_3.$$

• Since $\textbf{v}_3 = 5\textbf{v}_1+3\textbf{v}_2$, we may substitute

$$\begin{align} \textbf{x} &= c_1 \textbf{v}_1 + c_2 \textbf{v}_2 + c_3 (5\textbf{v}_1 + 3 \textbf{v}_3) \\ &= (c_1 + 5c_3) \textbf{v}_1 + (c_2 +3c_3) \textbf{v}_2 \end{align}$$

• Thus $\textbf{x}$ is in $\text{Span }\left\{ \textbf{v}_1, \textbf{v}_2 \right\}$, so every vector in $H$ already belongs to $\text{Span }\left\{ \textbf{v}_1, \textbf{v}_2 \right\}$.

• We conclude that $H$ and $\text{Span }\left\{ \textbf{v}_1, \textbf{v}_2 \right\}$ are actually the set of vectors.

• It follows that $\left\{ \textbf{v}_1, \textbf{v}_2 \right\}$ is a basis of $H$ since $\left\{ \textbf{v}_1, \textbf{v}_2 \right\}$ is linearly independent.

Example 8 :

Find a basis for Col $B$, where

$$\begin{align} B &= \begin{bmatrix} \textbf{b}_1, \textbf{b}_2, \cdots, \textbf{b}_5 \end{bmatrix}\\ &=\begin{bmatrix} 1 & 4 & 0 & 2 & 0 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{align}$$

Solution

• Each nonpivot column of $B$ is a linear combination of the pivot columns.
• In fact, $\textbf{b}_2 = 4 \textbf{b}_1$ and $\textbf{b}_4 = 2 \textbf{b}_1-\textbf{b}_3$.
• By the Spanning Set Theorem, we may discard $\textbf{b}_2$ and $\textbf{b}_4$, and $\left\{ \textbf{b}_1, \textbf{b}_3, \textbf{b}_5 \right\}$ will still span Col $B$.
• Let

$$\begin{align} S &= \left\{ \textbf{b}_1, \textbf{b}_3, \textbf{b}_5 \right\} \\ &= \left\{ \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} , \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} , \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} \right\} \end{align}$$

• Since $\textbf{b}_1 \ne \textbf{0}$ and no vector in $S$ is a linear combination of the vectors that precede it, $S$ is linearly independent. (Theorem 4).
• Thus $S$ is a basis for Col $B$.

Theorem 6:

The pivot columns of a matrix $A$ form a basis for Col $A$.

Proof:

• Let $B$ be the reduced echelon form of $A$.
• The set of pivot columns of $B$ is linearly independent, for no vector in the set is a linear combination of the vectors that precede it.
• Since $A$ is row equivalent to $B$, the pivot columns of $A$ are linearly independent as well, because any linear dependence relation among the columns of $A$ corresponds to a linear dependence relation among the columns of $B$.
• For this reason, every nonpivot column of $A$ is a linear combination of the pivot columns of $A$.
• Thus the nonpivot columns of $A$ may be discarded from the spanning set for Col $A$, by the Spanning Set Theorem.
• This leaves the pivot columns of $A$ as a basis for Col $A$.

Warning:

• The pivot columns of a matrix $A$ are evident when $A$ has been reduced only to echelon form.
• But, be careful to use the pivot columns of $A$ itself for the basis of Col $A$.
• Row operations can change the column space of a matrix.
• The columns of an echelon form $B$ of $A$ are often not in the column space of $A$.

Two Views of a Basis

• When the Spanning Set Theorem is used, the deletion of vectors from a spanning set must stop when the set becomes linearly independent.
• If an additional vector is deleted, it will not be a linear combination of the remaining vectors, and hence the smaller set will no longer span $V$.
• Thus a basis is a spanning set that is as small as possible.
• A basis is also a linearly independent set that is as large as possible.
• If $S$ is a basis for $V$, and if $S$ is enlarged by one vector-say,$\textbf{w}$-from $V$, then the new set cannot be linearly independent, because $S$ spans $V$, and $\textbf{w}$ is therefore a linear combination of the elements in $S$.