线性代数 简明教程

前言

本文是 所著《线性代数》（原书第十版）的简要总结与算法竞赛方面的扩充，适合线性代数入门者学习并把握线性代数的基本概念和内容。

需要注意的是：本教程中的矩阵表示方法可能与你在课上或是其他教程中看到的有些许出入。为了兼具美观和统一，单行行向量用圆括号包围，变量顶部用向量符号标记，如行向量：，其余情况均以方括号包围；向量/一般变量用单一小写字母或符号表示，矩阵则用大写字母表示，如 矩阵 。

第一章 矩阵与方程组

相信大多数人入门线性代数的第一堂课就是学习如何利用矩阵求解线性方程组的吧。矩阵作为一个仅由数字和括号组成的表示方法，既避免了书写各种未知数符号的麻烦，也能一眼看出各未知量之间的数量关系，实属上乘的表示方法。矩阵的一些特殊性质也可以帮助我们解决一些难以解决的问题。

第一节 方程组与矩阵的互相转化

假设我们有一个方程组：。首先将所有未知数提到等号左侧，常数全部移到右侧。我们暂时先忽略掉等号右边的常数项。我们将每行未知数的系数提取出来，放入矩阵的第一行，矩阵的第一行就表示方程组中第一个方程的未知数系数（没有默认为 0），以此类推到下边几行，最终你会得到一个列数与未知数个数相等、行数与方程个数相等的矩阵。本例中它长成这个样子：

如此得到的矩阵叫做系数矩阵，顾名思义，它只表示了原方程组的系数，而忽略了常数项。

它同时也是一个 矩阵。

一般地，对于一个 矩阵（），它有 行 列。

此时，如果我们加上等号右侧的常数项，原先的 矩阵会变成 的。

人们为了区分常数和系数，选择在书写时将常数加入到最右侧那一列，并且在最右一列的前面加上竖线分隔系数，如此得到的矩阵叫做增广矩阵。

本例中 的增广矩阵形式 写作：

当矩阵元素不明时，我们为了简便表示矩阵本身，采用字母 + 下标 + 括号的方式。例如一个 矩阵 ，可以写作：。

第二节 矩阵的基本运算

一. 矩阵加法

构造相同的矩阵，即两个矩阵行列数相同，称这样的两个矩阵是同型的。

矩阵加法仅限两个同型矩阵，相加时同一行同一列的元素相加即可（增广矩阵同理）。

例如：

矩阵加法满足：结合律、交换律

二. 矩阵减法

矩阵减法是矩阵加法的逆运算，因此对于两个矩阵的形式要求同上，只是相同位置的元素相减而已。

矩阵减法满足：结合律、交换律

三. 标量乘法/矩阵数乘

矩阵的数乘也很简单，让矩阵中每个元素乘以这个数就可以了。

例如：

矩阵数乘满足：交换律、结合律、分配律

四. 矩阵转置

将原矩阵的行变成新矩阵的列，称为矩阵的转置。

直观理解就是顺时针旋转 90 度后再水平镜像过去。转置用上标 表示。

例如：，则

矩阵的主对角线（左上 - 右下）元素转置前后不变，且具有可逆性 []、数乘不变 []、分配律 []。

转置后恰好就是它自身的矩阵称为对称矩阵。它是自转置的，即 。对称矩阵的元素恰好关于主对角线对称，且是一个 的方阵。

五. 矩阵乘法

该内容将在第二章涉及。

第三节 消元

按照一般思路（就是我们在小学学的方法），我们会选择通过方程互相加减各自的倍数，达到消去未知数的目的。这种方法在矩阵上同样适用，而且它有一个贼高坤的名称：高斯消元法（Gaussian Elimination）。

回忆一下我们从出生就会用的消元原理，我们的目标就是让每个未知数都对应一个常数项，那么它的值就可以直接用常数除以系数的方式求出。矩阵中也是如此，为了能够化简出可直接求解的矩阵，我们在此引入初等行变换的概念：

1. 交换某两行
2. 把矩阵的某一行同乘以一个非零的数
3. 把某行的若干倍加和到另一行

这三条很容易理解。第一条：相当于交换方程组顺序，不影响计算；第二条：相当于对某一行方程放缩某倍，它等价于原方程；第三条：相当于前两条的融合，也是消元的关键一招。这三条规则在之后的初等矩阵内容中会再次出现。

首先从一个例子讲起，让读者感受一下初等行变换的魅力：

考虑这个方程组：

按照如上所述，将它转写成增广矩阵的形式：

我们总结一下常用的消元原理，应用到矩阵上就是：

1. 枚举每一列 ，选出无序组中第 列系数绝对值最大的一行 ，并移到无序组的最上边。（变换规则一）
2. 行通过自乘，将第 列的系数变成 ，并标记 为有序。（变换规则二）
3. 通过加减有序组中某一行的非零倍，将之后所有行的第 列系数化为 。（变换规则三）

令矩阵 （有序组用绿色表示）

枚举第一列，。开始时，所有行均无序。选出绝对值最大的那一项，本例中为第二行，进行移动，原矩阵变为：

第二步，自乘并标记有序，因此第一行除以 ，原矩阵就变成了：

第三步，将无序组的第 列消成 。本例中，我们让第二行减去二倍第一行；第三行直接减去第一行，得到：

枚举第二列，此时 。第一步，选出第二列系数绝对值最大的那一行，移到无序组最上端。本例中无需移动，自乘 ，标记有序，原矩阵为：

最终的最终，第三行减 倍第二行，得到我们心心念念的化简后的矩阵：

为什么把矩阵化简成这种金字塔型的形式呢？你会发现：最后一行仅有一个带系数的未知数 ，我们直接求，。向上一行，现在 相当于常数，移到常数中与 合并， 也可直接求了……经过如上的反代操作，三个未知数都会被求出来。至此我们才发现这个三角形矩阵的魅力之处。

一般地，对于一个矩阵，如果它的非零系数呈阶梯形分布，则称这类矩阵为行阶梯形矩阵。将非零系数挑出来，它们组成的是一个上三角形矩阵；对应地，零项就会组成下三角矩阵。上三角矩阵通常以 表示、下三角矩阵通常用 表示。

原方程组有唯一解：

在这里，我没有给出代码实现。因为对于一些特殊情况，化简出的矩阵不能很好地被计算机处理，更适合算法竞赛体质的高斯消元模板将在本章第五节给出。

第四节 秩

类比一元二次方程的实数根存在性判别法 —— 判别式法，即对于一元二次方程 ，实数根的个数 。那么，矩阵方程是否也有类似的根存在性判别方法呢？

答案是有的，而且不止一种，这意味着“矩阵是否有解” 这样的问题会有多种解决方案。现在介绍的是最为简单常用的一种——秩。

在线性代数中，一个矩阵 A 的列秩是 A 的线性独立的纵列的极大数目。类似地，行秩是 A 的线性无关的横行的极大数目。即如果把矩阵看成一个个行向量或者列向量，秩就是这些行向量或者列向量的秩，也就是极大无关组中所含向量的个数。

……咱们抛掉这种看也看不懂的高级语文句法，听我给你总结：

通俗来讲，把一个矩阵化成最简形式（特指行阶梯形）后，非零行的个数就是矩阵的秩。这其实是秩的最大线性无关组的定义。再次白话总结：如果存在三个行向量（列向量一样的，保证所有向量都是行 / 列向量即可）：。根据高中数学中立体几何的知识 —— 和 显然是共线的，这两个向量就是线性相关的。如果对于一组 维向量，可以成为 维空间的一组基底向量，那么它们就是线性无关的。

矩阵 的秩用 表示，或者用 、、 等表示。

现在明白了吧，如果一个矩阵的某两行线性相关，它们都会被初等行变换第三条狠狠薄纱 —— 在乘或除以一个非零数后相减，其中一行就会被全部消成 0，从方程组角度来看就是 ，带什么值都成立（相当于去重了一个方程）。

当然上边这一段也有表述不准确之处，假设有一个增广矩阵 。初等行变换第三条秒了第一、第二行，然而事情有些不对劲了……

第二行不乐意了，它还存留这最后一点倔强，好像在说：“你总结的不对呢真是雑鱼”。但是明眼人都看得出来， 这种事情是绝对不可能发生的，也就是无解。按照刚刚说的，这个增广矩阵的秩 ，可是它对应的系数矩阵 的秩 ，就有 且 ，于是我们就找到了矩阵无解的一个条件了。也就是 。

再考虑有无穷解的情况：无非就是出现了 的情况，此时 可以代任何值。与无解不同，这次的最简行阶梯形矩阵，无论是系数矩阵还是增广矩阵形式，它们的秩都是相同的，并且都浪费了至少一行方程式。我们知道：一个三元一次方程组是无法用相异的（行向量形式表示下不共线）两个方程解出唯一值的，相反，解形如： 表明 由 确定、而 又由 确定，然而这俩都不确定，导致这两个数可以取无穷多的值，也就导致矩阵有无穷组解。综上：矩阵有无穷组解的充要条件是 （ 为未知数个数）。

最后就是有唯一解：如果一切进行顺利的话，既没有全零行，也没有无解行。那么此时系数矩阵和增广矩阵的秩会相同，且等于未知数个数，即 。

总结，假设一个由 个未知数组成的最简行阶梯形矩阵 、以及它的增广矩阵 。矩阵解的个数由如下规则导出：

例 1.4.1 Delivery Mathematics 快递员的数学题

「稻妻狛荷屋的人气跨国快递员绮良良在送货途中遇到了一个难题，你作为无所不知无所不晓的旅行者自然是乐意地接下了她的委托。当你来到委托地点时，你发现这是一道解谜题目……」

稻妻号称最难的方块解谜是一组由 个正方体可旋转方块组成的阵列，击打其中的某个方块会使得与之相关联的其他方块共同旋转一个特定角度。在这个谜题中，每个方块每次仅能水平顺时针旋转 90 度，传动方式在下图给出。问若要使所有方块同时朝向北方，需要如何击打方块？给出任意可行解，但需要保证每个方块旋转的次数不超过 4（不击打也可以，相当于次数为 0）。

由于钟离先生远在海那一头的璃月喝茶听评书、宵宫也正忙着制作夏日祭的烟花而无法抽身、香菱在万民堂做饭、安柏在侦察蒙德郊区、芙宁娜忙着吃蛋糕…… 总之没有其他人召唤物能帮你解决这个问题，你只能凭借自己的力量解开这个谜题。

问题分析：首先我们要搞清楚传动规则，我们会发现当你击打了一个方块，包括它在内、再按顺时针方向数两个方块都在旋转相同的角度。这也是这道题被称作难题的原因之一，只用想象力是很难想象的出来的…… 于是为了用代数方法解决该问题，我们选择用四个未知数、四个方程表示每个方块操作后的状态，问题解决的标志既为四个方块的状态均为 （ 表示北方）。

算法设计：考虑到单个方块每旋转四次就相当于一次循环，因此我们重定义方向标，从北开始，顺时针方向将方位标记为 。这么做可以避免一些复杂的取模运算。接着我们根据传动规则表示每个方块的状态，令方块 1-4 被击打次数分别为 。以方块 1 为例：击打自己、3 号和 4 号都会导致 1 号顺时针旋转 90°，再算上 1 号初始朝向为 ，得到：。其他方块以此类推，解析出的方程组对其求解即可。这样的矩阵一定有唯一解，每个未知数都以 表示，将一个自然数代入 值即可解出答案。

解：设方块 1-4 的击打次数分别为 ，设朝向从北方按顺时针方向分别为 。

根据传动规则，有如下线性方程组：

增广矩阵形式为：

（化简过程略），行阶梯形式为：

因为系数矩阵的秩与增广矩阵的秩相同且都等于未知数个数 ，因此矩阵有唯一解 。易知 的合法值满足 的数学关系，此处求最小值，令 ，得到 。

因此，最佳方案是暴击击打 2 号和 3 号方块各两次。

后日谈：有些读者可能会问，这个难道不是有无穷解吗？为什么上边说这个矩阵只有唯一解？其实这个矩阵确实只有唯一解，因为 ，造成它有无数组解的原因是 这个自然数。我们在开头只为这个矩阵设定了四个未知数 ，因此矩阵只有四个元，因而有唯一解。事实上，这个问题也可以转化成同余高斯消元，在普通高斯消元的基础上变除法为乘逆元即可。

对于有 （质数）个有效旋转面的方块，详见洛谷 P10315，顺便推一下 我的题解。

第五节 计算机高斯消元

一. 实数高斯消元

基本思路与手推时相同：

1. 找到当前列元素绝对值最大的那一行，并移动到无序组的上端。
2. 将这一行的第一个元素除成 。

此时需要进行一个神秘步骤：让除开当前行和第 列为零之外的所有行都用当前行消元一次。

如果有唯一解，我们会得到一个主对角线全为 的增广矩阵，此时每个未知数的结果就是右侧的常数。如果无解，还是像手推那样判断。如果存在无数组解，输出解的方法如下：

1. 枚举每一行，找到当前行第一个非零元素，并记录它的结果为右侧常数。该行的其余元素作为自由元，不作操作（或赋值为任意值）
2. 重复操作直到遍历到全零行。

我们会发现上三角矩阵中同一列可能有多个非零系数，这意味着上层方程组的结果依赖于下层的求解，如果出现自由元将会十分棘手。用上述方法将矩阵进一步化为对角矩阵后，就不会存在这种依赖关系了，因而判断和输出变得简单了许多。

核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

int gauss() {
    int rank = 0; // 秩
    for (int c = 1, r = 1; c <= n; c++) {
        int t = r;
        for (int i = r; i <= n; i++) {
            if (abs(matrix[i][c]) > abs(matrix[t][c])) t = i; // 找出主元绝对值最大的那一行
        }
        if (abs(matrix[t][c]) < EPS) continue; // 非零才能消成1
        if (t != r) swap(matrix[t], matrix[r]); // 交换
        for (int i = n + 1; i >= c; i--) matrix[r][i] /= matrix[r][c]; // 主元消成1
        for (int i = 1; i <= n; i++) { // 反复消元，成为对角线矩阵
            if (abs(matrix[i][c]) > EPS && i ^ r) { // 当前行不消，若当前位已经是零了也不消
                for (int j = n + 1; j >= c; j--) {
                    matrix[i][j] -= matrix[i][c] * matrix[r][j]; // 消成零
                }
            }
        }
        r++;
        rank++;
    }
    if (rank < n) {
        // 无解or无数组解
        for (int i = rank + 1; i <= n; i++) {
            for (int j = 1; j <= n + 1; j++) {
                if (abs(matrix[i][j]) > EPS) return NO_SOLUTION; // 无解
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (abs(matrix[i][j]) > EPS) {
                    ans[j] = matrix[i][n + 1]; // 无数组解，找到主元并直接赋值，剩余的自由元自动赋值为0
                    break;
                }
            }
        }
        return INFINITE_SOLUTIONS;
    }
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1]; // 有唯一解，此时常数项即为答案
    return UNIQUE_SOLUTION;
}

复杂度 。

二. 同余高斯消元

上一节的例题就是同余高斯消元的一个典例，我们需要求解模 意义下 元非齐次线性方程组的特解（即每个未知数的解均在 之内）。本质上和上面的高斯消元是一样的，不同的一点是我们需要把除法换成逆元，而且需要对减法取模格外小心；对于 不为质数的情况，还需要额外考虑是否存在逆元。代码与上面雷同，不放了。

复杂度 。

三. 异或高斯消元

适用于方程组和奇偶性相关联的时候，此时列出的方程组是异或和起来的。鉴于方程组的系数只有 ，我们的判断和消元也会简单许多，只需判断当前元素是否为 。实践时一般使用 bitset 来优化时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

int gauss() {
    int rank = 0; // 矩阵的秩
    for (int c = 1, r = 1; c <= n; c++) {
        int t = r;
        for (int i = r; i <= n; i++) {
            if (matrix[i].test(c)) {
                // 找到绝对值最大的行（只要第一个系数是 1 即可）
                t = i;
                break;
            }
        }
        if (!matrix[t].test(c)) continue; // 跳过零行
        if (t ^ r) swap(matrix[r], matrix[t]); // 交换到第一行

        for (int i = 1; i <= n; i++) {
            // 与普通高斯消元的不同之处，对 1~n 行全部消元
            if (matrix[i].test(c) && i ^ r) {
                // 当前行不消，零行不消
                matrix[i] ^= matrix[r]; // 异或代替减法进行消元
            }
        }
        r++;
        rank++;
    }
    if (rank < n) {
        // 秩小于 n，可能是无数组解、有可能无解
        for (int i = rank + 1; i <= n; i++) {
            if (matrix[i].test(n + 1)) return NO_SOLUTION; // 存在类似于 0=k 的矛盾情况，无解
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n + 1; j++) {
                if (matrix[i].test(j)) {
                    // 无数组解，找到主元并赋值
                    ans[j] = matrix[i][n + 1];
                    break;
                }
            }
        }
        return INFINITE_SOLUTIONS;
    }
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1]; // 有唯一解，对角矩阵每个未知数的解就是常数项的值
    return UNIQUE_SOLUTION;
}

复杂度 。

洛谷习题：

1. P3389 [模板] 高斯消元法
2. P2455 [SDOI2006] 线性方程组
3. P4035 [JSOI2008] 球形空间产生器
4. P10315 [SHUPC2024] 原神，启动！
5. P6126 [JSOI2012] 始祖鸟
6. P2447 [SDOI2010] 外星千足虫

第二章 矩阵乘法

第一节 什么是矩阵乘法

你经常能在各种线性代数的书上看到这样一串定义式：。这对于自学者（比如说我自己）其实是非常不友好的。他们在举例计算时很容易被 绕进去，不仅计算速度慢不说，还很容易出错…… 那我在此举出一个简记方法：

将左边的矩阵的每一行看作每个未知数都代了确定值的方程、右边的矩阵每一列看作是前者方程的未知数系数。二者相乘本质上就是让未知数和系数匹配上，并计算出结果放入结果矩阵的特定位置。这个特定位置也有讲究，假如选择了前一个矩阵的 行和后一个矩阵的 列进行运算，求和过后的答案应该放在答案矩阵的 位置。看以下例子来加深理解：

那么什么样的矩阵才能进行乘法运算呢？答案是一个 和一个 的矩阵。观察规律，我们发现前矩阵的列数需要等于后矩阵的行数。根据如上概括的矩阵乘法的意义——即搭配未知数与系数。显然，当后一个矩阵的列数大于前一个矩阵的行数时，我们进行系数配对时就会发现多出几个失配的系数。矩阵乘法国不养闲人，这种单身汉显然是不可以光天化日下大摇大摆出来遛弯的。因此保证其中一个矩阵的行数等于另一个矩阵的列数后方可相乘。

类比四则运算的乘法，矩阵乘法是否也有结合律、分配律和交换律呢？很遗憾，不完全是，前二者是矩阵乘法运算所具备的性质、但最后那个交换律不是。不是所有的矩阵相乘都满足乘法交换律。但是还是有满足交换律的特例：同型零矩阵相乘、一个矩阵（可逆）和它的逆矩阵相乘，矩阵乘法满足交换律的充要条件证明过于复杂烧脑，此处不做陈述主要是我也不会证满足交换律的充要条件 qwq……。

证明：一般矩阵不满足乘法交换律

假设一般矩阵 ，一般矩阵 ，则 可以进行，因为 的行数和 的行数均为 。得到的乘积 是一个 矩阵；反过来， 无法进行，因为 的列数不等于 的行数，即 。

假设 。 和 均可进行，假设乘积为 。当 时，根据矩阵乘法的计算式，得到 ；当 时，根据计算公式得 。一般情况下，。得证。

矩阵和数字一样，也有幂次方的计算。特殊地，任意 非零矩阵的零次幂都是一个 的单位矩阵。主对角线的值全是 1，其余元素均为 0 的矩阵叫做单位矩阵，用字母 表示；零矩阵的任何非零正整数次幂都是一个零矩阵，零矩阵的元素全部是 0，用字母 表示。一个 的单位矩阵是这样的：。在算法设计中，经常用类似于大数快速幂（位运算版本）的方式快速计算矩阵的幂次方。

例 2.1.1 Akasha Browser with Irminsul Kernel 世界树搜索引擎

你作为刚刚清除了须弥世界树痼疾的英雄旅行者，突然对虚空终端的运作方式有了兴趣。你从大贤者那里了解逼问到，虚空终端实质上是一个仅显示搜索结果的前端程序，但关键词搜索功能却是基于须弥地下空间的世界树。带着这个疑问，你再次来到了世界树前，见到了小吉祥草王大人，希望能让她告诉你世界树的运作方式……

背景知识： 很多浏览器的检索功能都依赖于矩阵运算，这里属于最简单的一种——我们只需要矩阵的乘法运算（某些情况下会用到转置，甚至正交性）。然而随着科技的快步发展，数据量的快速增加，这种方式如今只在很小的范围内被使用（由于码量小思维简单，它有时会在个人博客的关键词搜索功能中被用到）；目前广泛使用的一种是向量相似性搜索，它本质上是在一定范围内搜索与目标向量辐角最为接近的已有向量，在“矩阵的几何表示” 章节中会涉及到。这里介绍的是简单匹配搜索。

问题分析：因为矩阵乘法本质上是未知数和系数的配对求值，我们需要构造一个方法来使得“搜索内容” 和“已有内容” 配对。并且搜索引擎总会返回与你搜索的内容最为相似的结果，搜索“比尔・盖茨”，第一条肯定是关于他个人的介绍，而绝对不可能是一则寻狗启示……因此，我们设计的矩阵必须能在经历一轮运算后能够正确返回每个关键词出现的频率（简单点说就是出现次数），这样虚空终端才能对频率进行排序，并返回频率最大的那个结果。

算法设计：不妨考虑这样几个矩阵 —— 其中一个存储关键词、另一个存储搜索内容。比如我需要将几篇论文（为方便使用英文表示，并且假设词根相同的单词为同一个单词，即不考虑词汇变形）《Basic Structure of Elemental Monuments》（元素方碑的底层构造）、《Junior Elemental Reaction》（初等元素反应）、《Advanced Elemental Theory》（高等元素论）、《Architectural Structure in the Mausoleum of King Deshret》（赤王陵的建筑结构）以及《Advanced Sumeru Linguistic Analysis》（高等须弥语音学解析）。我们在此次挑选一些关键词存储（方便读者观察）：Structure、Element、Junior 和 Advanced。为每篇论文编号 1-5，矩阵如下图：

假如热爱学习的艾尔海森来到了教令院的大图书馆，它想测试一下这全新开发的文献查询系统，输入了 Advanced 一词。假设已录入数据库就是以上形式，我们如何构造一个“查询矩阵” 来和数据库矩阵进行运算呢？

首先根据矩阵乘法的前提要求，这个查询矩阵必须是四行。不妨让每行代表我们的词库词语，艾尔海森输入的是 Advanced—— 即对应数据库矩阵的第四列（未知数），我们要配对它的系数，因此它必须在第四行，才能保证系数正确匹配未知数。同理，查询矩阵的第一行对应 Structure、第二行 Element、第三行 Junior。他输入了一个 Advanced，因此我们的查询矩阵如下图：

乘法的目的是将二者匹配起来，得到的结果如下图：

返回矩阵的数字代表关键词在对应数据库项中的出现次数，也就是说，如果此时再加入一篇论文《Advanced Usage of the Word Advanced》（“Advanced” 一词的进阶用法），返回矩阵的最后一行（第六行）会出现一个 。经过虚空终端的一轮排序，它自然就会来到第一位的位置。如果要分别查询两个不同关键词，在查询矩阵右侧再加一列即可，返回矩阵中多出的一列就是新关键词的出现次数；如果需要同时查询两个关键词，在同一列对应位置写入 即可……

例 2.1.2 Light Novel Query 轻小说查询

八重堂的主编八重神子最近在为轻小说的事情发愁…… 并不是因为销量不够，正相反：八重堂最近推出了一项跨国销售项目，各种经典作品被远销往了枫丹廷。这就牵涉出一个问题 —— 枫丹的市民们不想远离枫丹城区、横穿须弥沙漠、翻越璃月高山、躲避稻妻雷暴就为了看一看有哪些轻小说符合自己的独特口味…… 于是八重神子找到了见多识广的你，希望你能帮她做出一套轻小说内容检索系统。当然作为报酬给你的原石和摩拉是肯定是不会少的……

当然，这套系统有一定要求。因为有很多轻小说为了吸引读者，取的标题和内容是完全对不上号的，神子的想法是做一套正文内容检索 —— 每本轻小说的总字数在出版时就统计好了，但是苦于稻妻的信息存储技术不是很发达，神子希望存储在数据库矩阵里的数据尽可能小。请问该如何设计符合要求的存储算法？

问题分析：每本书中特定的词可能重复出现成百上千次（同样用英文单词表示，且同词根不同词形的两个词算作同一个单词参与计数），我们的要求是让数据尽可能小，既然总字数都已经给出了，我们不妨使用指定词出现的频率来表示这个词的出现次数（单词出现次数 = 全书总词数 × 出现频率）。这样的搜索方法叫做相对频率搜索。

算法设计：大致原理和例 2.1.1 里的一模一样，只是数据库矩阵存储的不再是出现总次数，而是对应词的相对频率。因而图例 2.1.3 可以变化为如下形式：

明显一看，第三篇文章出现 Advanced 的频率最高，应该优先返回。但是这个例子并不是很好（明明说了按内容搜索你还在这搜索标题），但是当加入大量的正文内容时，这个方法的优势也就体现出来了。这里由于篇幅原因就不举过于复杂的例子，本例仅作对相对频率搜索的原理的理解。

第二节 初等矩阵与矩阵递推

假设存在一个 的单位矩阵 ，对 只进行一次初等行变换得到的矩阵叫做初等矩阵，通常用 表示。一个矩阵的行变换和列变换都可以用初等矩阵的乘法进行。

仅交换了两行的单位矩阵称作第 I 类初等矩阵（只进行了初等行变换第一条），将它左乘到一个矩阵前，可以进行相应的行运算；右乘到一个矩阵后可以进行相应的列运算。比如，一个第 I 类初等矩阵 （交换第一、二行），和一个 矩阵 。左乘就是 （交换一、二行）；右乘就是 （交换一、二列）。

仅将某一行乘以一个非零倍数的矩阵叫做第 II 类初等矩阵（只进行了初等行变换第二条），左乘行运算、右乘列运算。例如一个第 II 类初等矩阵 （第一行乘 3）和一个 矩阵 。（第一行乘 3）；（第一列乘 3）。

仅将某一行的非零倍加到另一行上的矩阵叫做第 III 类初等矩阵（只进行了初等行变换第三条），同样是左乘行运算、右乘列运算，但是有一点点小不同，不要根据思维定势随便写答案！例如一个第 III 类初等矩阵 （第二行乘 2 加到第一行）和祖传的矩阵 。（第二行的 2 倍加到第一行）；（第一列的 2 倍加到第二列）。注意初等矩阵的行列变换与乘法后矩阵的行列变换，哪一行/列乘了倍数、哪一行/列被加上了！

因此我们可以不必使用高斯消元，仅使用初等矩阵乘法也可以达到将普通矩阵消元变成最简行阶梯形矩阵！而且它可以进行列运算，甚至比高斯消元法更高级一点。

接下来是我们的矩阵递推。大家都知道斐波那契数列，它的前两项均为 1，此后的每一项都是前两项之和，即 。大多数信息竞赛生在学习到递归算法时都会被要求写程序求解斐波那契数列的某一项，当然代码也非常的简单，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <bits/stdc++.h>
using namespace std;

long long fib(int n)
{
    if (n == 1 || n == 2)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

int main()
{
    int n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

这段代码其实就是照搬了上面的通项公式，但是递归有个弊端就是效率和内存，当 为百万级别、甚至十亿级别时它就显得很小丑了。那么我们如何用矩阵加速计算呢？我们用斐波那契数列的递推来向读者介绍矩阵递推的操作方法：

首先我们将通项公式变成我们想要求的形式，为了便于输出，要求结果矩阵的第一个元素就是答案，因此结果矩阵就是：。又因为 ，并且 。我们还需要保证初始矩阵在经历一轮变换前后，始终都是同型的，这里是 的矩阵，操作后也应该是 的矩阵。于是我们的递推矩阵应该是一个 矩阵。不妨将递推矩阵 的每一行从上至下分别表示为 和 的系数，由以上二式可得：。别急，左边还有一列未填满 —— 我们希望每次操作都会把矩阵元素整体向左移一个位置，就好像一个滑动窗口（但不是单调队列），我们的第一列也可以求出来了。最终就是

那么求数列第 项 —— 每次右乘 都相当于多求出一项，并且当 只被乘了一次时，结果矩阵的第一个元素是 。因此要让第 项来到第一个位置，我们需要进行 次乘法， 也就是 的第一行第一列元素。可以写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <bits/stdc++.h>
#define MOD 1000000007
#define N 15
using namespace std;

typedef long long ll;

int n = 2; // 递推矩阵行列数均为2

struct Matrix {
    ll mat[N][N];

    Matrix()
    {
        memset(mat, 0.0, sizeof mat); // 初始化时内部变量自动置零，无需每次定义变量时再置零
    }

    void I()
    {
        for (int i = 1; i <= n; i++)
            mat[i][i] = 1; // 构造2×2单位矩阵
    }
};

Matrix operator*(const Matrix& l, const Matrix& r)
{
    // 重载乘法运算符，实现矩阵乘法
    Matrix res;
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // res.mat[i][j] = (res.mat[i][j] + l.mat[i][k] * r.mat[k][j] % MOD) % MOD; // 取模用这个
                res.mat[i][j] += l.mat[i][k] * r.mat[k][j];
            }
        }
    }
    return res;
}

Matrix qpow(Matrix a, ll b)
{
    Matrix res;
    res.I(); // 单位矩阵相当于实数运算中的 1，因此任何矩阵乘以一个单位矩阵的结果都是这个矩阵
    while (b) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int main()
{
    int a;
    cin >> a;

    Matrix A;
    A.mat[1][1] = A.mat[1][2] = 1; // 初始矩阵
    Matrix M;
    M.mat[1][2] = M.mat[2][2] = M.mat[2][1] = 1; // 递推矩阵
    A = A * qpow(M, a - 1);
    cout << A.mat[1][1] << endl;
    return 0;
}

它的时间复杂度可以做到 ， 是 的长/宽，这里是 ； 是幂。因此这里的时间复杂度是矩阵快速幂的 ，比朴素斐波那契递推的 强了不少！

例 2.2.1 Lost Control! Blubberbeast's Reproduction 膨膨兽泛滥危机

由于枫丹水质的大幅改善，膨膨兽的天敌数量锐减，枫丹城区近海的膨膨兽也得到了更多的食物，进而开始大量地繁殖。水质改善的第一年，已登记的膨膨兽数量是 头，恰好是斐波那契数列的第 项。第二年，膨膨兽数量没有变化，之后的每一年，膨膨兽数量都是前两年之和的 ，已知膨膨兽的平均寿命是 15 年、枫丹廷近海能承载的最大膨膨兽数量是 万只。那么请问 年后近海的膨膨兽数量是多少？这 年内枫丹廷是否需要向近海投放膨膨兽的天敌以遏制后者疯狂繁殖？（结果出现出现小数则向上取整）

问题分析：这是一道标准的矩阵快速幂递推问题，它基于斐波那契数列递推、却比它更高级。首先，它的初始值不再是 而是 ，其次，从第三项起，每一项都是前两项和的一个倍数，这里是 。那我们怎么构造递推矩阵 来解决问题呢？

算法设计： 已知初始矩阵 。根据题目描述很容易写出通项公式：。我们要保证初始矩阵经过一次递推后，得到的新矩阵与初始矩阵同型，因此根据矩阵乘法定义，我们的递推矩阵必须是一个 矩阵。于是拿出祖传单位矩阵模板 开始构造递推矩阵！

对于前项和的问题，前面已经给出了，因而我们的递推矩阵变成了 ；接下来解决倍数问题 —— 根据通项公式， 和 的系数都是 ，我们构造递推矩阵时也要考虑到这一点，当 时，递推公式展开如下：。如果第一行代表 的系数、第二行代表 的系数 ，第二列显然应该同时乘以 0.85，左边一列的作用是使原矩阵整体向左移一个位置。最后我们的递推矩阵就是 。直接将初始矩阵右端乘以递推矩阵的幂次方就可以了。注意因为初始矩阵的右侧是第二年的膨膨兽个数，乘以递推矩阵本身，会让第二年的膨膨兽个数移到结果矩阵的前端，要想让第一项变成第 年的个数，递推矩阵的幂必须是 ，即 。

代码实现上，仅需将 矩阵和 矩阵的初始值改变就可以了。

最终结果：875076。结果小于 90 万，因此不需要投放天敌。

后日谈：那如果将系数改变为 呢？输出的结果将是 977427，接近 100 万了。可见其增长速度之恐怖。

洛谷例题：

1. P3390 [模板] 矩阵快速幂
2. P1962 斐波那契数列
3. P1349 广义斐波那契数列
4. P1939 矩阵加速（数列）
5. P3216 [HNOI2011] 数学作业

第三章 矩阵的逆

第一节 浅谈矩阵的逆

“逆” 这个词相信你早已听说过：同余意义下存在乘法逆元，大多数矩阵也存在逆矩阵。“逆” 普遍用来描述不同意义下的“倒数” 的概念，倒数一般满足 的性质，即本体 × 本体的逆 = 单位一。矩阵中的“单位一” 是单位矩阵 ，也因此我们的逆矩阵需要满足这个式子：，并且这个式子倒过来也必须成立（为数不多的满足矩阵乘法交换律的情况之一）。

如果对于一个矩阵 ，存在另一个矩阵 ，使得： 成立。则称矩阵 是可逆的，或称之为非奇异的，矩阵 是矩阵 的逆矩阵，通常表示成 。特殊地，单位矩阵 的逆矩阵是它本身，即 ；零矩阵 不可逆，或称之为奇异的，即不可能存在矩阵 ，使得 。

这一点类比实数运算： 的倒数永远是它本身、 没有倒数，因为分母为 ，没有意义；，同时 。

第二节 行列式

行列式是一种函数，写出来有点像矩阵的绝对值。它可以用来判断一个矩阵是否有解、也可以定量分析线性变换对原向量的影响。矩阵 的行列式通常用 或者是 表示。这一节主要介绍行列式判断矩阵是否可逆。同时，行列式也可以用来判断方程组是否有解。

定义 矩阵 的行列式为 。特殊地， 矩阵的行列式就是 的值。当一个矩阵的行列式为 时，它是奇异的、也就是不可逆的；反之则非奇异/可逆。

那我们在上边只提到了两种尺寸的方阵，那对于 、、以至于 的方阵又该怎么办呢？答案是分而治之——分治！

第三节 代数余子式展开/ 展开