矩阵

定义ψ(｀∇´)ψ

矩阵是啥应该不用说了吧。

一般表示的时候用大写字母表示矩阵。用小写字母加一个二元组下标表示矩阵里的元素。

比如 \(A\) 为一个 \(n \times m\) 的矩阵：

这里 \(n\times m\) 指 \(n\) 行 \(m\) 列。

\[A=\begin{bmatrix} a_{1,1} & \cdots & a_{1,m} \\ \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,m}\end{bmatrix}\]

\(a_{i,j}\) 就表示矩阵 \(A\) 当中第 \(i\) 行第 \(j\) 列的元素。

（线性代数里不是经常说行列式吗，所以是行 \(\times\) 列啊（划掉））

也可以简记为 \(A=(a_{i,j})\)。

向量：注意这里的向量和几何里的向量的不同。

一般把 \(n\) 个实数组成的 \(n\) 元组称为向量。

如果它表示为一个 \(1\times n\) 的矩阵，则称为行向量，如果是 \(n \times 1\) ，则称为列向量：

行向量：\((a_1,a_2,a_3,...,a_n)\)

列向量：\(\begin{bmatrix}a_1 \\ a_2 \\ \vdots \\ a_n \end{bmatrix}\)

一般都是用列向量（方便一点），一般会用黑体斜体表示列向量。

有兴趣的可以了解一下 \(n\) 维欧几里德空间（可以考虑看看《线性代数》）。

单位矩阵（\(I\)）：

对于一个 \(n \times n\) 的矩阵 \(A\) ，如果满足 \(\forall i ,a_{i,i}=1,\text{Others}=0\)，那么称 \(A\) 是一个单位矩阵，一般记作 \(I\)

比如：

\[I=\begin{bmatrix}1 &0 & 0 \\ 0& 1 & 0 \\ 0 & 0& 1\end{bmatrix}\]

标量乘法ψ(｀∇´)ψ

\(\alpha\) 是一个标量，\(A\) 是一个 \(n \times m\) 的矩阵，

则 \(\alpha A=B\) 是一个 \(n \times m\) 的矩阵，且 \(B_{i,j}=\alpha\times A_{i,j}\)。

满足结合律，分配律。

矩阵加法ψ(｀∇´)ψ

\(A\) 是一个 \(n \times m\) 的矩阵，\(B\) 是一个 \(n\times m\) 的矩阵，

则他们进行矩阵加法 \(A+B\) 得到的结果矩阵 \(C\) 是一个 \(n \times m\) 的矩阵。

且 \(C_{i,j}=A_{i,j}+B_{i,j}\)。

满足结合律，交换律。

矩阵乘法ψ(｀∇´)ψ

重头戏。

\(A\) 是一个 \(n \times m\) 的矩阵，\(B\) 是一个 \(m \times k\) 的矩阵。

注意，\(A\) 的列数和 \(B\) 的行数必须相等！

那么他们进行矩阵乘法 \(A \times B\) 的到的结果矩阵 \(C\) 是一个 \(n \times k\) 的矩阵。

且满足：

\[C_{i,j}=\sum\limits_{k=1}^m A_{i,k}\times B_{k,j}\]

形象的解释就是，\(C_{i,j}\) 等于 \(A\) 的第 \(i\) 行和 \(B\) 的第 \(j\) 列一一对应地乘起来。

注意：矩阵乘法不一定满足交换律！！

但是它满足结合律。

struct Matrix{
    int a[si][si];
    Matrix(){ memset(a,0,sizeof a); }
    inline Matrix operator * (const Matrix &B)const{
        Matrix C,A=*this;
        for(register int i=1;i<=cnt;++i){
            for(register int j=1;j<=cnt;++j){
                for(register int k=1;k<=cnt;++k){
                    C.a[i][j]+=A.a[i][k]*B.a[k][j];
                }
            }
        } return C;
        // 最好循环的时候不要用 si。
        // 用一个设定好的常数或者题目给的变量会比较好。
        // 但是如果乘法不止需要适用于一对 n,m,k，那么就最好用 si - 1。
        // 为啥不会有影响呢？因为构造函数里把没有用到的设置成 0 了。
    }
};

如果被卡常了，可以考虑手动展开内层循环。

要求取模的话手动加上就行。

矩阵快速幂ψ(｀∇´)ψ

因为矩阵乘法满足结合律，所以一个矩阵的 \(k\) 次幂定义为：

\[A^k=\begin{matrix}\underbrace{A \times A\times A \dots \times A}\\k \text{ times}\end{matrix}\]

因为所有满足结合律的元算都可以使用快速幂求解。

所以可以利用矩阵乘法的结合律写出一个矩阵快速幂算法：

Matrix Ans,A;
inline Matrix Qpow(int b){
    for(;b;b>>=1){
        if(b&1) Ans=Ans*A;
        A=A*A;
    } return Ans;
} // 有的时候根据情况需要初始化一下 Ans.

矩阵乘法优化递推ψ(｀∇´)ψ

给你一个数字 \(n\)，求出 \(Fib_n \text{ mod }998244353 ,n \le 1e18\)。

\(Fib\) 是斐波那契数列。

看到 \(n\) 的范围发现直接递推明显爆炸。

所以考虑把 \(Fib_i,Fib_{i-1}\) 表示成一个行向量 \(\begin{bmatrix} Fib_i & Fib_{i-1} \end{bmatrix}\)

然后我们想把递推式子表示成矩阵乘法的形式再利用矩阵快速幂进行高速递推：

\(\begin{bmatrix} Fib_{i-1} & Fib_{i-2} \end{bmatrix} \times ? = \begin{bmatrix} Fib_i & Fib_{i-1} \end{bmatrix}\)

不妨设这个 \(?\) 为一个矩阵 \(base\)。

根据矩阵乘法的定义，\(base\) 应该是一个 \(2\times 2\) 的矩阵。

考虑列出原来的递推式：\(Fib_{n}=Fib_{n-1}+Fib_{n-2}\)。

发现结果矩阵的 \((1,1)\) 这个位置是 \(Fib_i\)，而这个位置 \(C_{1,1}\) 应该是等于 \(A_{1,1}\times B_{1,1}+A_{1,2}\times B_{2,1}\)

也就是 \(Fib_{i-1} \times B_{1,1}+Fib_{i-2}\times B_{2,1}\)

所以 \(B_{1,1}\) 和 \(B_{2,1}\) 都是 \(1\) ：\(\begin{bmatrix}1\\1\end{bmatrix}\)

同理可以得到 \(B_{2,1}\) 和 \(B_{2,2}\) ：\(\begin{bmatrix}1\\0\end{bmatrix}\)

所以 \(base=\begin{bmatrix}1 & 1\\ 1 & 0\end{bmatrix}\)

原式可以化为 \(\begin{bmatrix} Fib_{i-1} & Fib_{i-2} \end{bmatrix} \times \begin{bmatrix}1 & 1\\ 1 & 0\end{bmatrix} = \begin{bmatrix} Fib_i & Fib_{i-1} \end{bmatrix}\)。

那么设 \(Ans=\begin{bmatrix} 1 & 1 \end{bmatrix}=\begin{bmatrix} Fib_2 & Fib_1\end{bmatrix}\)

所以 \(Fib_n\) 就是 \(Ans \times base^{n-2}\) 的 \((1,1)\)。

写一个矩阵快速幂即可。

广义斐波那契数列也是一样的。

然后举一个 OI-Wiki 上的例子

\[ f_{1} = f_{2} = 0 \\ f_{n} = 7f_{n-1}+6f_{n-2}+5n+4\times 3^n \]

发现 \(f_n\) 和 \(f_{n-1}, f_{n-2}, n\) 有关，于是考虑构造一个矩阵描述状态。

但是如果矩阵仅有这三个元素 \(\begin{bmatrix}f_n& f_{n-1}& n\end{bmatrix}\) 是难以构造出转移方程的，因为乘方运算和 \(+1\) 无法用矩阵描述。

于是考虑构造一个更大的矩阵。

\[ \begin{bmatrix}f_n& f_{n-1}& n& 3^n & 1\end{bmatrix} \]

我们希望构造一个递推矩阵可以转移到

\[ \begin{bmatrix} f_{n+1}& f_{n}& n+1& 3^{n+1} & 1 \end{bmatrix} \]

转移矩阵即为

\[ \begin{bmatrix} 7 & 1 & 0 & 0 & 0\\ 6 & 0 & 0 & 0 & 0\\ 5 & 0 & 1 & 0 & 0\\ 12 & 0 & 0 & 3 & 0\\ 5 & 0 & 1 & 0 & 1 \end{bmatrix} \]

再举一个例子：\(f(i) = (f(i - 1) + \dfrac{p}{100}) / 2\)。

（要取模的）

先展开式子：\(f(i) = \dfrac{1}{2} f(i - 1) + \dfrac{p}{200}\)

如果初始矩阵是 \(1\times 2\) 的感觉上完全不够，因为没法很好的处理这个“加上一个常数”的东西。

发现转移矩阵里的数的本质是初始矩阵的数的某个系数。

所以本着“递推式里需要啥，就在初始矩阵里放啥”的思想，我们放一个 \(1\) 在初始矩阵里，然后每次转移都让 \(1\) 的系数为 \(\dfrac{p}{200}\) 即可。

初始矩阵：

\[\begin{bmatrix}f(i), f(i - 1), 1\end{bmatrix}\]

得到的矩阵：

\[\begin{bmatrix}f(i + 1), f(i), 1\end{bmatrix}\]

转移矩阵：

\[\begin{bmatrix} \frac{1}{2} & 1 & 0 \\ 0 & 0 & 0 \\ \frac{p}{200} & 0 & 1 \end{bmatrix}\]

矩阵的一些常见应用ψ(｀∇´)ψ

恰好 K 条边最短路ψ(｀∇´)ψ

首先用邻接矩阵 \(A\) 存图。

然后 \(A[i,j]\) 就可以看做 \(i \to j\) 经过恰好一条边的最短路。

考虑求出经过恰好两条边的最短路 \(B\)。

可以发现 \(B[i,j]=\min\limits_{1\le k \le n}\{A[i,k]+A[k,j]\}\)

这里就是用了类似 Floyd 的枚举中间点思想（其本质是 dp）。

类似的可以得到经过恰好 \(K\) 条边的最短路。

设 \(A^{r}\) 表示经过恰好 \(r\) 条边的最短路矩阵。

可以得到 \(A^{r}[i,j]=\min\limits_{1\le k \le n}\{A^p[i,k]+A^q[k,j]\},r=p+q\)。

发现这个运算就是个类似于矩阵乘法的东西，我们将其定义为 \(\oplus\)。

把 \(\sum\) 换成 \(\min\) ，把 \(\times\) 换成 \(+\) 就能看出来。

刚好这个东西仍然满足结合律，我们把式子写一下：

\[ A^{r} = A^{r-1} \oplus A^1 \]

发现 \(A^r\) 就等于 \(A^1\) 在 \(\oplus\) 意义下的 \(r\) 次幂。

那么就可以用矩阵快速幂 \(n^3\log K\) 求 \(A^K\) 了。

矩阵表达修改ψ(｀∇´)ψ

这个可以看线段树那个页面，写到那里去了。

links

最后更新: October 13, 2023

矩阵