线性代数

yaoyunxiang · 2026-03-07 17:21:57 · 算法·理论

0x01 向量

向量（vector），也称矢量，是一种有方向，有大小的量。向量可以用 \overrightarrow{a} = (x ,y , \dots) 或 \begin{bmatrix}x \\ y \\ \vdots\end{bmatrix} 表示，也可以用极坐标 (\theta , \psi , \dots , r) 表示。通俗的，可以用导航中向 \theta 方向行驶 r 千米来理解向量。

向量加法

有 (a,b) + (c,d) = (a+c,b+d)。

对于 (1,0) + (0,1) = (1,1)，可以这样理解：先向右走 1 个单位，然后在向上走 1 个单位。

平行四边形法则、三角形法则：

对于两个向量相加，相当于用两个向量做出一个平行四边形，然后其对角线（从原点开始）就是两个向量的加和。

或者相当于将向量平移与另一个向量相接，构成的三角形第三边就是答案。

数乘

有 (a,b) \cdot x = (ax , bx)。相当于延长 x 倍。

点积（数量积）

设 \overrightarrow{a}=(x_1,y_1),\overrightarrow{b}=(x_2,y_2)，点积是一个标量，定义为： \overrightarrow{a}\cdot\overrightarrow{b}=x_1x_2+y_1y_2

几何意义： \overrightarrow{a}\cdot\overrightarrow{b}=|\overrightarrow{a}||\overrightarrow{b}|\cos\theta 其中 \theta 为两向量夹角。

常用性质：

• 垂直判定：\overrightarrow{a}\perp\overrightarrow{b}\iff\overrightarrow{a}\cdot\overrightarrow{b}=0

• 投影：\overrightarrow{a} 在 \overrightarrow{b} 上的投影长度为 \displaystyle\frac{\overrightarrow{a}\cdot\overrightarrow{b}}{|\overrightarrow{b}|}

叉积（向量积）

二维叉积（常用）： \overrightarrow{a}\times\overrightarrow{b}=x_1y_2-x_2y_1

几何意义：两向量围成平行四边形的有向面积，绝对值等于三角形面积的 2 倍。

三维叉积：结果是一个新向量，同时垂直于 \overrightarrow{a},\overrightarrow{b}，满足右手定则。

常用性质：

• 共线判定：\overrightarrow{a}\parallel\overrightarrow{b}\iff\overrightarrow{a}\times\overrightarrow{b}=0
• 方向判断：叉积符号可判断 \overrightarrow{b} 在 \overrightarrow{a} 的左侧/右侧。

0x02 矩阵的定义与意义

多个向量写在一行就是矩阵。

形式化地

矩阵表示的是平面的线性变换。

基向量 e_x = \begin{bmatrix}1\\0\end{bmatrix}, e_y = \begin{bmatrix}0\\1\end{bmatrix}，这两个向量构成了一个平面直角坐标系，且为 1 倍缩放。那么 I = \begin{bmatrix}1 & 0\\0 & 1\end{bmatrix} 就是标准的单位元（无变换），即单位矩阵。对于矩阵 I，存在 I \times \overrightarrow{\alpha} = \overrightarrow{\alpha}，性质相当于实数域中的 1。

类似的，有 E = \begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}，相当于将 I 中的 x 轴，y 轴互换，有 E \times \overrightarrow{\alpha} = \overrightarrow{\beta}, \overrightarrow{\alpha} = (a,b), \overrightarrow{\beta} = (b,a)。

对于矩阵 F = \begin{bmatrix}u & 0\\0 & v\end{bmatrix}，相当于给向量两个轴分别缩放 u,v 倍。

对于 A \times B，相当于计算一个连续的变换规则。

一般的，给定矩阵 A \times B = C，有：

保证能够运算的前提是 A 的列数与 B 的行数相同。

通俗的解释

如果记录 [a_1 \ a_2 \ \dots] 为一个同学买的物品个数，比如 [2 \ 3 \ 5] 表示买了A,B,C 商品各 2,3,5 个。有定义 \begin{bmatrix}b_1\\b_2\\\vdots\end{bmatrix} 为每一个物品的单价。那么我们可以钦定 [a_1 \ a_2 \ \dots] \times \begin{bmatrix}b_1\\b_2\\ \vdots\end{bmatrix}= \sum a_i \times b_i，因此我们只要知道物品个数 A 与商品单价 B，那么总价就是 A \times B。

如果有多个商店，单价不同，可以把几个商店的价格像列表格这样列出来，比如这样：B= \begin{bmatrix}b_{11}&b_{12}&\dots\\b_{21}&b_{22}&\dots\\ \ddots\end{bmatrix}。

如果有多个同学，购买数量不同，也像列表格这样列出来，比如这样：A= \begin{bmatrix}a_{11}&a_{12}&\dots\\a_{21}&a_{22}&\dots\\ \ddots\end{bmatrix}。

我们可以钦定 A \times B 出来的结果为每一个同学在不同商店里购买所需的总价。定义规则：

那么矩阵乘法就是类似于由需求变换为总价的东西，形式的，矩阵乘法就是矩阵 A 的变换。

矩阵的意义在于用寥寥几个数字描述一个复杂的变换过程。

一些特殊矩阵参考上方【形式化地】。

让我们来计算一次矩阵乘法：

结合律，交换律

矩阵满足结合律，因为定义就说明他是一个变换，结果肯定与优先级无关。

矩阵不满足交换律，比如：

简单递推

这里主要描述程序有关的内容。

对于有一些问题，能得到形如 f_i = F(f_{i-1} , f_{i-2} , \dots , f_{i-k}) 的递推式。如果能找到一种变换过程，使得 f_i 能快速变换到 f_{i+1} 就可以了。

对于上述简单递推式，f_i 的变换绝对依赖前 k 项。我们需要同时记录下 f_i,f_{i-1},\dots,f_{i-k+1} 的值。然后再来计算。

比如一个式子 f_i = 2\times f_{i-1} + 3 \times f_{i-2}，我们要记录 A = \begin{bmatrix}f_{i}\\f_{i-1}\end{bmatrix}。于是需要找到：

我们需要找到这个 M。设 M = \begin{bmatrix}M_{11} & M_{12} \\ M_{21} & M_{22}\end{bmatrix}。那么：

不难发现：M_{11} = 2 , M_{12} = 3。（一一对应）

这里，M_{21} = 1 , M_{22} = 0。

于是 M \times A_i = A_{i+1} , M = \begin{bmatrix}2 & 3 \\ 1 & 0\end{bmatrix}。

然后，如果我们知道 A_1 = \begin{bmatrix}1\\1\end{bmatrix}，那么 A_2 = M A_1 , A_3 = M A_2 = M^2 A_1 \implies A_n = M^{n} A_1。

0x03 高斯消元

怎么手动计算n元一次方程

初中时，计算一个二元一次方程的方法有两种，一是代入消元，二是加减消元。这里可以发现加减消元编码更加简单。

我们先思考如和实现。

我们计算时，会利用 (1) + 2\times (2) 使得两式的 x 系数相同，为了照顾计算机，我们使用更简单的方式，将上面的式子 x 项系数向下对其。于是：

所以，y 的值为 3。

我们可以用矩阵的方式描述一个方程组的系数。比如上述的方程组可以这样表示：\begin{bmatrix}2 & 3 \\ -1 & 2\end{bmatrix}

当然，你会发现将每一个未知数的值列成一个矩阵 \begin{bmatrix}x \\ y\end{bmatrix}，比如 x=2,y=1 时的矩阵 \begin{bmatrix}2\\1\end{bmatrix}。那么 \begin{bmatrix}2 & 3 \\ -1 & 2\end{bmatrix} \times \begin{bmatrix}2\\1\end{bmatrix} = \begin{bmatrix}7\\0\end{bmatrix}。

然后：将 x=2,y=1 带入方程：2x+3y=7,-x+2y=0。与上面的答案矩阵一致，当然，这里不会用到。

上述的方程组还可以这样表示：\left[\begin{array}{cc|c}2 & 3 & 13 \\ -1 & 2 & 4\end{array}\right]。

我们发现，他最后要求的就是竖线左边是单位矩阵时右侧的值。

利用计算机消元

每一次，用最第 i 行向下消元，每一次对齐第 i 个未知数进行消元，然后整个矩阵 i+1\sim N 行的第 i 个系数都会变成 0。比如：

我们来看一组线性方程组的例子，并进行手动模拟高斯消元法的过程。

方程组： \begin{cases} 3x + 2y - z = 10 \\ x - y + 2z = 5 \\ 2x + 3y + z = 12 \end{cases}

增广矩阵： \left[\begin{array}{ccc|c} 3 & 2 & -1 & 10 \\ 1 & -1 & 2 & 5 \\ 2 & 3 & 1 & 12 \end{array}\right] 。

第一步：将第一行的第一个非零元素作为主元（已经是 3，无需交换） 我们希望将第一列的下方元素消为 0。 - 用第二行减去 \frac{1}{3} 倍的第一行： R_2 \leftarrow R_2 - \frac{1}{3}R_1 计算： 1 - \frac{1}{3} \times 3 = 0 ， -1 - \frac{1}{3} \times 2 = -\frac{5}{3} ， 2 - \frac{1}{3} \times (-1) = \frac{7}{3} ， 5 - \frac{1}{3} \times 10 = \frac{5}{3} - 用第三行减去 \frac{2}{3} 倍的第一行： R_3 \leftarrow R_3 - \frac{2}{3}R_1 计算： 2 - \frac{2}{3} \times 3 = 0 ， 3 - \frac{2}{3} \times 2 = \frac{5}{3} ， 1 - \frac{2}{3} \times (-1) = \frac{5}{3} ， 12 - \frac{2}{3} \times 10 = \frac{16}{3} 。

更新后的矩阵： \left[\begin{array}{ccc|c} 3 & 2 & -1 & 10 \\ 0 & -\frac{5}{3} & \frac{7}{3} & \frac{5}{3} \\ 0 & \frac{5}{3} & \frac{5}{3} & \frac{16}{3} \end{array}\right] 。

第二步：将第二行的第二个非零元素作为主元（-\frac{5}{3}） 我们希望将第二列的下方元素消为 0。 - 用第三行加上第二行（因为 \frac{5}{3} / (-\frac{5}{3}) = -1）： R_3 \leftarrow R_3 + R_2 计算： 0 + 0 = 0 ， \frac{5}{3} + (-\frac{5}{3}) = 0 ， \frac{5}{3} + \frac{7}{3} = 4 ， \frac{16}{3} + \frac{5}{3} = 7 。

更新后的矩阵： \left[\begin{array}{ccc|c} 3 & 2 & -1 & 10 \\ 0 & -\frac{5}{3} & \frac{7}{3} & \frac{5}{3} \\ 0 & 0 & 4 & 7 \end{array}\right] 。

第三步：回代求解 现在矩阵已经是上三角形式，可以回代求解：

• 从第三行：4z = 7 \implies z = \frac{7}{4} 。
• 从第二行：-\frac{5}{3}y + \frac{7}{3}z = \frac{5}{3} 代入 z = \frac{7}{4}： -\frac{5}{3}y + \frac{7}{3} \times \frac{7}{4} = \frac{5}{3} ， -\frac{5}{3}y + \frac{49}{12} = \frac{5}{3} ， -\frac{5}{3}y = \frac{5}{3} - \frac{49}{12} = \frac{20}{12} - \frac{49}{12} = -\frac{29}{12} ， y = \frac{29}{12} \times \frac{3}{5} = \frac{29}{20} 。
• 从第一行：3x + 2y - z = 10 代入 y = \frac{29}{20} 和 z = \frac{7}{4}： 3x + 2 \times \frac{29}{20} - \frac{7}{4} = 10 ， 3x + \frac{58}{20} - \frac{35}{20} = 10 ， 3x + \frac{23}{20} = 10 ， 3x = 10 - \frac{23}{20} = \frac{200}{20} - \frac{23}{20} = \frac{177}{20} ， x = \frac{177}{60} = \frac{59}{20} 。
• 解： x = \frac{59}{20}, \quad y = \frac{29}{20}, \quad z = \frac{7}{4} 。

再来一个：

来手动模拟一遍：

这里说明方程组有无数个解。

我们发现模拟完后最后一行只有最后一个系数为 1，其他都是 0，相当于方程中 x_N 的解。

如果最后 x_N 系数为 0，那么表示无解。

得到最后一个值后依次向上对齐就可以将每一个式子化为 w_ix_i = C_i 的样子，得到 x_i = \frac{C_i}{w_i}。

0x04 线性基

异或问题

给你 N 个数字，输出他们子序列的异或和之和，相同的子序列异或和记一次。（\forall a_i \in [0 , 2^{16} - 1]）

如果正常做，那么暴力枚举的时间复杂度为 O(2^N)，但是异或值最多只到 O(2^Q-1) (Q为最大二进制位数)，比暴力少得多。于是我们需要找到等效替代的一个序列。

异或空间线性基

对于 A = \{2,3,5,6,7\}，所有异或和为 X = \{1,2,3,4,5,6,7\}。而 B = \{1,2,4\} 的所有异或和也是 X。

他的求法也很简单：对于一个新的数字 s，那么这个数字应该与原来的集合内所有的数字异或一遍得到 s'，s' \not= 0。

比如 A_2 = \{8,13,15\} :

0x05 复杂递推

在简单递推的基础上，当递推式包含常数项、一次项、多项式项等复杂形式时，依然可以通过扩充状态向量的方式，构造出对应的转移矩阵，继续使用矩阵快速幂进行加速。

我们需要把所有需要用到的变量、常数全部塞进状态向量里，让整个递推过程变成纯矩阵乘法。

带常数项的递推

以最常见的递推式为例： f_i = a\cdot f_{i-1} + b\cdot f_{i-2} + c 由于出现了常数 c，需要在状态向量中加入一个恒为 1 的维度来承载常数。 构造状态向量： A_i = \begin{bmatrix} f_i \\ f_{i-1} \\ 1 \end{bmatrix} 。

目标： M \times A_i = A_{i+1} = \begin{bmatrix} a\cdot f_i + b\cdot f_{i-2} + c \\ f_i \\ 1 \end{bmatrix} 构造转移矩阵： M = \begin{bmatrix} a & b & c \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} 。

带一次项/多项式的递推

如果递推式包含 i 相关的项，例如： f_i = f_{i-1} + f_{i-2} + i 需要把 i 和 1 都加入状态向量： A_i = \begin{bmatrix} f_i \\ f_{i-1} \\ i \\ 1 \end{bmatrix} 利用 i+1 = i + 1 的关系，同样可以构造出合法的转移矩阵。

通用规则

1. 状态向量包含：f_i, f_{i-1}, \dots, f_{i-k+1}、所有变量项（如 i）、常数项 1 2.
2. 转移矩阵的每一行，对应新状态向量中一个位置的计算式
3. 构造完成后，依然满足 A_n = M^{n-t} \times A_t ，通过矩阵快速幂可在 O(k^3\log n) 时间内求出结果。

0x06 矩阵行列式