【算法基础篇】（五十七）线性代数之矩阵乘法从入门到实战：手撕模板 + 真题详解

前言

线性代数是算法学习中的重要数学基础，而矩阵乘法更是其中的核心内容，不仅是理解后续矩阵快速幂、矩阵加速的前提，还广泛应用于图论邻接矩阵、动态规划优化、数列求解等算法场景。本文将从矩阵的基本概念出发，一步步拆解矩阵乘法的定义、运算规则，再结合洛谷经典真题，手把手实现矩阵乘法、矩阵快速幂的 C++ 模板，同时讲解矩阵加速在数列求解中的实际应用，让零基础的同学也能彻底吃透矩阵乘法！下面就让我们正式开始吧！

一、矩阵基础概念：认识 “数表” 的世界

在正式学习矩阵乘法前，我们首先要搞清楚什么是矩阵，以及算法中常用的特殊矩阵有哪些。这些基础概念是后续所有运算的前提，理解透彻才能避免后续踩坑。

1.1 矩阵的定义

简单来说，矩阵就是由n×m 个数字排成的n 行 m 列的数表，我们通常用大写字母 A、B、C 来表示矩阵，其中第 i 行第 j 列的元素记作aij​。其标准形式如下：

比如一个 2 行 3 列的矩阵可以表示为

，这就是一个 2×3 矩阵。

在算法中，矩阵的一个典型应用就是图论的邻接矩阵—— 用一个 n×n 的矩阵存储 n 个节点的图，若节点 i 和节点 j 之间有边，则aij​=1，否则为 0，通过邻接矩阵可以快速判断节点间的连通性，而邻接矩阵的运算本质就是矩阵乘法。

1.2 算法中高频的特殊矩阵

在矩阵乘法的运算中，我们会经常遇到几种特殊的方阵（行数 = 列数的矩阵），它们各自有独特的性质，更是矩阵快速幂、单位矩阵运算的关键，下面逐个讲解，结合例子理解更直观。

1.2.1 方阵

行数等于列数的矩阵称为方阵，比如 4×4、3×3 矩阵都是方阵。方阵中从左上角到右下角的元素构成主对角线，后续的三角矩阵、对角矩阵都是基于方阵的主对角线定义的。例：4 阶方阵（4×4）

1.2.2 三角矩阵

三角矩阵分为上三角矩阵和下三角矩阵，核心是主对角线一侧的元素全为 0：

• 上三角矩阵：主对角线左下方的元素均为 0，只有主对角线和右上方有非 0 元素；
• 下三角矩阵：主对角线右上方的元素均为 0，只有主对角线和左下方有非 0 元素。

例：4 阶上三角矩阵

​​例：4 阶下三角矩阵

1.2.3 对角矩阵

主对角线之外的元素均为 0的方阵称为对角矩阵，简单说就是只有主对角线上有非 0 元素，其余位置全 0。对角矩阵是三角矩阵的特殊形式，上三角和下三角矩阵的交集就是对角矩阵。例：4 阶对角矩阵

1.2.4 单位矩阵

主对角线的元素均为 1的对角矩阵称为单位矩阵，通常用字母 E 表示。单位矩阵是矩阵乘法中的 “数字 1”，任何矩阵乘以单位矩阵，结果都等于原矩阵，即AE=EA=A，这一性质是矩阵快速幂的核心基础，一定要牢记！

例：4 阶单位矩阵

二、矩阵的基本运算：加减与数乘

在学习矩阵乘法前，我们先掌握矩阵的线性运算—— 加法、减法和数乘，这些运算规则简单，是理解复杂运算的铺垫，核心要求是同型矩阵（行数和列数都相同的矩阵）。

2.1 矩阵加法与减法

矩阵加减法的规则非常直观：两个同型矩阵相加减，结果为对应位置的元素分别相加减。

• 前提：必须是同型矩阵，比如 2×3 矩阵只能和 2×3 矩阵相加减，3×3 矩阵只能和 3×3 矩阵相加减，不同型矩阵无法进行加减运算；
• 结果：相加减后得到的矩阵，行数和列数与原矩阵保持一致。

2.2 矩阵数乘

矩阵数乘指的是一个数字乘以一个矩阵，规则是：矩阵中的每一个元素都乘以这个数字，结果矩阵的行数和列数不变。这里的 “数” 可以是整数、小数，正数、负数均可，数乘是对矩阵的整体缩放，不会改变矩阵的维度。

2.3 线性运算的运算规律

矩阵的加法和数乘满足交换律、结合律和分配律，和我们小学学的数字运算规律基本一致，记起来很容易：

1. 交换律：A+B=B+A；
2. 结合律：(A+B)+C=A+(B+C)，k×(l×A)=(k×l)×A；
3. 分配律：k×(A+B)=k×A+k×B，(k+l)×A=k×A+l×A。

这些规律看似简单，但在后续的矩阵运算化简中会经常用到，熟悉后能大幅提高运算效率。

三、矩阵乘法：核心定义与运算规则

矩阵乘法是本文的核心重点，也是和普通数字运算差异最大的部分，其规则不是简单的对应元素相乘，而是 “行乘列求和”，且有严格的维度要求，很多同学初次学习容易出错，建议结合例子反复理解。

3.1 矩阵乘法的前提条件

矩阵 A 和矩阵 B 能够相乘的唯一前提：矩阵 A 的列数 = 矩阵 B 的行数。如果不满足这个条件，矩阵乘法无意义，无法进行运算。比如：

• A 是 n×s 矩阵（n 行 s 列），B 是 s×m 矩阵（s 行 m 列）：A 的列数 = s，B 的行数 = s，满足条件，可以相乘；
• A 是 2×3 矩阵，B 是 3×4 矩阵：满足条件，可以相乘；
• A 是 2×3 矩阵，B 是 2×3 矩阵：A 的列数 = 3，B 的行数 = 2，不满足条件，无法相乘。

3.2 矩阵乘法的结果维度

若 A 是 n×s 矩阵，B 是 s×m 矩阵，那么 A×B 的结果是一个n×m 矩阵（n 行 m 列），记为 C=AB。

简单总结：结果矩阵的行数等于第一个矩阵的行数，列数等于第二个矩阵的列数，而中间的 “s” 是两个矩阵的 “公共维度”，是行乘列求和的次数。

例：2×3 矩阵 × 3×4 矩阵 = 2×4 矩阵；3×5 矩阵 ×5×2 矩阵 = 3×2 矩阵。

3.3 矩阵乘法的核心公式

设 C=AB，其中 A 是 n×s 矩阵，B 是 s×m 矩阵，C 是 n×m 矩阵，那么 C 中第 i 行第 j 列的元素cij​的计算公式为：

用通俗的语言解释就是：cij​等于矩阵 A 的第 i 行所有元素，与矩阵 B 的第 j 列对应位置元素分别相乘后，再将所有乘积相加，也就是我们常说的 “行乘列求和”。

这里的 k 从 1 到 s，对应 A 的第 i 行有 s 个元素，B 的第 j 列有 s 个元素，刚好一一对应相乘，求和后得到cij​。

3.4 实例解析：手把手计算矩阵乘法

光看公式和定义容易抽象，我们用一个具体的例子，手把手计算矩阵乘法，把 “行乘列求和” 的规则落地，看完这个例子，矩阵乘法的计算就基本掌握了。

步骤 1：判断是否可乘 + 确定结果维度A 的列数 = 2，B 的行数 = 2，满足条件；结果 C 是 3×3 矩阵（n=3，m=3）。

步骤 2：逐行逐列计算cij​C 是 3 行 3 列，需要计算 9 个元素，逐个计算：

1. c11​：A 第 1 行 × B 第 1 列 → 1×7+2×10=7+20=27
2. c12​：A 第 1 行 × B 第 2 列 → 1×8+2×11=8+22=30
3. c13​：A 第 1 行 × B 第 3 列 → 1×9+2×12=9+24=33
4. c21​：A 第 2 行 × B 第 1 列 → 3×7+4×10=21+40=61
5. c22​：A 第 2 行 × B 第 2 列 → 3×8+4×11=24+44=68
6. c23​：A 第 2 行 × B 第 3 列 → 3×9+4×12=27+48=75
7. c31​：A 第 3 行 × B 第 1 列 → 5×7+6×10=35+60=95
8. c32​：A 第 3 行 × B 第 2 列 → 5×8+6×11=40+66=106
9. c33​：A 第 3 行 × B 第 3 列 → 5×9+6×12=45+72=117

步骤 3：整理结果矩阵C=AB=

3.5 矩阵乘法的重要运算规律

矩阵乘法的运算规律和普通数字乘法有很大差异，最核心的区别是不满足交换律，这一点是算法编程中必须注意的，一旦顺序写错，结果完全错误！下面总结矩阵乘法的核心规律：

3.5.1 不满足交换律

一般情况下，AB≠BA，甚至 BA 可能无意义。

原因有两点：

1. 维度不允许：比如 A 是 2×3 矩阵，B 是 3×4 矩阵，AB 是 2×4 矩阵，但 BA 的话，B 的列数 = 4，A 的行数 = 2，不满足相乘条件，BA 无意义；
2. 维度允许但结果不同：比如 A 和 B 都是 3×3 矩阵，AB 和 BA 都有意义，但计算结果几乎一定不同。

结论：矩阵乘法中，顺序决定一切，AB 表示 A 左乘 B，BA 表示 B 左乘 A，二者完全不同，编程时必须严格按照题目要求的顺序相乘。

3.5.2 满足结合律

A(BC)=(AB)C，即多个矩阵相乘时，改变括号的位置（运算顺序），结果不变。

结合律是矩阵快速幂的核心数学基础，正因为有结合律，我们才能像整数快速幂那样，将Ak拆解为多个小矩阵的乘积，实现对数级别的时间复杂度优化。

3.5.3 满足分配律

1. 左分配律：A(B+C)=AB+AC；
2. 右分配律：(B+C)A=BA+CA。

注意：分配律中也要注意顺序，左分配律中 A 始终在左边，右分配律中 A 始终在右边，不能随意交换。

3.5.4 单位矩阵的特殊性质

任何矩阵乘以单位矩阵，结果等于原矩阵，即AE=EA=A（前提是相乘维度满足条件）。

比如 A 是 n×s 矩阵，E 是 s×s 单位矩阵，则 AE=A；E 是 n×n 单位矩阵，则 EA=A。单位矩阵的这一性质，对应整数乘法中的 “1×x=x×1=x”，是矩阵快速幂中初始值的设置依据。

四、洛谷真题实战 1：基础矩阵乘法（B2105）

理解了矩阵乘法的定义和规则后，我们结合洛谷的基础真题B2105 矩阵乘法，用 C++ 实现基础的矩阵乘法模板。这道题是矩阵乘法的入门题，核心是模拟 “行乘列求和” 的过程，适合新手上手。

题目链接：https://www.luogu.com.cn/problem/B2105

4.1 题目描述

计算两个矩阵的乘法：n×m 阶的矩阵 A 乘以 m×k 阶的矩阵 B，得到 n×k 阶的矩阵 C。

• 输入：第一行是 n, m, k，随后 n 行是矩阵 A 的元素，再 m 行是矩阵 B 的元素；
• 输出：输出矩阵 C，共 n 行，每行 k 个整数，元素间用空格分隔；
• 数据范围：n, m, k 均小于 100，矩阵元素绝对值不大于 1000。

4.2 解题思路

1. 数据存储：用二维数组存储三个矩阵 A、B、C，由于数据范围小，定义数组大小为 110 即可（留余量，避免越界）；
2. 输入处理：依次输入 n, m, k，再输入矩阵 A 和矩阵 B 的元素；
3. 矩阵乘法核心：三层循环实现 “行乘列求和”：
   • 外层循环：遍历矩阵 A 的行（共 n 行）；
   • 中层循环：遍历矩阵 B 的列（共 k 列）；
   • 内层循环：遍历公共维度 m，计算行乘列的和，赋值给 C [i][j]；
4. 输出结果：按行输出矩阵 C 的所有元素，每行 k 个，空格分隔。

4.3 C++ 代码实现

#include <iostream>
using namespace std;

// 定义数组大小，留余量避免越界
const int N = 110;
// a:矩阵A, b:矩阵B, c:结果矩阵C
int a[N][N], b[N][N], c[N][N];
// n:A的行, m:A的列/B的行, s:B的列（题目中的k）
int n, m, s;

// 矩阵乘法核心函数
void mul() {
    for (int i = 1; i <= n; i++) { // 遍历A的行
        for (int j = 1; j <= s; j++) { // 遍历B的列
            for (int k = 1; k <= m; k++) { // 遍历公共维度m
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
}

int main() {
    cin >> n >> m >> s;
    // 输入矩阵A
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    // 输入矩阵B
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= s; j++) {
            cin >> b[i][j];
        }
    }
    // 执行矩阵乘法
    mul();
    // 输出结果矩阵C
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= s; j++) {
            cout << c[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

4.4 代码说明

1. 数组下标从 1 开始：符合数学中矩阵的行、列编号习惯，避免下标 0 带来的混淆，新手更容易理解；
2. 三层循环的顺序：i（A 的行）→ j（B 的列）→ k（公共维度），这是矩阵乘法的标准循环顺序，也可以调整为 i→k→j，结果一致，但前者更贴合 “行乘列求和” 的直观逻辑；
3. 结果矩阵初始化：C 数组的初始值为 0，通过累加a[i][k]∗b[k][j]得到最终的c[i][j]，符合求和公式的定义。

五、洛谷真题实战 2：矩阵快速幂（P3390）

掌握了基础矩阵乘法后，我们来学习矩阵乘法的进阶应用 —— 矩阵快速幂，这是算法竞赛中的高频考点，核心是类比整数快速幂，利用矩阵乘法的结合律，将Ak的计算时间复杂度从O(k)优化到O(logk)，适用于 k 极大的场景（比如 k≤10^18）。

5.1 矩阵快速幂的核心思想

整数快速幂的核心是 “快速幂降次”，比如计算

，可以拆解为

，而不是连续乘 10 次 x。矩阵快速幂完全复用这一思想，唯一的区别是：

• 整数快速幂的初始值是 1；
• 矩阵快速幂的初始值是单位矩阵 E（因为单位矩阵是矩阵乘法的 “1”）。

简单来说，矩阵快速幂的步骤为：

1. 初始化结果矩阵为单位矩阵 RET；
2. 将指数 k 进行二进制分解，遍历每一位；
3. 若当前位为 1，将结果矩阵 RET 与当前的矩阵 A 相乘；
4. 将矩阵 A 自乘，指数右移一位（除以 2）；
5. 直到指数 k 变为 0，此时 RET 就是Ak。

5.2 题目描述

题目链接：https://www.luogu.com.cn/problem/P3390

洛谷 P3390 【模板】矩阵快速幂：给定 n×n 的矩阵 A，求Ak，结果矩阵的每个元素对109+7取模。

• 输入：第一行是 n 和 k，随后 n 行是矩阵 A 的 n×n 个元素；
• 输出：输出Ak的 n×n 矩阵，每行 n 个元素，空格分隔；
• 数据范围：n≤100，k≤10^18。

5.3 解题思路

1. 数据结构：用结构体封装矩阵，方便矩阵的存储和乘法运算，结构体中包含一个二维数组存储矩阵元素；
2. 运算符重载：重载乘法运算符*，实现两个矩阵的相乘，同时完成取模操作，简化代码；
3. 快速幂函数：实现矩阵快速幂的核心逻辑，初始化结果矩阵为单位矩阵，按二进制分解指数 k；
4. 取模操作：由于 k 极大，矩阵元素会溢出，因此每一步乘法都要对109+7取模，使用 long long 类型存储矩阵元素，避免整数溢出。

5.4 C++ 代码实现

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 110;
const int MOD = 1e9 + 7; // 取模模数

LL n, k; // n:矩阵阶数, k:指数

// 矩阵结构体
struct Matrix {
    LL m[N][N];
    // 构造函数，初始化矩阵为全0
    Matrix() {
        memset(m, 0, sizeof(m));
    }
    // 重载乘法运算符，实现矩阵乘法
    Matrix operator*(const Matrix& B) const {
        Matrix C; // 结果矩阵
        for (int i = 1; i <= n; i++) { // 遍历A的行
            for (int j = 1; j <= n; j++) { // 遍历B的列
                for (int t = 1; t <= n; t++) { // 遍历公共维度
                    C.m[i][j] = (C.m[i][j] + m[i][t] * B.m[t][j]) % MOD;
                }
            }
        }
        return C;
    }
}A, ret; // A:原始矩阵, ret:结果矩阵(初始为单位矩阵)

// 矩阵快速幂函数
void qpow(LL b) {
    // 初始化结果矩阵为单位矩阵
    for (int i = 1; i <= n; i++) {
        ret.m[i][i] = 1;
    }
    while (b) {
        if (b & 1) { // 若当前二进制位为1，结果矩阵乘当前A
            ret = ret * A;
        }
        A = A * A; // 矩阵自乘
        b >>= 1; // 指数右移一位，等价于除以2
    }
}

int main() {
    cin >> n >> k;
    // 输入原始矩阵A
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> A.m[i][j];
        }
    }
    // 执行矩阵快速幂
    qpow(k);
    // 输出结果矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << ret.m[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

5.5 代码关键说明

1. 结构体与运算符重载：将矩阵封装为结构体，重载*运算符后，矩阵相乘可以直接写为A*B，和整数乘法一样直观，大幅简化代码，避免重复写矩阵乘法的三层循环；
2. long long 类型：由于矩阵元素会不断相乘，即使取模，中间结果也会超过 int 的范围（int 最大约 2×10^9），因此必须用 long long 存储矩阵元素，防止溢出；
3. 单位矩阵初始化：快速幂的结果矩阵初始值必须是单位矩阵，这是矩阵快速幂的关键，若初始化为全 0 矩阵，最终结果会始终为 0，完全错误；
4. 二进制分解：用b & 1判断当前二进制位是否为 1，b >>= 1实现指数降次，这是快速幂的标准操作，时间复杂度为O(logk)，即使 k=10^18，也只需循环 60 次左右，效率极高。

六、矩阵乘法的进阶应用：矩阵加速求解数列

矩阵快速幂的核心应用是矩阵加速，用于求解线性递推数列的第 n 项，比如斐波那契数列、递推式为ax​=ax−1​+ax−3​的数列等。对于递推数列，当 n 极大时（比如 n≤10^18），动态规划的 O (n) 算法会超时，而矩阵加速结合快速幂可以将时间复杂度优化到 O (logn)，这是算法竞赛中的经典优化手段。

6.1 矩阵加速的核心思想

矩阵加速的关键是构造递推矩阵（也叫转移矩阵），将数列的线性递推关系转化为矩阵的幂次运算，即：转移矩阵其中 k 是递推式的初始项数，比如斐波那契数列的递推式是Fn​=Fn−1​+Fn−2​，初始项是 F1=1、F2=1，k=2。

简单来说，矩阵加速的步骤为：

1. 根据数列的递推式，构造合适的转移矩阵；
2. 将数列的第 n 项转化为转移矩阵的幂次乘以初始项的矩阵；
3. 用矩阵快速幂计算转移矩阵的幂次，再与初始项矩阵相乘，得到第 n 项。

6.2 实战：矩阵加速求解斐波那契数列（洛谷 P1962）

题目链接：https://www.luogu.com.cn/problem/P1962

斐波那契数列是最经典的线性递推数列，递推式为：F1​=1,F2​=1,Fn​=Fn−1​+Fn−2​(n≥3)我们用矩阵加速结合快速幂，求解

。

6.2.1 构造转移矩阵

首先，将斐波那契的递推式转化为矩阵形式：

验证：右边矩阵相乘的结果为

，与左边一致。

由此可以推导出通式：

转移矩阵就是

，初始项矩阵是

。

6.2.2 C++ 代码实现

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 3;
const int MOD = 1e9 + 7;

LL n;
// 矩阵结构体
struct Matrix {
    LL m[N][N];
    Matrix() {
        memset(m, 0, sizeof(m));
    }
    // 重载乘法运算符
    Matrix operator*(const Matrix& B) const {
        Matrix C;
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= 2; j++) {
                for (int t = 1; t <= 2; t++) {
                    C.m[i][j] = (C.m[i][j] + m[i][t] * B.m[t][j]) % MOD;
                }
            }
        }
        return C;
    }
}A, ret;

// 矩阵快速幂
void qpow(LL b) {
    // 初始化结果矩阵的初始值（对应初始项[F2,F1]）
    ret.m[1][1] = 1;
    ret.m[1][2] = 1;
    // 构造转移矩阵
    A.m[1][1] = 1; A.m[1][2] = 1;
    A.m[2][1] = 1; A.m[2][2] = 0;
    while (b) {
        if (b & 1) {
            ret = ret * A;
        }
        A = A * A;
        b >>= 1;
    }
}

int main() {
    cin >> n;
    // 初始项直接输出
    if (n == 1 || n == 2) {
        cout << 1 << endl;
        return 0;
    }
    // 计算转移矩阵的n-2次幂
    qpow(n - 2);
    // 结果为ret.m[1][1]
    cout << ret.m[1][1] << endl;
    return 0;
}

总结

矩阵乘法看似抽象，但只要掌握了核心规则和模板，再结合真题反复练习，就能彻底吃透。作为算法学习的重要基础，矩阵乘法的掌握程度直接影响后续复杂算法的学习，希望本文能帮助大家从入门到实战，彻底搞懂矩阵乘法！