矩阵乘法 学习笔记

· · 个人记录

0.前置知识

无

1.矩阵

矩阵乘法即为两个矩阵相乘。

矩阵长这样：

a_{1,1} & \dots & a_{1,m}\\ \vdots & \ddots & \vdots \\ a_{n,1} & \dots & a_{n,m} \end{bmatrix}

矩阵乘法需要满足的条件为两个分别为 n \times k，k \times m的矩阵相乘。

单元矩阵为对角线为 1 的矩阵，就是数字中的 1。

2.矩阵运算

1.加法

令

\begin{bmatrix} 2 & 3 & 1\\ 1 & 4 & 2 \end{bmatrix}$，

B=\begin{bmatrix} 4 & 3 & 2\ 2 & 3 & 2 \end{bmatrix}$，则

2+4 & 3+3 & 1+2\\ 1+2 & 4+3 & 2+2 \end{bmatrix}=\begin{bmatrix} 6 & 6 & 3\\ 3 & 7 & 4 \end{bmatrix}

2.减法

令

\begin{bmatrix} 4 & 3 & 2\\ 2 & 4 & 2 \end{bmatrix}$，

B= \begin{bmatrix} 2 & 3 & 1\ 1 & 3 & 2 \end{bmatrix}$，则

4-2 & 3-3 & 2-1\\ 2-1 & 4-3 & 2-2 \end{bmatrix}=\begin{bmatrix} 2 & 0 & 1\\ 1 & 1 & 0 \end{bmatrix}

3.数乘

令

\begin{bmatrix} 4 & 3 & 2\\ 2 & 4 & 2 \end{bmatrix}$，则 $2 \times A= \begin{bmatrix} 2 \times 4 & 2 \times 3 & 2 \times 2\\ 2 \times 2 & 2 \times 4 & 2 \times 2 \end{bmatrix}= \begin{bmatrix} 8 & 6 & 4\\ 4 & 8 & 4 \end{bmatrix}

4.乘法

设 A 为一个 n \times k 的矩阵，B 为一个 k \times m 的矩阵。

则 A 与 B 的乘积 C 为一个 n \times m的矩阵，且满足C_{i,j}=\sum_{r=1}^kA_{i,r} \times B_{r,j}

举个例子，A= \begin{bmatrix} 1 & 2 & 2\\ 1 & 3 & 2 \end{bmatrix}， B= \begin{bmatrix} 1 & 0 \\ 2 & 2 \\ 1 & 1 \end{bmatrix}，则 $A \times B= \begin{bmatrix} 1 \times 1+2 \times 2+2 \times 1 & 1 \times 0+2 \times 2+2 \times 1\ 1 \times 1+3 \times 2+2 \times 1 & 1 \times 0+3 \times 2+2 \times 1 \end{bmatrix}= \begin{bmatrix} 7 & 6 \ 9 & 8 \end{bmatrix}

### 5.快速幂 就是快速幂将普通乘法改为矩阵乘法即可。 ```cpp while(n) { if(n&1) ans=ans*a; a=a*a;n>>=1; } ``` 还要重定义 `*` 运算。 ```cpp struct arr { int a[102][102]; arr() {memset(a,0,sizeof(a));} arr operator *(const arr &b) const { arr c; for(int i=1;i<=N;++i) for(int j=1;j<=K;++j) for(int k=1;k<=M;++k) c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%mo)%mo; return c; } }a,ans; ``` 就可以运算了。 模板题：P3390。 ## 3.应用 可以快速求除斐波那契数列的第 $n$ 项。 设

\begin{bmatrix} f{n-1} & f{n-2} \end{bmatrix} \times \begin{bmatrix} a & b \ c & d \end{bmatrix}= \begin{bmatrix} f{n} & f{n-1} \end{bmatrix}$

则 \begin{bmatrix} f_{n-1} \times a+f_{n-2} \times c & f_{n-1} \times b+f_{n-2} \times d \end{bmatrix}= \begin{bmatrix} f_{n} & f_{n-1} \end{bmatrix}

所以 \left\{\begin{matrix} f_{n-1} \times a+f_{n-2} \times c=f_{n} \\ f_{n-1} \times b+f_{n-2} \times d=f_{n-1}\end{matrix}\right.

因为 f_{n}=f_{n-1}+f_{n-2}

解得 \left\{\begin{matrix}a=1 \\b=1 \\c=1 \\d=0\end{matrix}\right.

所以 \begin{bmatrix} f_{n-1} & f_{n-2} \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}= \begin{bmatrix} f_{n} & f_{n-1} \end{bmatrix}

进一步转换得 \begin{bmatrix} f_{2} & f_{1} \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-2}= \begin{bmatrix} f_{n} & f_{n-1} \end{bmatrix}

所以这玩意就可以用快速幂做了，复杂度为O(\log_{2}n)。

4.总结

挺玄学的算法。

练习题：

P1962

P1349

P1306

P4834