MIT 18.06：线性代数

方程组的几何解释

二元一次方程组：

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

可以写成矩阵形式：

$$\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} =\begin{bmatrix} 0 \\ 3 \end{bmatrix}$$

更进一步抽象：

$$Ax = b$$

列的线性组合：

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

对任何 $b$，能否求解 $Ax = b$

也就是，列的线性组合能否覆盖整个空间

矩阵右乘一个向量表示列的线性组合

$$\begin{bmatrix} 2 & 5 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix} = 1 \begin{bmatrix} 2\\ 1 \end{bmatrix}+2\begin{bmatrix} 5 \\ 3 \end{bmatrix} = \begin{bmatrix} 12 \\ 7 \end{bmatrix}$$

矩阵消元

高斯消元过程演示：

$$\left[\begin{array}{ccc:c} \boxed{1} & 2 & 1 & 2\\ 3 & 8 & 1 & 12\\ 0 & 4 & 1 & 2 \end{array}\right] → \left[\begin{array}{ccc:c} \boxed{1} & 2 & 1 & 2\\ 0 & \boxed{2} & 2 & 6\\ 0 & 4 & 1 & 2 \end{array}\right] → \left[\begin{array}{ccc:c} \boxed{1} & 2 & 1 & 2\\ 0 & \boxed{2} & 2 & 6\\ 0 & 0 & \boxed{5} & -10 \end{array}\right]$$

方框框出来的为每一步消元得到的主元 pivot，主元不能为 0，如果为 0，则与下面的非 0 元素作行交换

虚线左边的是增广矩阵 augmented matrix，相当于新增加的一列

最后进行回代即可解决

消元的目的是从 $A$ 得到 $U$（上三角矩阵）

一个矩阵左乘一个向量表示行的线性组合，而每个消元的过程就是矩阵的行变换，故每个消元过程可以用原始矩阵左乘一个矩阵表示，如：

$$\begin{bmatrix} 1 & 0 & 0 \\ -3 &1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix} =\begin{bmatrix} 1 & 2 & 1\\ 0 & 2 & 2\\ 0 & 4 & 1 \end{bmatrix}$$

第一个矩阵就是一个消元矩阵，记作 $E_{21}$

所以例子的消元过程为：

$$E_{32}(E_{21}A) = U$$

矩阵乘法中括号可以移动，故整个过程可以用一个矩阵表示

单位矩阵：

$$\begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix}$$

置换 permutation矩阵：

$$\begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix}$$

某个矩阵左乘该矩阵，表示置换其两行；
某个矩阵右乘该矩阵，表示置换其两列；

逆 inverse：如何将 $U$ 还原为 $A$

$$\begin{bmatrix} 1 & 0 & 0 \\ 3 &1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ -3 &1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

表示为 $E^{-1}E=I$

乘法和逆矩阵

两个矩阵相乘 $AB = C$：

• 新矩阵中的某个元素 $c_{34} =$ (row 3 of A)⋅(col 4 of B) $= \sum_{k=1}^n a_{3k}b_{k4}$
• $C$ 的列是 $A$ 的列的线性组合
• $C$ 的行是 $B$ 的行的线性组合
• $AB$ = $A$ 各列与 $B$ 各行乘积之和
• 矩阵分块

逆 inverse：

$$A^{-1}A = I = AA^{-1}$$

如果左逆存在，则称该矩阵为可逆的 invertible或非奇异的 nonsingular

如果可以找到一个非零向量 $x$，使得 $Ax = 0$，则该矩阵是不可逆的

高斯-若尔当 Gauss-Jordan（同时处理两个方程组）

$$\begin{cases} \begin{bmatrix} 1 & 3 \\ 2 & 7 \end{bmatrix} \begin{bmatrix} a\\ b \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix} \\ \begin{bmatrix} 1 & 3 \\ 2 & 7 \end{bmatrix} \begin{bmatrix} c\\ d \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix} \end{cases} → \left[\begin{array}{cc:cc} 1 & 3 & 1 & 0\\ 2 & 7 & 0 & 1 \end{array}\right] → \left[\begin{array}{cc:cc} 1 & 3 & 1 & 0\\ 0 & 1 & -2 & 1 \end{array}\right] → \left[\begin{array}{cc:cc} 1 & 0 & 7 & -3\\ 0 & 1 & -2 & 1 \end{array}\right]$$

整个过程就是 $AI → IA_{-1}$

简单证明：$E[AI] = [IA^{-1}]$

矩阵 A 的 LU 分解

$$(AB)(B^{-1}A^{-1})=I$$

$$(AA^{-1})^T = (A^{-1})^TA^T = (A^T)^{-1}A^T$$

没有行交换的一个消元过程：$E_{21}A = U$

$$\begin{bmatrix} 1 & 0\\ -1 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1\\ 8 & 7 \end{bmatrix} = \begin{bmatrix} 2 & 1\\ 0 & 3 \end{bmatrix}$$

两边左乘 $E_{21}$ 的逆，就是分解过程 $A = LU$：

$$\begin{bmatrix} 2 & 1\\ 8 & 7 \end{bmatrix} =\begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1\\ 0 & 3 \end{bmatrix}$$

其中 $L$ 是下三角矩阵

有时可以更进一步分解得到 $LDU$，D 为对角矩阵 Diagonal matrix：

$$\begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix} \begin{bmatrix} 2 & 0\\ 0 & 3 \end{bmatrix} \begin{bmatrix} 1 & \frac{1}{2}\\ 0 & 1 \end{bmatrix}$$

为什么 $L$ 比 $E_{32}E_{21}$ 好？

$$E= \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & -5 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} =\begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ 10 & -5 & 1 \end{bmatrix}$$

$$L= \begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 5 & 1 \end{bmatrix} =\begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 0 & 5 & 1 \end{bmatrix}$$

观察可得，$E$ 中有 -2 和 -5 相乘得到的 10，而 $L$ 中不存在未出现的数

如果没有行交换，消元所用的乘数全部记录在 $L$ 中，即 $A$ 的信息全部记录在 $L$ 和 $U$ 中

对于 $n × n$ 的矩阵 $A$，分解需要 $n^3$ 次操作

对于单位矩阵所有经过置换得来的置换矩阵，构成一个群，其两两乘积也在这个群中，

置换矩阵的性质：逆等于其转置

转置、置换、向量空间

有行交换的消元：$PA = LU$，其中 $P$ 为置换矩阵，即行重新排列了的单位矩阵，对于 $n × n$ 的矩阵有 $n!$ 个，$P^{-1}=P^T$

转置 transpose：$(A^T)_{ij}=A_{ji}$

对称矩阵 symmetric matrix：$A^T=A$

定理：$R^TR$ 是对称的

证明：$(R^TR)^T=R^TR$

向量空间：$R^2$ 指所有二维向量，也可称为“xy 平面”，且其中所有向量的线性组合也在这个空间内（对线性组合封闭）

$R^2$ 的子空间 subspace

• $R^2$ 本身
• 所有穿过原点的线（不同于 $R_1$）
• 零向量

从矩阵中构造子空间：列向量的所有线性组合构成一个子空间，称作列空间 $C(A)$

列空间和零空间

对于两个子空间 $S$ 和 $T$，$S ∩ T$ 也是一个子空间

从线性方程组的角度 $Ax = b$：

$$\begin{bmatrix} 1 & 1 & 2\\ 2 & 1 & 3\\ 3 & 1 & 4\\ 4 & 1 & 5 \end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}= \begin{bmatrix} b_1\\b_2\\b_3\\b_4 \end{bmatrix}$$

一般情况下这种方程组无解，因为列空间无法填充整个向量空间，即有些向量 $b$ 不会落在该子空间内

所以线性方程组有解的充要条件是 $b$ 在列空间内

该矩阵中的第三列没有作出任何贡献，可以去掉，其它两列称为主列

$A$ 的零空间 nullspace是 $Ax = 0$ 的解，例如上述矩阵的零空间为 $k(1,1,-1)^T$

定理：零空间是子空间

证明：如果 $Av = 0$ 且 $Aw = 0$，则 $A(v + w) = 0$

求解 Ax=0、主变量、特解

进行消元：

$$A= \begin{bmatrix} 1 & 2 & 2 & 2\\ 2 & 4 & 6 & 8\\ 3 & 6 & 8 & 10 \end{bmatrix} → \begin{bmatrix} \boxed{1} & 2 & 2 & 2\\ 0 & 0 & \boxed{2} & 4\\ 0 & 0 & 0 & 0 \end{bmatrix}$$

矩阵的秩 rank = 主元的个数 = 自由变量的个数

主元所在的列为主列，其它的列为自由列，自由列表示的变量为自由变量

取线性无关的自由变量，回代得到主变量

$$x=c\begin{bmatrix} -2\\1\\0\\0 \end{bmatrix}+d\begin{bmatrix} 2\\0\\-2\\1 \end{bmatrix}$$

简化行阶梯形式 reduced row echelon form：主元上下全为 0 且主元为 1

$$\begin{bmatrix} \boxed{1} & 2 & 0 & -2\\ 0 & 0 & \boxed{1} & 2\\ 0 & 0 & 0 & 0 \end{bmatrix}$$

该形式可以得到主行和主列，主行和主列构成一个单位矩阵，自由列和主行也构成一个矩阵。

可以观察到，零解也存在这一个单位矩阵和那个矩阵的相反数，即 rref 告诉了我们特解的性质

用矩阵表达 $Rx = 0$，$RN = 0$：

$$R=\begin{bmatrix} I&F\\0&0 \end{bmatrix}$$

$$N=\begin{bmatrix} -F\\I \end{bmatrix}$$

可解性和解的结构

$Ax = b$ 的可解的条件（两个条件是等价的）：

• $b$ 在 $C(A)$ 中
• 如果 $A$ 的行的线性组合得到 0，则 $b$ 的相同组合也必须得到 0

找到 $Ax = b$ 的全部解：

• 特解：把所有自由变量设为 0，求解主变量（$Ax_p=b$）
• 通解：零空间（$Ax_n = 0$）
• 解 = 特解 + 通解（$A(x_p+x_n) = b$）

$m × n$ 的矩阵，秩为 $r$，当然，$r ≤ m, r ≤ n$

• 列满秩（$r = n < m$），$R=\left[\begin{smallmatrix} I\\0 \end{smallmatrix}\right]$此时只有 1 或 0 个解
• 行满秩（$r=m<n$），$R=[I F]$ 必然有解
• $r = m = n$，$R = I$，1 个解

线性相关性、基、维数

如果向量 $v_1, v_2, ⋯, v_n$ 没有线性组合能得到 0（除了 $c$ = 0），则该向量组线性无关 independent

和矩阵的关系：若 $v_1, v_2, ⋯, v_n$ 是 $A$ 的列向量，如果 $A$ 的零空间只有零向量，则其线性无关；反之，则线性相关

$v_1, v_2, ⋯, v_n$ 生成 span 了一个空间：该空间由那些向量的所有线性组合构成

空间的基 basis 是一系列向量 $v_1, v_2, ⋯, v_n$，满足

• 线性无关
• 其生成了该空间

给定一个空间，其每一组基向量数目相同（空间的维度 dimension）

$A$ 的秩 = 主列数 = $C(A)$ 的维度 $N(A)$ 的维度 = 自由变量数 = $n - r$

四个基本子空间

• 列空间 $C(A)$，在 $R^m$ 中
• 零空间 $N(A)$，在 $R^n$ 中
• 行空间 = 行的所有线性组合 = $A^T$ 的列的所有线性组合，在 $R^m$ 中
• $A^T$ 的零空间 = $N(A^T)$，叫做左零空间，在 $R^n$ 中

在高斯-若尔当消元法中，列空间改变了，但行空间没有改变

$rref[A_{m×n}I_{m×n}] → [R_{m×n}E_{m×n}]$，即 $E$ 将行变换记录了下来

新的向量空间：所有 $3 × 3$ 的矩阵，即把矩阵看成向量（因为其能够数乘和相加），实质是把 $R^n$ 变成 $R^{n×n}$

其子空间：

• 上三角矩阵
• 对称矩阵
• 对角矩阵

矩阵空间、秩 1 矩阵、小世界图

$3 × 3$ 的矩阵空间 $M$，其维度为 9，其一个子空间 $S$ 由对称矩阵组成，$S$ 的维度为 6

$S ∩ U = D$，维度为 3；$S + U$ 的维度为 9

可以得到：对于两个子空间，其维度之和 = 相交得到的空间的维度 + 相加得到的空间的维度

对于微分方程

$$\frac{\mathrm{d}^2y}{\mathrm{d}x^2} + y = 0$$

$$y = c_1 \cos x + c_2 \sin x$$

其中 $\cos x$ 和 $\sin x$ 都是一组基，尽管是函数，但因为也可以做加法和数乘，故可以看做向量

对于秩为 1 的矩阵，可以写成一行乘一列的形式($A=uv^T$)

$$\begin{bmatrix} 1 & 4 & 5\\ 2 & 8 & 10 \end{bmatrix}=\begin{bmatrix} 1\\2 \end{bmatrix}\begin{bmatrix} 1 & 4 & 5 \end{bmatrix}$$

更一般地说，一个秩为 4 的矩阵可以被分解为 4 个秩为 1 的矩阵（泛化的基向量），这些矩阵不构成一个子空间

向量 $v = (v_1, v_2, v_3, v_4)^T$，$v_1 + v_2 + v_3 + v_4 = 0$

将其构造为矩阵 $[1 1 1 1]$ 的零空间

图和网络

关联矩阵：如果图中两结点有有向边相连，则该行中结点的值为 -1 和 1

$$\begin{bmatrix} -1 & 1 & 0 & 0\\ 0 & -1 & 1 & 0\\ -1 & 0 & 1 & 0\\ -1 & 0 & 0 & 1\\ 0 & 0 & -1 & 1 \end{bmatrix}$$

注意到前三行线性相关，说明图中存在无向回路

而该矩阵的零空间则表明结点电势都是由一个常数决定的

其左零空间表示为：

$$\begin{aligned} -y_1 - y_3 - y_4 &= 0 \\ y_1 - y_2 &= 0\\ y_2 + y_3 - y_5 &= 0 \\ y_4 + y_5 &= 0 \end{aligned}$$

该空间的两组基：

$$\begin{bmatrix} 1\\1\\-1\\0\\0 \end{bmatrix}, \begin{bmatrix} 0\\0\\1\\-1\\1 \end{bmatrix}$$

表示电路中的两个回路，两者相加则是大回路

对于行空间，主列表示的边形成一个生成树

维度公式的意义：$N(A^T)$ 的维度 = $m - r$，即 回路数 = 边数 - （节点数- 1）

改写以下得到二维的欧拉公式：结点数 - 边数 + 回路数 = 1

若 $x = x_1, x_2, x_3, x_4$ 表示结点处电势 → 其与关联矩阵相乘可得到电势差 → 通过欧姆定律，得到每条边的电流 → $A^Ty = 0$ KCL

更进一步得到平衡公式：$A^T CAX = f$，其中 $C$ 为与欧姆定律有关的常数，$f$ 为外加电流

正交向量和子空间

若向量 $x^Ty = 0$，则这两个向量正交 orthogonal

证明勾股定理：

$$\Vert x\Vert ^2 + \Vert y\Vert ^2 = \Vert x + y\Vert ^2$$

即证：

$$x^Tx + y^Ty = (x + y)^T(x + y)$$

展开得到：

$$0 = 2x^Ty$$

如果 $S$ 中的每个向量都和 $T$ 中的每个向量正交，则子空间 $S$ 和 $T$ 正交

行空间和零空间正交，列空间和左零空间正交，即实际上将某个空间分成了两个正交的子空间

将零空间和行空间称作空间 $R^n$ 的正交补 orthogonal complements

对于 $Ax = b$ 无解的情况，$m > n$，即数据过多了，需要将 $A$ 转化为一个可逆的矩阵，方法是两边同乘 $A^T$，得到

$$A^TA\hat{x} = A^Tb$$

$N(A^TA) = N(A)$，$A^TA$ 的秩 = $A$ 的秩

子空间投影

$x$ 满足 $a^T(b - xa) = 0$，解得

$$x = \frac{a^Tb}{a^Ta}$$

$$p = ax = a\frac{a^Tb}{a^Ta}$$

所以投影 $p = Pb$，其中 $P$ 是个矩阵，$P = \frac{aa^T}{a^Ta}$

• $C(P)$是一条经过 $a$ 的线
• $P$ 的秩为 1
• 对称 $P^T = P$
• 重复投影不变 $P^2 = P$

为什么要做投影？

• $Ax = b$ 可能无解
• 转而求解 $A\hat{x} = p$，$p$ 为 $b$ 向列空间的投影

$b$ 向平面作投影，$e = b - A\hat{x}$($e$ 在 $N(A^T)$ 中，即 $e$ 与 $C(A)$ 正交)垂直于平面，即

$$\begin{cases} a_1^T(b - A\hat{x}) = 0 \\ a_2^T(b - A\hat{x}) = 0 \end{cases}$$

写成矩阵的形式：

$$A^T(b - A\hat{x}) = 0$$

进一步得出向矩阵投影的投影矩阵：

$$P = A\hat{x} = A(A^TA)^{-1}A^T$$

投影矩阵、最小二乘

最小二乘法 least squares 拟合直线

最小化 $|Ax - b|^ = |e|^2$

定理：如果 $A$ 各列线性无关，则 $A^TA$ 可逆

证明：假设 $A^TAx = 0$

两边同乘 $x^T$，得到$(Ax)^T(Ax) = 0$，即 $Ax = 0$

故 $x = 0$

如果各列标准正交 orthonormal vectors，则其线性无关

正交矩阵、Schmidt 正交化

标准正交向量组：$q_i^T q_j = \begin{cases} 0, i ≠ j\\ 1, i = j \end{cases}$

正交矩阵（各列标准正交）：$Q^TQ = I$

如果 $Q$ 是方阵，则有性质：$Q^T = Q^{-1}$

$Q$ 的投影矩阵的性质：

$P = QQ^T$，如果 $Q$ 为方阵，则进一步简化为 $I$

对于公式 $A^TA\hat{x} = A^Tb$，若 $A = Q$

简化为 $\hat{x} = Q^T b$，即 $\hat{x_i} = q_i^T b$，所求的 $\hat{x}$ 就是一个数量积

Gram-Schmidt 正交化

• 线性无关的向量 $a, b$
• 正交化 $A, B$：$B = b - \frac{A^Tb}{A^TA}A$（若有第三个向量 $c$，则 $C = c - \frac{A^Tc}{A^TA}A - \frac{B^Tc}{B^TB}B$
• 单位化 $q_1 = \frac{A}{|A|}, q_2 = \frac{B}{|B|}$

从消元的角度审视 Gram-Schmidt 正交化：

$$A = QR$$

$R$ 是个上三角矩阵，因为

$$\begin{bmatrix} a \\ b \end{bmatrix}=\begin{bmatrix} q_1\\q_2 \end{bmatrix}\begin{bmatrix} a_1^Tq_1 & *\\ a_1^Tq_2 & * \end{bmatrix}$$

其中 $a_1^Tq_2 = 0$，因为构造出的 $q_2$ 垂直于原先的向量

行列式及其性质

行列式 determinants：把尽可能多的关于矩阵的信息包含在一个数里

性质：

1. $\operatorname{det}I = 1$
2. 交换行：反转行列式的符号

3. 1. $$\begin{vmatrix} ta & tb \\ c & d \end{vmatrix}=t \begin{vmatrix} a & b \\ c & d \end{vmatrix}$$

   2. $$\begin{vmatrix} a + a^{\prime} & b + b^{\prime} \\ c & d \end{vmatrix} = \begin{vmatrix} a & b \\ c & d \end{vmatrix} + \begin{vmatrix} a^{\prime} & b^{\prime} \\ c & d \end{vmatrix}$$

4. 两行相等 → 行列式为 0
5. 从某一行减去另一行的 $k$ 倍不改变行列式
6. 有一行全是 0 → 行列式为 0
7. 上三角矩阵的行列式的值等于对角线上元素的乘积
8. 可逆矩阵的行列式为 0
9. $\operatorname{det}AB = \operatorname{det}A × \operatorname{det}B$ $\operatorname{det}A^{-1} = \frac{1}{\operatorname{det}A}$
10. $\operatorname{det}A^T = \operatorname{det}A$

行列式公式、代数余子式

行列式公式：

$$\operatorname{det}A = \sum_{n!}±a_{1α}a_{2β}a_{3γ}⋯a_{nω}, (α,β,γ,⋯ω) = (1,2,⋯,n)\text{的排列}$$

$a_{ij}$ 的代数余子式 cofactor $C_{ij}$ 为 $(-1)^{i+j} \operatorname{det}$除去第 $i$ 行和第 $j$ 列的矩阵

代数余子式公式：

$$\operatorname{det}A = a_{11}C_{11} + a_{12}C_{12} + ⋯ + a_{1n}C_{1n}$$

克拉默法则、逆矩阵、体积

$2 × 2$矩阵的逆矩阵公式：

$$\begin{bmatrix} a & b\\ c & d \end{bmatrix}^{-1}=\frac{1}{ad - bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}$$

广泛的版本：$C$为代数余子式矩阵

$$A^{-1}=\frac{1}{\operatorname{det}A}C^T$$

克拉默法则 Cramer's rule：

$$x_i = \frac{\operatorname{det}B_i}{\operatorname{det}A}$$

$B_i$ 为将 $A_i$ 的第 $i$ 列换成 $b$ 得到的矩阵

克拉默法则并不适合解方程，只是告诉我们可以使用代数式子而不是一个算法来解方程

几何解释：$A$ 的行列式的体积 = 箱子的体积

例：求解顶点坐标分别为 $(x_1, y_1)$、$(x_2, y_2)$、$(x_3, y_3)$ 的三角形面积 =

$$\frac 12 \begin{vmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{vmatrix}$$

特征值、特征向量

特征向量 eigenvector $x$ 满足：$Ax$ 平行于 $x$，即

$$Ax = λx$$

$λ$ 为特征值 eigenvalue

如果 $A$ 不可逆，则其中一个特征值为 $λ = 0$

对于投影矩阵，如果向量 $x$：

• 在投影平面上，则特征值为 1
• 垂直于投影平面，特征值为 0

特征值的和 = 对角线元素和（迹 trace）

求解方法：$Ax = λx = λIx$，移项后得到 $(A-λI)x = 0$

即可以先通过求解 $\operatorname{det}(A - λI) = 0$ 求出 $λ$

$$\begin{bmatrix} 0 & 1\\ -1 & 0 \end{bmatrix}$$

特征值为 $±i$

如果矩阵是对称的或者接近对称的，特征值就是实数；如果越不对称（反对称），特征值是纯虚数

$$\begin{bmatrix} 3 & 1 \\ 0 & 3 \end{bmatrix}$$

只有一个特征向量，是退化矩阵

对角化、A 的幂

如果 $A$ 中有 $n$ 个线性无关的特征向量，将它们放在 $S$ 的列上，则

$$AS = \begin{bmatrix} λ_1x_1 & … & λ_nx_n \end{bmatrix} = \begin{bmatrix} x_1 & … & x_n \end{bmatrix}\begin{bmatrix} λ_1 & 0 \\ 0 & 0 \\ 0 & λ_n \end{bmatrix} = SΛ$$

$A$ 对角化公式：$S^{-1}AS = Λ$

另一种表示形式：

$$A = SΛS^{-1}$$

矩阵幂：$A^k = SΛ^kS^{-1}$

定理：如果所有的$|λ_i| < 1$，当 $k → ∞$ 时，$A^k → 0$

• 如果所有的 $λ$ 不同，则 $A$ 必然有 $n$ 个线性无关的向量，即可对角化
• 如果 $λ$ 有相同的，则可能有 $n$ 个线性无关的向量

差分方程：$u_{k+1} = Au_k$，解得 $u_k = A^ku_0 = SΛ^{100}c$

例：斐波那契数列，令

$$u_k = \begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix}, u_{k+1} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}u_k$$

特征值

$$λ_1 = \frac{1 + \sqrt{5}}{2}, λ_2 = \frac{1 - \sqrt{5}}{2}$$

$$F_{100} ≈ c_1 (\frac{1 + \sqrt{5}}{2})^{100}$$

特征向量

$$x_1 = \begin{bmatrix} λ_1 \\ 1 \end{bmatrix}, x_2 = \begin{bmatrix} λ_2 \\ 1 \end{bmatrix}$$

根据初始值确定常数：

$$c_1x_1 + c_2x_2 = u_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$

微分方程、exp(At)

详见微分方程

对其中解耦合部分的作一些更详细的解释：

$$\frac{\mathrm{d}u}{\mathrm{d}t} = Au$$

所谓的解耦合，就是矩阵 $A$ 的对角化，故令 $u = Sv$

代入得到 $S\frac{\mathrm{d}v}{\mathrm{d}t} = ASv$

最终得到：

$$\frac{\mathrm{d}v}{\mathrm{d}t} = Λv$$

最终答案：

$$v(t) = e^{Λt}v(0)$$

$$u(t) = Se^{Λt}S^{-1}u(0)$$

马尔科夫矩阵、傅里叶级数

马尔科夫矩阵 Markov matrix：和概率思想有关联

• 每个元素 $≥ 0$
• 每一列加起来都为 1

性质：

• 一个特征值为 1
• 其它所有特征值 $|λ_i| < 1$
• 稳态为 $c_1x_1 > 0, λ_1 = 1$

$A - I$ 是奇异的，因为 $(1, 1, 1)$ 在 $N((A - I)^T)$ 中，故行线性相关

$A$ 和 $A^T$ 的特征值相同

$$u_{k+1} = Au_k$$

$A$ 是马尔科夫矩阵

人口迁移问题

向正交基 $q_1, …, q_n$ 的投影：

任何向量 $v = x_1q_1 + x_2q_2 + … + x_nq_n$

得到 $x_1$ 的方法——同乘 $q_1^T$：$q_1^Tv = x_1$

表示成矩阵：$Qx = v$

变化得到：

$$x = Q^{-1}v = Q^Tv$$

两个向量正交：

$$v^w = \sum_{i=1}^n v_iw_i = 0$$

两个函数正交：

$$f^tg = \int_0^{2π}f(x)g(x)\mathrm{d}x$$

从此引出傅里叶级数

对称矩阵及正定性

实对称矩阵：

• 特征值为实数
• 特征向量垂直 perpendicular

证明：特征值为实数：

$$Ax = λx \implies A\bar{x} = \bar{λ}\bar{x} \implies \bar{x}^TA=\bar{x}^T\bar{λ}$$

$$∵\bar{x}^TAx = λ\bar{x}^Tx$$

$$∴λ\bar{x}^Tx = \bar{λ} \bar{x}^T x \implies \bar{λ} = λ$$

其中 $\bar{x}^Tx > 0$，因为其表示复数向量长度

一般情况：$A = SΛS^{-1}$

对称矩阵：

$$A = QΛQ^{-1} = QΛQ^T$$

每一个对称矩阵都是一些相互垂直的投影矩阵的组合

主元的符号和特征值的符号相同，主元的乘积 = 特征值的乘积 = 行列式

应用：因为难以计算高阶矩阵的特征值，但计算主元比较容易，通过将矩阵平移 $k$ 个单位矩阵来得知有多少特征值大于 $k$，有多少小于 $k$

正定矩阵 positive definite matrix：对称矩阵

• 所有特征值为正
• 所有的主元为正
• 所有子行列式为正

复数矩阵、快速傅里叶变换

复数向量求模长：$|z|^2 = \bar{z}^Tz = z^Hz$，$H$ 是埃尔米特 Hermitian

内积也改变了：$y^Hx$

复数矩阵的对称：$A = \bar{A}^T$

正交矩阵（酉矩阵 unitary）：$Q^HQ = I$

最著名的复矩阵，也是酉矩阵——傅里叶矩阵：

$$F_n = \begin{bmatrix} 1 & 1 & 1 & ⋯ & 1 \\ 1 & w & w^2 & ⋯ & w^{n-1} \\ 1 & w^2 & w^4 & ⋯ & w^{2(n-1)} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & w^{n-1} & w^{2(n-1)} & ⋯ & w^{(n-1)^2} \end{bmatrix}$$

$$(F_n)_{ij} = w^{ij}, i,j = 0, ⋯, n-1$$

其中 $w^n = 1$，即

$$w = e^{i2π/n}$$

$n$ 点的离散傅里叶变换：

• 傅里叶变换：$n$ 维向量左乘矩阵 $F_n$
• 傅里叶逆变换：$n$ 维向量左乘矩阵 $F_n^{-1}$，因为是正交矩阵，所以逆矩阵很好求

FFT：

矩阵可以分解为一系列稀疏矩阵

注意到：$w_{64} = w_{32}$之类的

两个矩阵之间的关联：

$$F_{64} = \begin{bmatrix} I & D \\ I & -D \end{bmatrix}\begin{bmatrix} F_{32} & 0 \\ 0 & F_{32} \end{bmatrix}P$$

$P$ 矩阵的作用是将奇数列和偶数列重新排列，$D$ 是对角矩阵，对角线上元素为 $1, w^1, w^2, \cdots, w^{31}$

最后得到该变换的时间复杂度：$\frac{1}{2}n\log_2n$

正定矩阵、最小值

正定性最重要的定义（通常一推三）：$x^TAx > 0$

二次型：$x^TAx = ax_1^2 + 2bx_1x_2 + cx_2^2 > 0$

对于微积分来说，$f(x)$ 一阶导数为 0，极小值和二阶导数为正相关联

在线性代数中，$f(x_1, x_2, \dots, x_n)$ 极小值存在的条件是二阶导数矩阵是正定的

二次型配方后和高斯消元的关系：

$$\begin{bmatrix} 2 & 6 \\ 6 & 20 \end{bmatrix}=\begin{bmatrix} 1 & 0 \\ \boxed{3} & 1 \end{bmatrix}\begin{bmatrix} \boxed{2} & 6 \\ 0 & \boxed{2} \end{bmatrix}$$

二次型的配方结果：

$$\boxed{2}(x + \boxed{3}y)^2 + \boxed{2}y^2$$

平方项里边是消元的倍数因子，外边的系数是主元，这就是为什么正主元得到的是平方和

主轴定理：$A = QΛQ^T$，二次型画成的图形取某一高度处，得到一个椭圆体，特征值说明主轴的长度，特征向量说明主轴的方向

相似矩阵、若尔当形

正定矩阵来自最小二乘法，关键在于 $A^TA$

• 正定矩阵的逆矩阵也是正定矩阵
• 如果 $A$ 和 $B$ 都是正定矩阵，则 $A+B$ 也是正定矩阵

证明：$A^TA$ 是正定的

$$x^T(A^TA)x = (Ax)^T(Ax) = |Ax|^2 > 0$$

如果有某个矩阵 $M$，使得 $B = M^{-1}AM$，则称矩阵 $A$ 和 $B$ 相似 similar

例：$S^{-1}AS = Λ$，则 $A$ 和 $Λ$ 相似

证明：相似矩阵有相同的特征值

$$Ax = λx$$

$$(M^{-1}AM)x = λM^{-1}x$$

$$BM^{-1}x = λM^{-1}x$$

坏情况：有相同的特征值

家族中只有一个成员：

$$\begin{bmatrix} 4 & 0 \\ 0 & 4 \end{bmatrix}$$

较大的家族：

$$\begin{bmatrix} 4 & 1 \\ 0 & 4 \end{bmatrix}$$

该矩阵是若尔当标准型 Jordan form：最简洁，最接近对角阵的一个矩阵

若尔当块 Jordan block：只有一个特征向量

$$\begin{bmatrix} λ_1 & 1 & 0 & …\\ 0 & λ_2 & 1 & …\\ 0 & 0 & λ_3 & 1\\ 0 & 0 & … & λ_n \end{bmatrix}$$

故以下两个矩阵不相似：

$$\left[\begin{array}{ccc|c} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \end{array}\right] \left[\begin{array}{cc|cc} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array}\right]$$

每个方阵 $A$ 都相似于一个若尔当矩阵：

$$J = \begin{bmatrix} \boxed{J_1} & & \\ & \boxed{J_2} & \\ & & \boxed{J_3} \end{bmatrix}$$

若尔当分块的个数 = 特征向量数

奇异值分解

奇异值分解 SVD

$$A\begin{bmatrix} v_1 & v_2 & … & v_r \end{bmatrix} = \begin{bmatrix} u_1 & u_2 & … & u_r \end{bmatrix}\begin{bmatrix} σ_1 & & \\ & σ_2 & \\ & & ⋱ \end{bmatrix}$$

写成矩阵：

$$AV = UΣ$$

目标：寻找行空间的一组标准正交基 $V$，列空间的一组标准正交基 $U$，有点像对角化 $A$

对称矩阵是一种特例：$U$ 和 $V$ 都是 $Q$

$$A = UΣV^{-1}$$

$A^TA = VΣ^2V^T$ 是正定矩阵，由此求出 $V$

类似的，$AA^T = UΣ^2U^T$，由此求出 $U$

或 $u_i = \frac{Av_i}{\sigma_i}$

如果行空间的特征向量不够，就使用零空间的向量

$$\begin{bmatrix} 4 & 3 \\ 8 & 6 \end{bmatrix} = \frac{1}{\sqrt{5}}\begin{bmatrix} 1 & 2 \\ 2 & -1 \end{bmatrix}\begin{bmatrix} \sqrt{125} & 0 \\ 0 & 0 \end{bmatrix}\begin{bmatrix} 0.8 & 0.6 \\ 0.6 & -0.8 \end{bmatrix}$$

真正的工作：在四个子空间中选出合适的基：

• $v_1, …, v_r$ 行空间的正交基
• $u_1, …, u_r$ 列空间的正交基
• $v_{r+1}, …, v_n$ 零空间的正交基
• $u_{r+1}, …, u_n$ 左零空间的正交基

线性变换及对应矩阵

线性变换 $T$ 的两大条件：

• $T(v + w) = T(v) + T(w)$
• $T(cv) = cT(v)$

线性变换的本质：背后的矩阵

如果知道对于所有的基 $v_1, …, v_n$ 的线性变换 $T(v_1), …, T(v_n)$，就可以知道对于所有输入 $v$ 的线性变换 $T(v)$

坐标 coordinate来自于一组基

如果以特征向量为基，则得到对角矩阵

特殊的线性变换：求导数

基变换、图像压缩

傅里叶基：$8 × 8$

$$\begin{bmatrix} 1\\1\\1\\1\\1\\1\\1\\1 \end{bmatrix}\begin{bmatrix} 1\\w\\w^2\\w^3\\w^4\\w^5\\w^6\\w^7 \end{bmatrix} ⋯$$

信号 → 基变换无损压缩得到系数 → 丢掉较小的系数有损压缩得到有很多 0 的系数 → 使用这些系数重构信号

小波 wavelet：

$$\begin{bmatrix} 1\\1\\1\\1\\1\\1\\1\\1 \end{bmatrix}\begin{bmatrix} 1\\1\\1\\1\\-1\\-1\\-1\\-1 \end{bmatrix}\begin{bmatrix} 1\\1\\-1\\-1\\0\\0\\0\\0 \end{bmatrix}\begin{bmatrix} 0\\0\\0\\0\\1\\1\\-1\\-1 \end{bmatrix}\begin{bmatrix} 1\\-1\\0\\0\\0\\0\\0\\0 \end{bmatrix}⋯$$

• $p = Wc$
• $c = W^{-1}p$

好的基：

• 计算快（FFT，FWT）
• 少量基向量就能重现图像

两组基构成的矩阵 $A$ 和 $B$ 的关系：$B = M^{-1}AM$，$M$ 是基变换矩阵

最完美的基：由特征向量构成的一组基

左右逆、伪逆

• 两边的逆：$AA^{-1} = I = A^{-1}A, r = m = n$ 满秩
• 左逆：$r = n < m$

$$\underbrace{(A^TA)^{-1}A^T}_{A^{-1}_{left}}A = I$$

• 右逆：$r = m < n$

$$A\underbrace{A^T(AA^T)^{-1}}_{A^{-1}_{right}} = I$$

想要接近单位矩阵的投影矩阵：

• $A(A^TA)^{-1}A^T$
• $A^T(A^TA)^{-1}A$

找出伪逆的方法：$A^+ = VΣ^+U^T$

2020 视野下的线性代数

聚焦于矩阵的几种分解：

$$A = CR$$

$$A = LR$$

$$A = QR$$

$$S = QΛ Q^T$$

$$A = X Λ X^{-1}$$

$$A = UΣ V^T$$

• 前三种分解是关于如何解方程的
• 后三种分解关系到特征值、特征向量、奇异值，从另一种方式研究问题

这些公式分别对应：

1. 矩阵乘法
2. 求解 $Ax = b$
3. 最小二乘法
4. 谱定理
5. $A^n$，关注数据中重要的部分
6. 非方阵数据中挑出重要部分和随机采样

Gil Strang's Final 18.06 Linear Algebra Lecture

2022.5.15 Gil Strang 退休了