---
title: "矩阵与线性代数"
description: "向量与矩阵运算、矩阵快速幂，以及高斯消元解线性方程组。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 矩阵与线性代数

![](https://img.dailyup.xyz/optimized/8207672306748-92729879-49dc-40b6-a551-7257be66b68c.jpg)

矩阵在竞赛里有两种用途。一种是把线性递推式写成矩阵乘法，再用快速幂把 $O(n)$ 的递推降到 $O(\log n)$；另一种是解线性方程组。两者都建立在一个基础运算上：矩阵乘法。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

| 考试 | 大纲要求 | 本章位置 |
| --- | --- | --- |
| NOI 提高级 | 2.5.4 线性代数：向量与矩阵的概念、向量的运算、矩阵的初等变换、矩阵的运算（加减乘与转置）、特殊矩阵、高斯消元法 | 全章 |

## 向量

向量是一组有序的数。二维向量 $(x, y)$ 可以看成一个点，也可以看成从原点出发的一个箭头。

基本运算：

| 运算 | 定义 | 几何意义 |
| --- | --- | --- |
| 加法 | $(x_1 + x_2, y_1 + y_2)$ | 首尾相接 |
| 数乘 | $k(x, y) = (kx, ky)$ | 方向不变，长度变成 $k$ 倍 |
| 点积 | $(x_1, y_1) \cdot (x_2, y_2) = x_1x_2 + y_1y_2$ | $= 0$ 表示两向量垂直 |
| 模 | $\sqrt{x^2 + y^2}$ | 向量的长度 |

点积的几何意义是 $|a||b|\cos\theta$，所以点积为零就是夹角 $90^\circ$。它在判断垂直、算投影时很有用。

## 矩阵的概念与运算

矩阵是排成矩形的数表。$n$ 行 $m$ 列的矩阵记作 $n \times m$ 的矩阵，第 $i$ 行第 $j$ 列的元素记作 $a_{ij}$。

### 加法与数乘

两个同型矩阵相加，对应位置相加；矩阵乘一个数，每个元素都乘这个数。这两种运算都很直观。

### 转置

把矩阵的行和列互换，得到转置矩阵，记作 $A^T$。$n \times m$ 的矩阵转置后是 $m \times n$。

### 乘法

矩阵乘法规则稍复杂，也是最重要的一个：

$$C_{ij} = \sum_{k=1}^{p} A_{ik} \times B_{kj}$$

其中 $A$ 是 $n \times p$ 的矩阵，$B$ 是 $p \times m$ 的矩阵，乘积 $C$ 是 $n \times m$ 的矩阵。**左矩阵的列数必须等于右矩阵的行数**，否则不能相乘。

一句话记忆：结果的第 $i$ 行第 $j$ 列，等于左矩阵第 $i$ 行与右矩阵第 $j$ 列逐项相乘再求和。

```cpp
struct Matrix {
    static const int N = 105;
    long long a[N][N];
    int n;
    Matrix(int n = 0) : n(n) { memset(a, 0, sizeof(a)); }
};

Matrix mul(const Matrix &A, const Matrix &B, long long mod) {
    Matrix C(A.n);
    for (int i = 0; i < A.n; i++) {
        for (int k = 0; k < A.n; k++) {
            if (A.a[i][k] == 0) continue;   // 跳过零元素，稀疏时能省不少时间
            for (int j = 0; j < A.n; j++) {
                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % mod;
            }
        }
    }
    return C;
}

三重循环的次序写成 `i, k, j` 而不是 `i, j, k`，是因为这样访问内存更连续，速度更快，而且能顺手跳过零元素。

矩阵乘法**不满足交换律**：一般情况下 $AB \neq BA$。这一点和普通乘法不同，推导时要注意顺序。它满足结合律，这正是快速幂能用的前提。

## 特殊矩阵

| 名称 | 特征 |
| --- | --- |
| 零矩阵 | 所有元素都是 0 |
| 单位矩阵 $I$ | 主对角线是 1，其余是 0；$AI = IA = A$ |
| 对角矩阵 | 除主对角线外都是 0 |
| 上（下）三角矩阵 | 主对角线一侧全为 0 |
| 对称矩阵 | 满足 $a_{ij} = a_{ji}$，即 $A^T = A$ |
| 稀疏矩阵 | 大部分元素为 0 |

单位矩阵在矩阵快速幂里的角色，相当于数字 1 在普通快速幂里的角色，是初始的「答案矩阵」。

## 矩阵快速幂

这是矩阵在竞赛里最主要的用途。以斐波那契数列为例：

$$F_n = F_{n-1} + F_{n-2}$$

把状态写成向量 $\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}$，那么递推可以写成一次矩阵乘法：

$$\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}$$

不断展开，就得到

$$\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix}$$

矩阵的幂可以用快速幂在 $O(\log n)$ 内算出来，于是 $F_n$ 的计算从 $O(n)$ 降到 $O(\log n)$。$n$ 到 $10^{18}$ 时，普通循环不可能跑完，矩阵快速幂却能秒出。

```cpp
Matrix mpow(Matrix base, long long e, long long mod) {
    int n = base.n;
    Matrix res(n);
    for (int i = 0; i < n; i++) res.a[i][i] = 1; // 单位矩阵
    while (e > 0) {
        if (e & 1) res = mul(res, base, mod);
        base = mul(base, base, mod);
        e >>= 1;
    }
    return res;
}

用法和普通快速幂完全一样，只是把「乘」换成了矩阵乘法，「1」换成了单位矩阵。

任何形如

$$f(n) = c_1 f(n-1) + c_2 f(n-2) + \cdots + c_k f(n-k)$$

的线性递推，都能用矩阵快速幂加速，构造出 $k \times k$ 的转移矩阵即可。

## 高斯消元

高斯消元用来解线性方程组：

$$
\begin{cases}
a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\
a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 \\
\vdots \\
a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n = b_n
\end{cases}
$$

把系数和常数项写成增广矩阵，然后做**初等行变换**（交换两行、某行乘非零常数、把一行的倍数加到另一行），这些变换不改变方程组的解。

步骤是：

1. 在当前列找一个非零元素作为主元。
2. 把主元所在行换到当前处理的行。
3. 用这一行把该列其它行的元素消成 0。
4. 处理下一列。

消完以后矩阵接近单位阵，解就出来了。

```cpp
const double EPS = 1e-9;
double a[105][105]; // 增广矩阵，第 n 列是常数项
int n;

bool gauss() {
    for (int col = 0; col < n; col++) {
        // 选列主元：当前列绝对值最大的那一行
        int pivot = col;
        for (int i = col + 1; i < n; i++) {
            if (fabs(a[i][col]) > fabs(a[pivot][col])) pivot = i;
        }
        if (fabs(a[pivot][col]) < EPS) return false; // 这一列全是 0，无唯一解

        for (int j = 0; j <= n; j++) swap(a[col][j], a[pivot][j]);

        double div = a[col][col];
        for (int j = col; j <= n; j++) a[col][j] /= div; // 主元化成 1

        for (int i = 0; i < n; i++) {
            if (i == col) continue;
            double factor = a[i][col];
            if (fabs(factor) < EPS) continue;
            for (int j = col; j <= n; j++) a[i][j] -= factor * a[col][j];
        }
    }
    return true; // 此时 a[i][n] 就是 x_i
}

上面第一步就是**列主元**：不是随便找一个非零元素，而是在当前列中挑绝对值最大的那一个。如果直接用第一个非零元素，一旦它很小（比如 $10^{-8}$），后面要拿它作除数，误差会被放大很多倍。

代码里把主元化成 1、再消掉该列所有其它元素，这种做法叫高斯-约当消元，比「先消成上三角、再回代」写起来更短。

## 复杂度

| 运算 | 复杂度 |
| --- | --- |
| 矩阵加法、转置 | $O(n^2)$ |
| 矩阵乘法（$n \times n$） | $O(n^3)$ |
| 矩阵快速幂 | $O(n^3 \log k)$ |
| 高斯消元 | $O(n^3)$ |

朴素矩阵乘法是 $O(n^3)$，所以转移矩阵的阶数不能太大。$n = 100$ 时一次乘法就是 $10^6$ 次运算，$\log k$ 次下来还算能接受；$n$ 到 500 就悬了。

## 常见易错点

- 矩阵乘法要求左矩阵的列数等于右矩阵的行数，维度对不上直接乘不了。
- 矩阵乘法没有交换律，$AB$ 和 $BA$ 一般不同，递推顺序写反结果就错。
- 快速幂的初始矩阵必须是单位矩阵，不是全零矩阵。
- 取模时注意中间结果溢出，两个 $10^9$ 级别的数相乘要用 `long long`。
- 高斯消元没有选列主元，浮点误差会累积到解完全不能用。
- 用 `fabs(x) < EPS` 判断浮点数的零，不能写 `x == 0`。

## 初赛选择题精选

下面 8 道题中，题 1 选自 GESP 八级真题，其余 7 道按本章考点编写。向量的运算（点积、叉积）在《平面几何基础》那一章有专门的真题解析，这里不重复。

### 题 1（GESP 八级，2023 年 12 月）

使用邻接矩阵表达 $n$ 个顶点的有向图，则该矩阵的大小为（ ）。

A. $n$　　B. $n \times n$　　C. $\dfrac{n(n-1)}{2}$　　D. $\dfrac{n(n+1)}{2}$

**答案：B**

**解析**：邻接矩阵是 $n$ 行 $n$ 列的方阵，$a_{ij}$ 表示从 $i$ 到 $j$ 有没有边。不管图是稀疏还是稠密，都要占 $n^2$ 个位置，这也是它相比邻接表的劣势。

### 题 2（矩阵乘法·维度）

已知 $A$ 是 $3 \times 4$ 的矩阵，$B$ 是 $4 \times 5$ 的矩阵，则 $A \times B$ 是（ ）。

A. $3 \times 4$　　B. $4 \times 5$　　C. $3 \times 5$　　D. 不能相乘

**答案：C**

**解析**：左矩阵的列数（4）等于右矩阵的行数（5），可以相乘；结果的行数取自左矩阵（3），列数取自右矩阵（5），所以是 $3 \times 5$。

### 题 3（单位矩阵与对称矩阵）

设 $I$ 是 $n$ 阶单位矩阵，下列关于它的说法**错误**的是（ ）。

A. 主对角线上的元素都是 1

B. 其余位置的元素都是 0

C. 对任意可以进行乘法的矩阵 $A$，都有 $AI = IA = A$

D. 单位矩阵的转置不再是单位矩阵

**答案：D**

**解析**：单位矩阵是对称矩阵，转置之后还是它自己。A、B、C 都是单位矩阵的基本性质。

### 题 4（矩阵乘法的性质）

关于矩阵乘法，下列说法正确的是（ ）。

A. 满足交换律　　B. 满足结合律

C. 只有方阵之间才能相乘　　D. 结果矩阵的行数等于右矩阵的行数

**答案：B**

**解析**：矩阵乘法满足结合律 $(AB)C = A(BC)$，这正是快速幂能用的前提；但不满足交换律，$AB$ 和 $BA$ 一般不等。维度只要求左矩阵的列数等于右矩阵的行数，不必是方阵；结果矩阵的行数等于左矩阵的行数。

### 题 5（单位矩阵的作用）

设 $I$ 是 $n$ 阶单位矩阵，$A$ 是任意的 $n \times n$ 矩阵，则下列正确的是（ ）。

A. $AI = A$，且 $IA = A$　　B. $AI = I$，且 $IA = I$

C. $A + I = A$　　D. $AI \neq IA$

**答案：A**

**解析**：单位矩阵在矩阵乘法里的作用相当于数字 1。加法不满足这个性质，$A + I \neq A$；$AI$ 和 $IA$ 都等于 $A$，所以 D 也不对。

### 题 6（矩阵快速幂复杂度）

用矩阵快速幂求斐波那契数列的第 $n$ 项（$n \le 10^{18}$），时间复杂度是（ ）。

A. $O(n)$　　B. $O(\log n)$　　C. $O(n \log n)$　　D. $O(n^3)$

**答案：B**

**解析**：斐波那契的转移矩阵是 $2 \times 2$ 的常数矩阵，一次矩阵乘法是 $O(1)$，一共做 $O(\log n)$ 次。如果递推式要开 $k$ 阶矩阵，就是 $O(k^3 \log n)$。

### 题 7（矩阵转置）

设 $A$ 是一个 $3 \times 4$ 的矩阵，则它的转置矩阵 $A^T$ 的维度是（ ）。

A. $3 \times 4$　　B. $4 \times 3$　　C. $3 \times 3$　　D. $4 \times 4$

**答案：B**

**解析**：转置就是把矩阵的行列互换，$A^T_{ij} = A_{ji}$。所以 $3 \times 4$ 的矩阵转置后变成 $4 \times 3$。

**两个要记住的性质**：

- $(A^T)^T = A$（转置两次回到原样）；
- $(AB)^T = B^T A^T$（**注意顺序要反过来**，这是最容易错的地方）。

### 题 8（高斯消元与行列式）

用高斯消元法解 $n$ 元线性方程组，时间复杂度是（ ）。

A. $O(n)$　　B. $O(n^2)$　　C. $O(n^3)$　　D. $O(n^4)$

**答案：C**

**解析**：高斯消元有两层结构：对每一行（$n$ 次）都要消去它下面所有行的对应列（每次 $O(n)$ 行 × $O(n)$ 列），所以是 $O(n^3)$。

**直观理解**：消元过程要处理的是一个 $n \times n$ 的系数矩阵，每次消元都要更新矩阵的一个 $O(n^2)$ 的子块，一共 $n$ 轮，合计 $O(n^3)$。

**和矩阵快速幂的区别**：矩阵快速幂是 $O(k^3 \log n)$（$k$ 是矩阵阶数，$\log n$ 来自快速幂），高斯消元是 $O(n^3)$（$n$ 是方程个数）。**两者的 $n^3$ 含义不同**，别混。

## 练习

### 练习 1：矩阵乘法

#### 题目描述

给定两个矩阵 $A$（$n \times m$）和 $B$（$m \times k$），求 $A \times B$。

#### 输入格式

第一行三个整数 $n$、$m$、$k$；接下来 $n$ 行，每行 $m$ 个整数，表示矩阵 $A$；再接下来 $m$ 行，每行 $k$ 个整数，表示矩阵 $B$。

#### 输出格式

输出 $n$ 行，每行 $k$ 个整数，表示乘积矩阵。

#### 数据范围

- $1 \le n, m, k \le 100$，矩阵元素的绝对值不超过 1000。

#### 输入输出样例

输入

```
2 3 2
1 2 3
4 5 6
7 8
9 10
11 12

输出

```
58 64
139 154

#### 题目分析

按定义直接三重循环。结果矩阵是 $n \times k$ 的，计算 $C_{ij}$ 时把 $A$ 的第 $i$ 行和 $B$ 的第 $j$ 列对应相乘再相加。

要注意数组的下标范围：$A$ 要用 `[n][m]`，$B$ 要用 `[m][k]`，结果用 `[n][k]`，三者不能混。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/matrix/index.md

### 练习 2：斐波那契数列第 n 项

#### 题目描述

求斐波那契数列第 $n$ 项对 $10^9 + 7$ 取模的结果。规定 $F_1 = F_2 = 1$。

#### 输入格式

一个整数 $n$。

#### 输出格式

输出一个整数，表示 $F_n \bmod (10^9+7)$。

#### 数据范围

- $1 \le n \le 10^{18}$。

#### 输入输出样例

输入

```
10

输出

```
55

#### 题目分析

$n$ 到 $10^{18}$，递推循环肯定跑不完，要用矩阵快速幂。

$$
\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix}
$$

把转移矩阵的 $n-1$ 次幂用快速幂算出来，取结果矩阵的左上角元素即可。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/matrix/index.md

### 练习 3：解线性方程组

#### 题目描述

给定一个 $n$ 元线性方程组的增广矩阵，解出 $n$ 个未知数。保证有唯一解。

#### 输入格式

第一行一个整数 $n$；接下来 $n$ 行，每行 $n+1$ 个实数，表示增广矩阵。

#### 输出格式

输出 $n$ 行，每行一个实数，表示对应未知数的值，保留两位小数。

#### 数据范围

- $1 \le n \le 100$。

#### 输入输出样例

输入

```
3
1 1 1 6
0 2 5 -4
2 5 -1 27

输出

```
5.00
3.00
-2.00

#### 题目分析

高斯-约当消元的标准题。每一步选当前列绝对值最大的行做列主元，把主元化成 1，再消掉该列其余所有位置。消完以后最后一列就是答案。

判断「这一列全为 0」用 `fabs(x) < EPS`，不能写 `x == 0`。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/matrix/index.md

### 练习 4（进阶）：定长路径计数

#### 题目描述

给定一个有向图的邻接矩阵 $A$（$a_{ij} = 1$ 表示 $i$ 到 $j$ 有一条边），求从顶点 $1$ 到顶点 $n$、长度（边数）恰好为 $k$ 的路径条数，对 $10^9+7$ 取模。

#### 输入格式

第一行两个整数 $n$、$k$；接下来 $n$ 行，每行 $n$ 个整数（0 或 1），表示邻接矩阵。

#### 输出格式

输出一个整数，表示路径条数对 $10^9+7$ 取模的结果。

#### 数据范围

- $1 \le n \le 50$，$1 \le k \le 10^9$。

#### 输入输出样例

输入

```
3 3
0 1 1
1 0 1
1 1 0

输出

```
3

从 1 到 3、长度恰好为 3 的路径有 `1→2→1→3`、`1→3→1→3`、`1→3→2→3`，共 3 条。

#### 题目分析

矩阵乘法还有一个很漂亮的性质：**$A^k$ 的第 $i$ 行第 $j$ 列，就是「从 $i$ 到 $j$ 长度为 $k$ 的路径条数」**。

道理在定义里：$(A^k)_{ij} = \sum_t (A^{k-1})_{it} A_{tj}$，即「先走 $k-1$ 步到 $t$，最后一步从 $t$ 到 $j$」，把所有中间点 $t$ 的情况加起来。

所以只要把邻接矩阵做 $k$ 次幂就行，$k$ 到 $10^9$ 用矩阵快速幂，复杂度 $O(n^3 \log k)$。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/matrix/index.md

## 小结

矩阵在竞赛里的价值在于**把递推变成幂运算**：只要能写成 $f(n) = c_1 f(n-1) + \cdots + c_k f(n-k)$，就能用 $k \times k$ 的转移矩阵加快速幂把 $O(n)$ 降到 $O(k^3 \log n)$。

- 向量有点积和叉积，点积判断垂直，叉积判断共线与方向。
- 矩阵乘法 $C_{ij} = \sum_k A_{ik} B_{kj}$，满足结合律但不满足交换律。
- 单位矩阵是矩阵乘法里的「1」，也是快速幂的初始值。
- 线性递推写成矩阵乘法后可以用快速幂加速；$A^k$ 还能数出长度固定的路径条数。
- 高斯消元解线性方程组，写的时候一定要选列主元。

学完这一章，下面这些事应该能独立完成：

- 写出矩阵乘法的三重循环，并说清维度对齐的条件。
- 说清矩阵乘法为什么能用快速幂（结合律），为什么不能随意交换顺序。
- 把斐波那契一类线性递推写成转移矩阵，并写出矩阵快速幂的代码。
- 写出带列主元的高斯消元，并说清为什么不能直接用第一个非零元素。
- 说清「$A^k$ 的元素是定长路径条数」这个结论的道理。

Source: https://cppguide.xyz/maths/matrix/index.mdx
