矩阵——线性变换的高峰

· · 算法·理论

矩阵——线性变换的高峰

标有 * 的在 OI 中用处不大，标有 ** 的在 OI 中貌似没有任何用处。

本文从矩阵的定义出发，讲解矩阵的几何意义，数学上的应用和算法竞赛中的应用，详细、严谨又不枯燥。然而，本文难免会有疏漏（比如出现了没有定义过的运算），如果发现了可以在评论区指出。

定义、运算等基础

定义

一个 n\times m 的矩阵是一个 n\times m 的网格，每个格子里有一个数字。

可以看作一个二维数组。

记法

写出这个网格（没有边框），然后在左右两边加上圆括号 () 或方括号 []。我更习惯写方括号。

即：

二元组 (n,m) 称为这个矩阵的大小。

若 n=m，则称这个矩阵为方阵。OI 中一般使用的都是方阵。

定义 n 阶单位矩阵为满足 A_{i,j}=[i=j] 的矩阵。即，主对角线上全为 1，其它全为 0，记为 \bm{I_n}。在没有歧义的的情况下记为 \bm I。很多矩阵在没有歧义的情况下都可以省略大小。

运算

向量

行向量是一个只有一行的矩阵。列向量是一个只有一列的矩阵。两者互为转置，因此是等价的。我更喜欢列向量，所以后面基本只讨论列向量。

定义标准单位向量为，只有一个值为 1，其它为 0 的向量。显然，n 阶基向量可能有多个。

:::info[为什么叫做这个名字？]

单位向量指的是，模长等于 1 的向量。什么是模长？就是“长度”（参见下文的几何意义）。也就是，各个数字的平方和等于 1 的向量。

标准单位向量增加了“标准”二字，说明有且仅有一个值为 1，其余为 0。容易发现标准单位向量一定是单位向量。

:::

向量乘向量，向量乘矩阵，矩阵乘向量的方法和矩阵乘法相同。向量加向量也与矩阵相同。 ## 几何意义 我不会截图。 ### 向量 可以看成一个点。但既然叫做向量了，我们就看作向量吧。 [二维向量](https://www.desmos.com/geometry/ww32e0duot)。[三维向量](https://www.desmos.com/3d/w9ekrl7dom)。 因为三维的矩阵不好画，所以我们之后只讨论二维（二阶）。 ### 矩阵 我们这里只讨论方阵。非方阵的矩阵涉及到升维和降维，没什么几何意义。 注意到矩阵乘向量（我们上面说过了向量在这里默认指行向量）还是向量，那么可以看成对于向量的……变换？ 首先考虑标准单位向量。发现一个矩阵 $\begin{bmatrix}a&b\\c&d\end{bmatrix}$ 乘 $\begin{bmatrix}1\\0\end{bmatrix}$ 得到 $\begin{bmatrix}a\\c\end{bmatrix}$，也就是提取第一列；相应地，乘 $\begin{bmatrix}0\\1\end{bmatrix}$ 能够提取第二列。 当然还可以推广一下，对于任意矩阵乘 $e_i$ 就能得到第 $i$ 列（左乘行向量 $e_i$ 能得到第 $i$ 行）。 那么我们考虑**单位矩阵**。单位矩阵乘任何向量都等于它自身（容易证明），所以这是一个恒等变换。也就是这样的：[desmos](https://www.desmos.com/calculator/zs7j0buvnk)。 那么，标准单位向量 $e_1$ 被映射到了 $\begin{bmatrix}a\\c\end{bmatrix}$，$e_2$ 被映射到了 $\begin{bmatrix}b\\d\end{bmatrix}$。以矩阵 $\begin{bmatrix}1&2\\-1&0\end{bmatrix}$ 为例，原本的网格就变成了这样（可以自行拖动 $a,b,c,d$ 来观察。绘制方法使用了矩阵求逆，可以先不看）：[desmos](https://www.desmos.com/calculator/etv2ia6c7b)。 三维矩阵也可以自行脑补。如果有用 desmos 3D 画出来的可以跟我说一声？ ## 性质 ### 运算律 - 加法：拥有交换律和结合律。这个是显然的。 - 减法：容易发现 $A-B=A+(-B)$。 - 乘法：我们注意到交换律不成立（反例容易举出），但是矩阵是一个函数，那么 $(AB)C$ 和 $A(BC)$ 都表示 $f(g(h(\cdot)))$，它们是等价的。所以结合律是成立的（代数证明留给读者暴力算）。对加法的分配律也是成立的。 ## 特殊矩阵 下列矩阵都是方阵，除了第一个： - 零矩阵：所有数字均为 $0$。通常直接用数字 $0$ 表示，大小从上下文推断。 - 对角矩阵：除了主对角线上的元素之外，其它元素均为 $0$。记为 $\operatorname{diag}(a_{1,1},a_{2,2},\dots,a_{n,n})$。 - 容易发现，单位矩阵是对角矩阵。 - 上三角矩阵：主对角线下面的元素都为 $0$（不包括主对角线）。即 $\begin{bmatrix}a_{1,1}&a_{1,2}&\dots&a_{1,n}\\0&a_{2,1}&\dots&a_{2,n}\\\vdots&\vdots&\ddots&\vdots\\0&0&\dots&a_{n,n}\end{bmatrix}$。 - 如果对角线上的元素均为 $1$，那么是单位上三角矩阵。 - 下三角矩阵类似。也可以定义单位下三角矩阵。 - 对角矩阵同时是上三角矩阵和下三角矩阵，反之亦然。 - 单位矩阵同时是单位上三角矩阵和单位下三角矩阵。反之亦然。 - *排列矩阵：每行每列有且仅有一个元素为 $1$，其余都是 $0$。也就是每行每列都是标准单位向量。 - 对称矩阵：转置等于其自身。 - 范德蒙德矩阵：$V(x_0,x_2,\dots,x_{n-1})=\begin{bmatrix}1&x_0&x_0^2&\dots&x_0^{n-1}\\1&x_1&x_1^2&\dots&x_1^{n-1}\\1&x_2&x_2^2&\dots&x_2^{n-1}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_{n-1}&x_{n-1}^2&\dots&x_{n-1}^{n-1}\end{bmatrix}$。在 FFT 中会用到，且满足 $x_i=\omega^i$。 ### 对角矩阵 它有非常好的性质，有必要拿来讲一讲。设 $D$ 为对角矩阵 $D=\operatorname{diag}(x_1,x_2,x_3,\dots,x_n)$。 - $AD$ 相当于将 $A$ 的第 $i$ 列乘 $x_i$。 - $DA$ 相当于将 $A$ 的第 $i$ 行乘 $x_i$。 - 推论：$D^k=\operatorname{diag}(x_1^k,x_2^k,\dots,x_n^k)$。 加法太显然，就不必说了。 ## 运算 ### 子矩阵 子矩形。 **$\bm i$ 行 $\bm j$ 列子矩阵不是**子矩阵，但它很重要。是去除一个矩阵的第 $i$ 行和第 $j$ 列所得到的矩阵。记为 $A_{[i,j]}$。 ### 行列式 **非常重要**。 只对方阵有定义（如果你是 Jumping，忽略这句话）。 我们回顾几何意义。显然，矩阵乘向量对于向量是一个**线性变换**。也就是说，对于所有图形，经过矩阵乘法的变换之后**有向面积**都乘了一个常数。 我们就定义这个常数为**行列式**，记为 $\det(A)$（或者 $\lvert A \rvert$，并且 $A$ 没有左右括号。比如 $\left\lvert\begin{matrix}1&2\\3&4\end{matrix}\right\rvert$。也可以是 $\det\lvert A\rvert$）。它代表了一个矩阵的“面积”。 行列式的计算方法不是很重要。算式如下： $$\det(A)=\begin{cases}a_{1,1}&n=1\\\sum_{i=1}^n(-1)^{i+1}a_{1,i}\det(A_{[1,i]})&n>1\end{cases}$$ 其中，$(-1)^{i+j}\det(A_{[i,j]})$ 称为元素 $A_{i,j}$ 的**代数余子式**。也就是说，$\det(A)$ 在 $n>1$ 时就是第一行所有元素的代数余子式之和。 具体是怎么得到的，这里不深究。只需要知道还有另一个等价的定义： $$\begin{aligned}\det(A)=&\sum_{p}(-1)^{\operatorname{inv}(p)}\prod a_{p}\\=&\sum_{p}(-1)^{\operatorname{inv}(p)}a_{p_1}a_{p_2}a_{p_3}\dots a_{p_n}\end{aligned}$$ 其中，$\sum$ 枚举的 $p$ 是 $1\dots n$ 的排列。而 $\operatorname{inv}(p)$ 是 $p$ 的**逆序对个数**。这居然和逆序对有关系，神奇吧！ 性质： - 若 $A$ 某行或某列为 $0$，则 $\det(A)=0$（由第二个定义易证）。 - 若 $A$ 某行或某列乘 $\lambda$，则 $\det(A)$ 也乘 $\lambda$（由第二个定义）。 - 若 $A$ 某行（列）加到另外一行（列）上，则 $\det$ 不变。好像不是很好证。 - $\det(A)=\det(A^T)$（由第二个定义）。 - 交换任意两行（列），行列式取反（变为相反数）（由第二个定义）。 - $\det(AB)=\det(A)\det(B)

容易发现，范德蒙德矩阵的行列式为 \displaystyle\prod_{0\le j<k\le n-1}(x_k-x_j)。

*秩

定义线性相关为，一组向量 v_1,v_2,\dots,v_n，如果存在一个数组 a_1,a_2,\dots,a_n 满足 \exist i,a_i\neq 0 且 \sum v_ia_i=0（0 指零向量）。

行秩定义为，取出每一行为单独的向量，那么其最大线性无关向量集合为其行秩。也就是说，取出尽量多的行，使得它们线性无关。

列秩定义类似，只不过是每一列。

但是行秩还是列秩其实不重要。因为可以证明行秩横等于列秩！就用秩来指代这个了。

秩有什么几何意义呢？容易发现，在几何意义一块的 desmos 图表中，如果把矩阵变为类似 \begin{bmatrix}1.14&5.14\\2.28&10.28\end{bmatrix} 的东西，那么整个网格就变成一条线了。其实不只是网格，原本所有点都跑到一条线上了。当然，也可以让它们都跑到一个点上，此时只能是零矩阵。

那么，秩就是变换后的维度数。记为 \operatorname{rank}(A)。

容易发现显然的性质：方阵的秩等于 n（称作满秩）等价于行列式不等于 0。

同时也显然有性质：\operatorname{rank}(AB)\le \min(\operatorname{rank}(A),\operatorname{rank}(B))。等号不一定成立。

带入定义计算行列式的方法是指数级的，没什么用。多项式级别的计算方法是利用性质高斯消元。

幂

定义 A^n=\displaystyle\prod_{1\le i\le n}A，也就是 n 个 A 相乘。

:::info[**什么，矩阵也可以放到指数上？]

使用泰勒展开来定义即可。比如 e^{I_2}=eI_2。

:::

求逆

一个方阵，可能存在另一个矩阵 A^{-1} 满足 AA^{-1}=I。此时一定满足 A^{-1}A=I。这个 A^{-1} 就叫做 A 的逆。

矩阵的逆存在的充要条件是矩阵满秩，即行列式不为 0。不存在逆的矩阵称做奇异矩阵，否则叫做非奇异矩阵（可逆矩阵）。

*特征值，特征向量

一个矩阵对向量显然不只有缩放。但是，对于某些特殊的向量，可能确实只有缩放。

\begin{aligned}Av=&\lambda v\\Av=&I\lambda v\\(A-\lambda I)v=&0\\\det(A-\lambda I)=&0\end{aligned}

我们就得到了一个充要条件。即，\det(A-I\lambda)=0。解方程很简单。可能有多解。

*线性递推？

Fibonacci 数列

一般地，我们把线性递推所需要的所有项塞到一个向量里，然后构造矩阵就是顺手的事儿。 ### 对角化 插播一条运算。 一个矩阵的幂 $A^k$ 可能在数学上不是很好求通项，但如果是对角矩阵就好了。 所以，把 $A$ 拆分为 $PDP^{-1}$，$D$ 是对角矩阵。这样进行乘方后 $P^{-1}P$ 就可以抵消了。最后结果就是 $A^k=PD^kP^{-1}$。 如何对角化呢？ 首先考虑行列式，因为有 $P$ 和 $P^{-1}$。显然 $\det(P)\det\left(P^{-1}\right)=1$，那么有 $\det(D)=\det(A)$。同时考虑 $\det(A)$ 是多少。它把**特征向量** $v_i$ 乘了 $\lambda_i$，也就是说，它是 $\dfrac{\left\lvert\begin{matrix}\lambda_1v_1&\lambda_2v_2&\lambda_3v_3&\cdots&\lambda_nv_n\end{matrix}\right\rvert}{\left\lvert\begin{matrix}v_1&v_2&v_3&\cdots&v_n\end{matrix}\right\rvert}$，也就是 $\prod\lambda$！ 所以，$\det(D)=\prod\lambda$。而显然 $D=\operatorname{diag}(x_1,x_2,x_3,\dots,x_n)$，$\det(D)=\prod x$，所以不妨设 $x_i=\lambda_i$。 那我们考虑左右两边乘特征向量 $v_i$。就有 $PDP^{-1}v_i=v_i\lambda_i$。那么设 $M=\begin{bmatrix}v_1&v_2&v_3&\cdots&v_n\end{bmatrix}$，就有 $PDP^{-1}M=MD$，也就是 $PDP^{-1}=MDM^{-1}$！ 也就是说，设 $P=M$，然后算一下 $P^{-1}$ 即可。什么时候可逆？当 $M$ 可逆的时候。 需要注意的是，对角化不一定能够进行。第一个问题是，可能特征值不存在。不过实际上一定存在，只是需要在复数范围内寻找。而更大的问题是，$P$ 不一定是非奇异的！比如如果 $n=2$ 时 $\lambda_1=\lambda_2$，则线性相关，所以无法进行对角化。 ### 求解通项公式 虽然一般来讲线性递推的通项公式用生成函数更容易理解一些，但是矩阵也可以做。 首先，我们令 $A=\begin{bmatrix}0&1\\1&1\end{bmatrix}$。有 $F_n=A^n_{2,1}$，我们考虑求出 $A^n$。 对 $A$ 进行对角化。过程略去，得到 $A=PDP^{-1}$，其中 $D=\begin{bmatrix}\varphi&0\\0&\hat\varphi\end{bmatrix}$，其中 $\varphi=\dfrac{1+\sqrt 5}{2}$ 和 $\hat\varphi=\dfrac{1-\sqrt 5}{2}$，而 $P=\begin{bmatrix}1&1\\\varphi&\hat\varphi\end{bmatrix}$，$P^{-1}=\dfrac{\begin{bmatrix}-\hat\varphi&1\\\varphi&-1\end{bmatrix}}{\sqrt 5}$。 然后经过计算（不要将 $\varphi$ 和 $\hat\varphi$ 带入，也不要将 $\sqrt 5$ 带入！虽然理论上能做，但是这样很累，也非常容易算错！）就能得到 $A^n=\dfrac{\begin{bmatrix}\varphi^{n-1}-\hat\varphi^{n-1}&\varphi^n-\hat\varphi^n\\\varphi^n-\hat\varphi^n&\varphi^{n+1}-\hat\varphi^{n+1}\end{bmatrix}}{\sqrt 5}$。 所以 $F_n=\dfrac{\varphi^n-\hat\varphi^n}{\sqrt 5}$。 这种方法相比生成函数，并没有什么优势。生成函数需要解方程，当次数较高时难以解出。这里虽然没有显式解方程，但是对角化时求解特征值需要解方程，并且两者次数相同。 ## 算法 - 矩阵快速幂：满足结合律就可以矩阵快速幂。可以用来求线性递推数列。还有变种的矩阵乘法，比如连通性。$A_{i,j}^{(k)}=[i\text{ 可以经过恰好 }k\text{ 条边到达 j}]$。那定义 $(AB)_{i,j}=\underset{k=1}{\overset{n}{\lor}}(A_{i,k}\land B_{k,j})$，那就有 $A^{(k)}=A^k$，其中 $k$ 是这个图的邻接矩阵！所以可以快速求出一个图经过恰好 $k$ 条边的连通性。结合律显然。时间复杂度 $O(n^3\log k)$。 - 推广：如果给每个点都加一个自环，则还可以求经过 $\le k$ 条边的连同性。 - 再推广：可以求路径数量。此时就是经典矩阵乘法。 - 高斯消元：可以求矩阵的逆，矩阵的行列式，也可以解线性方程组（其实就是矩阵的逆）。时间复杂度均为 $O(n^3)$。请读者自行了解，这里不详细展开。 - 带修 DP：有时候 DP 方程很简单，类似 $F_i=a_iF_{i-1}+b_iF_{i-2}$，但是带修改。就可以写成矩阵形式，用线段树维护（如果可逆，还可以直接维护）。 - \*\*Strassen 算法：快速计算矩阵乘法。基本可以说（在 OI 中）没有任何用处。甚至很多神经网络（需要大量的矩阵乘法）的高效实现都也没有使用 Strassen。理论复杂度不等于实际效率啊。 是的，矩阵相关的算法就是这么少。矩阵的应用主要在于理论层面，比如可以求数列通项。 ## 有关行列式 ### \*Carmer 法则 线性方程组 $Ax=y$（其中，$A$ 是 $n\times n$ 矩阵，$x,y$ 均为 $n$ 行的列向量）的解为 $x_i=\dfrac{\det(B_i)}{\det(A)}$，其中 $B_i$ 为将 $A$ 的第 $i$ 列替换为 $y$ 的结果。 也可以用于矩阵求逆。此时 $(A^{-1})_{i,j}=\dfrac{\det(B_{i,j})}{\det(A)}$，其中 $\det(B_{i,j})$ 为将 $A$ 的第 $i$ 行替换为列标准单位向量 $e_j$ 的结果。 ## 结语 就先写到这吧。我感觉还有要写的，但是我不知道要写什么。