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*} \]
重要推论:当 $Ax = 0$ 时,如果 $A$ 可逆($Det(A)\neq0$),那么 可知 $x=0$.
三阶矩阵的秩可以按下面的方式快速记忆:
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*}
\]
\[
\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 的次数,来判定其正负:
还是以刚才的三阶为例,其列的升序排列为 $123$。以 $aei$ 为例,$a$ 在第一列,$e$ 在第二列,$i$ 在第三列,因此其列顺序为 $123$,与升序一致。因此 permutation 次数为 $0$,因此 $aei$ 是 $+aei$。其他 term 可以参考下面表格:
term | column order | permutation tlmes(flips) | type | sign(result) |
---|---|---|---|---|
aei | 1,2,3 | 0 | even | + |
afh | 1,3,2 | 1 | odd | - |
bfg | 2,3,1 | 2 | even | + |
bdi | 2,1,3 | 1 | odd | - |
cdh | 3,1,2 | 2 | even | + |
ceg | 3,2,1 | 1 | odd | - |
所以最终结果为: $$ Det(A)=aei+bfg+cdh-afh-bdi-ceg $$
$Det(A)$ 可以被视作一个接收矩阵为参数,返回一个标量的函数。
\[ \begin{vmatrix} 1 & 0\\ 0&1 \end{vmatrix}=1 \]
\[ \begin{vmatrix} a & b\\ c&d \end{vmatrix}=- \begin{vmatrix} c & d\\ a&b \end{vmatrix} \]
\[ \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} \]
假设有矩阵 $A$ 与列向量 $x$ 的乘积 $Ax$。假设该结果可以用一个常量 $\lambda$ 与 $x$ 表示,那么我们称 $\lambda$ 为 $A$ 的 Egenvalue,$x$ 为 Eigen Vector:
此时,如果 $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$:
现有如下矩阵 $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$:
上述的例子是对称矩阵(symmetric matrix)。对称矩阵的特征值都是实数特征值;特征向量的数量为 $n$ 个,且都为线性无关的向量。
如果矩阵 $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$。之前的步骤为:
求 $S^{-1}$ 的时候需要查看矩阵 $S$ 是否是 Orthagonal Matrix。如果是的话:
如果矩阵 $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} $$