--by SmallBasic
目录本文是拿来玩耍，而不是学习的！
矩阵的加法，要求两个矩阵大小相等，于是可以对位单点相加。
\[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\) 列，一一对应相乘后求和的结果。
我们可以考察两个运算的性质：
- 加法的结合律，交换律，数乘的分配律。这基于加法满足这些性质，而矩阵只是将多个运算一起进行了。
- 乘法的结合律，分配律。结合律我不会证明，分配律可以从定义出发。
值得注意的是，矩乘运算一般情况下不满足交换律！
矩阵在 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引理] 我不会……
矩阵与线段树
乱七八糟的标记，看着头痛。
矩阵与 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} \]快速傅里叶变换做的事情本质上就是优化这一个矩阵乘法！
矩阵与期望
很经典的应用有一个 # 算法学习笔记(23): 马尔可夫链中的期望问题
还有好多期望的问题都需要用到矩阵转移。
例如说 P4457 [BJOI2018] 治疗之雨 和矩阵强相关！
不过线性代数的东西也不少。
不知道还能扯啥了
咱就不扯了吧 QwQ
标签：begin,end,37,矩阵,times,算法,pmatrix,我们 From： https://www.cnblogs.com/jeefy/p/17830145.html