算法学习笔记(37): 矩阵-526互联

一切线性操作都可以归为矩阵乘法

--by SmallBasic

本文是拿来玩耍，而不是学习的！

线性递推
超级矩阵快速幂！
矩阵与邻接矩阵
矩阵与线段树
矩阵与 FFT
矩阵与期望
不知道还能扯啥了

矩阵的加法，要求两个矩阵大小相等，于是可以对位单点相加。

\[C_{i, j} = A_{i, j} + B_{i, j} \]

关于矩阵乘法，定义一个 \(n \times c\) 的矩阵 \(A\) 和一个 \(c \times m\) 的矩阵 \(B\)，其乘法 \(C = AB\) 可以表示为：

\[C_{i, j} = \sum_{k = 1}^c A_{i, k} \times B_{k, j} \]

最终得到一个 \(n \times m\) 的矩阵。

用一个简单一点的话来说，\(C_{i, j}\) 表示的是 \(A\) 的第 \(i\) 行，\(B\) 的第 \(j\) 列，一一对应相乘后求和的结果。

我们可以考察两个运算的性质：

加法的结合律，交换律，数乘的分配律。这基于加法满足这些性质，而矩阵只是将多个运算一起进行了。
乘法的结合律，分配律。结合律我不会证明，分配律可以从定义出发。

\[(A + B)C \to \sum_{k = 1}^c (A_{i, k} + B_{i, k}) \times C_{k, j} = \sum_{k = 1}^c A_{i, k} \times C_{k, j} + \sum_{k = 1}^c B_{i, k} \times C_{k, j} = AC + BC \]

值得注意的是，矩乘运算一般情况下不满足交换律！

矩阵在 OI 的用处比较广，很多较为高级的东西都可以用它来解释，所以了解是必要的。

线性递推

矩阵可以快速的求出形如 \(F_i = \sum_{j = 1}^k c_j F_{i - j}\) 的递推式，例如斐波那契数列：\(F_i = F_{i - 1} + F_{i - 2}\)。

利用矩阵乘法可以表示为：

\[\begin{pmatrix} F_i \\ F_{i - 1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{i - 1} \\ F_{i - 2} \end{pmatrix} \]

如果我们多递推几次，可以有：

\[\begin{pmatrix} F_i \\ F_{i - 1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{i - 1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} \]

考虑到矩阵乘法满足结合律，那么我们就可以通过快速幂的方式在 \(O(2^3 \log n)\) 的复杂度内求出斐波那契的第 \(n\) 项了。

如果有一个序列满足 \(g_n = g_{n - 1} + g_{n - 2}\)，初始 \(g_0 = a, g_1 = b\)，那么我们可以知道 \(g_n = F_{n - 1} g_1 + F_{n - 2} g_0\)。

证明是不难的。由于存在：

\[\begin{pmatrix} g_n \\ g_{n - 1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n - 1} \begin{pmatrix} b \\ a \end{pmatrix} \]

将 \(\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\) 写为：\(\begin{pmatrix} F_1 & F_0 \\ F_0 & 0 \end{pmatrix}\)，那么自然的，\(\begin{pmatrix} F_1 & F_0 \\ F_0 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix}\)，归纳一下，得出：\(\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_n & F_{n - 1} \\ F_{n - 1} & F_{n - 2} \end{pmatrix}, n > 1\)。

于是

\[\begin{pmatrix} g_n \\ g_{n - 1} \end{pmatrix} = \begin{pmatrix} F_{n - 1} & F_{n - 2} \\ F_{n - 2} & F_{n - 3} \end{pmatrix} \begin{pmatrix} g_1 \\ g_0 \end{pmatrix} \]

也就是说 \(g_n = F_{n - 1} g_1 + F_{n - 2} g_0\)。

发现我们在证明中并没有用到 \(g_0, g_1\) 是什么，所以这可以轻易的扩展到任意类斐波那契的数列上。

然而推广是困难的，当初始项 \(\ge 3\) 后，我并没有想到该如何推广~~可能是我太菜了 QwQ~~

回到正常的斐波那契数列，如果我们稍稍将 \(n - 1\) 拆解一下，我们可以得到一个好玩的结论。

\[\begin{pmatrix} F_n \\ F_{n - 1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{k} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n - 1 - k} \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} F_k & F_{k - 1} \\ F_{k - 1} & F_{k - 2} \end{pmatrix} \begin{pmatrix} F_{n - k - 1} & F_{n - k - 2} \\ F_{n - k - 2} & F_{n - k - 3} \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \]

将 \(F_n\) 那一堆展开，得到

\[F_n = F_k (F_{n - k - 1} + F_{n - k - 2}) + F_{k - 1} (F_{n - k - 2} + F_{n - k - 3}) = F_k F_{n - k} + F_{k - 1} F_{n - k - 1} \]

于是我们就这么发现并且无需证明的得到了某个恒等式，而不是通过更简单的归纳证明。

如果我们遇到了这种问题：

定义递推数列 \(F\)，维护一个序列 \(A\)，多次区间加 \(F\)，也就是对于区间 \([l, r]\)，令 \(A_i = A_i + F_{i - l}\)，询问最终的序列。

如果只有一个加法是简单的，我们在前 \(k\) 个位置累加一下 \(F\) 初始序列，在 \(l + k\) 开始加入一个初始向量 \(F_{[0, k)}\)。

每次向后一个，乘上一个转移矩阵，顺便累加到原序列即可，在 \(r + 1\) 的位置，我们直接将维护的向量减去 \(F_{[0, k)} T^{r - l - k + 1}\) 即可，如果是纯矩阵是 \(O(n k^2)\) 的，但是容易优化到 \(O(nk)\)。

我们考虑矩阵满足结合律，于是每一个修改加入和减去向量是不会相互影响的，所以我们可以直接优化到 \(O(nk + mk)\)。

超级矩阵快速幂！

哈密尔顿–凯莱定理，这是本方法最重要的理论。

在任何交换环上实或复的方阵 \(A\) 都满足 \(p(\lambda) = \det (\lambda I_n - A)\)。

而哈密尔顿–凯莱断言，\(p(A) = O\)。

具体来说，考虑方阵：\(\begin{pmatrix}1 & 2 \\ 3 & 4\end{pmatrix}\)，其特征多项式为：\(p(\lambda) = \begin{vmatrix}\lambda - 1 & -2 \\ -3 & \lambda -4\end{vmatrix} = \lambda^2 - 5\lambda - 2\)。

根据哈密尔顿–凯莱定理，我们可以知道 \(A^2 - 5A - 2I = O \iff A^2 = 5A + 2I\)。

于是对于一个高次的 \(A^k\) 我们可以如此不断的简化，变成只需要对于原矩阵进行数乘和加法即可，这是 \(O(n^2)\) 的。

但是本方法的瓶颈并不是在于求答案，而是求出特征方程，以及预处理矩阵的过程，这是很难完成的。最终出来的特征多项式是与矩阵的大小线性相关的，也就意味着我们需要预处理 \(O(n)\) 次的矩阵乘法才可以做到 \(O(n^2)\) 的计算，而预处理的代价太昂贵，所以本方法其实没有任何作用。

矩阵与邻接矩阵

你猜猜为什么叫邻接矩阵而不是邻接表？

邻接矩阵 \(G_{i, j}\) 可以看作走一条边从 \(i \to j\) 的方案数。

自然的，我们考虑其乘法：\(G^2_{i, j} = \sum_{k} G_{i, j} \times G_{k, j}\)，惊奇的发现 \(G^2\) 表示的是走两条边从 \(i \to j\) 的方案数！

于是自然的，推广出来，\(G^k\) 表示的是走 \(k\) 条边从 \(i \to j\) 的方案数！

我们继续玩，将矩阵乘法变为 \((\min, +)\)，那么 \(G^2_{i, j} = \min_k (G_{i, k} + G_{k, j})\)，如果我们将 \(G_{i, j}\) 看作 \(i \to j\) 的最短路径，那么不就是说 \(G^n\) 就是全源最短路了！（这可以 \(O(n^3 \log n)\) 求欸，好优秀）

但是 floyd 不乐意了，咱拿着 DP 不用，用矩阵干嘛，于是利用类似的东西搞出来了 \(O(n^3)\) 的做法。

在稀疏图上不如 Johnson 全源最短路，\(O(nm + nm \log m)\)。

我们回到方案数上，看这么一个问题：求一个图的 \(k\) 元环数量。

\(k = 2, 3, 4\) 都是极其简单好做的，很容易做到 \(O(n^3)\) 以内，但是在 \(n \ge 5\) 后事情开始变得复杂。

我们回到 \(G^k\) 的定义，自然的联想到 \(G^k_{i, i}\) 中一定包含了满足为环的东西，但是也有不是的，需要容斥掉。

在 \(k = 5\) 时，发现可能为一个 \(2\) 元环和 \(3\) 元环构成，如果我们能够把二元环不计入其中，是否就意味着我们就不需要容斥了？

问题在于如何容斥，我们考虑矩阵递推，设 \(M_k\) 表示不计入二元环的长度为 \(k\) 的路径数，自然 \(M_1 = G\)，\(G^2\) 中显然包含二元环，我们只需要减去 \(D\) 即可，也就是 \(M_2 = G^2 - D\)。

然而 \(M_3\) 可以从 \(M_2 G\) 转移过来，但是发现多了一些东西，就是类似于 \(a \to b \to c \to b\) 的路径，这可以从 \(M_1\) 减去走一次二元环转移过来。我们可能会直接减去 \(M_1 D\)，但是发现会多减了一些东西，具体来说，多减了 \(a \to b \to a \to b\) 的路径，也就是说这里的路径不应该包含走回去的路径，所以得出实际上的递推式：\(M_k = M_{k - 1} G - M_{k - 2} (D - I), k > 2\)

于是我们得到了 CF1662C European Trip 的优秀做法。

回到 \(k\) 元环上，当 \(k = 6\) 时，我们去掉了二元环，但是算出来会多一点点东西，具体来说，多了形如 \(a \to b \to c \to a \to d \to e \to a\)，也就是两个三元环拼起来的东西，而算这个东西是简单的，所以我们简单的得出了 \(k = 6\) 时的答案。

如果继续考虑 \(k = 7\) 时，我们就会多算 \(3 + 4\) 的情况，类似的容斥即可。

但是当 \(k \ge 8\) 后，事情逐渐变的复杂，因为我们会遇到更多的情况，例如 \(3 + 5, 4 + 4\)，在更大的时候还可能遇到 \(4 + 5, 3 + 3 + 4, 3 + 5 + 7\) 等等情况，这讨论就会十分复杂度了。

完了，还有好多东西需要邻接矩阵。

经典的，矩阵树定理，\(D - G\) 的任一代数余子式也就是 \(\sum_T \prod_{e \in T} w(e)\)。

好神秘的东西，还有一个 [# LGV引理] 我不会……

矩阵与线段树

乱七八糟的标记，看着头痛。

于是有了算法学习笔记(33): 矩阵乘法与线段树标记

矩阵与 FFT

不是，这确实能扯，有多少人知道矩阵与 # 算法学习笔记(17): 快速傅里叶变换（FFT）有什么关系？

离散傅里叶变换可以利用矩阵表示为：

\[\begin{bmatrix} h(\omega^0) \\ h(\omega^1) \\ h(\omega^2) \\ \vdots \\ h(\omega^{n-1}) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 & \cdots & 1 \\ 1 & w_n^1 & w_n^2 & w_n^3 & \cdots & w_n^{n-1} \\ 1 & w_n^2 & w_n^{2\times2} & w_n^{2\times3} & \cdots & w_n^{2\times(n-1)}\\ \vdots & \vdots & \vdots & \vdots & \ddots & \cdots \\ 1 & w_n^{(n-1)\times2} & w_n^{(n-1)\times3} & w_n^{(n-1)\times2} & \cdots & w_n^{(n-1)\times(n-1)} \end{bmatrix} \begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ \vdots \\ c_{n-1} \end{bmatrix} \]

快速傅里叶变换做的事情本质上就是优化这一个矩阵乘法！