矩阵

矩阵定义

矩阵（Matrix）通俗地讲可以看做一个二维数组，每个位置上都是一个数字，更准确地说它是一个按照矩形阵列排列的实数或复数集合。

下面来看看矩阵的运算，其中矩阵加减法和数乘矩阵被称为矩阵的线性运算

矩阵加减法

定义

矩阵加减法仅在矩阵形态相同时被定义，也就是两个矩阵行数列数均相同时才有加减法。矩阵的加法和减法就是把它们对应位置上的数字相加减，假设有两个矩阵 (A,B)，均有 (n) 行 (m) 列，那么 (A pm B) 得到的新矩阵 (C) 也是 (n*m) 的矩阵，其中 (forall iin[1,n],forall jin[1,m], C_{i,j}=A_{i,j}pm B_{i,j})，更形象的写法如下：

运算律

矩阵加减法满足如下运算律（注意 (A,B,C) 都必须是同型矩阵）：

交换律：(A+B=B+A)

结合律：(A+(B+C)=(A+B)+C)

数乘矩阵

定义

一个数字乘一个矩阵就是把矩阵中的每一个数都乘上这个数字。假设 (B=lambda A)，那么有 (forall iin[1,n],forall jin[1,m], B_{i,j}=lambda A_{i,j})，即：

运算律

数乘矩阵满足如下运算律：

交换律：(lambda(mu A)=mu(lambda A)=(lambdamu)A)

分配律：((lambda+mu)A=lambda A+mu Aqquadlambda(A+B)=lambda A+lambda B)

矩阵转置

定义

假设有一个 (n) 行 (m) 列的矩阵 (A)，那么我们把 (A) 中的每一行都换成序号相同的列，把每一列都换成序号相同的行，得到的新矩阵就称作原矩阵 (A) 的转置矩阵记为 (A^T) 或 (A')，此处 (A) 的转置矩阵就是 (m) 行 (n) 列的

也就是说 (forall iin[1,n],forall jin[1,m], A^T_{j,i}=A_{i,j})

运算律

矩阵转置满足如下运算律：

((A^T)^T=A)

((A^T+B^T)=A^T+B^T)

((lambda A)^T=lambda(A^T))

((AB)^T=B^TA^T)

矩阵乘法

定义

仅当一个矩阵的列数与另一个矩阵的行数相同时矩阵乘法才被定义，假设矩阵 (A) 为 (n*m) 的矩阵，矩阵 (B) 为 (m*p) 的矩阵，那么 (A*B) 所得到的矩阵 (C) 就是一个 (n*p) 的矩阵，其中：

也就是说参与矩阵乘法运算的两个矩阵中，第一个矩阵的列数等于第二个矩阵的行数，算出的新矩阵的行数为第一个矩阵的行数，新矩阵的列数为第二个矩阵的列数，新矩阵中第 (i) 行第 (j) 列的元素就等于第一个矩阵的第 (i) 行的所有元素与第二个矩阵的第 (j) 行的所有元素分别相乘，然后把乘积相加得到的结果

下面来举个例子帮助直观理解，例如我们令 (AB=C)，那么我们可以展开写成：

那么 (c_{1,2}) 和 (c_{2,1}) 分别是由哪些数字相乘得到的呢？

从图上就能直观地看出 (c_{1,2}=a_{1,1}*b_{1,2}+a_{1,2}*b_{2,2}+a_{1,3}*b_{3,2}+a_{1,4}*b_{4,2}) ，也就是 (A) 的第一行和 (B) 的第二列相乘相加

运算律

矩阵乘法满足如下运算律：

乘法结合律：((AB)C=A(BC))

乘法（左、右）分配律：((A+B)C=AC+BC) 以及 (C(A+B)=CA+CB)

数乘结合性：((lambda A)B=lambda(AB)=A(lambda B))

c++ code

int a[MAXN][MAXN],b[MAXN][MAXN],n,m,p;
//这里省略读入，假设输入的a，b分别为n行m列和m行p列的矩阵，从下标0开始存放
int c[n][p];//矩阵乘法结果为一个n行p列的矩阵
memset(c,0,sizeof(c));//初始化数组
for(int i=0;i<n;i++)
    for(int j=0;j<p;j++)
        for(int k=0;k<m;k++)//枚举
        	c[i][j]+=a[i][k]*b[k][j];//乘上并加入c中
//最后c中存放的矩阵即为矩阵乘法的结果

拓展与应用

单位矩阵

单位矩阵在矩阵乘法中有重要作用，它相当于普通数字乘法中的 (1)，任何矩阵左乘或者右乘单位矩阵都等于这个矩阵自身

单位矩阵是一个方阵（全称方块矩阵，指行数列数相等的矩阵），它的左上角到右下角对角线上的所有元素都为 (1)，其他元素都是 (0)，记作 (I_n) 或 (E_n)，常用 (I) 或 (E) 表示

满足性质：

矩阵快速幂

对于一个方阵来说，显然它反复乘以自己得到的仍旧是相同大小的方阵，如果我们需要反复乘同一个方阵，单纯 (Theta(n)) 求就会导致效率极其低下，在以前相信大家都学过快速幂，由于矩阵乘法的运算律，我们仍然可以使用快速幂计算一个方阵的幂，思路与普通的快速幂极为类似，所以就不多解释了，不了解快速幂可以自行查阅相关资料，

注意这里 (ans) 矩阵一开始应该初始化为单位矩阵

下面直接上代码：

const int mod=1e9+7;
int n,p;
cin>>n>>p;
long long a[n][n],ans[n][n],tmp[n][n];
for(int i=0;i<n;i++)//初始化
{
    for(int j=0;j<n;j++)
        cin>>a[i][j],ans[i][j]=tmp[i][j]=0;
    ans[i][i]=1;
}
while(p)//快速幂
{
    if(p&1)
    {
        for(int i=0;i<n;i++)//tmp=ans*a
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                    tmp[i][j]=(tmp[i][j]+ans[i][k]*a[k][j]%mod)%mod;
        for(int i=0;i<n;i++)//ans=tmp
            for(int j=0;j<n;j++)
                ans[i][j]=tmp[i][j],tmp[i][j]=0;
    }
    for(int i=0;i<n;i++)//tmp=a*a
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
                tmp[i][j]=(tmp[i][j]+a[i][k]*a[k][j]%mod)%mod;
    for(int i=0;i<n;i++)//a=tmp
        for(int j=0;j<n;j++)
            a[i][j]=tmp[i][j],tmp[i][j]=0;
    p>>=1;
}
for(int i=0;i<n;i++)//输出
{
    for(int j=0;j<n;j++)
        cout<<ans[i][j]<<' ';
    putchar('n');
}

这样码风有点丑，只是为了展示方便，没有写成结构体+函数的形式，自己做题时建议都写成结构体形式，更方便调试

加速递推

举个栗子：点我传送 Luogu P1962 斐波那契数列

题意简述：给定 (n)，请你给出斐波那契数列第 (n) 项对 (10^9+7) 取模的结果，其中 (1le n<2^{63})

如果暴力解决这道题那么就是 (Theta(n)) 递推，但由于 (n) 过大，显然会超时，利用矩阵就可以优化

我们设一个 (1*2) 的矩阵 (A_i=left(begin{matrix}F_i & F_{i-1}end{matrix}right))，其中 (F_i) 表示斐波那契数列的第 (i) 项，那么根据斐波那契数列的定义有 (A_{i+1}=left(begin{matrix}F_i+F_{i-1} & F_{i}end{matrix}right))，我们发现可以找到一个矩阵 (B=left(begin{matrix}1 & 1\1 & 0end{matrix}right)) 使得 (A_i B=A_{i+1}) 即：

简单手动计算一下就可以知道这个式子的正确性

所以斐波那契数列的 (A_n(nge3)) 就可以表示为 (A_1 B^{n-2})，根据矩阵乘法的运算律，我们利用矩阵快速幂把 (B^{n-2}) 算出来再用 (A_1) 乘，就能在 (Theta(log n)) （常数有点大，主要是矩阵乘法的 (Theta(2^3))）的时间复杂度内解决这个问题

上面这种方法就是利用矩阵乘法加速递推，类似的线性递推题目可以尝试使用矩阵乘法进行优化，上面题目中矩阵 (A) 就称作状态矩阵，矩阵 (B) 就称作转移矩阵，正确地定义状态矩阵并计算出转移矩阵就可以成功优化

该文为本人原创，转载请注明出处

博客园传送门

洛谷传送门