2025 Summer Day4

2026 年 2 月 26 日 星期四(已编辑)
5

2025 Summer Day4

Content：Math

Date：2025.7.20

内容

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

具体内容

矩阵

矩阵定义

定义

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

矩阵基本操作

  1. 矩阵加法：对于矩阵 Am×nA_{m \times n}, Bm×nB_{m \times n}, 我们定义矩阵加法为 Ci,j=Ai,j+Bi,jC_{i,j} = A_{i, j} + B_{i, j} 即矩阵对应位置上的元素之和。
  2. 标量乘法：对于矩阵 Am×nA_{m \times n} 和标量 xx, 我们定义矩阵的标量乘法为：
Ci,j=Ai,j×x C_{i, j} = A_{i, j} \times x
  1. 转置：对于矩阵 Am×nA_{m \times n}，其转置为:
AT=[Aj,i] A^{T} = \begin{bmatrix} A_{j, i} \end{bmatrix}
  1. 矩阵的拼接：对于矩阵 Am×n1A_{m \times n_1}，Bm×n2B_{m \times n_2}，其拼接为记为 (A ∣ B)(A \ | \ B)，其大小为 m×(n1+n2)m \times (n_1 + n_2)。
  2. 矩阵的乘法：对于矩阵 Am×nA_{m \times n} 和矩阵 Bn×kB_{n \times k}，其矩阵乘法定义为：
Ci,j=∑x=1nAi,x×Bx,j C_{i, j} = \sum_{x = 1}^{n} A_{i, x} \times B_{x, j}
其中 i∈[1,n]i \in [1,n]，j∈[1,k]j \in [1,k]。 对于矩阵乘法，有如下性质： 
+ 矩阵乘法具备分配律：$(A + B)C = AC + BC$；
+ 矩阵乘法具有结合律：$(AB)C = A(BC)$;
  1. 矩阵乘法单位元： 矩阵的乘法单位元 II 为矩阵主对角线上全部为 11，其余均为 00 的 0/10/1 矩阵。
  2. 矩阵的逆：如果对于矩阵 AA 存在矩阵 BB，使得 AB=IAB = I，则 BB 称作矩阵 AA 的逆元，记作 A−1A^{-1}。 对于逆元我们可以使用高斯消元求解。我们对矩阵 (A ∣ I)(A \ | \ I) 进行高斯消元，最后会得到 (I ∣ B)(I \ | \ B) (若无法把左边化为乘法单位元，则矩阵 AA 不存在逆元)，则 BB 就为 AA 的逆元。

矩阵与线性方程组

对于线性方程组

{a1,1x1+a1,2x2+⋯+a1,nxn=b1a2,1x1+a2,2x2+⋯+a2,nxn=b2⋮am,1x1+am,2x2+⋯+am,nxn=bm \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}

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

(a1,1a1,2a1,3…a1,nb1a2,1a2,2a2,3…a2,nb2⋮⋮⋮⋱⋮⋮am,1am,2am,3…am,nbm) \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}

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

  1. 枚举变量 ii (i∈[1,m]i \in [1,m]) 表示当前要对未知元 xix_i 进行消元操作。
  2. 寻找最大的 j∈[i,m]j \in [i,m]，使得 aj,i≠0a_{j, i} \ne 0，交换 Mi⟷MjM_i \longleftrightarrow M_j。
  3. 将交换后的矩阵的第 ii 行的未知元 xix_i 的系数化为 11，即: ai,j←ai,jai,ia_{i,j} \leftarrow \frac{a_{i,j}}{a_{i,i}} (j∈[1,m]j \in [1,m])。
  4. 用矩阵的第 ii 行对矩阵的第 jj (j∈[i+1,m]j \in [i + 1,m]) 行进行消元操作，即：aj,k←aj,k−aj,k×aj,ia_{j,k} \leftarrow a_{j,k} - a_{j,k} \times a_{j,i}。
  5. 重复上述操作直到 i>ni > n 或者找不到满足条件 22 中的 jj。

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

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

洛谷 P3389 Code

#include <bits/stdc++.h>

using namespace std;

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

class Matrix {
    double mat[N][N] = {{0}};
    int size = 0;

    public:
    Matrix() = default;

    void input_matrix() {
        cin >> size;

        for (int i = 0; i < size; i++)
            for (int j = 0; j <= size; j++)
                cin >> mat[i][j];
    }

    int guess() {
        int i, j, r = 0;
        for (int c = 0; c < size; c++) {
            int t = r;
            for (i = t + 1; i < size; i++) {
                if (abs(mat[i][c]) > abs(mat[t][c])) {
                    t = i;
                }
            }

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

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

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

            for (i = r + 1; i < size; i++) {
                if (abs(mat[i][c]) > eps) {
                    for (j = size; j >= c; j--) {
                        mat[i][j] -= mat[r][j] * mat[i][c];
                    }
                }
            }

            r++;
        }

        if (r < size) {
            return -1;
        }

        for (i = size - 1; i >= 0; i--) {
            for (j = i + 1; j < size; j++) {
                mat[i][size] -= mat[i][j] * mat[j][size];
            }
        }

        return 1;
    }

    int get_size() const { return size; }

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    Matrix matrix;

    matrix.input_matrix();

    if (matrix.guess() == -1) {
        cout << "No Solution\n";
    } else {
        for (int i = 0; i < matrix.get_size(); i++) {
            double answer = matrix.get_solution(i);
            if (abs(answer) < eps) {
                answer = 0;
            } else {
                answer = round(answer * 100.00) / 100.00;
            }

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

    return 0;
}

洛谷 P2455 Code

#include <bits/stdc++.h>

using namespace std;

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

int gauss() {
    int i, j, c, r = 0;
    
    for (c = 0; c < n; c ++) {
        int t = r;
        for (i = t + 1; i < n; i ++)
            if (abs(a[i][c]) > abs(a[t][c])) t = i;
        
        if (abs(a[t][c]) < eps) continue;
        
        for (i = c; i <= n; i ++) swap(a[t][i], a[r][i]);
        
        for (i = n; i >= c; i --) a[r][i] /= a[r][c];
        
        for (i = r + 1; i < n; i ++)
            if (abs(a[i][c]) > eps)
                for (j = n; j >= c; j --)
                    a[i][j] -= a[r][j] * a[i][c];
        
        r ++;
    }
    
    if (r < n) {
        for (i = r; i < n; i ++)
            if (abs(a[i][n]) > eps) return 2;
        return 1;
    }
    
    for (i = n - 1; i >= 0; i --)
        for (j = i + 1; j < n; j ++)
            a[i][n] -= a[i][j] * a[j][n];
            
    return 0;
}

int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j <= n; j ++) {
            scanf("%lf", &a[i][j]);
        }
    }
    
    int t = gauss();
    if (t == 2) puts("-1");
    else if (t == 1) puts("0");
    else {
        for (int i = 0; i < n; i ++) {
            printf("x%d=", i + 1);
            if (abs(a[i][n]) < eps) a[i][n] = 0;
            printf("%.2lf\n", a[i][n]);
        }
    }
    
    return 0;
}

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

洛谷 P3389 Code

#include <bits/stdc++.h>

using namespace std;

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

class Matrix {
    double mat[N][N] = {{0}};
    int size = 0;

    public:
    Matrix() = default;

    void input_matrix() {
        cin >size;

        for (int i = 0; i < size; i++)
            for (int j = 0; j <= size; j++)
                cin >mat[i][j];
    }

    int guess() {
        int i, j, r = 0;
        for (int c = 0; c < size; c++) {
            int t = r;
            for (i = t + 1; i < size; i++) {
                if (abs(mat[i][c]) abs(mat[t][c])) {
                    t = i;
                }
            }

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

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

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

            for (i = r + 1; i < size; i++) {
                if (abs(mat[i][c]) eps) {
                    for (j = size; j >= c; j--) {
                        mat[i][j] -= mat[r][j] * mat[i][c];
                    }
                }
            }

            r++;
        }

        if (r < size) {
            return -1;
        }

        for (i = size - 1; i >= 0; i--) {
            for (j = i + 1; j < size; j++) {
                mat[i][size] -= mat[i][j] * mat[j][size];
            }
        }

        return 1;
    }

    int get_size() const { return size; }

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    Matrix matrix;

    matrix.input_matrix();

    if (matrix.guess() == -1) {
        cout << "No Solution\n";
    } else {
        for (int i = 0; i < matrix.get_size(); i++) {
            double answer = matrix.get_solution(i);
            if (abs(answer) < eps) {
                answer = 0;
            } else {
                answer = round(answer * 100.00) / 100.00;
            }

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

    return 0;
}

行列式

定义

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

det⁡(A)=∑p∈Pnsgn⁡(p)∏i=0nAi,pi \det(A) = \sum_{p \in P_n} \operatorname{sgn}(p) \prod_{i=0}^{n} A_{i,p_i}

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

快速求解行列式
快速求解行列式

性质

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

求解行列式

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 605;
int n;
long long p;

class Matrix {
    long long mat[N][N] = {{}};
    int size = 0;

    public:
    Matrix() = default;

    void get_input(int n) {
        size = n;

        for (int i = 1; i <= size; i++) {
            for (int j = 1; j <= size; j++) {
                cin >mat[i][j];
            }
        }
    }

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

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

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

                    sgn = -sgn;
                    swap(mat[i], mat[j]);
                }

                sgn = -sgn;
                swap(mat[i], mat[j]);
            }
        }

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

        return (retval + ModValue) % ModValue;
    }
} matrix;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >n >p;

    matrix.get_input(n);

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

    return 0;
}

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

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

余子式 对于矩阵 AA，Ai,jA_{i,j} 的余子式定义为 AA 去掉第 ii 行第 jj 列的矩阵行列式。

线性基

定义

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

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

使用社交账号登录

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...