矩阵基础学习笔记
Zskioaert1106
·
·
算法·理论
矩阵的感性理解
我真的把向量当数列整了
试想 n 维向量 (v_1,v_2,v_3,\dots,v_n) 和矩阵
A=
\begin{bmatrix}
A_{1,1} & A_{1,2} & A_{1,3} & \dots & A_{1,n}\\
A_{2,1} & A_{2,2} & A_{2,3} & \dots & A_{2,n}\\
A_{3,1} & A_{3,2} & A_{3,3} & \dots & A_{3,n}\\
\dots & \dots & \dots & \dots & \dots\\
A_{n,1} & A_{n,2} & A_{n,3} & \dots & A_{n,n}\\
\end{bmatrix}
，定义 A 对 v 的变换（记为 Av）使
v_1 \leftarrow A_{1,1} \cdot v_1 + A_{1,2} \cdot v_2 + \dots + A_{1,n} \cdot v_n \\
v_2 \leftarrow A_{2,1} \cdot v_1 + A_{2,2} \cdot v_2 + \dots + A_{2,n} \cdot v_n \\
\dots \\
v_n \leftarrow A_{n,1} \cdot v_1 + A_{n,2} \cdot v_2 + \dots + A_{n,n} \cdot v_n \\
即 v_i \leftarrow \sum\limits_{j=1}^{n} A_{i,j} \cdot v_j。
单位矩阵
若 A_{i,j}=[i=j]，则 Av=v。此时 A 被称为单位矩阵。
零矩阵
顾名思义。
矩阵的加法
定义向量加法 c=a+b 为 \forall i, c_i = a_i+b_i。
由 \sum\limits_{j=1}^{n}A_{i,j} \cdot v_j + \sum\limits_{j=1}^{n} B_{i,j} \cdot v_j = \sum\limits_{j=1}^{n}(A_{i,j}+B_{i,j}) \cdot v_j = \sum\limits_{j=1}^{n}B_{i,j} \cdot v_j + \sum\limits_{j=1}^{n} A_{i,j} \cdot v_j ，我们定义矩阵加法 C=A+B 为 \forall i,j:C_{i,j}=A_{i,j}+B_{i,j}，则
-
矩阵加法满足结合律：因为 (A_{i,j}+B_{i,j})+C_{i,j}=A_{i,j}+(B_{i,j}+C_{i,j})；
-
矩阵加法满足交换律：因为 A_{i,j}+B_{i,j}=B_{i,j}+A_{i,j}。
矩阵的乘法
由 \sum\limits_{k=1}^{n} B_{i,k} \cdot (\sum\limits_{j=1}^{n} A_{k,j} \cdot v_j) = \sum\limits_{j=1}^{n} v_j \cdot (\sum\limits_{k=1}^{n} B_{i,k} \cdot A_{k,j})，我们定义矩阵乘法 C=BA 为 \forall i, C_{i,j}=\sum\limits_{k=1}^{n} B_{i,k} \cdot A_{k,j}。则
-
矩阵乘法满足结合律：因为 \sum\limits_{j=1}^{n}(\sum\limits_{k=1}^{n}A_{i,k}\cdot B_{k,j})\cdot C_{j,l} = \sum\limits_{j=1}^{n} \sum\limits_{k=1}^{n} A_{i,k} \cdot B_{k,j} \cdot C_{j,l} = \sum\limits_{k=1}^{n} \sum\limits_{j=1}^{n} A_{i,k} \cdot B_{k,j} \cdot C_{j,l} = \sum\limits_{k=1}^{n} A_{i,k} \cdot (\sum\limits_{j=1}^{n} B_{k,j} \cdot C_{j,l})；
-
矩阵乘法不满足交换律：因为 A_{i,k} \cdot B_{k,j} \neq A_{k,j} \cdot B_{i,k}。但是不要紧，因为快速幂、线段树、ST 表这些只要满足结合律就行，你只需要在打代码时小心不要手欠交换位置。
代码模板
struct Matrix{
long long M[N][N];
void clear(){ memset(M,0,sizeof(M));}
void reset(){
clear();
for(int i=0;i<n;i++)M[i][i]=1;
}
Matrix operator + (const Matrix &o){
Matrix ans;
ans.clear();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
ans.M[i][j]=(M[i][j]*o.M[i][j])%p;
return ans;
}
Matrix friend operator * (const Matrix &a,const Matrix &b){
Matrix ans;
ans.clear();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
(ans.M[i][j]+=a.M[i][k]*b.M[k][j])%=p;
return ans;
}
}
矩阵快速幂
当一个数列有形如 a_n = \sum\limits_{i=1}^{K} a_{n-K-1+i} \cdot b_i 的递推式时，我们总可以用同一个矩阵将向量 (a_{n-K},a_{n-K+1},\dots ,a_{n-1}) 变换为 (a_{n-K+1},a_{n-K+2},\dots ,a_n)。具体地，矩阵形如：
A=
\begin{bmatrix}
0 & 1 & 0 & 0 & 0 & \dots & 0 \\
0 & 0 & 1 & 0 & 0 & \dots & 0 \\
0 & 0 & 0 & 1 & 0 & \dots & 0 \\
0 & 0 & 0 & 0 & 1 & \dots & 0 \\
\dots & \dots & \dots & \dots & \dots & \dots & \dots \\
0 & 0 & 0 & 0 & 0 & \dots & 1 \\
b_1 & b_2 & b_3 & b_4 & b_5 & \dots & b_K
\end{bmatrix}
此时要快速求出某个 a_n 的值，我们就要用 A 连续进行 n 次变换，根据矩阵乘法的结合律，这等价于用矩阵 A^n 对最初的向量 (a_1,a_2,a_3,\dots,a_K) 进行 1 次变换。
因为矩阵乘法满足结合律，所以我们可以用快速幂进行 O(\log n) 次矩阵乘法求出矩阵 A^n。
广义矩阵乘法
有时数列的递推式不是乘积求和，而是什么奇奇怪怪的先与再或之类的东西，或者是加代替了乘的位置，加的位置变成了取 \max，看起来无从下手，但仔细观察却发现，如果把矩阵变换的加和乘改成新的这两种运算，仍然满足结合律。这个时候不妨跳出矩阵定义的思维定式，直接把自定义的矩阵乘法运算符里的 \sum\limits A_{i,k} \times B_{k,j} 改成 \max A_{i,k}+B_{k,j} 或者 \operatorname{or} A_{i,k} \operatorname{and} B_{k,j}，然后照样用快速幂什么的加速。
同样，矩阵也不一定用递推式里得到，比如说每次转移相同的 dp，直接求出来转移矩阵，然后上快速幂 O(n) 变 O(\log n)。
P4159：注意到边权 \leqslant 9，所以将每个点的末 9 个 dp 状态放进向量，求出转移矩阵即可。
数据结构 + 矩阵维护信息
CF718C：给出数列 a_1\sim a_n，支持区间加、区间斐波那契数列的第 a_i 项求和。
考虑线段树维护。斐波那契数列是一个经典的矩阵快速幂维护的东西，发现答案合并就是矩阵加法，于是就能做到维护每段区间的答案矩阵了。此外下传标记时要乘斐波那契最初矩阵的 x 次幂，预先处理好这个矩阵再下传比更新时再快速幂少一个 \log。
Freivalds 算法
给出 n \times n 的矩阵 A,B,C，判断是否 AB=C。
朴素算法的瓶颈在于把矩阵 AB 乘起来，而 Freivalds 算法通过把矩阵乘矩阵改为矩阵乘向量再加上随机化达到了 O(n^2) 量级。也就是说，每次随出来一个向量 v，如果 A(Bv)\neq Cv 说明 AB \neq C。
这其中最关键的在于可以证明，若 AB \neq C 的话，随出来的两个向量相等的概率不大于 \frac 1 2。因此随机 k 次，单侧错误率在 \frac 1 {2^k} 以下。
分块矩阵
这个东西是我做矩阵幂求和的时候自己想到的。
我：矩矩阵阵。
同学：别叫了，这个东西已经被命名为分块矩阵了。
（被同学吊打了）
广义斐波那契矩阵列：给出矩阵 A,B，矩阵列 F 满足 F_i=A*F_{i-2}+B*F_{i-1}，F_1,F_2 给定，求 F_k。
我觉得这题可以让人很自然地理解何为分块矩阵。
分块矩阵这个名称的由来其实是将一个大的矩阵断齑画粥分割成若干块，每块又是一个小矩阵，这样原来的大矩阵就是这些小矩阵组成的了。
但我当时是从另一方面想的：对于本题，仿照广义斐波那契数列的向量，发现需要记录 F_{i-2} 和 F_{i-1} 这两个矩阵并转移，于是把向量里的两个整数替换成两个矩阵，在分块矩阵乘法中把整数乘法改为矩阵乘法，整数加法改为矩阵加法，即：我们需要找到一个由四个矩阵组成的大矩阵 \mathbb A，使得 \mathbb A (F_{i-2},F_{i-1}) = (F_{i-1},F_{i})。
按题目要求和上面的定义，不难解得
\begin{bmatrix}
O & I \\
A & B \\
\end{bmatrix}
\begin{bmatrix}
F_{i-2} \\
F_{i-1} \\
\end{bmatrix}
=
\begin{bmatrix}
F_{i-1} \\
F_i \\
\end{bmatrix}
，其中 O 为零矩阵，I 为单位矩阵。
因此，比如说有
A=
\begin{bmatrix}
1 & 2 \\
3 & 4 \\
\end{bmatrix},
B=
\begin{bmatrix}
5 & 6 \\
7 & 8 \\
\end{bmatrix}
，那我们转移用的大矩阵就是
\mathbb A=
\begin{bmatrix}
\begin{bmatrix}
0&0\\
0&0\\
\end{bmatrix} &
\begin{bmatrix}
1&0\\
0&1\\
\end{bmatrix} \\ \\
\begin{bmatrix}
1&2\\
3&4\\
\end{bmatrix} &
\begin{bmatrix}
5&6\\
7&8\\
\end{bmatrix}
\end{bmatrix}
，这样应该比较明白了，然后我们仿照矩阵快速幂即可。
这样看它也就是一种广义矩阵乘法嘛。