第九讲：线性相关性、基、维数
¶线性相关性
- 背景知识:假设一个矩阵A，m<n，即未知数个数大于方程数，因此在零空间内除了零向量之外还有别的向量，最多m个主元，存在n-m个自由向量，整个方程存在非零解。
- 什么条件下，$x_1,x_2,x_3…x_n$线性无关?存在一个系数不全为零的组合，使得线性相加结果为0,则为线性相关，反之为线性无关。
- 如果向量组里存在一个零向量，则这个向量组不可能线性无关。
- 假如在二维空间内随意画三个向量，则他们一定线性相关，为什么？由背景知识可得。
- 对一个矩阵A，我们关心各列是否线性相关，如果零空间内存在非零向量，则各列相关。
- 换一种方式解释：当$v_1,v_2…v_n$是A的各列，如果他们是无关的，那么A的零空间是怎样的？只有零向量。如果他们是相关的呢？那么零空间内除了零向量还存在一个非零向量。
- 列向量无关时，所有的列向量都是主向量，秩为n。列向量相关时，秩小于n。
¶生成空间、基
-
$v_1…,v_l$生成了一个空间，是指这个空间包含这些向量的所有线性组合。
-
向量空间的一组基是指一个向量组，这些向量有两个特性：他们线性无关、他们生成整个空间。
-
举个栗子：求$R^3$的一组基，最容易想到的是
$$
\begin{bmatrix}
1 \
0 \
0 \
\end{bmatrix}
,
\begin{bmatrix}
0 \
1 \
0 \
\end{bmatrix}
,
\begin{bmatrix}
0 \
0 \
1 \
\end{bmatrix}
$$ -
这是一组标准基，另一个栗子:
$$
\begin{bmatrix}
1 \
1 \
2 \
\end{bmatrix}
,
\begin{bmatrix}
2 \
2 \
5 \
\end{bmatrix}
$$ -
显然无法构成一个空间，只要再取一个不在这两个向量构成的平面上的任意一个向量即可。
-
如何检验他们是一组基？将他们作为列构成一个矩阵，矩阵必须可逆(因为此例中为方阵)。
-
若只有例2中2个向量，他们无法构成三维空间的基，那么他们能构成什么空间的基呢？这两个向量所构成的平面。
-
基不是唯一确定的，但所有的基都有共同点：基中向量的个数是相同的。
¶维数
- 上面提到的所有基向量的个数相同，这个个数就是空间的维数。不是基向量的维数，而是基向量的个数
¶最后举个栗子
对矩阵A
$$
\begin{bmatrix}
1 & 2 & 3 &1 \
1 & 1 & 2 & 1 \
1 & 2 & 3 & 1 \
\end{bmatrix}
$$
- 四列并不线性无关，可取第一列第二列为主列
- 2=A的秩=主列数=列空间维数
- 第一列和第二列构成列空间的一组基。
- 如果你知道列空间的维数，则确定了向量的个数，再满足线性无关，这些向量就可以构成一组基。
- 零空间的维数是多少？在本例中零空间中的两个向量(特殊解)为：
$$
\begin{bmatrix}
-1 \
-1 \
1 \
0 \
\end{bmatrix}
,
\begin{bmatrix}
-1 \
0 \
0 \
1 \
\end{bmatrix}
$$ - 这两个特殊解是否构成了零空间的一组基？是的，零空间的维数就是自由变量的个数,即n-r,在本例中是4-2=2。
第十讲：四个基本子空间
- 列空间C(A)，零空间N(A)，行空间C($AT$)，左零空间N($AT$)。
- 分别处于$Rm、Rn、Rn、Rm$空间中
- 列空间与行空间的维数都是秩r，零空间维数是n-r，左零空间维数是m-r
- 列空间的基：主列，共r列。零空间的基：特殊解(自由列)，共n-r个。行空间的基：最简形式R的非0行,共r行
- 行变换是行向量的线性组合，因此A和R的行空间相同，列空间发生了变化
- 为什么叫做左零空间？
$$
rref\begin{bmatrix}
A_{mn} & I_{mn}
\end{bmatrix}\rightarrow
\begin{bmatrix}
R_{mn} & E_{mn}
\end{bmatrix} \
$$ - 易得rref=E，即EA=R
- 通过E可以计算左零空
- 求左零空间即找一个产生零行向量的行组合
- 左零空间的基就是R非0行对应的E行,共m-r行
第十一讲：矩阵空间、秩1矩阵和小世界图
¶矩阵空间
- 可以看成向量空间，可以数乘，可以相加
- 以$3*3$矩阵空间M为例，空间的一组基即9个矩阵，每个矩阵中只包含一个元素1,这是一组标准基，可得这个矩阵空间维数是9
$$
\begin{bmatrix}
1 & 0 & 0 \
0 & 0 & 0 \
0 & 0 & 0 \
\end{bmatrix}，
\begin{bmatrix}
0 & 1 & 0 \
0 & 0 & 0 \
0 & 0 & 0 \
\end{bmatrix}，
\begin{bmatrix}
0 & 0 & 1 \
0 & 0 & 0 \
0 & 0 & 0 \
\end{bmatrix}…
\begin{bmatrix}
0 & 0 & 0 \
0 & 0 & 0 \
0 & 0 & 1 \
\end{bmatrix}
$$ - 再来研究$3*3$矩阵空间中对称矩阵子空间S的维数，可以看到原空间基中9个矩阵，有3个矩阵属于对称矩阵子空间，另外还有上三角与下三角对称的三个矩阵，所以对称矩阵子空间的维数是6
$$
\begin{bmatrix}
1 & 0 & 0 \
0 & 0 & 0 \
0 & 0 & 0 \
\end{bmatrix}，
\begin{bmatrix}
0 & 0 & 0 \
0 & 1 & 0 \
0 & 0 & 0 \
\end{bmatrix}，
\begin{bmatrix}
0 & 0 & 0 \
0 & 0 & 0 \
0 & 0 & 1 \
\end{bmatrix}
$$
$$
\begin{bmatrix}
0 & 1 & 0 \
1 & 0 & 0 \
0 & 0 & 0 \
\end{bmatrix}，
\begin{bmatrix}
0 & 0 & 1 \
0 & 0 & 0 \
1 & 0 & 0 \
\end{bmatrix}，
\begin{bmatrix}
0 & 0 & 0 \
0 & 0 & 1 \
0 & 1 & 0 \
\end{bmatrix}
$$ - 对于上三角矩阵子空间U，易得维数为6，且元空间的基包含了子空间的基
- 接着再来研究$S \bigcap U$ ，易得这个子空间即对角矩阵D，维度为3
- 如果是$S \bigcup U $呢？他们的并的基可以得到所有M的基，所以其维数是9
- 整理一下可得
$$
dim(S)=6,dim(U)=6,dim(S \bigcap U)=3,dim(S \bigcup U)=3 \
dim(S)+dim(U)=dim(S \bigcap U)+dim(S \bigcup U) \
$$ - 再来举一个栗子，说明向量空间不一定有向量，比如下面这个基于微分方程的向量空间
$$
\frac{d2y}{dx2}+y=0
$$ - 他的几个解为
$$
y=cos(x),y=sin(x)
$$ - 完整解为
$$
y=c_1cos(x)+c_2sin(x)
$$ - 即得到一个向量空间，基为2
¶秩1矩阵
- 先写一个简单的秩1矩阵
$$
\begin{bmatrix}
1 & 4 & 5 \
2 & 8 & 10 \
\end{bmatrix}=
\begin{bmatrix}
1 \
2 \
\end{bmatrix}*
\begin{bmatrix}
1 & 4 & 5 \
\end{bmatrix}
$$ - 所有的秩1矩阵都可以表示为一列乘一行
- 秩1矩阵就像积木，比如一个秩为4的矩阵可以由4个秩1矩阵构建而成
- 再来看一个秩1矩阵的栗子，在四维空间中，设向量$v=(v_1,v_2,v_3,v_4)$,集合$S={v|v_1+v_2+v_3+v_4=0}$,假如把S看成零空间，则相应的方程$Av=0$中的矩阵A为
$$
A=\begin{bmatrix}
1 & 1 & 1 & 1 \
\end{bmatrix}
$$ - 易得$dimN(A)=n-r$，所以S的维数是$4-1=3$，S的一组基为
$$
\begin{bmatrix}
-1 \
1 \
0 \
0 \
\end{bmatrix},
\begin{bmatrix}
-1 \
0 \
1 \
0 \
\end{bmatrix},
\begin{bmatrix}
-1 \
0 \
0 \
1 \
\end{bmatrix}
$$ - 矩阵A的四个子空间:易得行空间和列空间的秩(维数)均为1，行空间$C(AT)={a,a,a,a}$，列空间$C(A)=R1$，零空间$N(A)$即S的基线性组合，$N(A^T)={0}$
- 整理一下
$$
dim(N(A))+dim(C(A^T))=3+1=4=n \
dim(C(A))+dim(N(A^T))=1+0=1=m \
$$
¶小世界图
- 仅仅引入了图的概念，为下一讲准备
第十二讲：图和网络
¶图
- 图的一些基础概念，略过
¶网络
-
图的关联矩阵A，将列作为图的节点，行作为矩阵的边，起点为-1，终点为1，其余为0
-
构成回路的几行线性相关，回路意味着相关
-
关联矩阵A描述了图的拓扑结构
-
$dimN(A^T)=m-r$
-
假如图的节点是电势，$Ax$中x即电势，$Ax=0$得到一组电势差方程，零空间是一维的，$ATy$中y即边上的电流，电流与电势差的关系即欧姆定律，$ATy=0$得到基尔霍夫定律，零空间包含了基尔霍夫电流方程的两个解，从电路图上看即两个小回路
-
树就是没有回路的图
-
再来看看$dimN(A^T)=m-r$
-
$dimN(A^T)$=无关回路数
-
$m$=边数
-
$r=n-1$=节点数-1 (因为零空间是一维的)
-
即:节点数-边数+回路数=1(欧拉公式)
¶总结
-
将电势记为e,$e=Ax$
-
电势差导致电流产生，$y=Ce$
-
电流满足基尔霍夫电流方程,$A^Ty=0$
-
将三个方程联立：
$$
A^TCAx=f
$$
这就是应用数学中最基本的平衡方程
第十三讲：正交向量与子空间
¶正交向量
-
正交即垂直，意味着在n维空间内，这些向量的夹角是90度
-
当$x^Ty=0$,x与y正交，证明：
-
若x与y正交，易得:
$$
{||x||}2+{||y||}2={||x+y||}^2 \
$$ -
即：
$$
xTx+yTy={(x+y)}T(x+y)=xTx+yTy+xTy+xyT=2xTy \
$$ -
即：
$$
x^Ty=0 \
$$ -
子空间正交意味着一个子空间内的所有向量与另一个子空间内的每一个向量正交，显然，如果两个二维子空间在某一向量处相交，则这两个空间一定不正交
-
若两个子空间正交，则他们一定不会相交于某一个非零向量，因为这个非零向量同时存在于两个子空间内，它不可能自己垂直于自己
-
行空间正交于零空间，因为$Ax=0$，即矩阵的每一行以及这些行的线性组合(行空间)与解向量(零空间)点乘都为0。这样就证明了图中左半部分
-
图中右半部份，列空间和左零空间分别是矩阵A的转置矩阵的行空间和零空间，刚才的证明同样有效，因此列空间和左零空间正交，图中右半部份成立
-
图中给出了n维空间和m维空间的正交子空间，n维空间的正交子空间:r维行空间和n-r维零空间。m维空间的正交子空间:r维列空间和m-r维左零空间。
¶正交子空间
- 例如三维空间，假如行空间是一维的，则零空间是二维的，行空间是一条直线，零空间是垂直于这个直线的平面，从几何上可以直观看出他们正交
- 因为零空间是行空间的正交补集，所以零空间包含了所有正交于行空间的向量
- 以上是所有关于解$Ax=0$的知识，如果要解不可解的方程，或者说求最优解，该怎么办呢？我们引入一个重要的矩阵$A^TA$
- $A^TA$是一个$n*n$的方阵，而且对称
- 坏方程转换为好方程，两边同乘$A^T$
- $ATA$不总是可逆，若可逆，则$N(ATA)=N(A)$，且他们的秩相同
- $A^TA$可逆当且仅当零空间内只有零向量，即各列线性无关，下一讲将证明这些性质
第十四讲：子空间投影
¶投影
- 在二维情况下讨论投影
- 一个点b到另一条直线a的投影，即从这个点做垂直于a的垂线段交a于p点，p即b在a上的投影点，以p为终点的向量即投影p，垂线段即误差e，e=b-p
- p在a的一维子空间里，是a的x倍，即p=xa
- a垂直于e，即
$$
a^T(b-xa)=0 \
xaTa=aTb \
x= \frac {aTb}{aTa} \
p=a\frac {aTb}{aTa} \
$$ - 从式子中可以看到，若b翻倍，则投影翻倍，若a变化，则投影不变，因为分子分母抵消了
¶投影矩阵
- 现在可以引入投影矩阵P的一维模式(projection matrix)，$p=Pb$,$P= \frac {aaT}{aTa}$
- 用任意b乘投影矩阵，总会落在通过a的一条线上(即b在a上的投影p),所以投影矩阵的列空间是这条线，矩阵的秩为1
- 投影矩阵的另外两条性质：
- 对称,即$P^T=P$
- 两次投影在相同的位置，即$P^2=P$
¶投影的意义
- 下面在高维情况下讨论
- 当方程数大于未知数个数时，经常无解，这时我们只能找出最接近的解
- 如何找？将b微调，使得b在列空间中
- 怎么微调？将b变成p，即列空间中最接近b的那一个，即转换求解$Ax^{'}=p$,p时b在列空间上的投影
- 现在我们要求$x{'}$,$p=Ax{‘}$，误差向量$e=b-Ax^{’}$，由投影定义可知e需要垂直于A的列空间
- 综上可得
$$
AT(b-Ax{'})=0 \
$$ - 由上式可以看出e在A的左零空间，与列空间正交。解上式可得
$$
x{'}=(ATA){-1}ATb \
p=Ax{'}=A(ATA){-1}ATb \
$$ - 即投影矩阵P的n维模式:
$$
A(ATA){-1}A^T \
$$ - 投影矩阵P的n维模式依然保留了1维模式的两个性质
- 现在回到求最优解，最常见的一个例子是通过最小二乘法拟合一条直线
- 已知三个点$a_1,a_2,a_3$，找出一条直线拟合接近三个点,$b=C+Da$
- 假如$a_1=(1,1),a_2=(2,2),a_3=(3,2)$,则
$$
C+D=1 \
C+2D=2 \
C+3D=2 \
$$
写成线代形式为:
$$
\begin{bmatrix}
1 & 1 \
1 & 2 \
1 & 3 \
\end{bmatrix}
\begin{bmatrix}
C \
D \
\end{bmatrix}
\begin{bmatrix}
1 \
2 \
2 \
\end{bmatrix}
$$ - 即Ax=b,方程数大于未知数个数，若两边乘以A转置，即求$x^{'}$，这样就可以求出拟合直线。下一讲继续此例
第十五讲：投影矩阵和最小二乘法
¶投影矩阵
-
回顾，$P=A(ATA){-1}A^T$,$Pb$即b在A的列空间上的投影，现在考虑两种极端情况，b在列空间上和b正交于列空间：
b在列空间上：$Pb=b$；证明：若b在列空间上，则可以表示为$b=Ax$，在A各列线性无关的条件下，$(ATA)$可逆，代入$P=A(ATA){-1}AT$有$Pb=b$
b正交于列空间，$Pb=0$；证明：若b正交于列空间则b在左零空间内，即$ATb=0$，显然代入$P=A(ATA){-1}AT$有$Pb=0$ -
p是b在列空间上的投影，因为列空间正交于左零空间，自然e就是b在左零空间上的投影，如图：
$$
b=p+e \
p=Pb \
$$ -
所以
$$
e=(I-P)b \
$$ -
所以左零空间的投影矩阵为$(I-P)$
¶最小二乘法
-
回到上一讲的例子，找到一条最优直线接近三个点，最小化误差，如图
-
设直线为$y=C+Dt$，代入三个点坐标得到一个方程组
$$
C+D=1 \
C+2D=2 \
C+3D=2 \
$$ -
此方程组无解但是存在最优价，从代数角度看：
$$
||e||2=(C+D-1)2+(C+2D-2)2+(C+3D-2)2 \
$$ -
分别对C和D求偏导为0，得到方程组:
$$
\begin{cases}
3C+6D=5\
6C+14D=11\
\end{cases}
$$ -
写成矩阵形式，这里的$C,D$仅仅存在一个形式，他们无解，要解出$C,D$是将其作为拟合直线，即b被替换为投影p时的$C,D$。
$$
Ax=b \
\begin{bmatrix}
1 & 1 \
1 & 2 \
1 & 3 \
\end{bmatrix}
\begin{bmatrix}
C \
D \
\end{bmatrix}=
\begin{bmatrix}
1 \
2 \
2 \
\end{bmatrix}
$$ -
A满足各列线性无关，b不在A的列空间里，现在我们想最小化误差$e=Ax-b$，怎么量化误差？求其长度的平方$||e||^2$，在图中即y轴方向上点到拟合直线的距离的平方和。这些点$b_1,b_2,b_3$的误差线段$e_1,e_2,e_3$与拟合直线交于$p_1,p_2,p_3$，当将三个b点用三个p点取代时，方程组有解。
-
现在要解出$x{'},p$，已知$p=Ax{‘}=A(ATA){-1}ATb$，$Ax=b$，两边同乘$AT$联立有
$$
ATAx{’}=A^Tb
$$ -
代入数值可得
$$
\begin{cases}
3C+6D=5\
6C+14D=11\
\end{cases}
$$ -
与代数求偏导数结果一样,之后可以解出$C,D$，也就得到了拟合直线
-
回顾一下上面两幅图，一张解释了$b,p,e$的关系，另一张用$C,D$确定了拟合直线，由$C,D$确定的列组合就是向量p
-
如果A的各列线性无关，则$A^TA$是可逆的，这时最小二乘法使用的前提，证明：
如果矩阵可逆，则它的零空间仅为零向量，即$A^TAx=0$中x必须是零向量
$$
A^TAx=0 \
xTATAx=0 \
(Ax)^T(Ax)=0 \
Ax=0 \
$$ -
又因为A各列线性无关，所以
$$
x=0
$$ -
即证
-
对于处理相互垂直的单位向量，我们引入标准正交向量组，这个矩阵的各列是标准正交而且是单位向量组，下一讲将介绍更多关于标准正交向量组的内容
第十六讲：正交矩阵和Gram-Schmidt正交化
¶正交矩阵
- 已知一组正交向量集
$$
q_i^Tq_j=
\begin{cases}
0 \quad if \quad i \neq j \
1 \quad if \quad i=j \
\end{cases}
$$
$$
Q=
\begin{bmatrix}
q_1 & q_2 & … & q_n \
\end{bmatrix} \
Q^TQ=I \
$$ - 所以，对有标准正交列的方阵，$QTQ=I$,$QT=Q^{-1}$,即正交矩阵，例如
$$
Q=\begin{bmatrix}
cos \theta & -sin \theta \
sin \theta & cos \theta \
\end{bmatrix}or
\frac {1}{\sqrt 2}
\begin{bmatrix}
1 & 1 \
1 & -1 \
\end{bmatrix}
$$ - Q不一定是方阵。Q的各列将是列空间的标准正交基
- 对Q，投影到Q的列空间的投影矩阵P是什么？$P=Q(QTQ){-1}QT=QQT$
¶Gram-Schmidt正交化
- 给定两个不正交的向量a和b，我们希望从a,b中得到两个正交向量A,B，可设A=a，则B就是b投影到A上的误差向量e：
$$
B=e=b-\frac{ATb}{ATA}A
$$ - 正交基就是A,B除以他们的长度$q_1=\frac{A}{||A||}$
- 扩展到求三个向量，即A,B,C的情况，从上式我们已知A，B，同理，C需要c剪去在A和B上的投影分量
$$
C=c- \frac {ATc}{ATA}A- \frac {BTc}{BTB} B
$$ - 由a,b组成列向量的矩阵A就通过施密特正交化变成了正交矩阵Q,用公式推导可以看出，Q的各列$q_1,q_2,…$与$a,b,…$在同一列空间内，正交化可以写成
$$
A=QR \
$$ - 即
$$
\begin{bmatrix}
a & b \
\end{bmatrix}=
\begin{bmatrix}
q_1 & q_2 \
\end{bmatrix}
\begin{bmatrix}
q_1^Ta & q_1^Tb \
q_2^Ta & q_2^Tb \
\end{bmatrix} \
$$ - 其中，因为$QQ^T=I$
- 所以$R=Q^TA$
- $q_2$与$q_1$正交，而$q_1$只是$a$的单位化，所以$q_2^Ta=0$，即$R$是上三角矩阵