Week 4 Notes

之前提到过：二阶逆矩阵的秩为 $ad-bc$。秩（Determinants）的意义在于判断矩阵 $A$ 是否可逆；而我们可以通过矩阵是否可逆判断出 $Ax=b$ 是否存在独特解，即： \[ \begin{align*} &detA = ad - bc \neq 0 \\ \Rightarrow & Ax =b \\ \Rightarrow & x = A^{-1}b \end{align*} \]

三阶矩阵的秩可以按下面的方式快速记忆：

• 正对角线方向，三元素为一组的乘积的和，减去
• 反对角线方向，三元素为一组的乘积的和

Laplace Expansion 是一种求矩阵秩的通用方法。

以之前已知秩结果的 $3\times3$ 矩阵为例。如果对该结果分别提取公因数进行整理： \[ \begin{align*} &aei + bfg + cdh - ceg -bdi +afh \\ =&a(ei-fh) - b(di-fg)+c(dh-eg) \end{align*} \] 经过观察，我们发现公因数对应括号里的结果实际上是二阶矩阵的秩 因此上面的结果可以改写为：
\[ \begin{align*} &a(ei-fh) + b(di-fg)+c(dh-eg) \\ =&a\begin{vmatrix} e&f \\ h&i \end{vmatrix}{\color{Red} -} b\begin{vmatrix} d&f \\ g&i \end{vmatrix}+ c\begin{vmatrix} d&e \\ g&h \end{vmatrix} \end{align*} \]
对上面的结果进行进一步的观察：

可以发现的是，公因数对应的矩阵，实际上是将目标矩阵中公因数所在的行列元素全去掉后，剩下的元素组成的矩阵。这意味着，较大矩阵的秩，可以分解求更小矩阵秩的问题。

在 Laplace Expansion 的过程中，项的符号有正有负。这个正负性可以通过以下办法解决： $$ (-1)^{(x+y)} $$ 其中 $(x,y)$ 是公因数元素所在矩阵的位置。比如 $b$ 在 $(1,2)$，其符号为 $(-1)^3$，因此 $b$ 所在项符号为负。

Laplace Expalnsion 支持选择任意行 & 任意列 作为计算的起点。这也就意味着，选择 $0$ 最多的行或者列，是最易于计算的。

计算下面矩阵的秩：
\[ \begin{bmatrix*} 1& 0 & 0&-1 \\ 3 & 0 & 0 & 5\\ 2 & 2 & 4 & -3\\ 1& 0& 5&0 \end{bmatrix*} \]

• 首先观察 $0$ 所在的最多行&列：

\[ \begin{bmatrix*} 1& {\color{Red} 0} & 0&-1 \\ 3 & {\color{Red} 0} & 0 & 5\\ 2 & {\color{Red} 2} & 4 & -3\\ 1& {\color{Red} 0} & 5&0 \end{bmatrix*} \]

由于这一列只有第三行不为 $0$，因此只需要计算第三行元素与其对应的矩阵的秩的乘积。其位置为第2列第3行，系数为负。因此可得：

\[ \begin{bmatrix} 1& {\color{Blue} 0} & 0&-1 \\ 3 & {\color{Blue} 0} & 0 & 5\\ {\color{Blue} 2} & {\color{Red} 2} & {\color{Blue} 4} & {\color{Blue} -3} \\ 1& {\color{Blue} 0} & 5&0 \end{bmatrix} =0+0-2 \begin{vmatrix} 1& 0& -1\\ 3& 0& 5\\ 1& 5&0 \end{vmatrix} +0 \]

再接着对得到的三阶矩阵进行进一步的扩展。这里选取第二列作为起始。该列只有 $(3,2)$ 处元素不为零，因此系数为 $-5$：

\[ -2 \begin{vmatrix} 1& {\color{Blue} 0} & -1\\ 3& {\color{Blue} 0} & 5\\ {\color{Blue} 1} & {\color{Red} 5} &{\color{Blue} 0} \end{vmatrix} = -2(0+0-5\begin{vmatrix} 1& -1\\ 3&5 \end{vmatrix}) \]

根据二阶矩阵的秩公式，可得最后结果为 $-2\times-5\times8 = 80$

Leibniz Formula，又称 Big Formula，是另一种计算秩的方法。该方法通过按照指定规则排列出所有的 term，并使用该 term 的 permutation 的次数来计算 term 的正负；最终得到的所有 term 的和即为矩阵的秩。

如果是 $n$ 阶矩阵，那么每个 term 的组成为矩阵的 $n$ 个元素的乘积。term 的列举遵循一个规则：当前元素所在行列不能有其他的元素。因此如果以行优先来计算组合（term 的数量）：第一行有 $n$ 种选择，第二行有 $n-1$ 中选择… 容易观察出，$n$ 阶矩阵存在 $n!$ 个 term。 以之前的三阶矩阵为例：
\[ \begin{bmatrix} a & b & c\\ d& e& f\\ g& h&i \end{bmatrix} \] 第一行有 $a,b,c$ 三种选择，那么第二行就只能有两种选择，第三行就只能有一种选择。比如以 $a$ 开头，那么第二行就不能选与 $a$ 同列的；因此选择只有 $e,f$，那么第三行中，如果 term 选了 $e$ 就不能再选 $h$，同理 $f$ 与 $i$ 只能二选一。因此，$a$ 开头有两种组合方式：$aei, afh$。同理，$b$ 开头有两种：$bdi, bfg$，$c$ 开头有两种：$cdh,ceg$。一共 6 种组合，正好是 $3!$ 。

列举出所有的 term 之后，我们还需要知道每个 term 的正负。本方法使用当前 term 的列顺序转换到升序排列所需要的 permutation 的次数，来判定其正负：

• 当 permutation 的次数为偶数时，term 为正
• 反之为负

还是以刚才的三阶为例，其列的升序排列为 $123$。以 $aei$ 为例，$a$ 在第一列，$e$ 在第二列，$i$ 在第三列，因此其列顺序为 $123$，与升序一致。因此 permutation 次数为 $0$，因此 $aei$ 是 $+aei$。其他 term 可以参考下面表格：

所以最终结果为： $$ Det(A)=aei+bfg+cdh-afh-bdi-ceg $$

$Det(A)$ 可以被视作一个接收矩阵为参数，返回一个标量的函数。

• $Det(I) = 1$

\[ \begin{vmatrix} 1 & 0\\ 0&1 \end{vmatrix}=1 \]

• 矩阵 $A$ 两行互换后，$Det(A) = -Det(A)$

\[ \begin{vmatrix} a & b\\ c&d \end{vmatrix}=- \begin{vmatrix} c & d\\ a&b \end{vmatrix} \]

• $Det(A)$ 是矩阵的第一行的线性函数

\[ \begin{align} \begin{vmatrix} ka & kb\\ c&d \end{vmatrix}&=k \begin{vmatrix} c & d\\ a&b \end{vmatrix} \\ \begin{vmatrix} a + a' & b + b'\\ c&d \end{vmatrix}&= \begin{vmatrix} a & b\\ c&d \end{vmatrix}+ \begin{vmatrix} a' & b'\\ c&d \end{vmatrix} \end{align} \]

• $Det(A)$ 是任意行的线性函数（第三条的推广）
• 若矩阵两行相同，则 $Det(A) = 0$
• $k \times row-i + row-j$ 的运算不会改变 $Det(A)$ 的值
• 若矩阵中某行全为 $0$，则 $Det(A) = 0$
• 若 $Det(A) = 0$，则矩阵不可逆
• 对角矩阵，上三角矩阵，下三角矩阵的秩均为对角线元素的乘积（高斯消元法求秩）
• $Det(AB) = Det(A)Det(B)$
• $Det(A^{-1}) = \frac{1}{Det(A)}$
• $Det(A^T) = Det(A)$（这条证明了适用于行的性质也适用于列）

假设有矩阵 $A$ 与列向量 $x$ 的乘积 $Ax$。假设该结果可以用一个常量 $\lambda$ 与 $x$ 表示，那么我们称 $\lambda$ 为 $A$ 的 Egenvalue，$x$ 为 Eigen Vector：

• 首先，对 $Ax=\lambda x$ 的右边乘上一个单位矩阵 $I$，等式依然成立：$$Ax=Ax=\lambda Ix$$
• 将等式进行变形：\[\begin{align*} &Ax = \lambda Ix \\ &\Rightarrow (A-\lambda I)x = 0 \end{align*}\]

此时，如果 $Det(A-\lambda I)$ 不为零，则该矩阵可逆。如果对上面等式两边都乘以该逆矩阵，得到的结果为 $x=0$，也就是 trivial solution。我们无法通过这种解来求得 $\lambda$ 以及其对应的 $x$，因此需要:

$$Det(A-\lambda I) = 0$$

这个等式被我们称为 Characteristic Equation。

令二阶矩阵 $A$ 为： \[\begin{bmatrix} a &b \\ c&d \end{bmatrix} \] 根据单位矩阵的定义，$\lambda I$ 是对角线上所有元素都为 $\lambda$ 的矩阵；因此有： $$ A- \lambda I =\begin{bmatrix} a-\lambda &b \\ c&d-\lambda \end{bmatrix} $$ 根据二阶矩阵秩的公式： $$ Det(A- \lambda I) = (a-\lambda)(d-\lambda) + ad - bc = 0 $$ 此时我们得到一个多项式等式。将其展开以后，可得： $$ \lambda^2 -(a+d)\lambda + (ad - bc)= 0 $$ 可以注意到几点：

• a + d 是矩阵 $A$ 对角元素之和，也就是 $T_r(A)$
• ad-bc 是矩阵 $A$ 的秩

因此二阶矩阵的 Eigenvalue 的通用计算公式可以写成：

$$\lambda^2 -T_r(A)\lambda + Det(A) = 0$$

可见的是，该等式会有三种类型的根，也就是有三种不同类型的 $\lambda$：

• 判别式大于 $0$，$\lambda$ 为实数
• 判别式小于 $0$，$\lambda$ 为复数
• 判别式等于 $0$，$\lambda$ 为单一实数。这种情况我们称 Eigenvalue is Degenerate。

现有如下矩阵 $A$： $$ \begin{bmatrix} 0 & 1\\ 1 &0 \end{bmatrix} $$ 求其 Eigenvalue 和 Eigenvector。

由 $Det(A + \lambda I) = 0$ 可得：
\[ \begin{align*} \begin{vmatrix} -\lambda & 1 \\ 1& -\lambda \end{vmatrix} & = 0 \\ \Rightarrow \lambda^2-1=0 \end{align*} \]
可以得到 $\lambda = -1$ 和 $lambda = 1$ 两个特征值。每个值都有其对应的特征向量，因此需要分别讨论。令 $x$ 的分量为 $(v1, v2)$，由 $A + \lambda Ix = 0$：

• 当 $\lambda = -1$ 时：\[ \begin{align*} \begin{pmatrix} 1&1 \\ 1 &1 \end{pmatrix}\begin{pmatrix} v_1\\v_2 \end{pmatrix} =\begin{pmatrix} 0\\0 \end{pmatrix} \\ \Rightarrow v_1 +v_2 = 0 \\ \Rightarrow v_1=-v_2 \end{align*}\] 可以看到只要满足上述关系的 $v_1,v_2$ 都可以作为特征值 $-1$ 的特征向量。在这里我们对其进行 normalize，因此：$$x=\begin{pmatrix} 1\\-1 \end{pmatrix} $$
• $\lambda = 1$ 时也按照上面的步骤重新来一遍即可。

如果矩阵 $A$ 的 Eigenvector 都是线性无关的，那么该矩阵可以进行对角化（Diagonalization）。

以二阶矩阵为例。假设有二阶矩阵 $A$，其特征值和特征向量为： \[ \begin{align*} \lambda_1,x_1 = \begin{pmatrix} x_{11}\\x_{21} \end{pmatrix} \\ \lambda_2,x_2 = \begin{pmatrix} x_{21}\\x_{22} \end{pmatrix} \end{align*} \] 根据特征化等式，有： $$ Ax_1=\lambda_1x_1\\ Ax_2=\lambda_1x_2 $$ 将上式以矩阵的乘积表示，有： \[ A\begin{pmatrix} x_{11} & x_{12}\\ x_{21}&x_{22} \end{pmatrix} = \begin{pmatrix} \lambda_1x_{11} & \lambda_2x_{12}\\ \lambda_1x_{21}&\lambda_2x_{22} \end{pmatrix} \] 等式的右边实际上可以写成如下的矩阵乘积： \[ \begin{pmatrix} \lambda_1x_{11} & \lambda_2x_{12}\\ \lambda_1x_{21}&\lambda_2x_{22} \end{pmatrix} =\begin{pmatrix} x_{11} & x_{12}\\ x_{21}&x_{22} \end{pmatrix} \begin{pmatrix} \color{Red}\lambda_1 & \color{Red}0\\ \color{Red}0&\color{Red}\lambda_2 \end{pmatrix} \]
令特征向量组成的矩阵为 $S$，特征值组成的对角矩阵为 $\Lambda$；因此可以得到等式：

$$ AS=S\Lambda $$

也就是说，矩阵与其特征向量矩阵的乘积，等于其特征向量矩阵与特征值组成的对角矩阵的乘积。该结论可以推广到 $n \times n$ 矩阵，前提是特征向量矩阵中的向量线性无关。

由于 $S$ 是可逆的（向量线性无关），对 $AS=S\Lambda$ 两边同时乘以 $S^{-1}$ 可得：

\[ A=S\Lambda S^{-1} \]

对 $AS=S\Lambda$ 去掉右边的 $S$ 可得：

\[ \Lambda = S^{-1}AS \]

第一个等式被称为 $A$ 的 Factorization，第二个等式被称为 $A$ 的 Diagonalization。

根据 $\Lambda = S^{-1}AS$，要想将 $A$ 对角化，首先要求出其特征化矩阵 $S$。之前的步骤为：

• 根据 $Det(A-\lambda Ix) = 0$ 分别求出特征值与其对应的特征向量
• 将特征向量组成矩阵 $S$
• 之后只需求出 $S^{-1}$ 即可

如果矩阵 $A$ 的特征向量是线性无关的话，那么 $A^n$ 会非常好计算。首先，由 $A=S\Lambda S^{-1}$，那么可知：

\[ \begin{align*} A^2 & = (S\Lambda S^{-1})(S\Lambda S^{-1}) \\ &=S\Lambda (S^{-1}S)\Lambda S^{-1} \\ &=S\Lambda I\Lambda S^{-1} \\ &=S\Lambda^2 S^{-1} \end{align*} \] 根据上面的推导，非常容易就可以得到 $A^n$ 的表达式：

$$ A^n=S\Lambda^n S^{-1} $$