有的放矢——一个OIer兼训诂学爱好者的线性代数观

OTTF · 2026-04-25 22:49:04 · 算法·理论

前言—— STL 容器之命名，决定着将来五百年的历史

（这一节就是在发牢骚，不涉及对线性代数知识的解说……）

我曾在学习知名数学博主3Blue1Browm的视频【熟肉】线性代数的本质 - 01 - 向量究竟是什么？时，看到弹幕中对“向量”这一数学概念展开联想，认为其与 C++ 中的 STL 容器 vector 有关。此后，我又在洛谷上的博文线性代数的几何性质中看到了以下句子：

1.1 向量的实质

首先搬出一般的定义：同时具有大小与方向的量。但对于oiers来说，事实上m维向量就是具有m个元素的列表，例如stl中就把动态数组作为vector（向量）。线性代数中，常常把向量的起点认为是原点，而终点就可以唯一地表示一个向量。

其某些字眼同样暗示着数学中的概念“向量”与 C++ 中的 STL 容器 vector 有关。

关于这两个概念是否相关，以至于可以进行深入的对比，这两个作者都没有明确地点明。但我们可以料想到很多学习者会有如此的直觉，因为它们确实有着同样的名字——大家都知道数学中的概念“向量”是由英文词汇“vector”翻译而来的。然而，这是错的。

（噔噔噔噔噔噔）（新三权谋音）

一个 Oier 可能会在某些题目的变态优化中接触数学中的“矩阵”这一概念，从而接触数学中的“向量”这一概念。而一个正常的文化课学生第一次接触数学中的“向量”则可能是在物理课的直线运动研究上，物理老师告诉这个学生某些量是既有大小又有方向的，它们被称作“矢量”，当然我们知道这就是向量，在这种课上教授的应当是一维向量的知识；而这个学生第二次接触“向量”则应该是在数学课，其学习到二维向量的知识，并研究了研究它的加减乘除。无论如何，这些向量都有一个固定的“长度”，或者说“维数”，或者通俗地说，就是小括号或者方括号里包裹着的数字的个数。无论如何折腾向量，人们都不打算把它粗暴地添加一个维数。

C++ 中的 STL 容器 vector 这一概念，则应该只有 C++ 这一编程语言的使用者了解了。就我而言，我对它的认识是相对于 C++ 从 C 处带来的原生数组建构的：它使用了酷炫的模板类技术，比原生数组更高级；它有一个绚丽的英文名，当时初学 C++ 的我并不明白其真意；它归属于 STL 这一家族，拥有迭代器等在这一家族中普遍存在的辅助工具；最重要的是，它的长度可变，我可以依照自己的喜好向它添加数据，从它删除数据，甚至把它的长度任意伸缩为某值。“改变长度”这一动作貌似是 C++ 中的 STL 容器 vector 的核心操作之一，甚至是它在 C++ 的早期版本中就被缔造的原因——长度不可变的容器 array 在之后的版本中才出现，看起来 C++ 标委会觉得它的优先级并没有 vector 高。

对事物的相似度的判断，决定不能依赖于它们的名字，而更要研究它们的行为方式。计算机科学家们常说“如果一个东西走路像鸭子、说话像鸭子、长得像鸭子、啄食也像鸭子，那它肯定就是一只鸭子。”而现在，我要说：考察 C++ 中的 STL 容器 vector，它能变长，这不像数学中的概念“矢量”；孤证不立，所以我再说一条：它不能进行加减乘除，这不像数学中的概念“矢量”。所以，我说：它不是数学中的概念“矢量”，它的名字是来忽悠人的。

我在纯粹的纸面上的推理是不完全可信的，毕竟我不是个严谨的数学家，肯定为了让自己的观点更可信使用了不少的逻辑跳跃。现在我决定给读者们看一些更真实的东西。

知乎上存在着 c++ 里如何理解 vector 是动态数组，而这个单词本义是向量？为什么这么叫？这一问题，可见确实有初学者不明白 C++ 中的 STL 容器 vector 与数学中的概念“向量”有什么关系。而这一回答引用了 Stack Overflow 的部分内容，其翻译如下：

之所以选择这个名字，是因为 Alex Stepanov 作为 C++ 标准库的设计者当初在寻找一个可以与内置数组类型区分开来的名字的时候，使用了“向量”这个表示。他现在承认这确实是个错误，因为数学家们通常使用“向量”来表示一个定长的序列。C++0X 中又引入一个表示定长序列的 array 类型从而加剧了这个错误。

所以说，命名的时候一定要非常小心，这是 Alex 给我们带来的教训。

可以看到，C++ 语言部分内容的设计者和 C++ 语言的部分使用者都认识到了 vector 这一容器在命名上的疏忽——它将一个只是“类似”而不是“等同”的概念拿来，从而造成了不大不小的混乱。为了避免混乱，我们应该区别开 C++ 中的 STL 容器 vector 和数学中的“向量”这一概念——万幸 C++ 这门语言早就经历过类似的事，为了解决两个东西可能有相同的名字的麻烦，它引入了命名空间这一概念，我们不妨也这么做。在这篇文章中，我现在宣布 C++ 中的 STL 容器 vector 归属于命名空间 C++_languege，而数学中的“向量”这一概念归属于命名空间 Mathematics，它们完全不是一个东西，不要混淆它们。

注意，【熟肉】线性代数的本质 - 01 - 向量究竟是什么？这一视频和线性代数的几何性质这一博文都没有明确的作出对以上两个概念的混淆，我无意批判它们误导了读者，只是单纯地想补充一下对名称的解释。我唯一的攻击对象是 C++ 语言乱七八糟的命名——除了上面的例子，它还有 list move 等词不达意的命名，值得一笑。

单纯为了批判 C++ 这一编程语言的命名方式而写一篇博文好像显得有些刻薄了，所以我决定从此一笔荡开去，论说一下线性代数中的一些基本内容。方便起见，我现在要宣布我以后将一直处于 using namespace Mathematics 的状态，因为我要讨论的是线性代数这一领域，而非 C++ 这一编程语言。

缘起——斐波那契数列和快速幂，就像……就像桌上的这双筷子

我计划从斐波那契数列开始，但我懒得讲兔子繁殖的故事了，你可以在知乎上的文章一文带你走近斐波那契数列~中看到对斐波那契数列的解释。现在你应当理解，斐波那契数列被如此定义：

可以想象到，如果我们尝试在当 n 很大时计算 F_n 的值，一种比较快的计算方式是：开辟一段空间用来存储每个 F_i 的值；在预处理出 F_0 和 F_1 的值后，从 i=2 的情况开始一个一个 i 计算，每次都把得到的 F_i 储存起来，从而预备未来的计算；最终显然可以得到 F_n 的值。这个算法的时间复杂度是 \Theta (n) 的——如果你不认识这个说法，它表示这种运算方法所用的时间大致与 n 成正比。

或许你不知道上面的概念和线性代数有什么关系，别急，接下来你也不会知道，因为我计划用“快速幂”这个知识来继续文章。考虑两个正整数，a 与 n，如果我们要计算 a^n，你肯定能想到一种时间复杂度为 \Theta (n) 的算法——就是把 a 乘 n 遍嘛。这看起来很快，但我们还可以更快，因为科学家们发明了“快速幂”这个算法。

这一算法首先依赖于这个事实：

别笑，这很简单，但这很重要。容易想到，如果 i 是偶数，那么我们能找到 j = \frac {i} {2}；如果 i 是奇数，那我们怎么都找不到那个正整数 j——万幸，我们可以把 i 减去 1，如果得到了 0，那我们就算到头了，否则我们就用对偶数的方法处理它。

我们可以用简明的公式来翻译上述又臭又长的文字：

注意那一条竖线表示前者整除后者，即后者是前者的倍数；加一个斜线就表示前者不整除后者，即后者。

知道了这些之后，我们就可以写出被称为“快速幂”的算法。它的一个基本形态是：如果 i 不是 0，那就按它的奇偶性讨论，要么我们需要递归计算 i 折了半的那个幂，要么我们需要把 i 减去 1；如果 i 是 0，那我们的这部分递归就到头了。使用 C++ 编程语言可以写出这样的代码：

template <typename T>
T quick_pow (T a, long long i) {
    if (i == 0) {
        return 1;
    }
    else if (i % 2 == 0) {
        T mid_pow = quick_pow (a, i / 2);
        return mid_pow * mid_pow;
    }
    else {
        return quick_pow (a, i - 1) * a;
    }
}

你可能会觉得看代码比看公式和文字更好懂，我就这么觉得。其实这样写出来的快速幂算法还有很大的改进空间，首先递归这一操作就有够慢的了，其次在很多题目中我们都需要取模……我自己的板子是这样的：

template <typename T>
T quick_pow (T a, long long n, long long mod) {
    T res = 1;
    while (n) {
        if (n & 1) {
            res = (res % mod) * (a % mod) % mod;
        }
        a = (a % mod) * (a % mod) % mod;
        n >>= 1;
    }
    return res % mod;
}

不需要去细究它的实现细节，它与上面的算法在本质上没有不同。显然，可以感知到，这里给出的快速幂算法的时间复杂度是 \Theta (\log n) 的，没有底数的 \log 表示我们不需要在意底数，其原因涉及到算法时间复杂度的真正严谨定给读者自己查询。顺便，我不为上面两段代码的正确性负责，如果有人问我，我就说它们是 AI 生成的。

现在把斐波那契数列和快速幂算法放到一起来看：对于斐波那契数列，我们现在拥有一个时间复杂度为 \Theta (n) 的算法；对于快速幂，它是一个能把原本 \Theta (n) 的运算加快到 \Theta (\log n) 的时间复杂度的奇妙方法。诶？你说，我们能不能把快速幂的思想套用到斐波那契数列的计算上呢？

凝思——这矩阵说得好啊！说得咱家心里舒服死了！

把斐波那契数列和快速幂结合到一起？好吧，这个想法可能听起来有些不切实际。我们可以意识到，快速幂计算的是幂，是乘方；乘方，就是把很多相同的东西乘在一起。而在斐波那契数列中，我们有通项公式 F_i = F_{i-1} + F_{i-2}，这算是一种“相同的东西”，但是它是个加法，是个通项公式，看起来我们并不能把通项公式“乘在一起”。

诶？如果我们新定义一个数学概念，它可以通过奇妙的数字游戏表达一种“通项公式”，即对某些数字的变换；并且它还能做我们需要的乘法，或者说它有一种运算可以通过快速幂来加速——那我们不就可以用快速幂来加速斐波那契数列了吗？

这种概念真的存在吗？

我们该不会疯了吧？

不！我们没有疯！经过不懈的努力，数学家们发现，“矩阵”这一概念就是我们所需要的！我们需要做的，就是用这个叫做“矩阵”的玩意儿来描述一下我们的通项公式！这肯定给了你充足的信心吧！

现在冷静下来，观察这个式子：

我们可以把它扩写一下：

容易发现，等号左边只存在 F_i 与 F_{i-1} 两项，而等号右边则只存在 F_{i-1} 与 F_{i-2} 两项，这依然是一个递推的流程。我们可以认为，F_{i-1} 和 F_{i-2} 这两项在经过一个由第一行的 1 和 1、以及第二行的 1 和 0 所组成的神奇变换之后，就变成了等号左边的 F_i 和 F_{i-1}。天呐，我们必须要说“第一行的 1 和 1、以及第二行的 1 和 0 所组成的神奇变换”吗？既然它们在算式里有行列关系，那么我们也把它们写出行列关系！

为了方便人看，我们用两个巨大的方括号来界定这些数字的范围。

还有剩下的那些斐波那契数列的第某某项，左边有两个，右边也有两个，我们不妨把它们也写成那种方块的形式：

这还没完！我们需要的是一个巨大的方块式子，一个乘法的方块式子，用来填充进我们喜欢的快速幂！我们应当把它们放到等式中，并且强硬地在等号右边塞一个乘号！

是的！这种把数字写到方括号里形成方块样式的东西叫做“矩阵”，它们可以很大，虽然这里的矩阵比较小。矩阵可以做乘法，且这是有严格的定义的，让我们从小处来建立这个概念。

首先，为了方便，我们约定记矩阵 A 的第 i 行 第 j 列为 A_{i, j}。现在，先回忆一下刚才的式子：

我把调换了等号左右两边，这看起来更有做运算的样子。回忆上面的式子：

我们可以写出：

然后，用 A_{i, j} 这样的记号来代替具体数字，我们就有了这个抽象的式子：

我们其中的一处精华提取出来，也就是：

不难发现，在等号右侧的 C_{1,1}，是乘法的结果中某行某列的值。而在等号左侧，乘号前的矩阵 A 提供了一些数来参与运算，乘号后的矩阵 B 也是。不同之处在于，矩阵 A 提供的是一整行，这一行的序数等于 C_{1,1} 的行的序数；矩阵 B 提供的是一整列，这一列的序数等于 C_{1,1} 的某行某列的列的序数。矩阵 A 和矩阵 B 提供的数的个数应该是相同的，这样它们才能配对相乘，然后相加。

再把这个过程抽象一下，我们把矩阵 A 的行数设为 m，列数设为 n；而把矩阵 B 的行数设为 n，列数设为 p。对于矩阵 A 和矩阵 B，矩阵 A 列数等于矩阵 B，是因为我们提到了，矩阵 A 和矩阵 B 提供的数的个数应该是相同的，而矩阵 A 会提供一整行，个数就是列数；矩阵 B 会提供一整列，个数就是行数。规定了行数和列数，我们可以列出矩阵乘法的结果的通式：

以防你不知道，那个巨大的翻过来的“M”名叫“求和符号”，你可以自己去了解它的功能。容易想到，乘法结果的行数是 m，列数是 p。

我们刚才对矩阵乘法运算法则的归纳是建立在一个较为简单的乘法例子的基础上的，但是我们一直做得很对！刚才得到的通式就是数学家们对矩阵乘法的定义！我们的法则放之四海皆准！

明确了矩阵乘法的定义后，我们就需要看看它是否能被塞到快速幂里。快速幂需要我们有怎样的乘法呢？由于在快速幂中，相乘的东西都是一样的，所以显然交换律不被需要。而快速幂实际上是把依次顺序做乘法，给改成了递归或者递推的不依次做乘法，所以结合律是被需要的。我们的矩阵乘法满足结合律吗？

数学家们帮我们证明过了，是满足的！你也可以自己去试试，拿三个可以做乘法的矩阵去套一下通式，就可以自己验证一个例子了。容易想到如果三个可以，那么更多也是可以的。

顺便，容易想到矩阵乘法是不满足交换率的，一个行数为 m，列数为 n 的矩阵 A 和一个 n，列数为 p 的矩阵 B 可以相乘，但如果调换乘号两边的顺序就可能乘不了了——m \neq p。就算我们让 m=n=p，交换乘号两边顺序后得到的结果也可能不同，你也可以自己去试试。

现在，我们可以有：

只要注意乘号两边的东西的顺序，你就能用快速幂把斐波那契数列的计算加速到 \Theta (\log n) 了！

高潮——我初学者，恭迎线性代数！

我们通过尝试用快速幂优化斐波那契数列的计算而发明了矩阵和矩阵乘法，从而踏入了线性代数的大门。然而你估计还不知道“矩阵”和“向量”有什么关系，因为我没说；你也不知道“线性代数”为什么要叫“线性代数”，因为我也没说。

追忆一下这个式子：

可以看到，矩阵 B 和矩阵 C——或者说第二个和第三个矩阵，如果你忘了的话——都只有一列。上文的论说中已经暗示了，只有一列的矩阵是比较“小”的，不足以代表所有矩阵。事实上，它们都是“向量”。

到此为止，“向量”这一概念在读者脑中应该已经明朗了。物理课中曾在直线运动的相关研究中提到向量，现在看来那是一个一行一列的矩阵。后来数学课和物理课肯定都提到过二维向量，也就是平面上的，现在看来那是一个二行一列的矩阵。我们可以自然地推广出，存在三维的向量，那是一个三行一列的矩阵。你看：在一维中有一个数，在二维中有两个数，在三维中有三个数，显然向量可以对应一个点。我们有时还希望把两个维数相同的向量相加或者相减，并且得到的还要是一个有意义的向量，嗯，那么向量表示的就是从坐标原点到某个点的那根有长度的箭头了。我们还把向量乘起来，运算法则与矩阵乘法是相同的，只是有一点书写上的变化，比如说，我们在高中数学中可能会写：

而用矩阵的方式，我们可以写：

你会看到 $\left[ {\begin{array}{c} \begin{matrix} 1 & 2 \ \end{matrix} \end{array}} \right]