特别声明：本文仅作本人成长过程的记录，无不良引导或其他特殊含义。

由于本文内容特殊，不接受任何形式的转载，感谢理解。

2024/6/30 upd:填坑。

线代总结

要是我不会 Ctrl+C Ctrl+V Ctrl+F 我的手就废了。

向量与矩阵

向量

有大小和方向的量被称为向量（Vector）。

在 OI 中，向量一般用一个水平或竖向放置的一维数组表示：

在这个例子中， 是列向量， 是行向量。

向量是线性代数的主要研究对象。

矩阵

发明这玩意的人一定是个天才吧。

一个 的矩阵是一个有 行 列的矩形元素阵列，如下：

矩阵可以简单地理解为一个下标从 开始的二维数组。特别的，当 时矩阵为列向量， 时矩阵为行向量。

当 时矩阵也被称为方阵。

我们可以把一个矩阵看作 个行向量或者 个列向量。（牢记这一点，对于理解矩乘非常重要）

同形矩阵

两个矩阵 同形当且仅当两个矩阵的 分别相同。

矩阵的加、减、数乘

两个矩阵能加减当且仅当这两个矩阵同形。

矩阵很大，你忍一下。

总之矩阵的加减就是矩阵对应位置加减，矩阵的数乘就是每个位置乘上这个数。

矩阵的转置

我们把矩阵的行列交换就是这个矩阵的转置，记作 ，即对于所有 都有 一般而言我们都将行向量写作列向量的转置，即

矩阵乘法

两个矩阵能进行乘法当且仅当第一个矩阵的列数与第二个矩阵的行数相等。

（要是我再把整个矩阵都打出来我就要废了）

我们设 是 的矩阵， 是 的矩阵，那么 即为 的矩阵：

我们可以把 简写为 。

容易发现方阵可以无限地自乘，我们可以把方阵的自乘 写作 。

单次矩乘的时间复杂度为 。若认为 同阶则为 。

矩乘有结合律但是没有交换律，因此我们需要区分左乘与右乘。

卡常小寄巧

在实际写代码的时候按照 i,k,j 的顺序枚举变量，可以使内存访问连续，会稍微快一点。

1
2
3
4

for(int i=1;i<=n;++i)
    for(int k=1;k<=p;++k)
        for(int j=1;j<=m;++j)
            ans[i][j]+=a[i][k]*b[k][j];

矩乘的理解

由于写博客的蒟蒻都觉得这玩意比 LCT 还难理解，因此附上一种理解的方式。

我们首先行向量乘上列向量（即 ）的结果，那么显然

也就是

现在我们把 变成 的矩阵：

此时 ，结果就是 的矩阵，然后我们试着再用矩乘的定义计算一下结果：

欸，是不是看出来点门道了？

我们进一步把 拓展为 的矩阵，那么结果即为 的矩阵（即行向量）：

也就是

结合上文提到的把一个矩阵看作行向量或列向量的组合，我们把 看作 个列向量。

我们试着画个图看一下（下图是一个 的例子）：

我们发现单独抽每一列出来，得到的答案都是 中每一项乘上在这一列里对应行（在这个例子里是小写字母）的和，我们称之为 的线性组合。

那么如果我把 也变成 行的矩阵，此时可以发现各个行向量再怎么乘都只会乘到对应的这一行上：

而我们发现列向量在结果中也只会影响对应的这一列，因此我们找到了一个规律：两个矩阵相乘，结果的的第 行第 列为 第 行的行向量与 第 列的列向量的乘积，而这个向量的积就是给 第 行的行向量的第 项乘上第 列的第 项之后加起来，或者说 就是 的线性组合的系数。

事实上我们也可以先增加行向量的数量再增加列向量的数量，于是 就成了 的系数。由此我们也发现：当我们需要求行的线性组合时，就把列作为行的系数；当我们需要求列的线性组合时，就把行作为列的系数。

矩阵的初等变换

我们定义下面的三种操作为矩阵的初等变换：

• 交换两行/列
• 把一行/列的倍数加到另一行/列上
• 把一行/列乘上一个常数

这三类初等变换都可以通过左乘或右乘一个矩阵来达成。

单位方阵

定义 的单位方阵 为：

也就是 。如果我们定义 为方阵的主对角线，那么 就是只在主对角线上有值且值为 的方阵。

单位方阵的性质：。

在有了单位方阵后，我们就可以在这个单位方阵做手脚了。

下文只讨论行操作，因此只需要右乘。列操作换成左乘即可。

行交换

我们希望交换矩阵的第 行和第 行，则只需要交换单位矩阵的第 行和第 行即可。

行乘常数

我们希望把矩阵的第 行乘上 ，则只需要把单位矩阵的第 行第 列换为 即可。

行加另一行的倍数

我们希望把矩阵的第 行乘上 再加到第 行，则只需要把单位矩阵的第 行第 列换为 即可。

证明直接带进去就好了。

矩阵快速幂

矩阵乘法有结合律，因此方阵自乘可以套用快速幂。

求 的矩阵 的 次方的时间复杂度是 。

矩阵与递推

引入

求 Fibonacci 数列的第 项（从第 项开始）。

我会递推！

。

hmmmmmmm...

这个问题可以用矩阵快速幂加速。

矩阵加速线性递推

Fibonacci 数列的递推式：。

这是一个典型的线性递推，我们可以通过构造一个矩阵通过乘矩阵达到相同的效果。

首先 必定是 的，然后我们就可以构造下列矩阵：

因为

因此

用矩阵快速幂加速即可，时间复杂度 。

类似的，如果我们要求下面这个递推式的第 项：

我们同样设

我们构造出

满足条件。

这里还有一个例子：

你有一个 个结点的有向图，点 和点 之间有 条边，你需要求出从任意点出发走 步的方案数。两个方案不同当且仅当经过的点不同或经过的边不同。

。

我们很容易想出朴素 DP：定义 为从 出发到 ，走 步的方案数，那么

ちょっと待って，这个咋和矩阵乘法这么像？

我们把 的前两维看作矩阵的两维，第三维看作数组标号，即 ，那么这个东西可以写作

这就是一个裸的矩阵乘法。

由于 ，因此 即为 的矩阵的 次方。

时间复杂度 。

我们考虑 Floyd 也类似这个转移，所以 Floyd 实质上也是一种矩阵乘法（加法是 ，乘法是加法）。

线性方程组与高斯消元

线性方程组

上式即为一个线性方程组的标准形式。

我们一般把 都写作矩阵，也就是

我们也可以写作增广矩阵，也就是在 的后面加一列为 。

比如下面这个线性方程组

就可以写作

或

高斯消元

我们可以用高斯消元来解线性方程组。

高斯消元的核心思想是把矩阵消成上三角阵，也就是主对角线以下都是 的矩阵。

我们回忆一下小学解二元一次方程，大多都是通过其中一个式子乘上某个常数后减去另一个得到，现在我们试着把它推广到所有线性方程组。

现在假设要消去 这一项，即将第 的系数都消成 。

我们随意地选取一行用它的倍数来减掉其他行里 这一项。在减完之后，其他的几项里就都没有 了，这样就是完成了一轮消元。

由于每一次我们都会消掉一列，而消元完了后的行就没用了，只要重复这个过程，一定要么只剩一行要么只剩一列（不含增广的那一列）。

当 时，会被消成只剩一列，此时还有 行。我们继续消元就会变成一堆

那么当这些 都是 时方程有唯一解；否则无解。

当 时，会被消到只剩一行，就会变成若干未知数的线性组合等于一个数，这种情况有无穷解。我们在此时定义 为主元，其余为自由元。自由元可以任意取值，而一组自由元可以唯一确定一组主元。

我们回到原问题，若方程有唯一解，那么我们就将这个解带到倒数第二个被消掉的方程里，然后就可以解出倒数第二个未知数；以此类推。

例子

我们假设要解方程

首先我们消掉第一列。

我们用第二行和第三行减去第一行：

此时 就被消掉了，第一行也没用了，所以我们现在只需先考虑第二行第二列及以下的子矩阵：

我们继续用第三行减去第二行：

再删掉第一行和第一列：

即

因此 。

我们把 回带到 ：

即

解得

再把 回带到 ：

解得 。

到此我们就解出了该方程的唯一一组解：

代码实现

代码实现上可能会有一些细微的差异。

令 。重复下列过程直到 或 ：

1. 找到第 列绝对值最大的元素。
2. 如果找不到一个绝对值大于 的元素，说明这一列已经被消完了，令 并返回 1。
3. 否则设我们找到绝对值最大的是第 行，将第 行与第 行交换。（优化精度）
4. 将第 行的所有元素除以 。
5. 对第 行第 列的元素（），将其减去 。
6. 此时完成一轮消元，令 。

如果 ，我们解出第 行的答案（解不出即为无解），将这个答案代入到第 行中。如果都成立，则我们找到了 的唯一解；否则无解。

否则方程有自由元，返回无穷多解。

如果方程有唯一解，那么我们从 开始，在它作主元的上方的每一行的增广列都减去 乘上对应的系数，这样在循环到某一行时我们就已经解出了这一行主元的真实值。

在 时需要分讨的情况会少非常多。

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

//Luogu3389 【模板】高斯消元法
//此题中n=m因此代码较为简洁
for(int i=1;i<=n;++i){
    int k=0;
    double maxn=0;
    for(int j=i;j<=n;++j)if(maxn<std::fabs(a[j][i]))k=j,maxn=std::fabs(a[j][i]);
    if(!maxn)return puts("No Solution"),0;
    std::swap(a[k],a[i]);
    double d=a[i][i];
    for(int j=i;j<=n+1;++j)a[i][j]/=d;
    for(int j=i+1;j<=n;++j){
        d=a[j][i];
        for(int k=i;k<=n+1;++k)a[j][k]-=a[i][k]*d;
    }
}
for(int i=n;i;--i)
    for(int j=i-1;j;--j)
        a[j][n+1]-=a[j][i]*a[i][n+1],a[j][i]=0;

高斯-约旦消元

回带还是太麻烦了，有没有什么不需要回带的方法吗？

有，高斯-约旦（Gauss-Jordan）消元就不需要回带。

和高斯消元消成上三角阵不同，Gauss-Jordan 消元的目标就是直接把矩阵消成对角阵。

Gauss-Jordan 消元与普通高斯消元的区别在于：Gauss-Jordan 消元不会缩小求解的范围。

它的大体流程如下：

• 选择一个主元。
• 选择一个含有该主元的方程。
• 用这个方程消去其他方程中的这个主元。

Gauss-Jordan 消元的优势在于码量较小、代码简单；缺点在于无法区分无解和无数解。

高斯消元的应用

求逆矩阵

如果 ，则称 是 的逆矩阵。

解法：构造一个增广矩阵 ，通过消元消成 ，即为答案；如果消不成，则不存在逆矩阵。

求行列式

定义一个方阵的行列式为

其中 是 中逆序对个数。

行列式的性质：对矩阵作初等变换，行列式不变。

因此我们只需把矩阵消成上三角阵后，就只需要计算主对角线的乘积了（其他情况都必定有乘积结果为 ）。

出模数不是质数的出题人想必一定有点什么心理疾病吧。

Matrix-Tree 定理

设一张有向图 ，结点 的入度为 。

我们构造矩阵 满足

那么如果我要求以 为根的外向生成树形图的个数，那么只需要去掉 的第 行和第 列，则答案即为剩余矩阵的行列式。

总结

OI 中线代内容不算多，但是在 DP 与数论等方面有一定意义，值得理解。

部分参考资料

OI-Wiki