矩阵和矩阵快速幂的初步认识

ymhh

2026-08-18 21:01:48

发布于：广东

18阅读

0回复

0点赞

通过查询本喵的获奖记录可以看到，我只有 5 级钩，所以可能不会讲得很深，但应该不会出错。

一、矩阵定义

把若干个数字排成一个矩形表，就是矩阵。

例如：

$\begin{bmatrix} a & b \\ c & d \end{bmatrix}$

通常记作：

$A=(a_{ij})_{m\times n}$

其中：

$m$ 表示行数；
$n$ 表示列数；
$a_{ij}$ 表示第 $i$ 行第 $j$ 列的元素。

二、常用概念

同型矩阵：行数和列数都相等的两个矩阵。
方阵：行数和列数都相等的一个矩阵。
零矩阵：所有元素都是 $0$ 的矩阵，记作 $O$ 。
单位矩阵：主对角线全为 $1$ 、其余元素为 $0$ 的方阵，记作 $I$ 。

主对角线是指从左上角到右下角的对角线。

三、矩阵的加减法

只有同型矩阵才可以进行加减运算，即两个矩阵的行数和列数分别相等。

运算规则：对应位置上的元素相加减。

例如：

$\begin{bmatrix} 1 & 3 \\ 2 & 4 \end{bmatrix} + \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix} = \begin{bmatrix} 1+5 & 3+6 \\ 2+7 & 4+8 \end{bmatrix} = \begin{bmatrix} 6 & 9 \\ 9 & 12 \end{bmatrix}$

四、矩阵乘法

我觉得这部分最难了，也可能是本喵太菜了。

1. 乘法条件

若矩阵 $A$ 是 $m\times n$ 的矩阵，矩阵 $B$ 是 $n\times p$ 的矩阵，则它们可以相乘：

$C=AB$

结果 $C$ 是一个 $m\times p$ 的矩阵。

也就是说：

$A$ 的列数等于 $B$ 的行数才可相乘（当然，把这句话反过来说，也就是“ $B$ 的行数等于 $A$ 的列数”，意思是一样的喵）。

2. 乘法规则

接上条，设：

$C=AB$

则 $C$ 的第 $i$ 行第 $j$ 列的元素为：

$c_{ij}=\sum_{k=1}^{n} a_{ik}b_{kj}$

用喵话说，就是：

$A$ 的第 $i$ 行与 $B$ 的第 $j$ 列的对应元素相乘后再相加。

例如：

$A= \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, \quad B= \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix}$

计算 $C=AB$ ：

$c_{11}=1\cdot 5+2\cdot 7=19$

$c_{12}=1\cdot 6+2\cdot 8=22$

$c_{21}=3\cdot 5+4\cdot 7=43$

$c_{22}=3\cdot 6+4\cdot 8=50$

所以：

$C= \begin{bmatrix} 19 & 22 \\ 43 & 50 \end{bmatrix}$

3. 特殊性质

矩阵乘法不满足交换律，即 $AB\neq BA$ 。
矩阵乘法满足结合律，即 $(AB)C=A(BC)$ 。
矩阵乘法满足分配律，即 $A(B+C)=AB+AC$ 。

五、方阵的幂

显然只有方阵才能自己乘自己。

定义：

$A^k = \underbrace{A A \cdots A}_{k \text{ 个}}$

特别地，约定：

$A^{0}=I$

六、矩阵快速幂

矩阵快速幂和普通整数快速幂的思想完全一样：将指数按二进制拆分，利用幂的运算性质加速。

我们要计算 $A^b$ ，其中 $A$ 是方阵。

如果直接乘 $b$ 次，复杂度是 $O(b\cdot n^3)$ ，当 $b$ 很大时不可接受。

快速幂做法：

把指数 $b$ 写成二进制。例如：

$b=13=1101_2$

那么：

$A^{13}=A^8 \cdot A^4 \cdot A^1$

我们只需要维护一个底数 $base=A^{2^k}$ ，每次让 $base$ 自己乘自己，就能得到 $A^1,A^2,A^4,A^8,\cdots$ 。

如果当前二进制位是 $1$ ，就把结果乘上这个 $base$ 。

算法流程

设结果矩阵 $res=I$ ，底数矩阵 $base=A$ 。

当 $b>0$ 时：

如果 $b$ 的最低位是 $1$ ，则 $res=res\times base$ ；
令 $base=base\times base$ ；
令 $b=b>>1$ 。

最后 $res=A^b$ 。

复杂度：一次矩阵乘法是 $O(n^3)$ ，快速幂需要乘 $O(\log b)$ 次，总复杂度 $O(n^3\log b)$ 。

七、矩阵快速幂优化递推

终于到了喵。

例子：斐波那契数列

斐波那契数列的定义：

$F_0=0,\quad F_1=1$

$F_n=F_{n-1}+F_{n-2}$

直接递推求解显然为 $O(n)$ ，但可以使用今天的内容优化到 $O(\log n)$ 。

构造转移矩阵

我们把当前需要的两项打包成一个列向量：

$v_n= \begin{bmatrix} F_n\\ F_{n-1} \end{bmatrix}$

那么下一项：

$v_{n+1}= \begin{bmatrix} F_{n+1}\\ F_n \end{bmatrix}$

观察：

$F_{n+1}=1\cdot F_n+1\cdot F_{n-1}$

$F_n=1\cdot F_n+0\cdot F_{n-1}$

所以转移矩阵为：

$M= \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}$

于是：

$v_{n+1}=Mv_n$

连续递推可得：

$v_k=M^k v_0$

其中初始向量：

$v_0= \begin{bmatrix} F_1\\ F_0 \end{bmatrix} = \begin{bmatrix} 1\\ 0 \end{bmatrix}$

因此求 $F_k$ ，只需计算 $M^k$ ，然后乘上 $v_0$ ，结果向量的第二行就是 $F_k$ 。

另外，通过归纳法可以证明：

$M^k= \begin{bmatrix} F_{k+1} & F_k\\ F_k & F_{k-1} \end{bmatrix}$

所以也可以直接取 $M^k$ 的第一行第二列。

一般二阶线性递推

如果递推形式是：

$a_n=p\cdot a_{n-1}+q\cdot a_{n-2}$

同样把当前两项打包：

$v_n= \begin{bmatrix} a_n\\ a_{n-1} \end{bmatrix}$

那么：

$a_{n+1}=p\cdot a_n+q\cdot a_{n-1}$

$a_n=1\cdot a_n+0\cdot a_{n-1}$

所以转移矩阵为：

$M= \begin{bmatrix} p & q\\ 1 & 0 \end{bmatrix}$

更高阶递推

若递推式涉及前 $d$ 项，则需要维护 $d$ 维列向量，转移矩阵为 $d\times d$ ，第一行放递推系数，下面各行负责把旧分量向下搬运。

例如递推式：

$a_n=p\cdot a_{n-1}+q\cdot a_{n-2}+r\cdot a_{n-3}$

转移矩阵为：

$\begin{bmatrix} p & q & r\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix}$

规律非常明显喵。

至此，矩阵快速幂优化递推的核心思想就讲完了。总结一下：

确定状态向量；
写出递推关系；
构造转移矩阵；
快速幂求解。

有帮助，赞一个

去预览

0/2000

全部评论 3

ymhh
置顶
一个悲伤的故事：我小学做裂项题时，经常将式子化成秦九韶公式（当时还不知道），但是由于秦九韶公式只能递推且裂项题n通常很大，所以我从那时开始，只要看到式子很像秦九韶公式就会怕，今天学习矩阵快速幂看到一个很像秦九韶公式的式子（其实不是），就怕了，所以和AI深度学习3h，发现根本不是一个东西，注意到OIer其实不用了解那么多的底层原理（起码我这种蒟蒻不用），因此我浪费了集训的一个下午+晚自习

昨天来自广东
0
- ymhh
  回复
  ymhh
  但现在起码我知道：我不该怕了
  
  昨天来自广东
  1
亚洲卷王 AK IOI
矩阵满足结合律和分配律不考虑写一下证明吗

7小时前来自北京
0
- ymhh
  回复
  亚洲卷王 AK IOI
  这个试一下就出来了吧
  
  6小时前来自广东
  0
🥥
注意到你GO大蛇越来越多了

20小时前来自美国
0
- ymhh
  回复
  🥥
  《来自美国》
  
  11小时前来自广东
  0