%display latex
latex.matrix_delimiters(left='[', right=']')
latex.matrix_column_alignment('c')
$\newcommand{\la}{\langle}$ $\newcommand{\ra}{\rangle}$ $\newcommand{\vu}{\mathbf{u}}$ $\newcommand{\vv}{\mathbf{v}}$ $\newcommand{\vw}{\mathbf{w}}$ $\newcommand{\vzz}{\mathbf{z}}$ $\newcommand{\nc}{\newcommand}$ $\nc{\Cc}{\mathbb{C}}$ $\nc{\Rr}{\mathbb{R}}$ $\nc{\Qq}{\mathbb{Q}}$ $\nc{\Nn}{\mathbb{N}}$ $\nc{\cB}{\mathcal{B}}$ $\nc{\cE}{\mathcal{E}}$ $\nc{\cC}{\mathcal{C}}$ $\nc{\cD}{\mathcal{D}}$ $\nc{\mi}{\mathbf{i}}$ $\nc{\sp}[1]{\langle #1 \rangle}$ $\nc{\ol}[1]{\overline{#1} }$ $\nc{\norm}[1]{\left\| #1 \right\|}$ $\nc{\abs}[1]{\left| #1 \right|}$ $\nc{\vz}{\mathbf{0}}$ $\nc{\vo}{\mathbf{1}}$ $\nc{\DMO}{\DeclareMathOperator}$ $\DMO{\tr}{tr}$ $\DMO{\nullsp}{nullsp}$ $\nc{\va}{\mathbf{a}}$ $\nc{\vb}{\mathbf{b}}$ $\nc{\vx}{\mathbf{x}}$ $\nc{\ve}{\mathbf{e}}$ $\nc{\vd}{\mathbf{d}}$ $\nc{\vh}{\mathbf{h}}$ $\nc{\ds}{\displaystyle}$ $\nc{\bm}[1]{\begin{bmatrix} #1 \end{bmatrix}}$ $\nc{\gm}[2]{\bm{\mid & \cdots & \mid \\ #1 & \cdots & #2 \\ \mid & \cdots & \mid}}$ $\nc{\MN}{M_{m \times n}(K)}$ $\nc{\NM}{M_{n \times m}(K)}$ $\nc{\NP}{M_{n \times p}(K)}$ $\nc{\MP}{M_{m \times p}(K)}$ $\nc{\PN}{M_{p \times n}(K)}$ $\nc{\NN}{M_n(K)}$ $\nc{\im}{\mathrm{Im\ }}$ $\nc{\ev}{\mathrm{ev}}$ $\nc{\Hom}{\mathrm{Hom}}$ $\nc{\com}[1]{[\phantom{a}]^{#1}}$ $\nc{\rBD}[1]{ [#1]_{\cB}^{\cD}}$ $\DMO{\id}{id}$ $\DMO{\rk}{rk}$ $\DMO{\nullity}{nullity}$ $\DMO{\End}{End}$ $\DMO{\proj}{proj}$ $\nc{\GL}{\mathrm{GL}}$
Given a set of vectors $A$ (in $K^n$). We have seen in Part I how
to decide whether a given vector $\vb$ is in the span of $A$ and;
if $\vb \in \sp{A}$, to write $\vb$ as a linear combination of vectors in $A$.
A set of vectors $S$ in a vector space $V$ is a spanning set (of $V$) if the span of $S$ is $V$. In this case, we also say that $S$ spans $V$.
Put it in another way, $S$ is a spanning set of $V$ if every $\vv \in V$ is a linear combination of vectors in $S$.
If the span of a subset $A$ of $V$ contains a spanning set $S$, then $A$ itself is a spanning set. This is because $V = \sp{S} \subseteq \sp{\sp{A}} = \sp{A}$.
Example 1. The set $\{\ve_i \colon 1 \le i \le n\}$ is a spanning set of $K^n$. For instance, $$ \{ \ve_1,\ve_2,\ve_3\} = \left\{ \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \right\} $$ is a spanning set of $K^3$.
The set $A = \left\{\vv_1 = \bm{1 \\1 \\ 1}. \vv_2 = \bm{1 \\ 1 \\ 0}, \vv_3 = \bm{1 \\ 0 \\0}\right\}$ is also a spanning set of $K^3$. This is becasue $\ve_1 = \vv_3$, $\ve_2 = \vv_2 - \vv_3$ and $\ve_3 = \vv_1 - \vv_2$, so $\sp{A}$ contains a spanning set $\{\ve_1, \ve_2, \ve_3\}$ and hence $A$ itself is a spanning set.
The question is: given a finite subset $A$ of $V$, can we decide whether $\sp{A} = V$? If so, how?
In these notes, we will only answer the question for $V = K^n$ ($n \in \Nn$).
This may look rather restrictive at first, but later we will see that any finite dimensional $K$-vector space is essentially (isomorphic) to one of the $K^n$'s. So, we are actually answering the question in general.
Example 2. Here is a concrete example of what we mean by isomorphic.
$M_2(K)$ can be identified with $K^4$ via
$$ \bm{a & b \\ c & d} \stackrel{\Phi}{\longrightarrow} \bm{a \\ b \\ c \\d} $$This map $\Phi$ is not only a bijection of the two sets, it preserves vector addition and scalar multiplication: one checks readily that for any $A, B \in M_2(K)$ and $c \in K$,
A bijection between two $K$-vector spaces having properties (1) and (2) is called an isomorphism.
From now on we often identify a finite list $A=\{\va_1, \ldots, \va_m\}$ of vectors in $K^n$ with the $n \times m$ matrix, still denoted by $A$, whose $i$-th column is the $i$-th element of $A$. If we do not specify the order of $A$ then it is understood an arbitrary order is choosen.
Theorem 1. The following are equivalent
Corollary 2. Any spanning set of $K^n$ has size at least $n$.
Proof. In $R_A$, the number non-zero rows = the number of pivotal columns. Therefore, if $A$ is a spanning set, then by Theorem 1 (3), $R_A$ has $n$ nonzero columns and so the size of $A$, which is the number of columns of $R_A$ must be at least $n$.
Proof (of Theorem 1). (1) $\implies$ (2)
Since $\ve_i \in K^n = \sp{A}$, $A\vx_i = \ve_i$ for some $\vx_i$ ($1 \le i \le n$).
Hence,
$$AX = A\gm{\vx_1}{\vx_n} = \gm{A\vx_1}{A\vx_n} = \gm{\ve_1}{\ve_n} = I_n$$In other words, $A$ has a right inverse. (N.B. $A \in \NM$ and $X \in \MN$.)
(2) $\implies$ (3) Suppose $X$ is a right inverse of $A$ and $B$ be an invertible matrix so that $BA = R_A$. Then $$B = BI_n = B(AX) = (BA)X = R_AX.$$ That implies no rows of $R_A$ can be zero for otherwise $B$ would have a zero row, contradicting invertibility.
(3) $\implies$ (1) Suppose all $n$ rows of $R_A$ are not zeros. Then its $n$ pivotal columns, say indexed by $1 \le j_1 < \cdots < j_n \le m$, form $I_n$. Thus $R_AP = I_n$ where $P=\bm{| & \cdots & | \\ \ve_{j_1} & \cdots & \ve_{j_n} \\ | & \cdots & |} \in \MN$.
Take $X = PB$ where $B$ is an invertible matrix so that $BA = R_A$. Then we have
$$AX = (B^{-1}R_A)(PB) = B^{-1}(R_AP)B= B^{-1}I_nB = I_n.$$That means $A\vx_i = \ve_i$ and so $\ve_i \in \sp{A}$ ($1 \le i \le n$) whence $A$ is a spanning set of $K^n$.
Example 3. Do the columns of the following matrix $A$ span $\Rr^2$?
A = matrix([[-7,-28,112],[-2,-8,32]]); A, A.rref()
Since the rref$(A)$ has only 1 nonzero row, the columns of $A$ do not span $\Rr^2$.
Checkpoint 1. Do the columns of the following matrix $A$ span $\Rr^2$?
%display latex
A = matrix([[-5,1,8],[-9,30,5]]); A, A.rref()
Example 4. Let $\va_1,\va_2,\va_3$ be the following vectors:
var('h');
aa1= column_matrix([3,15,3]); aa2 = column_matrix([h,-18,-3]); aa3 = column_matrix([-7,-7,-1]); aa1,aa2,aa3
Determine the values of $h$ so that $\{\va_1,\va_2,\va_3\}$ will form a spanning set of $\Rr^3$.
Ans. Construct the matrix $A$ with these vectors as columns and start row-reducing $A$. Keep in mind that we should not divide by any quantity that may be 0 (i.e. involving the variable(s))
A = column_matrix([aa1.column(0),aa2.column(0),aa3.column(0)]); A
A.add_multiple_of_row(1,0,-5); A.add_multiple_of_row(2,0,-1); A
A.swap_rows(1,2); A
A.add_multiple_of_row(2,1,-5); A
A.swap_rows(1,2);A
So the rref of $A$ will have a zero row if and only if $\lambda[-3,-2] = [-h-3,6]$ for some $\lambda \neq 0$.
By comparing the last entry, we see that $\lambda$ must be $-3$ and so $-h-3 = \lambda(-3) = (-3)(-3) = 9$.
Thus, $h$ must be $-12$ and therefore the columns of $A$ will span $\Rr^3$ unless $h=-12$.
Remark. In this case, since $A$ is a square matrix. By the theorem, the columns of $A$ will span $\Rr^3$ if and only if $A$ is invertible, i.e. $\det(A) \neq 0$.
det(A)
So from this we can also conclude that the columns of $A$ will span $\Rr^3$ unless $\det(A) = -6h-72 = 0$, i.e. unless $h = -12$.
But the first method is more general, since it applies even if $A$ is not a square matrix.
Let us illustrate the steps in the proof of Theorem 1 by a concrete example.
Let $A$ be the following matrix. We would like to know if the columns of $A$ spans $K^3$.
A = column_matrix([[0,0,1],[0,0,3],[2,1,0],[-1,1,3]]); A
First, let's find an invertible $B$ so that $BA = R_A$. We can do that by row-reducing the matrix $M:=[A|I_3]$
I3 = identity_matrix(3); M = block_matrix([A,I3], ncols=2); RM=M.rref(); M, RM
The left portion of rref($M$) is rref($A$) and we can take $B$ as the right portion of rref($M$).
R = A.rref(); B = RM.submatrix(0,4); R, B
Since all rows of $R_A$ are nonzero, the columns of $A$ spans $K^3$.
The 1st, the 3rd and the 4th columns of $R_A$ are pivotal. According to the proof of Theorem 1, take $P = \bm{1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 &1 &0 \\ 0 & 0 & 1}$ and $X =PB$.
P = column_matrix([(1,0,0,0),(0,0,1,0),(0,0,0,1)]); X = P*B; X, A*X