2025 Summer Day4

Content：Math

Date：2025.7.20

内容

矩阵
线性方程组
行列式
矩阵树定理
线性基

具体内容

矩阵

矩阵定义

定义

将一些元素排列成若干行，每行放上相同数量的元素，就是一个矩阵 (Matrix)。对于矩阵 $A$ 的第 $i$ 行，第 $j$ 列，我们记作 $a_{i,j}$ 或 $a_{ij}$ 。对于举证 $A_{m \times n}$ ，如果 $m = n$ ，则我们称矩阵 $A$ 为方阵。

矩阵基本操作

矩阵加法：对于矩阵 $A_{m \times n}$ , $B_{m \times n}$ , 我们定义矩阵加法为 $C_{i,j} = A_{i, j} + B_{i, j}$ 即矩阵对应位置上的元素之和。
标量乘法：对于矩阵 $A_{m \times n}$ 和标量 $x$ , 我们定义矩阵的标量乘法为：

C_{i, j} = A_{i, j} \times x

转置：对于矩阵 $A_{m \times n}$ ，其转置为:

A^{T} = \begin{bmatrix} A_{j, i} \end{bmatrix}

矩阵的拼接：对于矩阵 $A_{m \times n_1}$ ， $B_{m \times n_2}$ ，其拼接为记为 $(A \ | \ B)$ ，其大小为 $m \times (n_1 + n_2)$ 。
矩阵的乘法：对于矩阵 $A_{m \times n}$ 和矩阵 $B_{n \times k}$ ，其矩阵乘法定义为：

C_{i, j} = \sum_{x = 1}^{n} A_{i, x} \times B_{x, j}

1
  其中 $i \in [1,n]$，$j \in [1,k]$。
2
  对于矩阵乘法，有如下性质：
3

4
  + 矩阵乘法具备分配律：$(A + B)C = AC + BC$；
5
  + 矩阵乘法具有结合律：$(AB)C = A(BC)$;

7. 矩阵乘法单位元：矩阵的乘法单位元 $I$ 为矩阵主对角线上全部为 $1$ ，其余均为 $0$ 的 $0/1$ 矩阵。 8. 矩阵的逆：如果对于矩阵 $A$ 存在矩阵 $B$ ，使得 $AB = I$ ，则 $B$ 称作矩阵 $A$ 的逆元，记作 $A^{-1}$ 。对于逆元我们可以使用高斯消元求解。我们对矩阵 $(A \ | \ I)$ 进行高斯消元，最后会得到 $(I \ | \ B)$ (若无法把左边化为乘法单位元，则矩阵 $A$ 不存在逆元)，则 $B$ 就为 $A$ 的逆元。

矩阵与线性方程组

对于线性方程组

\begin{cases} a_{1,1} x_1 + a_{1,2} x_2 + \dots + a_{1,n} x_n = b_1 \\ a_{2,1} x_1 + a_{2,2} x_2 + \dots + a_{2,n} x_n = b_2 \\ \vdots \\ a_{m,1} x_1 + a_{m,2} x_2 + \dots + a_{m,n} x_n = b_m \end{cases}

将未知数的系数写成矩阵的形式，用系数所在的矩阵的行表示未知数，我们就得到了线性方程组的矩阵 (增广矩阵) 表达形式：

\begin{pmatrix} \begin{array}{ccccc|c} a_{1,1} & a_{1,2} & a_{1,3} & \dots & a_{1,n} & b_1 \\ a_{2,1} & a_{2,2} & a_{2,3} & \dots & a_{2,n} & b_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{m,1} & a_{m,2} & a_{m,3} & \dots & a_{m,n} & b_m \\ \end{array} \end{pmatrix}

对于线性方程组，我们通常会使用消元来求解。在矩阵表示下的线性方程组可以用高斯消元来求解。高斯消元是通过对矩阵进行初等变换，以保证在方程的解不变的情况下求出方程的解。一般来说步骤如下 (记增广矩阵为 $M$ )：

枚举变量 $i$ ( $i \in [1,m]$ ) 表示当前要对未知元 $x_i$ 进行消元操作。
寻找最大的 $j \in [i,m]$ ，使得 $a_{j, i} \ne 0$ ，交换 $M_i \longleftrightarrow M_j$ 。
将交换后的矩阵的第 $i$ 行的未知元 $x_i$ 的系数化为 $1$ ，即: $a_{i,j} \leftarrow \frac{a_{i,j}}{a_{i,i}}$ ( $j \in [1,m]$ )。
用矩阵的第 $i$ 行对矩阵的第 $j$ ( $j \in [i + 1,m]$ ) 行进行消元操作，即： $a_{j,k} \leftarrow a_{j,k} - a_{j,k} \times a_{j,i}$ 。
重复上述操作直到 $i > n$ 或者找不到满足条件 $2$ 中的 $j$ 。

最后的结果可能会有以下三种

如果 $i < n$ ，且存在 $j$ 使得 $a_{j,n} > 0$ ，则原线性方程组无解。
如果 $i < n$ ，且对于 $\forall j$ 满足 $a_{j,n} = 0$ ，则原线性方程组有无数解。
否则原线性方程组有唯一解。

洛谷 P3389 Code

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int N = 105;
6
constexpr double eps = 1e-8;
7

8
class Matrix {
9
  double mat[N][N] = {{0}};
10
  int size = 0;
11

12
  public:
13
  Matrix() = default;
14

15
  void input_matrix() {
16
    cin >> size;
17

18
    for (int i = 0; i < size; i++)
19
      for (int j = 0; j <= size; j++)
20
        cin >> mat[i][j];
21
  }
22

23
  int guess() {
24
    int i, j, r = 0;
25
    for (int c = 0; c < size; c++) {
26
      int t = r;
27
      for (i = t + 1; i < size; i++) {
28
        if (abs(mat[i][c]) > abs(mat[t][c])) {
29
          t = i;
30
        }
31
      }
32

33
      if (abs(mat[t][c]) < eps) continue;
34

35
      for (i = c; i <= size; i++) {
36
        swap(mat[t][i], mat[r][i]);
37
      }
38

39
      for (i = size; i >= c; i--) {
40
        mat[r][i] /= mat[r][c];
41
      }
42

43
      for (i = r + 1; i < size; i++) {
44
        if (abs(mat[i][c]) > eps) {
45
          for (j = size; j >= c; j--) {
46
            mat[i][j] -= mat[r][j] * mat[i][c];
47
          }
48
        }
49
      }
50

51
      r++;
52
    }
53

54
    if (r < size) {
55
      return -1;
56
    }
57

58
    for (i = size - 1; i >= 0; i--) {
59
      for (j = i + 1; j < size; j++) {
60
        mat[i][size] -= mat[i][j] * mat[j][size];
61
      }
62
    }
63

64
    return 1;
65
  }
66

67
  int get_size() const { return size; }
68

69
  double get_solution(int i) const { return mat[i][size]; }
70
};
71

72
int main() {
73
  ios::sync_with_stdio(false);
74
  cin.tie(nullptr);
75
  cout.tie(nullptr);
76

77
  Matrix matrix;
78

79
  matrix.input_matrix();
80

81
  if (matrix.guess() == -1) {
82
    cout << "No Solution\n";
83
  } else {
84
    for (int i = 0; i < matrix.get_size(); i++) {
85
      double answer = matrix.get_solution(i);
86
      if (abs(answer) < eps) {
87
        answer = 0;
88
      } else {
89
        answer = round(answer * 100.00) / 100.00;
90
      }
91

92
      cout << setiosflags(ios::fixed) << setprecision(2) << answer << "\n";
93
    }
94
  }
95

96
  return 0;
97
}

洛谷 P2455 Code

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 110;
6
const double eps = 1e-8;
7
int n;
8
double a[N][N];
9

10
int gauss() {
11
  int i, j, c, r = 0;
12

13
  for (c = 0; c < n; c ++) {
14
    int t = r;
15
    for (i = t + 1; i < n; i ++)
16
      if (abs(a[i][c]) > abs(a[t][c])) t = i;
17

18
    if (abs(a[t][c]) < eps) continue;
19

20
    for (i = c; i <= n; i ++) swap(a[t][i], a[r][i]);
21

22
    for (i = n; i >= c; i --) a[r][i] /= a[r][c];
23

24
    for (i = r + 1; i < n; i ++)
25
      if (abs(a[i][c]) > eps)
26
        for (j = n; j >= c; j --)
27
          a[i][j] -= a[r][j] * a[i][c];
28

29
    r ++;
30
  }
31

32
  if (r < n) {
33
    for (i = r; i < n; i ++)
34
      if (abs(a[i][n]) > eps) return 2;
35
    return 1;
36
  }
37

38
  for (i = n - 1; i >= 0; i --)
39
    for (j = i + 1; j < n; j ++)
40
      a[i][n] -= a[i][j] * a[j][n];
41

42
  return 0;
43
}
44

45
int main() {
46
  scanf("%d", &n);
47

48
  for (int i = 0; i < n; i ++) {
49
    for (int j = 0; j <= n; j ++) {
50
      scanf("%lf", &a[i][j]);
51
    }
52
  }
53

54
  int t = gauss();
55
  if (t == 2) puts("-1");
56
  else if (t == 1) puts("0");
57
  else {
58
    for (int i = 0; i < n; i ++) {
59
      printf("x%d=", i + 1);
60
      if (abs(a[i][n]) < eps) a[i][n] = 0;
61
      printf("%.2lf\n", a[i][n]);
62
    }
63
  }
64

65
  return 0;
66
}

除了高斯消元外，我们还有另外一种消元的方式——高斯-约旦消元，下面给出代码。

洛谷 P3389 Code

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int N = 105;
6
constexpr double eps = 1e-8;
7

8
class Matrix {
9
  double mat[N][N] = {{0}};
10
  int size = 0;
11

12
  public:
13
  Matrix() = default;
14

15
  void input_matrix() {
16
    cin >size;
17

18
    for (int i = 0; i < size; i++)
19
      for (int j = 0; j <= size; j++)
20
        cin >mat[i][j];
21
  }
22

23
  int guess() {
24
    int i, j, r = 0;
25
    for (int c = 0; c < size; c++) {
26
      int t = r;
27
      for (i = t + 1; i < size; i++) {
28
        if (abs(mat[i][c]) abs(mat[t][c])) {
29
          t = i;
30
        }
31
      }
32

33
      if (abs(mat[t][c]) < eps) continue;
34

35
      for (i = c; i <= size; i++) {
36
        swap(mat[t][i], mat[r][i]);
37
      }
38

39
      for (i = size; i >= c; i--) {
40
        mat[r][i] /= mat[r][c];
41
      }
42

43
      for (i = r + 1; i < size; i++) {
44
        if (abs(mat[i][c]) eps) {
45
          for (j = size; j >= c; j--) {
46
            mat[i][j] -= mat[r][j] * mat[i][c];
47
          }
48
        }
49
      }
50

51
      r++;
52
    }
53

54
    if (r < size) {
55
      return -1;
56
    }
57

58
    for (i = size - 1; i >= 0; i--) {
59
      for (j = i + 1; j < size; j++) {
60
        mat[i][size] -= mat[i][j] * mat[j][size];
61
      }
62
    }
63

64
    return 1;
65
  }
66

67
  int get_size() const { return size; }
68

69
  double get_solution(int i) const { return mat[i][size]; }
70
};
71

72
int main() {
73
  ios::sync_with_stdio(false);
74
  cin.tie(nullptr);
75
  cout.tie(nullptr);
76

77
  Matrix matrix;
78

79
  matrix.input_matrix();
80

81
  if (matrix.guess() == -1) {
82
    cout << "No Solution\n";
83
  } else {
84
    for (int i = 0; i < matrix.get_size(); i++) {
85
      double answer = matrix.get_solution(i);
86
      if (abs(answer) < eps) {
87
        answer = 0;
88
      } else {
89
        answer = round(answer * 100.00) / 100.00;
90
      }
91

92
      cout << setiosflags(ios::fixed) << setprecision(2) << answer << "\n";
93
    }
94
  }
95

96
  return 0;
97
}

行列式

定义

对于矩阵 (通常为方阵) $A_{n \times n}$ ，我们定义其行列式为：

\det(A) = \sum_{p \in P_n} \operatorname{sgn}(p) \prod_{i=0}^{n} A_{i,p_i}

其中 $P_n$ 表示长度为 $n$ 的所有排列的集合， $\operatorname{sgn}(p)$ 表示 $(-1)^{排列 p 中的逆序对的个数}$ 。这里有一张快速求解行列式的图：

快速求解行列式

性质

对矩阵做行 (列) 交换，行列式反号。根据排列的奇偶性，我们可以知道交换一个排列中的一对元素，其排列奇偶性也会发生变化，所以 $\operatorname{sgn}(p) = -\operatorname{sgn}(p^{\prime})$ ，证毕。
对矩阵做行 (列) 数乘，行列式乘上同样的常数我们知道一个排列包含 $[1,n]$ 之间的所有整数，所以被修改的元素会在每个连乘中出现且每个连乘中仅出现一次，所以可以提到整个式子的前面，证毕。
对矩阵做行 (列) 加法，行列式不变。

求解行列式

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int N = 605;
6
int n;
7
long long p;
8

9
class Matrix {
10
  long long mat[N][N] = {{}};
11
  int size = 0;
12

13
  public:
14
  Matrix() = default;
15

16
  void get_input(int n) {
17
    size = n;
18

19
    for (int i = 1; i <= size; i++) {
20
      for (int j = 1; j <= size; j++) {
21
        cin >mat[i][j];
22
      }
23
    }
24
  }
25

26
  long long det(const long long ModValue) {
27
    long long retval = 1, sgn = 1;
28

29
    for (int i = 1; i <= size; i++) {
30
      for (int j = i + 1; j <= size; j++) {
31
        while (mat[i][i]) {
32
          long long divide = mat[j][i] / mat[i][i];
33

34
          for (int k = 1; k <= size; k++) {
35
            mat[j][k] = (mat[j][k] - divide * mat[i][k] % ModValue + ModValue) % ModValue;
36
          }
37

38
          sgn = -sgn;
39
          swap(mat[i], mat[j]);
40
        }
41

42
        sgn = -sgn;
43
        swap(mat[i], mat[j]);
44
      }
45
    }
46

47
    retval = sgn;
48
    for (int i = 1; i <= size; i ++) {
49
      retval = retval * mat[i][i] % ModValue;
50
    }
51

52
    return (retval + ModValue) % ModValue;
53
  }
54
} matrix;
55

56
int main() {
57
  ios::sync_with_stdio(false);
58
  cin.tie(nullptr);
59
  cout.tie(nullptr);
60

61
  cin >n >p;
62

63
  matrix.get_input(n);
64

65
  cout << matrix.det(p) << '\n';
66

67
  return 0;
68
}

矩阵树定理 (根本听不懂啊)

矩阵树定理是把图的生成树个数和矩阵行列式联系起来的一个定理。矩阵树定理对于无自环 (允许重边) 的有向图 $G = (V, E)$ 。设出度矩阵 $D(G)$ ，其中 $\forall u \in V$ ， $D_{u,u}$ 表示点 $u$ 的出度，其余位置全部为 $0$ 。而 $A(G)$ 表示图 $G$ 的邻接矩阵，其中 $a_{i,j}$ 表示 $i \to j$ 的边的数量 ( $i,j \in V$ )。那么可以得到对应的拉普拉斯矩阵 $L(G) = D(G) - A(G)$ 。 $L(G)$ 关于 $L(G)_{k,k}$ 的余子式是以 $k$ 为根节点的内向生成树的个数。

余子式对于矩阵 $A$ ， $A_{i,j}$ 的余子式定义为 $A$ 去掉第 $i$ 行第 $j$ 列的矩阵行列式。

线性基

定义

在 $K$ 维异或空间下，一个向量可以用一个 $[0,2^k)$ 内的整数表示 (即该数在二进制意义下的每一位都表示一个向量)。对于一组向量 $S = \{v_1, v_2, v_3, \dots, v_n\}$ ：

$S$ 中数字的异或和称为这些向量的线性组合。
若不存在非空子集 $W \subset S$ 满足 $\bigotimes_{v \in W} v = 0$ ，则称 $S$ 线性无关。
$S$ 的所有子集的异或和的集合构成 $S$ 的张成，记作 $\operatorname{Span}(S)$ 。
$S$ 的线性基是一个线性无关的向量集合 $W$ ，满足 $\operatorname{Span}(W) = \operatorname{Span}(S)$ 。
$K$ 维空间的线性基 $W$ 满足 $\left\vert W \right\vert = K$ 。