前言：这篇blog是《Linear Algebra and Its Applications》第二章的一些学习笔记

第二章 向量空间

  基本方法：高斯消去法
重点：向量空间(矩阵不只是一堆数，如果想更具象的理解矩阵，向量空间的概念一定要清楚，换句话说，要通过向量空间理解矩阵)，线性变换

1. 向量空间与子空间

1.1. 向量空间的定义

  在线性代数中，向量空间=线性空间。
向量空间就是满足下面8个性质的向量集，$x,y,z$为向量集中的向量，$c$为常数

1. $x+y=y+x$；
2. $x+(y+z)=(x+y)+z$；
3. 有一个"零向量"使得对所有向量$x$满足$x+0=x$；
4. 对每一个向量$x$有一个向量$(-x)$满足$x+(-x)=0$；
5. $1·x=x$；
6. $(c_{1}c_{2})x=c_{1}(c_{2}x)$；
7. $c(x+y)=cx+xy$；
8. $(c_{1}+c_{2})x=c_{1}x+c_{2}x$。

  向量空间产生的方法：

1. 由线性无关向量张成(spanning)；
2. 满足特殊条件，例如零空间$(\{x|Ax=0\})$。

  向量空间举例：平面所有向量，$3\times 2$ 矩阵，$C[0,1]=\{f(x)|f(x)连续且0\leq x\leq 1\}$，$R^{\infty}$(希尔伯特空间)=$\{x|x=(x_{1},x_{2},x_{3},x_{4}\dots),x_{i}\in R\}$。

1.2. 子空间定义

  子空间是向量空间的非空子集，且满足下面两式：

1. $x,y \in subspace，x+y \in subspace$；
2. $x\in subspace，cx \in subspace$。

子空间举例：$3\times 3$矩阵的上三角矩阵，矩阵的四大子空间(行空间，列空间，零空间，左零空间)。

---

2. 求解Ax=0与Ax=b

  对所有的线性方程组$Ax=b$，其解都可以写成$x=x_{p}+x_{n}$，其中$x_{p}$为特解，满足$Ax_{p}=b$，$x_{n}$为A的零空间中的某一个解向量，满足$Ax_{n}=0$。零空间为矩阵的四大子空间之一，这篇blog的后面会说明，下面先证明一下这一结论。

证明：
解向量$x$满足$Ax=b$，且$Ax_{p}=b$
则$A(x-x_{p}=0)$，故$x-x_{p}=x_{n}$
即$x=x_{p}+x_{n}$

2.1. 主元变量与自由变量

  主元变量：对应到主元(pivot)上的变量
自由变量：对应到非主元上的变量
例如：求解$Ax=b$，$A=\left[\begin{matrix}*1 & 3 & 0 & -1\\0 & 0 & *1 & 1\\0 & 0 & 0 & 0\\\end{matrix}\right] ，x=\left[\begin{matrix}*u\\v\\*w\\y\end{matrix}\right]$其中，$A$中加"$*$“的数字为主元(pivot)，那么对应$x$中加”$*$“的变量就是主元变量，即$u,w$，就是矩阵乘法中和$A$中主元相乘的变量；不加”$*$"的变量为非主元变量，即$v,y$。

2.2. 求Ax=b

  求解顺序是先求$Ax=0$的通解$x_{n}$，在求Ax=b的一个特解$x_{p}$，最后组合成组合解$x=x_{n}+x_{p}$即为线性方程组的解。下面举例说明
$Ax=\left[\begin{matrix}1 & 3 & 3 & 2\\2 & 6 & 9 & 7\\-1 & -3 & 3 & 4\\\end{matrix}\right]\left[\begin{matrix}u\\v\\w\\y\end{matrix}\right]=\left[\begin{matrix}1\\5\\5\end{matrix}\right]=b$经过高斯消去后，方程组变为$Ux=\left[\begin{matrix}1 & 3 & 3 & 2\\0 & 0 & 3 & 3\\0 & 0 & 0 & 0\\\end{matrix}\right]\left[\begin{matrix}u\\v\\w\\y\end{matrix}\right]=\left[\begin{matrix}1\\3\\0\end{matrix}\right]=c$把主元列的非主元也消为0，$Rx=\left[\begin{matrix}1 & 3 & 0 & -1\\0 & 0 & 1 & 1\\0 & 0 & 0 & 0\\\end{matrix}\right]\left[\begin{matrix}u\\v\\w\\y\end{matrix}\right]=\left[\begin{matrix}-2\\1\\0\end{matrix}\right]=d$当然，往往不需要化解到$Rx=d$，到$Ux=c$这一步即可。

1. 求$Ax=0$的通解，令自由变量依次为1，其余自由变量为0，解$Ux=0$，求得$n-r$个$x$($r$为$A$的秩)，$n-r$个$x$的线性组合，即为零空间解$x_{n}$。
   $\left[ \begin{matrix} 1 & 3 & 3 & 2\\ 0 & 0 & 3 & 3\\ 0 & 0 & 0 & 0\\ \end{matrix} \right]\left[ \begin{matrix} u\\ 1\\ w\\ 0 \end{matrix} \right]=\left[ \begin{matrix} 0\\ 0\\ 0 \end{matrix} \right]\Rightarrow x=\left[ \begin{matrix} -3\\ 1\\ 0\\ 0 \end{matrix} \right]$

$\left[\begin{matrix}1 & 3 & 3 & 2\\0 & 0 & 3 & 3\\0 & 0 & 0 & 0\\\end{matrix}\right]\left[\begin{matrix}u\\0\\w\\1\end{matrix}\right]=\left[\begin{matrix}0\\0\\0\end{matrix}\right]\Rightarrow x=\left[\begin{matrix}1\\0\\-1\\1\end{matrix}\right]$

$\Rightarrow x_{n}=c_{1}\left[\begin{matrix}-3\\1\\0\\0\end{matrix}\right]+c_{2}\left[\begin{matrix}1\\0\\-1\\1\end{matrix}\right]$

2. 求$Ax=b$的特解，令自由变量全为0，解$Ux=c$，其解即为$x_{p}$。
   $\left[ \begin{matrix} 1 & 3 & 3 & 2\\ 0 & 0 & 3 & 3\\ 0 & 0 & 0 & 0\\ \end{matrix} \right]\left[ \begin{matrix} u\\ 0\\ w\\ 0 \end{matrix} \right]=\left[ \begin{matrix} 1\\ 3\\ 0 \end{matrix} \right]\Rightarrow x_{p}=\left[ \begin{matrix} -2\\ 0\\ 1\\ 0 \end{matrix} \right]$
3. 组合解$x=x_{n}+x_{p}$即为线性方程组的解。$x=c_{1}\left[ \begin{matrix} -3\\ 1\\ 0\\ 0 \end{matrix} \right]+c_{2}\left[ \begin{matrix} 1\\ 0\\ -1\\ 1 \end{matrix} \right]+\left[ \begin{matrix} -2\\ 0\\ 1\\ 0 \end{matrix} \right]$

2.3. 矩阵的秩

  rank(A)=r(A)=pivots个数

---

3. 线性无关，基与维度

3.1. 线性无关

  对一组向量$v_{1},v_{2},v_{3}\dots v_{k}$，只在$c_{1}=c_{2}=c_{3}=\dots =c_{k}=0$时，$c_{1}v_{1}+c_{2}v_{2}+c_{3}v_{3}+\dots +c_{k}v_{k}=0$，则称$v_{1},v_{2},v_{3}\dots v_{k}$线性无关；否则称为线性相关。

3.2. 向量空间的基

  向量空间的基是向量空间中的一组向量，满足完备且线性无关的性质。所谓完备，即这一组向量可以张成(spanning)这个向量空间，也就是说这个向量空间的任何一个向量均可以表示成这组向量的线性组合。

3.3. 向量空间的维度

  向量空间的维度，即是向量空间的基中的向量个数，又称为自由度。向量空间的基可以选择不同的，但维度不变。

---

4. 矩阵的四个子空间

  对于矩阵$A_{m\times n}$，其四大子空间定义如下：

4.1. 列空间

  用集合表示是$\{y|Ax=y\}$，用符号表示是$C(A)$，维度为$r(A)$。

4.2. 零空间

  用集合表示是$\{x|Ax=0\}$，用符号表示是$N(A)$，维度为$n-r(A)$。

4.3. 行空间

  用集合表示是$\{y|A^{T}x=y\}$，用符号表示是$C(A^{T})$，维度为$r(A)$。

4.4. 左零空间

  用集合表示是$\{x|A^{T}x=0\}$，用符号表示是$N(A^{T})$，维度为$m-r(A)$。

$N(A)$与$C(A^{T})$是$R^{n}$的子空间，有$N(A)+C(A^{T})=R^{n}$。
$N(A^{T})$与$C(A)$是$R^{m}$的子空间，有$N(A^{T})+C(A)=R^{m}$。

---

5. 左逆与右逆

  对$A_{m\times n}$，若$A$列满秩，即$r=n$，潜在条件是$m>n=r$，存在左逆$B=(A^{T}A)^{-1}A^{T}$，使得$BA=I_{n}$。附带一提，此时$Ax=b$至多有一个解，如果$b$在$C(A)$中，就有一个解，如果$b$不在$C(A)$中，就无解，$b$的取值维度是$m$，$A$的列空间维度是$n$，如果$b$是$Ax$的解，那么$b$就要在$A$的列空间，这属于从高维空间选择一个向量，让它能落在低维的$C(A)$中，从概率的角度来看，这种概率发生的几率为0，相当于你在$x-y-z$三维空间随机找一个点，这个点还恰好落在$x-y$坐标平面中，这是很难的。
对$A_{m\times n}$，若$A$行满秩，即$r=m$，潜在条件是$n>m=r$，存在右逆$C=A^{T}(AA^{T})^{-1}$，使得$AC=I_{m}$。附带一提，此时$Ax=b$至少有一个解，$b$的取值维度是$m$，$A$的列空间维度是$m$，如果$b$是$Ax$的解，那么$b$就要在$A$的列空间，由于$b$的取值空间的维度等于$C(A)$，所以任$b$随便取值，$b$都一定在$C(A)$中，所以一定有解，由于$x$是$n$维空间中的向量，$Ax=b$相当于从高维的$x$映射到低纬的$b$，所以$x$一般有多个解。

证明左逆与右逆：
要证明这个结论，需要首先证明一个推论$r(A)=r(A^{T})=r(AA^{T})=r(A^{T}A)$
不难知道$r(A)=r(A^{T})$，下面证明$r(A)=r(A^{T}A)$
要证明$r(A)=r(A^{T}A)$，需要知道两个条件

1. $N(A)=N(A^{T}A)$
2. $A$与$A^{T}A$的列数相同

$A$与$A^{T}A$的列数相同是显而易见的。
同时，考虑到，$Ax=0 \Rightarrow A^{T}Ax=A^{T}(Ax)=0$
且$A^{T}Ax=0 \Rightarrow x^{T}A^{T}Ax=0\Rightarrow (Ax)^{T}(Ax)=0 \Rightarrow Ax=0$
所以$Ax=0$与$A^{T}Ax=0$的解一样，所以$N(A)=N(A^{T}A)$
所以零空间维度$n-r(A)=n-r(A^{T}A)$
所以$r(A)=r(A^{T}A)$
同理可证$r(A^{T})=r(AA^{T})$
所以$r(A)=r(A^{T})=r(AA^{T})=r(A^{T}A)$

$A_{m \times n}$列满秩，$r(A)=n$，所以$r(A^{T}A)=n$，所以$A^{T}A$是可逆的，所以$(A^{T}A)^{-1}A^{T}A=I_{n}$，所以左逆$B=(A^{T}A)^{-1}A^{T}$。

$A_{m \times n}$行满秩，$r(A)=m$，所以$r(AA^{T})=m$，所以$AA^{T}$是可逆的，所以$AA^{T}(AA^{T})^{-1}=I_{m}$，所以右逆$C=A^{T}(AA^{T})^{-1}$。证毕。

注：同上述条件1,2的方法可以证明，对可逆矩阵$P$，$r(A)=r(PA)$。

---

6. 线性变换

  定义一个变换操作$\tilde{A}$，对向量$x,y$，常数$c,d$，满足
$\tilde{A}(cx+dy)=c\tilde{A}(x)+d\tilde{A}(y)$

  即线性组合后的变换=变换后线性组合，满足这样性质的变换操作$\tilde{A}$，就叫做线性变换。线性变换连接两个线性空间，在变换前后的线性空间的基给定时，矩阵可以表示有限维的线性变换，即$\tilde{A} \rightarrow A_{m\times n}$。$A_{m\times n}x=b$表示线性空间$R^{n}$中的向量$x$变换到$R^{m}$中的向量$b$，特殊情况下$m=n$，表示把向量$x$变换到相同线性空间中的另一个向量$b$。结合下图证明$\tilde{A} \rightarrow A_{m\times n}$。

证明：
上图表示，我们有这样的线性变换$\tilde{A}$，能把向量空间$R_{n}$中的向量x变换到向量空间$R_{m}$中的向量y，同时向量空间$R_{n}$有一组基$u_{1},u_{2}\dots u_{n}$，向量空间$R_{m}$有一组基$v_{1},v_{2}\dots v_{m}$
我们先看线性变换$\tilde{A}$作用于$u_{1}$，映射结果用v基表示
$\tilde{A}(u_{1})=[v_{1},v_{2}\dots v_{m}]\left[\begin{matrix}a_{11}\\a_{21}\\\dot{\dot{\cdot}}\\a_{m1}\end{matrix}\right]$

再分别用线性变换$\tilde{A}$作用于$u_{2}\dots u_{n}$，得到下面的等式
$\tilde{A}([u_{1},u_{2}\dots u_{n}])=[v_{1},v_{2}\dots v_{m}]\left[\begin{matrix}a_{11} & a_{12} & \dots &a_{1n}\\a_{21} & a_{22} & \dots &a_{2n}\\\dot{\dot{\cdot}}&&&\dot{\dot{\cdot}}\\a_{m1} & a_{m2} & \dots &a_{mn}\end{matrix}\right]=[v_{1},v_{2}\dots v_{m}]A_{m\times n}$

我们用u基表示向量x：
$x=[u_{1},u_{2}\dots u_{n}]\left[\begin{matrix}x_{1}\\x_{2}\\\dot{\dot{\cdot}}\\x_{n}\end{matrix}\right]$

则线性变换$\tilde{A}$作用于x有
$\begin{aligned} \tilde{A}(x)&=\tilde{A}\left( [u_{1},u_{2}\dots u_{n}]\left[\begin{matrix}x_{1}\\x_{2}\\\dot{\dot{\cdot}}\\x_{n}\end{matrix}\right]\right)\\&=(\tilde{A} [u_{1},u_{2}\dots u_{n}])\left[\begin{matrix}x_{1}\\x_{2}\\\dot{\dot{\cdot}}\\x_{n}\end{matrix}\right] \\&=[v_{1},v_{2}\dots v_{m}]A_{m\times n}\left[\begin{matrix}x_{1}\\x_{2}\\\dot{\dot{\cdot}}\\x_{n}\end{matrix}\right] \\&=[v_{1},v_{2}\dots v_{m}]y\end{aligned}$

向量$y$是用v基表示的，向量$x$是用u基表示的，这就完成了$Ax=y$的操作，把向量$x$映射到$R_{m}$空间的向量$y$，线性变换$\tilde{A}$用矩阵$A$表示。证毕。

6.1. 线性变换与线性组合

  两者均作用于向量，不过线性变换连接两个线性空间，理解成把一个线性空间中的向量变换到了另一个线性空间中的某个向量。而线性组合仅仅在自己空间闹，即向量经线性组合后还在原来的向量空间中。

6.2. 线性变换举例

  放缩、投影、反射、微分、积分都是线性变换。
根据$Ax=y$，把$x=[1,0,0 \dots]$带入，这样求得的$y$就是$A$的第一列，同理改变$x$中1的位置，可求$A$的剩余列，用这种方法求二维旋转、映射、反射矩阵。下图的$c,s$分别是$cos\theta$与$sin\theta$的缩写

  旋转(rotation)矩阵
$R=\left[\begin{matrix}c & -s\\s & c\end{matrix}\right]$

  映射(projection)矩阵
$P=\left[\begin{matrix}c^{2} & cs\\cs & s^{2}\end{matrix}\right]$

  反射(reflection)矩阵，反射矩阵求法除了类似上面，还可以结合映射推出。设向量$x$，$Hx$表示反射向量，$Px$表示映射的向量，则根据向量加法的平行四边形法则($x,Hx$是边，$2Px$是对角线)，有$x+Hx=2Px$

$H=2P-I=\left[\begin{matrix}2c^{2}-1 & 2cs\\2cs & 2s^{2}-1\end{matrix}\right]$

---

7. 应用：图与网络

7.1. 图与关联矩阵

  我们要用矩阵解决图的知识，就要先把图抽象成矩阵。以上图为例，左边的图的关联矩阵即为$A$，$A$的每一行代表一条边，每一列代表一个结点，每一行中的-1表示这条边的起点结点，即边离开的结点，每一行中的1表示这条边的终点结点，即边进入的结点。
如果某些边连成一个循环(loop)，则说明这些边线性相关，如上图的边1,2,3与边3,4,5。

7.2. 四个子空间在图中的应用

  以电学为例，$x=[x_{1},x_{2},x_{3},x_{4}]^{T}$表示四个结点的点电势
$Ax=\left[\begin{matrix}-1 & 1 & 0 & 0\\-1 & 0 & 1 & 0\\0 & -1 & 1 & 0\\0 & -1 & 0 & 1\\0 & 0 & -1 & 1\end{matrix}\right]\left[\begin{matrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\end{matrix}\right]$

$y=[y_{1},y_{2},y_{3},y_{4},y_{5}]^{T}$表示五条边的边电流，沿图中边的箭头指向的电流为正电流。

$A^{T}y=\left[\begin{matrix}-1 & -1 &0 & 0 & 0\\1 & 0 & -1 & -1 & 0\\0 & 1 & 1 & 0 & -1\\0 & 0 & 0 & 1 & 1\end{matrix}\right]\left[\begin{matrix}y_{1}\\y_{2}\\y_{3}\\y_{4}\\y_{5}\end{matrix}\right]$

  零空间的向量$x$一定满足
$\begin{cases} x_{2}-x_{1}=0\\ x_{3}-x_{1}=0\\ x_{3}-x_{2}=0\\ x_{4}-x_{2}=0\\ x_{4}-x_{3}=0 \end{cases}$

  可见零空间中的向量全部满足结点等电势的条件，所以零空间维度一定是1，即$N(A)=1$，即$r(A)=$结点数量$-1$，$N(A)$中的向量表示成$x=c[1,1,1,1,1]^{T}$，c为常数。
列空间的向量$e$满足$Ax=e$，所以列空间中的向量表示给各个边的外加电压源。
左零空间的向量$y$一定满足
$\begin{cases} -y_{1}-y_{2}=0\\ y_{1}-y_{3}-y_{4}=0\\ y_{2}+y_{3}-y_{5}=0\\ y_{4}+y_{5}=0 \end{cases}$

  可见左零空间中的向量满足基尔霍夫电流定律，即各个结点的电流流入等于流出。其基向量可由$Loop$快速找出，沿着$Loop$的方向，顺方向的边电流为1，逆方向的边电流为-1，且按照$Loop$得到的电流分布一定也满足基尔霍夫电流定律，例如A的两个$Loop$确定了基向量$[1,-1,1,0,0]^{T}$与$[0,0,1,-1,1]^{T}$，所以$N(A^{T})=Loop数$，所以$r=$边数-$Loop$数。

  行空间的向量$I$满足$A^{T}y=I$，所以行空间的向量表示各个结点的外加电流源。

7.3. 树

  最小生成树的边的个数为$r(A)-1$，即$r-1$个线性无关的行所对应的边，就可以形成一个最小生成树。
我们可以进一步推导欧拉公式，用#表示数量，由左零空间知：r=#边-#Loop；由零空间知：r=#点-1。所以欧拉公式：#点-#边+#Loop=1

---

参考书籍：
《Linear Algebra and Its Applications》