16 Linearly independent sets and bases

library(tidyverse)
library(dasc2594)

Recall that a set of vectors $\{ \mathbf{v}_1, \ldots, \mathbf{v}_n\}$ is linearly independent if the only solution to the system of equations

\[ \begin{aligned} x_1 \mathbf{v}_1 + \cdots + x_n \mathbf{v}_n = \mathbf{0} \end{aligned} \]

is the trivial solution $\mathbf{x} = \mathbf{0}$. In other words, it is not possible to write any of the vectors in the set $\{ \mathbf{v}_1, \ldots, \mathbf{v}_n\}$ as a linear combination of the other vectors.

Definition 16.1 Let $\mathcal{H}$ be a subspace of a vector space $\mathcal{V}$. Then, the set of vectors $\mathcal{B} = \{ \mathbf{v}_1, \ldots, \mathbf{v}_n \}$ is a basis for $\mathcal{H}$ if

The set of vectors $\mathcal{B}$ are linearly independent
The subspace spanned by $\mathcal{B}$ is $\mathcal{H}$. In other words

\[ \begin{aligned} \mbox{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n) = \mathcal{H} \end{aligned} \]

Example 16.1

in class–standard basis $\mathbf{e}_1, \ldots \mathbf{e}_n$ which are the columns of the $n \times n$ identity matrix$\mathbf{I}$.

Example 16.2

in class–pick 3 vectors of length 3. Are they a basis for $\mathcal{R}^3$? What about $\mathcal{R}^4$?

Theorem 16.1 (The Spanning Set Theorem) Let $\mathcal{S} = \{\mathbf{v}_1, \ldots, \mathbf{v}_n\}$ be vectors in the vector space $\mathcal{V}$ and let $\mathcal{H}$ = span($\mathbf{v}_1, \ldots, \mathbf{v}_n$)

If one of the vectors, say $\mathbf{v}_k$, of $\mathcal{S}$ is a linear combination of the remaining vectors of $\mathcal{S}$, then the set formed by removing the vector $\mathbf{v}_k$ still spans $\mathcal{H}$
If $\mathcal{H} \neq \{\mathbf{0}\}$, then some subset of $\mathcal{S}$ spans $\mathcal{H}$.

Proof

We will show the proof for bot parts (a) and (b) of the theroem

WLOG assume $\mathbf{v}_n$ is a linear combination of $\mathbf{v}_1, \ldots, \mathbf{v}_{n-1}$ (if not, permute the labels to make the linearly dependent vector the $n$th vector). Then

\[ \begin{aligned} \mathbf{v}_n = x_1 \mathbf{v}_1 + \cdots + x_{n-1} \mathbf{v}_{n-1} \end{aligned} \tag{16.1}\]

Because the vectors $\{\mathbf{v}_1, \ldots, \mathbf{v}_n\}$ span $\mathcal{H}$, any vector $\mathbf{b}\in \mathcal{H}$ can be written as

\[ \begin{aligned} \mathbf{b} = c_1 \mathbf{v}_1 + \cdots + c_{n} \mathbf{v}_{n} \end{aligned} \tag{16.2}\]

for scalars $c_1, \ldots, c_n$. Plugging the result from Equation 16.1 into Equation 16.2 shows that any vector $\mathbf{b}$ in $\mathcal{H}$ can be written only using the vectors $\mathbf{v}_1, \ldots, \mathbf{v}_{n-1}$

As the vectors in $\mathcal{S}$ span $\mathcal{H}$, if there is a linearly dependent vector in $\mathcal{S}$, this vector can be removed from $\mathcal{S}$ and the span of this subset of $\mathcal{S}$ will still span $\mathcal{H}$. As long as $\mathbf{H} \neq \{\mathbf{0}\}$, there must be a least one nonzero vector in $\mathbf{S}$ so the removing of linearly dependent vectors will stop with at least one vector. As all of the linearly dependent vectors have been removed, the subset of $\mathcal{S}$ created in this manner will be a set of linearly independent vectors that span $\mathcal{H}$.

16.1 Bases for null($\mathbf{A}$) and col($\mathbf{A}$)

Example 16.3 Find a basis for the col($\mathbf{A}$) where

set.seed(2021)
A <- matrix(sample(-9:9, 15, replace = TRUE), 5, 3)

\[ \begin{aligned} \mathbf{A} = \begin{pmatrix} -3 & -4 & 5 \\ -4 & -4 & -3 \\ 4 & -4 & -1 \\ -3 & 4 & 2 \\ 2 & -5 & 9 \end{pmatrix} \end{aligned} \]

Calculate row echelon form and identify the pivot columns. The vectors $\mathbf{a}_1, \ldots, \mathbf{a}_n$ that make up the columns of $\mathbf{A}$ that are in the pivot columns form a basis for $\mathbf{A}$
Why is this? Think about the relationship between the columns of $\mathbf{A}$ and the vector $\mathbf{b}$ in $\mathbf{A} \mathbf{x} = \mathbf{b}$ that result in a consistent solution.

Example 16.4 Find a basis for the null($\mathbf{A}$) where

set.seed(2021)
A <- matrix(sample(-9:9, 15, replace = TRUE), 5, 3)

\[ \begin{aligned} \mathbf{A} = \begin{pmatrix} -3 & -4 & 5 \\ -4 & -4 & -3 \\ 4 & -4 & -1 \\ -3 & 4 & 2 \\ 2 & -5 & 9 \end{pmatrix} \end{aligned} \]

Calculate solutions to homogeneous system of equations, write solution in vector equation form. Vectors form a basis for null($\mathbf{A}$)

note: Facts about the basis for the null space null($\mathbf{A}$)

The spanning set produced using the method above produces a linearly independent set because the free variables are weights on the spanning vectors.
When null($\mathbf{A}$) contains nonzero vectors, the number of vectors in the spanning set for null($\mathbf{A}$) is the number of free variables in the solution of $\mathbf{A} \mathbf{x} = \mathbf{0}$.

Example 16.5 The matrix $4 \times 5$ $\mathbf{A}$ has columns given by the vectors $\mathbf{a}_1, \ldots, \mathbf{a}_5$ and is row equivalent to the matrix

\[ \begin{aligned} \mathbf{A} = \begin{pmatrix} 1 & 0 & 3 & -2 & 1 \\ 0 & 0 & 3 & -2 & 5 \\ 0 & 0 & 0 & -1 & -2 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix} \end{aligned} \]

What is a basis for col($\mathbf{A}$) in terms of the vectors $\mathbf{a}_1, \ldots, \mathbf{a}_5$

Note that two matrices that are row equivalent have the same linear dependence relationsihps between their vectors (but the basis for their column space is different)

Example 16.6 The matrix $\mathbf{A}$ is row equivalent to the matrix $\mathbf{B}$

A <- matrix(c(1, 3, 2, 5, 4, 12 , 8, 20, 0, 1, 1, 2, 2, 5, 3, 8, -1, 5, 2, 8), 4, 5)
B <- rref(A)

\[ \begin{aligned} \mathbf{A} = \begin{pmatrix} 1 & 4 & 0 & 2 & -1 \\ 3 & 12 & 1 & 5 & 5 \\ 2 & 8 & 1 & 3 & 2 \\ 5 & 20 & 2 & 8 & 8 \end{pmatrix} & \mathbf{B} = \begin{pmatrix} 1 & 4 & 0 & 2 & 0 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix} \\ \end{aligned} \]

What is a basis for col($\mathbf{A}$)?
What is a basis for col($\mathbf{B}$)?
What is span($\mathbf{a}_1, \ldots, \mathbf{a}_5$)?
What is span($\mathbf{b}_1, \ldots, \mathbf{b}_5$)?
Are the spaces spanned by the columns of $\mathbf{A}$ and the columns of $\mathbf{B}$ the same space?

Theorem 16.2 The pivot columns of a matrix $\mathbf{A}$ for a basis for col($\mathbf{A}$)

Proof

sketch: $\mathbf{B}$ rref of $\mathbf{A}$, linearly independent columns of $\mathbf{B}$ are same as linearly independent columns in $\mathbf{A}$. Other (non-pviot) columns are linearly dependent. By spanning set theorem, non-pivot columns can be removed from the spanning set without changing the span, leaving only the pivot columns of $\mathbf{A}$ as a basis for col($)

16.1 Bases for null(\(\mathbf{A}\)) and col(\(\mathbf{A}\))