详解矩阵乘法

本篇随笔详细讲解一下信息学奥林匹克竞赛中矩阵乘法的相关内容。矩阵和矩阵乘法的相关内容是数学中线性代数部分的内容，欢迎有兴趣的读者再自行涉猎一些纯粹的数学上的知识。本篇随笔只针对矩阵乘法在信息学和算法竞赛中的应用进行讲解。

矩阵加减法的概念

所谓矩阵其实就是一个数阵，我们可以把它看作一个二维数组。

这是矩阵的概念。

为了方便后面的学习，我们将一个矩阵记作大写字母，如\(A,B,C\)等等，而类比于二维数组，把矩阵中的每个数都用一个“坐标”来表示，记作：\(A(a,b)\)等等。

这里引用高中数学必修四中平面向量中我认为很搞笑的一句话：如果没有运算，向量只是一个“路标”，因为有了运算，向量的力量无限。

好的，把这句话搬过来：如果没有运算，矩阵只是个数阵，因为有了运算，矩阵的力量无限。（话说数学中无限力量的有好多东西啊！）

那么在这里隆重介绍矩阵加减法的概念：

就是把对应位置的两个数相加减。

觉得太草率？

那来一波数学一点的定义：

对于两个矩阵\(A,B\)进行加减运算，得到的结果矩阵\(C\)具备以下性质：
\[C(a,b)=A(a,b)\pm B(a,b)\]
需要说一下的是，进行矩阵加减法的两个矩阵必须尺寸相等。

你可能会说：这算什么啊，矩阵加减法还不能是大小不等的矩阵进行运算？

是的，就是不可以，这是规矩。后面的矩阵乘法的规矩还会更复杂。

矩阵乘法的概念

矩阵乘法的定义比较复杂，建议这个地方画图理解，千万别懒，要不然会耽误很长时间，而且还可能造成理解不透彻。

为了证明它的确很复杂，就先上一波纯数学定义：

设\(A\)是\(n*m\)的矩阵，\(B\)是\(m*p\)的矩阵，那么\(C=A\times B\)是一个\(n\times p\)的矩阵，其中每个数满足：
\[C(i,j)=\sum^{k=m}_{k=1}{A(i,k)\times B(k,j)}\]
当然，我坚定不移地认为还是有人一看到这个式子就明白了矩阵乘法在干嘛。但是反正蒟蒻我数学比较菜，想了五分钟才想出来，为了节约读者的宝贵的5分钟，我用一种比较通俗的解释来定义矩阵乘法。

我的解释就是：一行乘一列，再相加。

比如你现在要得出结果矩阵\(C\)中的\((3,5)\)这个数，你就把\(A\)矩阵的第\(3\)行和\(B\)矩阵的第\(5\)列（你会发现这一行和这一列含有相同个数），然后把这些数依次相乘，最后再把这些乘积加到一起即可。

这就是矩阵乘法的概念了。

再来一张图加深理解：

通过刚刚对矩阵乘法的定义中，我们应该能得出矩阵乘法运算的规矩：即\(A\)矩阵的列数和\(B\)矩阵的行数必须相等。比如\(3\times 4\)和\(4\times 5\)的矩阵可以相乘，但是\(3\times 4\)和\(5\times 4\)则不可以。

所以我们发现矩阵乘法的运算律：满足分配律和结合律，但是不满足交换律，因为交换后的矩阵并不能保证还符合定义中的“规矩”。

矩阵乘法加速递推

上文的讲解已经完成了对矩阵乘法概念的介绍，属于数学内容。其实，矩阵乘法是线性代数中很重要的一个模型，可以用来解决很多问题，事实上，它是和向量、线性方程组结合在一起的。有很多我们想不到的妙用。由于与信竞关系不大，便不予过多讲解。有兴趣的读者可以自己上网查阅相关资料。

那么接下来便开始介绍矩阵乘法在算法竞赛中的应用：加速递推。

我们用一道经典题目来认识矩阵乘法加速递推的过程：

求斐波那契数列的第\(n\)项。

斐波那契其实是最基本的递推问题，其递推式基本成为常识：\(f(n)=f(n-1)+f(n-2)\)。现在我们要求第\(n\)项的斐波那契数列，按照这个递推式，可以给出一个\(O(n)\)的解决方法。这个算法足以解决\(10^7\)以内的数据，并且支持取模。但是，假如要求的大一点，求\(10^{12}\)的数据呢？

我们顿时抓头了：\(O(n)\)的已经很快了，再快一点...

矩乘就可以做到这一点。

我们来分析：为什么\(O(n)\)的算法还是不够快？就是因为，我们在算\(f(n)\)的时候，必须先把\(f(n-1)\)和\(f(n-2)\)算出来。但是题目只需要我们给出第n项，并不需要我们算出\(1-n\)项，所以我们在求\(1-n-1\)这些项的时候耗费了大量没必要的时间。

那么我们怎么才能把中间的递推过程简化呢？

设有矩阵\(F(n)\)是一个\(1\times 2\)的矩阵，\(F(n)=[fib_n\,\,\,\,fib_{n+1}]\)。我们希望通过\(F(n-1)\)求出\(F(n)\)，那么这个\(F(n)\)矩阵的第一项就是要求的答案。因为\(F(n-1)=[fib_{n-1}\,\,\,fib_{n}]\)，那么，我们只需要把这个矩阵的后一个数变成前一个数，并且把这两个数加和变成后一个数。（因为\(fib_{n+1}=fib_{n}+fib_{n-1}\)）

那么，我们考虑在这个矩阵\(F(n-1)\)上乘以一个“状态矩阵”，实现这一目的。我们发现，这个矩阵是一个\(2\times 2\)的矩阵，是
\[0\,\,\,1\\1\,\,\,1\]
每一次递推，我们只需要乘以这个状态矩阵即可，那么，只需要给出初值，即\(fib_1,fib_2\)，使之构成矩阵\(F(1)\)，设状态矩阵为\(A\)，我们只需要乘上\(n-1\)个\(A\)，就能得出我们最终需要的\(F(n)\)，也就是说：
\[F(n)=F(1)\times A^{n-1}\]
这是个矩阵递推式，我们发现，\(A^{n-1}\)可以用一个快速幂方便的解决（当然是矩阵快速幂啦，这个在后面的代码部分会有详细的介绍）。

这样我们就实现了矩阵乘法优化递推，这样算法的时间复杂度是\(O(n^3logT)\)

总结

一般来讲，具备这些条件的递推问题，可以用矩乘进行加速：

首先，问题只需要我们求出最终的结果数据，而不要求中间数据。比如斐波那契数列，如果只求第\(n\)项的斐波那契，完全可以用上述的矩乘递推解决。但是如果要求\(1-n\)每一项的斐波那契数，矩乘就无能为力了。

然后，我们可以抽象出一个长度为\(n\)的一行矩阵，所有的变化都是从这里开始的，而且这个矩阵在单位时间内只发生一次变化。这个条件其实就是在说递推初值。

之后，这个递推过程必须是线性的。即每一次递推只能有两种操作：乘一个系数或者相加，而不支持高次递推。

最后，就是优化效果的问题，矩阵乘法只有在递推次数很大，但是初值数量很少的时候才能起到较大的效果。

我们在使用矩乘进行加速递推的时候，实际只需要考虑两个问题：初值矩阵，状态矩阵，剩下的就是矩乘函数和快速幂的板子问题了。（下面就讲）

矩阵乘法和矩阵快速幂的代码实现

矩阵乘法

矩阵乘法的代码根据矩阵乘法的定义就可以解决，用三重循环达到\(O(n^3)\)的时间复杂度。

代码：

int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];
void multiset(int a[][],int b[][],int n)
{
    for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++)
            for(int j=1;j<=n;j++)
                c[i][j]+=a[i][k]*b[k][j];
}

那么矩阵快速幂也很简单啦！把普通快速幂的乘法运算都换成矩阵乘法就可以啦！

代码：

int ret[maxn][maxn];
void qpow(int a[][],int n)
{
    memset(ret,1,sizeof(ret));
    while(n)
    {
        if(n&1)
            multiset(ret,a,maxn);
        multiset(a,a,maxn);
        n>>=1;
    }
}

以上就是矩阵乘法的大部分内容，感谢大家的推荐和收看。