矩阵来源于线性方程组，体现了一种“整体打包处理”的思想。

矩阵

一个 $n$ 行 $m$ 列的数表，叫做矩阵。当 $n=1$ ,就是一行，也叫做行向量，当 $m=1$ 时就是列向量。

例如： $\begin{bmatrix} 0 & 1 & 3\\ 1 & 2 & 0 \end{bmatrix}$

• 一般用 $A_{i,j}$ 表示第 $i$ 行第 $j$ 的数

矩阵加法

两个 $n \times n$ 的矩阵可以做加法，即对应位置上的数字相加，变成一个新的矩阵。

$A=\begin{bmatrix} A_{11} & A_{12} & \dots & A_{1m} \\ A_{21} & A_{22} & \dots & A_{2m} \\ \dots & \dots & \dots & \dots \\ A_{n1} & A_{12} & \dots & A_{1m} \\ \end{bmatrix}$ , $B=\begin{bmatrix} B_{11} & B_{12} & \dots & B_{1m} \\ B_{21} & B_{22} & \dots & B_{2m} \\ \dots & \dots & \dots & \dots \\ B_{n1} & B_{12} & \dots & B_{1m} \\ \end{bmatrix}$

$A+B=\begin{bmatrix} A_{11}+B_{11} & A_{12}+B_{12} & \dots & A_{1m}+B_{1m} \\ A_{21}+B_{21} & A_{22}+B_{22} & \dots & A_{2m}+B_{2m} \\ \dots & \dots & \dots & \dots \\ A_{n1}+B_{n1} & A_{n2}+B_{n2} & \dots & A_{nm}+B_{nm} \\ \end{bmatrix}$

矩阵乘法

矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。

设 $A$为 $m \times p$ 的矩阵，$B$ 为 $p \times n$ 的矩阵，那么称 $m \times n$ 的矩阵 $C$ 为矩阵 $A$ 与 $B$ 的乘积，记作 $C=AB$，其中矩阵 $C$ 中的第 $i$ 行第 $j$ 列元素可以表示为:

$C_{ij}=(AB)_{ij}=\sum _{k=1}^{p} a_{ik}b_{kj}=a_{i1}b_{1j}+a_{i2}b_{2j}+\dots+a_{ip}b_{pj}$

例如：

$A=\begin{bmatrix} a_{1,1}& a_{1,2} & a_{1,3}\\ a_{2,1}& a_{2,2} & a_{2,3} \end{bmatrix}$

$B=\begin{bmatrix} b_{1,1} & b_{1,2} \\ b_{2,1} & b_{2,2} \\ b_{3,1} & b_{3,2} \end{bmatrix}$

$C=AB=\begin{bmatrix} a_{1,1}b_{1,1}+a_{1,2}b_{2,1}+a_{1,3}b_{3,1} & a_{1,1}b_{1,2}+a_{1,2}b_{2,2}+a_{1,3}b_{3,2}\\ a_{2,1}b_{1,1}+a_{2,2}b_{2,1}+a_{2,3}b_{3,1} & a_{2,1}b_{1,2}+a_{2,2}b_{2,2}+a_{2,3}b_{3,2} \end{bmatrix}$

注意事项：

• 1、当矩阵 $A$ 的列数（column）等于矩阵 $B$ 的行数（row）时，$A$ 与 $B$ 可以相乘。
• 2、矩阵 $C$ 的行数等于矩阵 $A$ 的行数，$C$ 的列数等于 $B$ 的列数。
• 3、乘积 $C$ 的第 $m$ 行第 $n$ 列的元素等于矩阵 $A$ 的第 $m$ 行的元素与矩阵 $B$ 的第 $n$ 列对应元素乘积之和 , 口诀为左行右列。

矩阵乘法性质

• 乘法结合律： $(AB)C=A(BC)$
• 乘法左分配律： $(A+B)C=AC+BC$
• 乘法右分配律： $C(A+B)=CA+CB$
• 对数乘的结合性: $k(AB）=(kA)B=A(kB）$
• 转置 $(AB)^T=B^TA^T$

线性代数研究的向量多为列向量，根据这样的对矩阵乘法的定义方法，经常研究对列向量左乘一个矩阵的左乘运算，同时也可以在这里看出「打包处理」的思想，同时处理很多个向量内积。列向量左乘，列向量右乘。

方阵与单位矩阵

当矩阵行列相等，那么就是一个方阵。

“单位矩阵”（Identity matrix）的概念 定义： 从左上角到右下角的对角线（称为主对角线）上的元素均为 1。除此以外全都为 0。 顾名思义，它在矩阵乘法中就相当于算术乘法中的 1。

例如：

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

方阵的逆

对于方阵 $A$ ,如果存在方阵 $P$ ，使得 $𝐴 ×𝑃 = I$ ,那么方阵 $P$ 就是方阵 $A$ 的逆矩阵。

逆矩阵不一定存在。如果存在，可以使用 高斯消元 进行求解。

矩阵快速幂

利用结合律，矩阵乘法可以利用 快速幂 的思想来优化(参考教程：快速幂与逆元)，也就是矩阵快速幂。

可以利用函数封装矩阵乘法运算，或者重载乘法运算符。

矩阵快速幂核心代码：

struct mat
{
    ll v[N][N];   //N 是常量
    int n,m;    //n 行 m 列
    mat()   //构造函数，生成变量时自动运行
    {
        memset(v,0,sizeof(v));
    }
};

mat mul(mat A,mat B)  //矩阵乘法
{
    mat C;
    C.n=A.n, C.m=B.m;
    for(int i=1;i<=A.n;i++)
        for(int j=1;j<=B.m;j++)
            for(int k=1;k<=A.m;k++)
                C.v[i][j]+=(A.v[i][k]*B.v[k][j]),C.v[i][j]%=mod;
    return C;
}
mat pw(mat A,ll k) //求矩阵 A^k 矩阵快速幂
{
    mat ret;
    ret.n=A.n, ret.m=A.m;
    for(int i=1;i<=ret.n;i++)ret.v[i][i]=1;  //初始化为单位矩阵
    while(k)
    {
        if(k&1)ret=mul(ret,A);
        A=mul(A,A);
        k>>=1;
    }
    return ret;    
}

---

模板题：P3390 【模板】矩阵快速幂

参考代码：点击

更多时候，需要将原问题转化为矩阵快速幂，即就是用矩阵快速幂优化。

---

例 1. P1962 斐波那契数列

【题意简化】求斐波那契数列第 $n$ 项 ，其中 $n$ 很大。

【分析】直接 $O(n)$ 运算会超时。由 $f_i=f_{i-1}+f_{i-2}$ , 构造为矩阵乘法:

$\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}$= $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ $\begin{bmatrix} f_{i-1}\\ f_{i-2} \end{bmatrix}$= $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^2$ $\begin{bmatrix} f_{i-2}\\ f_{i-3} \end{bmatrix}$= $\dots$= $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{i-2}$ $\begin{bmatrix} f_{2}\\ f_{1} \end{bmatrix}$

转换为矩阵乘法时间复杂度为 $O(2^3*\log{n})$

例2. P1349 广义斐波那契数列

【题意简化】给定数列 $a_n=p\times a_{n-1}+q\times a_{n-2}$ ，$a_1$ , $a_2 ,m$ 已知 ，求 $a_n \mod m$ .

【分析】

由 $a_n=p\times a_{n-1}+q\times a_{n-2}$ 构造矩阵乘法：

$\begin{bmatrix} a_i\\ a_{i-1} \end{bmatrix}$= $\begin{bmatrix} p & q \\ 1 & 0 \end{bmatrix}$ $\begin{bmatrix} a_{i-1}\\ a_{i-2} \end{bmatrix}$

利用矩阵快速幂求解。

例 3. P1939 矩阵加速（数列）

【题意简化】给定数列 $a_n=a_{n-1}+a_{n-3}$， $a_1=a_2=a_3=1$ ,求 $a_n \mod 10^9+7$

【分析】

构造矩阵

$\begin{bmatrix} a_i \\ a_{i-1} \\ a_{i-2} \end{bmatrix}$= $\begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$ $\begin{bmatrix} a_{i-1}\\ a_{i-2} \\ a_{i-3} \end{bmatrix}$

---

更多例题，请参考 矩阵乘法应用

---

学习完毕

{{ select(1) }}

• YES
• NO