Linear Algebra MIT 18.06

https://www.bilibili.com/video/bv1bb411H7JN/?p=8

Lecture 1

矩阵乘列向量代表矩阵各列的线性组合

$$\begin{gathered} 2x-y=0 \\ -x+y=3 \end{gathered}$$

$$\begin{gathered} A=\left[\begin{array}{cc}2& -1\\ -1& 2\end{array}\right]X=\left[\begin{array}{c}x\\ y\end{array}\right]b=\left[\begin{array}{c}0\\ 3\end{array}\right] \\ AX=b \\ x\left[\begin{array}{c}2\\ -1\end{array}\right]+y\left[\begin{array}{c}-1\\ 2\end{array}\right]=\left[\begin{array}{c}0\\ 3\end{array}\right] \end{gathered}$$

将各列视作向量，做向量加法，得到右侧向量

Lecture 2

高斯消元法

$$\left[A|b\right]是增广矩阵$$

核心是矩阵行变换，将系数矩阵变为上三角阵（U矩阵），每行第一个非零元素称为主元

1. 交换行
2. scaling（乘标量）
3. 各行相加

$$AX=b\Rightarrow UX=c$$

高斯消元法的矩阵形式

行向量乘矩阵代表矩阵各行的线性组合
$$\begin{gathered} 消元矩阵E（初等矩阵）左乘系数矩阵 \\ {E}_{21}表示将系数矩阵2行1列位置变为0的初等矩阵 \\ E=\left[\begin{array}{ccc}{a}_{11}& & a_{12}\\ a_{21}& & a_{22}\\ a_{31}& & a_{32}\end{array}\right],A=\left[\begin{array}{c}ro{w}_1\\ ro{w}_2\end{array}\right] \\ EA=\left[\begin{array}{c}{a}_{11}\ast ro{w}_1+a_{12}\ast ro{w}_2\\ a_{21}\ast ro{w}_1+a_{22}\ast ro{w}_2\\ a_{31}\ast ro{w}_1+a_{32}\ast ro{w}_2\end{array}\right] \end{gathered}$$
矩阵满足结合律（暴力运算可证）

左乘初等矩阵交换行，右乘初等矩阵交换列（每一列都是将被乘矩阵的列进行线性组合）

利用左乘矩阵进行消元得到主元

可逆矩阵

$$E^{-1}称为E的逆矩阵，E^{-1}E=I$$

Lecture 3

矩阵乘法的求解

1. $$\begin{gathered} AB=C \\ {c}_{ij}=\sum _k{a}_{ik}{b}_{kj} \end{gathered}$$

2. $$\begin{gathered} C_{column\_1}=A{B}_{column\_1} \\ C中每一列等于A乘以B中对应列 \\ 等于A中各列的线性组合 \end{gathered}$$

3. $$\begin{gathered} C_{row\_1}=A_{row\_1}B \\ C中每一行等于A中对应行乘以B \\ 等于B中各行的线性组合 \end{gathered}$$

4. $$\begin{gathered} C=\sum (colofA)(rowofB) \\ {c}_{ij}=a_{第1列第i行}{b}_{第1行第j列}+a_{第2列第i行}{b}_{第2行第j列}+\cdots +a_{第n列第i行}{b}_{第n行第j列} \\ =a_{i1}{b}_{1j}+a_{i2}{b}_{2j}+\cdots +a_{in}{b}_{nj} \\ =\sum _k{a}_{ik}{b}_{kj} \end{gathered}$$

5. 分块计算

矩阵的逆

方阵如果有逆，左逆等于右逆，即
$$\begin{gathered} A^{-1}A=A{A}^{-1}=I \\ 设左逆为A_1,右逆为A_2 \\ {A}_{1}A=I \\ {A}_{1}A{A}_2=A_2 \\ 由结合律A_{1}A{A}_2=A_1(A{A}_2)=A_{1}I=A_1=A_2 \end{gathered}$$
存在非零向量X使得方阵AX=0，则A为不可逆矩阵（奇异矩阵），否则若A可逆，左乘A逆可得X=0，矛盾

Gauss-Jordan消元法

方阵A若有逆，则可通过如下变换求得
$$[A|I]\Rightarrow [I|A^{-1}]$$
求解 AX=I 即通过左乘初等矩阵将左式变为 IX，这些初等矩阵的乘积即为右式，即A的逆

或者用分块的思想看，消元的过程即做行变换，将初等矩阵的乘积记作E，则$E\left[\begin{array}{cc}A& I\end{array}\right]=\left[\begin{array}{cc}I& E\end{array}\right]，则E=A^{-1}$

Lecture 4

$$\begin{gathered} A{A}^{-1}=I \\ (A{A}^{-1}{)}^T=I \\ (A^{-1}{)}^T{A}^T=I \\ (A^T{)}^{-1}=(A^{-1}{)}^T \end{gathered}$$

A=LU分解(假设没有行变换)

下三角阵（L矩阵，右上角是0）相乘仍是下三角阵，上三角阵（U矩阵，左下角是0）相乘仍是上三角阵。

L矩阵可以直接观察得到，消元所需要乘的系数(各行主元系数的比值)可以直接写入L中
$$\begin{gathered} n阶置换矩阵有n!个（左乘可以互换行的矩阵），乘法运算封闭，其逆和其转置相等 \\ {P}^{-1}=P^T \end{gathered}$$

Lecture 5

PA=LU（存在行变换，令主元位置不为0）

对任意可逆矩阵，有PA=LU的分解

对称矩阵

$$定义：A^T=A即(A{)}_{ij}=(A{)}_{ji}$$

$$\begin{gathered} 对任意矩阵R，R^{T}R为对称矩阵 \\ (R^{T}R{)}^T=R^T(R^T{)}^T=R^{T}R \end{gathered}$$

向量空间

空间中的向量对于加法和数乘（线性组合）封闭

必须包含零向量
$$\begin{gathered} R^2的3个子空间： \\ 1.R^2 \\ 2.穿过原点的直线 \\ 3.\left\{\left[\begin{array}{c}0\\ 0\end{array}\right]\right\} \end{gathered}$$
任意两个子空间S和T，则S和T的交集仍然是子空间

Lecture 6

矩阵列空间

矩阵A的列空间C(A)为A中各列的线性组合

Ax=b有解当且仅当b属于A的列空间

矩阵A的零空间为Ax=0的所有向量x的集合

Lecture 7

矩阵的秩

rank(A)=消元之后主元的个数=有主元的行的个数=线性无关的行的个数=线性无关的列的个数（将A化作RREF形式可知这些定义等价），而主元各占一列，因此rank(A)=有主元的列的个数，行秩=列秩

主元所在的列叫主列(pivot column)，其他列称自由列(free column)

自由列对应的变量为自由变量，可任意取值，主元的值由自由变量表示

零空间

零空间是Ax=0的特解的线性组合(数乘系数c并相加)，特解的数量等于自由变量的个数(自由变量分别取1，其余取0，通过线性组合可以得到所有可能值)。以下针对Ax=0

RREF(reduced row echelon form) 简化行阶梯形式，即主元系数化为1，且使得其他行的该主元系数为0

将RREF的主列提前，自由列往后，得到
$$\begin{gathered} R=\left[\begin{array}{cc}I& F\\ 0& 0\end{array}\right] \\ F为自由变量所在的列，A为m行n列，秩为r，则I为r阶，F为n-r阶 \end{gathered}$$
零空间矩阵N(null space matrix)，它的各列由Rx=0的特解组成，RN=0
$$\begin{gathered} Rx=0 \\ [IF]\left[\begin{array}{c}{x}_{pivot}\\ x_{free}\end{array}\right]=0 \\ {x}_{pivot}+F{x}_{free}=0 \\ {x}_{pivot}=-F{x}_{free} \\ 用消元法回代，得到方程的解最终会呈现这种形式 \\ 将x_{free}的n-r个元素轮流取1，其他取0，即得到Rx=0的各个特解，即-F中的各个列（第1个元素取1对应第1列） \\ 即N_{n\ast (n-r)}=\left[\begin{array}{c}-F\\ I\end{array}\right]，注意此处每一列中变量的位置跟原始的[x_1,x_2,\dots ,x_n{]}^T位置不同 \end{gathered}$$

Lecture 8

Ax=b有解时b应满足的条件

仅当b属于A的列空间C(A)时，Ax=b有解，即b为A各列的线性组合，不会出现零行左侧为0右侧不为0的情况。

求Ax=b的所有解

1. 求$ Ax=b $ 的特解，令自由变量为0，求解主元，得到特解$x_p$
2. 取零空间中的向量$x_1,x_2,\cdots ,x_n$，则所有解$x=x_p+c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$

$Ax=b$的特解只需要求一个
$$\begin{gathered} 假设有不同的特解x_{p_1},x_{p_2},A{x}_{p_1}=b,A{x}_{p_2}=b \\ A(x_{p_1}-x_{p_2})=0 \\ (x_{p_1}-x_{p_2})\in N \\ 即x_{p_2}可通过x_{p_1}与N中向量的线性组合得到，所有解（通解）的形式不变 \end{gathered}$$

列满秩时Ax=b的解

每一列都有主元（意味着RREF必定可以化为$\left[\begin{array}{c}I\\ O\end{array}\right]$的形式，若行满秩则没有O），没有自由变量可以赋值，N中只有零向量，Ax=b若有解则有唯一解（只有0或1个解）。

行满秩时Ax=b的解

意味着消元时不会出现零行（$0=b_i，b_i\ne 0$），因此对任意b，Ax=b有解。主元有$m=r$个，自由变量有$n-r=n-m$个。

对于$r=m<n$，RREF必定可与化为$\left[\begin{array}{cc}I& F\end{array}\right]$的形式（可能需要交换行），F将构成零空间的特殊解。

对于$r=m=n,RREF(A)=I,A可逆,Ax=b$ 必定有唯一解。N中只有零向量。

r小于m且r小于n时Ax=b的解

$RREF(A)=\left[\begin{array}{cc}I& F\\ O& O\end{array}\right]$（可能需要行交换），要么无解$(0=b_i,b_i\ne 0)$，要么有无穷多解（若$x_1$为$Ax=b$的解，设$x_n$是$Ax=0$的非零解（$x_n$必定存在否则没有自由变量），则$x=x_1+c{x}_n$均为$Ax=b$的解）。

矩阵的秩决定了方程组解的数目

Lecture 9

线性相关性

向量组$x_1,x_2,\cdots ,x_n,c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n=0$，仅当$c_i$全为$0$时成立，则向量组线性无关，否则线性相关。

向量组里有零向量则必定线性相关。

在一个m维空间里，n>m个向量必定相关。将它们放进矩阵里，Ac=0有非零解，由定义得证。

A的零空间中存在非零向量，则A中各列线性相关，否则线性无关。

从自由变量的角度考虑，则rank(A)=n$\iff$列向量线性无关；rank(A)<n$\iff$线性相关。

基

向量空间的基是指一组向量满足2个性质：1、线性无关；2、生成整个空间。

方阵的列能组成$R^n$的基$\iff$方阵可逆。

对于给定空间，基向量的数量相等。

基向量的个数称为空间的维数。

rank(A)=线性无关的列的个数=主列的个数=列空间的维数

任意n个n维线性无关的向量构成一组基，生成同样的n维空间（若向量的维度大于n，则生成的空间不同；若向量维度小于n，则代入Ax=b，不是线性无关；取n维空间任意b，Ax=b有解，所以生成的空间一定相同。）

零空间的维数=自由变量的数量=n-r

Lecture 10

矩阵的4个基本子空间

列空间C(A)，零空间N(A)，行空间$C(A^T)$，A的左零空间（$A^T$的零空间）$N(A^T)$

C(A)的一组基是主列，维数为r，是$R^m$的子空间

主元所在行数=主元所在列数，因此$C(A^T)$的维数是r，基是RREF的前r行，是$R^n$的子空间

N(A)的一组基是Ax=0的特解，维数是n-r，是$R^n$的子空间

$N(A^T)$的维数是m-r，是$R^m$的子空间。求A的左零空间就是试着寻找一个产生零行向量的行组合，行初等变化可以做到这一点。对于$A_{m\ast n}$，构造$\left[\begin{array}{cc}{A}_{m\ast n}& I_{m\ast m}\end{array}\right]$，用Gauss-Jordan消元法变为$\left[\begin{array}{cc}{R}_{m\ast n}& E_{m\ast m}\end{array}\right]$，即通过左乘E进行行变换，EA=R，A和R的秩为r，R中的零行有m-r个（注意$N(A^T)$的维数是m-r），此时R中的零行对应的E中的行就是要找的$N(A^T)$的基。（行初等变换不改变秩，I的秩为m，所以E的秩为m，E中各行线性无关，所以R中的零行对应的E中的行可以作为基。）

Lecture 11

“向量”空间

$dim(S)+dim(U)=dim(S\cap U)+dim(S+U)$

此处空间（集合）的加法定义是从S任取一个元素与U任一个元素相加

秩的性质

秩为1的矩阵全部可以表示为一个列向量乘一个行向量

rank(A + B) <= rank(A) + rank(B)
$$\begin{gathered} 设A(a_1,a_2,\cdots ,a_n),B(b_1,b_2,\cdots ,b_n),A的秩为s，B的秩为t \\ A的极大线性无关组（最多的线性无关的列）为(a_{i_1},a_{i_2},\cdots ,a_{i_s}) \\ B的极大线性无关组为(b_{j_1},b_{j_2},\cdots ,b_{j_t}) \\ 构造C(a_{i_1},a_{i_2},\cdots ,a_{i_s},b_{j_1},b_{j_2},\cdots ,b_{j_t}) \\ 则A+B可以由C中的列线性组合得到 \\ 所以rank(A+B)\le rank(C)\le s+t=rank(A)+rank(B) \end{gathered}$$
秩为 $r$ 的矩阵可以分解成 $r$ 个秩为$1$的矩阵（每个一主列）

$rank(A^{T}A)\le rank(A),rank(A{A}^T)\le rank(A)$,第一个左边每一行是$A$的行的线性组合，第二个左边每一列是$A$的列的线性组合，得证。

Lecture 12

不说了，牛逼

Lecture 13

复习课

Lecture 14

正交

向量正交的定义$x^{T}y=0$

空间S和T正交的定义是每个S中的向量都与T中的每个向量正交

行空间正交于零空间。x为零空间向量，A中每一行与x点乘都为0，而行空间是由A的各行生成的。

列空间正交于A转置的零空间。

零空间是行空间的正交补，即零空间包含所有与行空间垂直的向量。
$$\begin{gathered} 任意x\in N(A)有Ax=0 \\ {A}^{T}Ax=0 \\ 所以x\in N(A^{T}A) \\ 所以N(A)\subset N(A^{T}A) \\ 对任意x\in N(A^{T}A)有 \\ \begin{array}{rl}0& =x^{T}0\\ & =x^T{A}^{T}Ax\\ & =(Ax{)}^{T}Ax\end{array} \\ 注意Ax为列向量，所以Ax=0 \\ 所以x\in N(A) \\ 所以N(A^{T}A)\subset N(A) \\ 得证N(A^{T}A)=N(A) \end{gathered}$$
$N(A^{T}A)=N(A),rank(A^{T}A)=rank(A)$

$A^{T}A$可逆$\iff$A的零空间内只有零向量$\iff$A的各列线性无关

Lecture 15

投影

向量到向量的投影

$n$维空间中向量$b$投影到向量$a$，投影记作$p,p=xa,e=b-p垂直于a,a^T(b-xa)=0,x=\frac{a^{T}b}{a^{T}a},p=a\frac{a^{T}b}{a^{T}a}$，投影矩阵$P=\frac{a{a}^T}{a^{T}a}$，投影为$p=Pb$

$rank(P)=1$，P的列空间是通过a的一条线，基是a

$P^T=P$

$P^2=P$，对b连续投影2次，和投影1次结果一样

为什么要投影

$Ax=b$可能无解，而$Ax$总在$A$的列空间中，找到列空间中与$b$最接近的向量，即$b$的投影$p$，求解$A\hat{x}=p,\hat{x}$就是最接近原问题的解。

向量到空间的投影

对于$m$维空间的$n$维子空间，有基向量$a_1,a_2,\cdots ,a_n$，空间外有向量$b$，b在空间中的投影记作$p$，$e=b-p$为b中垂直于空间的分量，$p$为基的线性组合，即$p=a_1\widehat{x_1}+a_2\widehat{x_2}+\cdots +a_n\widehat{x_n}$，令$A=\left[\begin{array}{cccc}{a}_1& a_2& \cdots & a_n\end{array}\right],\hat{x}=\left[\begin{array}{c}\widehat{x_1}\\ \widehat{x_2}\\ \cdots \\ \widehat{x_n}\end{array}\right],A\hat{x}=p$，由$a_i\perp e$，得以下方程：
$$\begin{gathered} \{\begin{array}{rl}& {a_1}^T(b-A\hat{x})=0\\ & {a_2}^T(b-A\hat{x})=0\\ & \cdots \\ & {a_n}^T(b-A\hat{x})=0\end{array} \\ 即\left[\begin{array}{c}{a_1}^T\\ {a_2}^T\\ \cdots \\ {a_n}^T\end{array}\right](b-A\hat{x})=\left[\begin{array}{c}0\\ 0\\ \cdots \\ 0\end{array}\right] \\ 即A^T(b-A\hat{x})=0 \end{gathered}$$
$e=(b-A\hat{x}),e\in N(A^T),N(A^T)与A的列空间正交，所以e\perp C(A)$

解上述方程，由$rank(A^{T}A)=rank(A),A^{T}A$列满秩可逆，得$\hat{x}=(A^{T}A{)}^{-1}{A}^{T}b,p=A(A^{T}A{)}^{-1}{A}^{T}b,投影矩阵P=A(A^{T}A{)}^{-1}{A}^T$，此处注意A不是方阵，所以逆不能化简。A如果是方阵，则$C(A)=R^n,P=I$，b就不在空间外，b的投影就是它本身。
对 于 可 逆 矩 阵 M , ( M M − 1 ) T = ( M − 1 ) T M T = I ， 得 到 ( M T ) − 1 = ( M − 1 ) T P T = ( A ( A T A ) − 1 A T ) T = A ( ( A T A ) − 1 ) T A T = A ( ( A T A ) T ) − 1 A T = A ( A T A ) − 1 A T = P P 2 = A ( A T A ) − 1 A T A ( A T A ) − 1 A T = A ( A T A ) − 1 A T = P 对于可逆矩阵M,(MM^{-1})^T=(M^{-1})^TM^T=I，得到\\ (M^T)^{-1}=(M^{-1})^T\\ \begin{aligned} P^T&=(A(A^TA)^{-1}A^T)^T\\ &=A((A^TA)^{-1})^TA^T\\ &=A((A^TA)^T)^{-1}A^T\\ &=A(A^TA)^{-1}A^T\\ &=P\\ P^2&=A(A^TA)^{-1}A^TA(A^TA)^{-1}A^T\\ &=A(A^TA)^{-1}A^T\\ &=P \end{aligned} 对于可逆矩阵M,(MM−1)T=(M−1)TMT=I，得到(MT)−1=(M−1)TPTP2​=(A(ATA)−1AT)T=A((ATA)−1)TAT=A((ATA)T)−1AT=A(ATA)−1AT=P=A(ATA)−1ATA(ATA)−1AT=A(ATA)−1A