矩阵乘法 学习笔记

0.前置知识

无

1.矩阵

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

矩阵长这样：
$\begin{bmatrix}
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.加法

令
$A=
\begin{bmatrix}
2 & 3 & 1\\
1 & 4 & 2
\end{bmatrix}$，$
B=\begin{bmatrix}
4 & 3 & 2\\
2 & 3 & 2
\end{bmatrix}$，则
$A+B=\begin{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.减法

令
$A=
\begin{bmatrix}
4 & 3 & 2\\
2 & 4 & 2
\end{bmatrix}$，$
B=
\begin{bmatrix}
2 & 3 & 1\\
1 & 3 & 2
\end{bmatrix}$，则
$A-B=\begin{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.数乘

令
$A=
\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.快速幂

就是快速幂将普通乘法改为矩阵乘法即可。

while(n)
{
    if(n&1) ans=ans*a;
    a=a*a;n>>=1;
}

还要重定义 * 运算。

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)$。