Introdunction to Linear Algebra-第3章-Vector Spaces and Subspaces

[TOC]
《Introdunction to Linear Algebra》的第 3 章：Vector Spaces and Subspaces.

3.1 Spaces of Vectors

本节概要

1. The standard $n$-dimensional space $\mathbf{R}^{n}$ contains all real column vectors with $n$ components.
2. If $\boldsymbol{v}$ and $\boldsymbol{w}$ are in a vector space $\boldsymbol{S}$, every combination $c \boldsymbol{v}+d \boldsymbol{w}$ must be in $\boldsymbol{S}$.
3. The “vectors“ in $\boldsymbol{S}$ can be matrices or functions of $\boldsymbol{x}$. The 1-point space $\boldsymbol{Z}$ consists of $\boldsymbol{x}=\mathbf{0}$.
4. A subspace of $\mathbf{R}^{n}$ is a vector space inside $\mathbf{R}^{n}$. Example: The line $y=3 x$ inside $\mathbf{R}^{2}$.
5. The column space of $A$ contains all combinations of the columns of $A$ : a subspace of $\mathbf{R}^{m}$.
6. The column space contains all the vectors $A \boldsymbol{x}$. So $A \boldsymbol{x}=\boldsymbol{b}$ is solvable when $\boldsymbol{b}$ is in $\boldsymbol{C}(A)$.

省略关于向量空间及子空间的概念.可参考《线性代数应该这样学》的学习笔记系列.

The Column Space of $A$

We are trying to solve $A\boldsymbol{x} = \boldsymbol{b}$. If $A$ is not invertible, the system is solvable for some band not solvable for other $\boldsymbol{b}$. We want to describe the good right sides $\boldsymbol{b}$-the vectors that can be written as $A$ times some vector $\boldsymbol{x}$. Those $\boldsymbol{b}$’ s form the column space of $A$.

定义: The column space consists of all linear combinations of the columns. The combinations are all possible vectors $A \boldsymbol{x}$. They fill the column space $C(A)$.

The system $A \boldsymbol{x} = \boldsymbol{b}$ is solvable if and only if $\boldsymbol{b}$ is in the column space of $A$.

The columns “span“ the column space.

3.2 The Nullspace of A: Solving $A\boldsymbol{x}= 0$ and $R\boldsymbol{x}=0$

本节概要

1. The nullspace $\boldsymbol{N}(A)$ in $\mathbf{R}^{n}$ contains all solutions $\boldsymbol{x}$ to $A \boldsymbol{x}=\mathbf{0}$. This includes $\boldsymbol{x}=\mathbf{0}$.
2. Elimination (from $A$ to $U$ to $R$ ) does not change the nullspace: $\boldsymbol{N}(A)=\boldsymbol{N}(U)=\boldsymbol{N}(R)$.
3. The reduced row echelon(梯形) form $R=\operatorname{rref}(A)$ has all pivots $=1$, with zeros above and below.
4. If column $j$ of $R$ is free (no pivot), there is a “special solution” to $A \boldsymbol{x}=\mathbf{0}$ with $x_{j}=1$.
5. Number of pivots $=$ number of nonzero rows in $R=\operatorname{rank} r$. There are $n-r$ free columns.
6. Every matrix with $m<n$ has nonzero solutions to $A \boldsymbol{x}=\mathbf{0}$ in its nullspace.

The nullspace $N(A)$ consists of all solutions to $A \boldsymbol{x}= 0$. These vectors $\boldsymbol{x}$ are in $R^n$.

The nullspace is a subspace of $R^n$. The column space $C(A)$ is a subspace of $R^m$.

The nullspace of $A$ consists of all combinations of the special solutions to $A \boldsymbol{x} = 0$.

Pivot Columns and Free Columns

含有 pivot 的列是 pivot column, 不含有 pivot 的列为 free column.

$$
C=\left[\begin{array}{rrrr}
1 & 2 & 2 & 4 \\
3 & 8 & 6 & 16
\end{array}\right] \text { becomes } U=\left[\begin{array}{llll}
1 & 2 & 2 & 4 \\
0 & 2 & 0 & 4 \\
\uparrow & \uparrow & \uparrow & \uparrow \\
\text{pivot} & \text{columns} & \text{free} & \text{columns}
\end{array}\right]
$$

The Reduced Row Echelon Form $R$

把矩阵化成简单形式, 共 2 步:

1. Produce zeros above the pivots. Use pivot rows to eliminate upward in $R$.
2. Produce ones in the pivots. Divide the whole pivot row by its pivot.

然后可以很方便地得出 $A\boldsymbol{x}=0$ 的可行解, 使一个 free column 为 1, 其余 free column 为 0 即可得到 1 个可行解, 然后对所有 free column 进行此过程即可得到所有可行解. 图解如下:

定理:
Suppose $A \boldsymbol{x} = 0$ has more unknowns than equations ($n > m$, more columns than rows). There must be at least one free column. Then $A \boldsymbol{x} = 0$ has nonzero solutions.

The Rank of a Matrix

考虑到线性组合得到的列最后是无效列(线性相关列, 可以由其他线性无关列组合出), $m \times n$并不能准确刻画矩阵的大小.
The true size of $A$ is given by its rank. 从列的角度.
The rank of $A$ is the number of pivots. This number is r.

Every “free column” is a combination of earlier pivot columns.
It is the special solutions $s$ that tell us those combinations.

Rank One

special rank one form $A=\boldsymbol{u} \boldsymbol{v}^T$

$$
\boldsymbol{A}=\text { column times row }=\boldsymbol{u} \boldsymbol{v}^{\mathrm{T}} \quad\left[\begin{array}{lll}
1 & 3 & 10 \\
2 & 6 & 20 \\
3 & 9 & 30
\end{array}\right]=\left[\begin{array}{l}
1 \\
2 \\
3
\end{array}\right]\left[\begin{array}{lll}
1 & 3 & 10
\end{array}\right]
$$

$A \boldsymbol{x}=0 \rightarrow \boldsymbol{u} (\boldsymbol{v}^T\boldsymbol{x})=0 \rightarrow \boldsymbol{v}^T\boldsymbol{x}=0$
也就是说 $\boldsymbol{x}$ nullspace 中的向量必须与 $\boldsymbol{v}$ 中的列向量正交, 因此可以得到如下结论:

对于秩等于 1 的情况:
$r=1$: row space = line, nullspace = perpendicular plane.

秩的另外两个定义:

• $A,U,R$均有 rank 个 independent rows(线性无关). 从行的角度.
• $r$ is the dimension of the nullspace

3.3 The Complete Solution to $A \boldsymbol{x} = \boldsymbol{b}$

本节概要

1. Complete solution to $A \boldsymbol{x}=\boldsymbol{b}: \boldsymbol{x}=$ (one particular solution $\left.\boldsymbol{x}{p}\right)+\left(\right.$ any $\boldsymbol{x}{n}$ in the nullspace $) .$
2. Elimination on $\left[\begin{array}{ll}A & \boldsymbol{b}\end{array}\right]$ leads to $\left[\begin{array}{ll}R & \boldsymbol{d}\end{array}\right] .$ Then $A \boldsymbol{x}=\boldsymbol{b}$ is equivalent to $R \boldsymbol{x}=\boldsymbol{d} .$
3. $A \boldsymbol{x}=\boldsymbol{b}$ and $R \boldsymbol{x}=\boldsymbol{d}$ are solvable only when all zero rows of $R$ have zeros in $\boldsymbol{d} .$
4. When $R \boldsymbol{x}=\boldsymbol{d}$ is solvable, one very particular solution $\boldsymbol{x}_{p}$ has all free variables equal to zero.
5. $A$ has full column rank $r=n$ when its nullspace $\boldsymbol{N}(A)=$ zero vector: no free variables.
6. $A$ has full row rank $r=m$ when its column space $\boldsymbol{C}(A)$ is $\mathbf{R}^{m}: A \boldsymbol{x}=\boldsymbol{b}$ is always solvable.
7. The four cases are $r=m=n$ ( $A$ is invertible) and $r=m<n$ (every $A \boldsymbol{x}=\boldsymbol{b}$ is solvable) and $r=n<m$ ( $A \boldsymbol{x}=\boldsymbol{b}$ has 1 or 0 solutions) and $r<m, r<n$ ( 0 or $\infty$ solutions).

对于第 2, 3 条:

1. 增广:

$$
\left[\begin{array}{llll}
1 & 3 & 0 & 2 \\
0 & 0 & 1 & 4 \\
1 & 3 & 1 & 6
\end{array}\right]\left[\begin{array}{l}
x_{1} \\
x_{2} \\
x_{3} \\
x_{4}
\end{array}\right]=\left[\begin{array}{l}
\mathbf{1} \\
\mathbf{6} \\
\mathbf{7}
\end{array}\right] \quad \begin{aligned}
&\text { has the } \\
&\text { augmented } \\
&\text { matrix }
\end{aligned} \quad\left[\begin{array}{lllll}
1 & 3 & 0 & 2 & \mathbf{1} \\
0 & 0 & 1 & 4 & \mathbf{6} \\
1 & 3 & 1 & 6 & \mathbf{7}
\end{array}\right]=\left[\begin{array}{ll}
A & \boldsymbol{b}
\end{array}\right]
$$

2. 化简成 $R$ 矩阵:

$$ \left[\begin{array}{ll} A & \boldsymbol{b} \end{array}\right]=\left[\begin{array}{lllll} 1 & 3 & 0 & 2 & \boldsymbol{b}_{1} \\\\ 0 & 0 & 1 & 4 & \boldsymbol{b}_{2} \\\\ 1 & 3 & 1 & 6 & \boldsymbol{b}_{3} \end{array}\right] \rightarrow\left[\begin{array}{ccccl} 1 & 3 & 0 & 2 & \boldsymbol{b}_{1} \\\\ 0 & 0 & 1 & 4 & \boldsymbol{b}_{2} \\\\ 0 & 0 & 0 & 0 & \boldsymbol{b}_{3}-\boldsymbol{b}_{1}-\boldsymbol{b}_{2} \end{array}\right]=\left[\begin{array}{ll} R & \boldsymbol{d} \end{array}\right] $$

3. 检查 $A$ 为 0 的列对应的 $\boldsymbol{b}$ 列是否为 0.

4. 化成通解形式:

$$ \begin{array}{lll} x_{\text {particular }} & \text { The particular solution solves } & A \boldsymbol{x}_{p}=\boldsymbol{b} \\\\ x_{\text {nullspace }} & \text { The } n-r \text { special solutions solve } & A \boldsymbol{x}_{n}=\boldsymbol{0} \end{array} $$ $$ \boldsymbol{x}=\boldsymbol{x}_{p}+\boldsymbol{x}_{n}=\left[\begin{array}{l} 1 \\\\ 0 \\\\ 6 \\\\ 0 \end{array}\right]+x_{2}\left[\begin{array}{r} -3 \\\\ 1 \\\\ 0 \\\\ 0 \end{array}\right]+x_{4}\left[\begin{array}{r} -2 \\\\ 0 \\\\ -4 \\\\ 1 \end{array}\right] $$

对于 $\boldsymbol{x}_p$ 为 pivot columns 对应的 $\boldsymbol{b}$ 的列元素, 其余元素均为0.
对于方阵:$\boldsymbol{x} =\boldsymbol{x}_p + \boldsymbol{x}_n = A^{-1} \boldsymbol{b} + 0$.

满列秩的特性:

Every matrix $A$ with full column rank $(r=n)$ has all these properties:

1. All columns of $A$ are pivot columns.
2. There are no free variables or special solutions.
3. The nullspace $N(A)$ contains only the zero vector $\boldsymbol{x}=0$.
4. If $A \boldsymbol{x}=\boldsymbol{b}$ has a solution (it might not) then it has only one solution.
5. The square matrix $A^TA$ is invertible when the rank is $n$.

$$
\text { Full column rank } \quad R=\left[\begin{array}{l}
I \\
0
\end{array}\right]=\left[\begin{array}{l}
n \text { by } n \text { identity matrix } \\
m-n \text { rows of zeros }
\end{array}\right]
$$

With full column rank, $A \boldsymbol{x} = \boldsymbol{b}$ has one solution or no solution ($m > n$ is overdetermined).

满行秩的情况下:
With full row rank, $A \boldsymbol{x} = \boldsymbol{b}$ has one or infinitely many solutions.

用几何说明:
$$
\begin{array}{lllrl}
\text { Full row rank } & x+y +z=3 \\
& x+2 y-z=4
\end{array} \quad(\operatorname{rank} r=m=2)
$$

满行秩的特性:

Every matrix $A$ with full row rank $(r=m)$ has all these properties:

1. All rows have pivots, and $R$ has no zero rows.
2. $A \boldsymbol{x}= \boldsymbol{b}$ has a solution for every right side $\boldsymbol{b}$.
3. The column space is the whole space $\mathbf{R}^{m}$.
4. There are $n-r=n-m$ special solutions in the nullspace of $A$.

The four possibilities for linear equations depend on the rank $r$
$$
\begin{array}{llllll}
r=m & \text { and } & r=n & \text { Square and invertible } & A \boldsymbol{x}=\boldsymbol{b} & \text { has } 1 \text { solution } \\
r=m & \text { and } & r<n & \text { Short and wide } & A \boldsymbol{x}=\boldsymbol{b} & \text { has } \infty \text { solutions } \\
r<m & \text { and } & r=n & \text { Tall and thin } & A \boldsymbol{x}=\boldsymbol{b} & \text { has } 0 \text { or } 1 \text { solution } \\
r<m & \text { and } & r<n & \text { Not full rank } & A \boldsymbol{x}=\boldsymbol{b} & \text { has } 0 \text { or } \infty \text { solutions }
\end{array}
$$

对应的化简形式为($F$ 为 free block 的意思):

$$
\begin{array}{lccc}
\text { Four types for } R & {[I]} & {\left[\begin{array}{ll}
I & F
\end{array}\right]} & {\left[\begin{array}{l}
I \\
0
\end{array}\right]} & {\left[\begin{array}{ll}
I & F \\
0 & 0
\end{array}\right]} \\
\text { Their ranks } & r=m=n & r=m<n & r=n<m & r<m, r<n
\end{array}
$$

3.4 Independence, Basis and Dimension

本节概要

1. Independent columns of $A$ : The only solution to $A \boldsymbol{x}=0$ is $\boldsymbol{x} = 0$. The nullspace is $\boldsymbol{Z}$.
2. Independent vectors: The only zero combination $c_{1} \boldsymbol{v}_{1}+\cdots+c_{k} \boldsymbol{v}_{k}=0$ has all $c$ 's $=0$.
3. A matrix with $m<n$ has dependent columns : At least $n-m$ free variables/special solutions.
4. The vectors $v_{1}, \ldots, v_{k}$ span the space $S$ if $S=$ all combinations of the $v$ ‘s.
5. The vectors $v_{1}, \ldots, v_{k}$ are a basis for $S$ if they are independent and they span $S$.
6. The dimension of a space $S$ is the number of vectors in every basis for $S$.
7. If $A$ is 4 by 4 and invertible, its columns are a basis for $\mathbf{R}^{4}$. The dimension of $\mathbf{R}^{4}$ is 4 .

The goal is to understand a basis: independent vectors that “span the space”.
Every vector in the space is a unique combination of the basis vectors.

heart of this subject:

1. Independent vectors (no extra vectors)
2. Spanning a space (enough vectors to produce the rest)
3. Basis for a space (not too many or too few)
4. Dimension of a space (the number of vectors in a basis)

Linear independence 线性无关
$x_1v_1 + x_2v_2 + · · · + x_nv_n = 0$ only happens when all $x$’s are zero.

Any set of $n$ vectors in $\textbf{R}^m$ must be linearly dependent if $n > m$. 推导出 $m \times n$ 矩阵一定至少有 $n-m$ 个 free variables(非零解), 也就是线性相关的变量.

Vectors that Span a Subspace

A set of vectors spans a space if their linear combinations fill the space.

The row space of a matrix is the subspace of $\textbf{R}^n$ spanned by the rows. The row space of $A$ is $C(A^T )$. It is the column space of $A^T$.

A Basis for a Vector Space

A basis for a vector space is a sequence of vectors with two properties:

• The basis vectors are linearly independent and they span the space.
• There is one and only one way to write $\boldsymbol{v}$ as a combination of the basis vectors.

The vectors $v_1, . .. , v_n$ are a basis for $\textbf{R}^n$ exactly when they are the columns of an $n \times n$ invertible matrix. Thus $\textbf{R}^n$ has infinitely many different bases.

The pivot columns of $A$ are a basis for its column space.

如何确定一组基向量:
Question Given 5 vectors in $\textbf{R}^n$, how do you find a basis for the space they span?

• First answer: Make them the rows of $A$, and eliminate to find the nonzero rows of $R$.
• Second answer: Put the 5 vectors into the columns of $A$. Eliminate to find the pivot columns (of $A$ not $R$). Those pivot columns are a basis for the column space.

Dimension of a Vector Space

The dimension of a space is the number of vectors in every basis.
The number of basis vectors depends on the space-not on a particular basis.

Bases for Matrix Spaces and Function Spaces

当把向量的概念外延到矩阵与函数, 我们也可以得到类似的维度结论.

Matrix spaces The vector space $\mathbf{M}$ contains all 2 by 2 matrices. Its dimension is 4 .
One basis is $A_{1}, A_{2}, A_{3}, A_{4}=\left[\begin{array}{ll}1 & 0 \\ 0 & 0\end{array}\right],\left[\begin{array}{ll}0 & 1 \\ 0 & 0\end{array}\right],\left[\begin{array}{ll}0 & 0 \\ 1 & 0\end{array}\right],\left[\begin{array}{ll}0 & 0 \\ 0 & 1\end{array}\right]$.
The dimension of the whole $n$ by $n$ matrix space is $n^{2}$.
The dimension of the subspace of upper triangular matrices is $\frac{1}{2} n^{2}+\frac{1}{2} n$.
The dimension of the subspace of diagonal matrices is $n$.
The dimension of the subspace of symmetric matrices is $\frac{1}{2} n^{2}+\frac{1}{2} n$.

Function spaces The equations $d^{2} y / d x^{2}=0$ and $d^{2} y / d x^{2}=-y$ and $d^{2} y / d x^{2}=y$

involve the second derivative. In calculus we solve to find the functions $y(x)$ :
$y^{\prime \prime}=0 \quad$ is solved by any linear function $y=c x+d$
$y^{\prime \prime}=-y \quad$ is solved by any combination $y=c \sin x+d \cos x$
$y^{\prime \prime}=y \quad$ is solved by any combination $y=c e^{x}+d e^{-x}$​.

3.5 Dimensions of the Four Subspaces

本节概要

1. The column space $C(A)$ and the row space $C\left(A^{\mathrm{T}}\right)$ both have dimension $r$ (the rank of $A$ ).
2. The nullspace $\boldsymbol{N}(A)$ has dimension $n-r .$ The left nullspace $\boldsymbol{N}\left(A^{\mathrm{T}}\right)$ has dimension $m-r .$
3. Elimination produces bases for the row space and nullspace of $A:$ They are the same as for $R$.
4. Elimination often changes the column space and left nullspace (but dimensions don’t change).
5. Rank one matrices : $A=\boldsymbol{u} \boldsymbol{v}^{\mathrm{T}}=$ column times row : $\boldsymbol{C}(A)$ has basis $\boldsymbol{u}, \boldsymbol{C}\left(A^{\mathrm{T}}\right)$ has basis $\boldsymbol{v} .$

Four Fundamental Subspaces:

• The row space is $C(A^T)$, a subspace of $R^n$, dimension is rank $r$. The nonzero rows of $R$ form a basis.
• The column space is $C(A)$, a subspace of $R^m$, dimension is rank $r$. The pivot columns form a basis.
• The nullspace is $N (A)$, a subspace of $R^n$, dimension $n - r$. The special solutions form a basis.
• The left nullspace is $N(A^T )$, a subspace of $R^m$.

$R^T \boldsymbol{y} = 0$ or $ \boldsymbol{y}^T R = 0^T$

解释:
In all cases $R$ ends with $m - r$ zero rows. Every combination of these $m - r$ rows gives zero. These are the only combinations of the rows of $R$ that give zero, because the pivot rows are linearly independent. So $\boldsymbol{y}$ in the left nullspace has $y_1 = 0, … , y_r = 0$.

Fundamental Theorem of Linear Algebra, Part I
The column space and row space both have dimension $r$.The nullspaces have dimensions $n - r$ and $m - r$.

Every rank one matrix is one column times one row
$A= \boldsymbol{u}\boldsymbol{v}^T$

例子:
$$
\left[\begin{array}{cccc}
2 & 3 & 7 & 8 \\
2 a & 3 a & 7 a & 8 a \\
2 b & 3 b & 7 b & 8 b
\end{array}\right]=\left[\begin{array}{l}
1 \\
a \\
b
\end{array}\right]\left[\begin{array}{llll}
2 & 3 & 7 & 8
\end{array}\right]=\boldsymbol{u} \boldsymbol{v}^{\mathrm{T}}
$$

$\boldsymbol{u} = [1 ; a ; b], \boldsymbol{v}^T = [ 2 : 3 : 7 : 8] $

Rank Two Matrices = Rank One plus Rank One

$$ \begin{array}{ll} \text { Matrix A Rank two } & A=\left[\begin{array}{lll} \boldsymbol{u}_{1} & \boldsymbol{u}_{2} & \boldsymbol{u}_{3} \end{array}\right]\left[\begin{array}{c} \boldsymbol{v}_{1}^{\mathrm{T}} \\\\ \boldsymbol{v}_{2}^{\mathrm{T}} \\\\ \text { zero row } \end{array}\right]=\boldsymbol{u}_{1} \boldsymbol{v}_{1}^{\mathrm{T}}+\boldsymbol{u}_{2} \boldsymbol{v}_{2}^{\mathrm{T}}=(\text { rank } 1)+(\text { rank } 1) \end{array} $$

例子:
$$
\begin{array}{ll}
\text { Rank two} & A=\left[\begin{array}{ccc}
1 & 0 & 3 \\
1 & 1 & 7 \\
4 & 2 & 20
\end{array}\right]=\left[\begin{array}{lll}
1 & 0 & 0 \\
1 & 1 & 0 \\
4 & 2 & 1
\end{array}\right]\left[\begin{array}{lll}
1 & 0 & 3 \\
0 & 1 & 4 \\
0 & 0 & 0
\end{array}\right]=C R
\end{array}
$$

$R$ clearly has two basis vectors $\boldsymbol{v}_1^T = [ 1 : 0 : 3]$ and $\boldsymbol{v}_2^T = [ 0 : 1 : 4]$

pivot columns of $A$ are also in columns 1 and 2: $\boldsymbol{u}_1 = [1 ; 1 ; 4]$ and $\boldsymbol{u}_2 = [0 ; 1 ; 2]$.Notice that Chas those same first two columns!