线性代数简记

· · 算法·理论

Guass-Jordan 消元

考虑线性方程组 A \mathbf{x} = \mathbf{b},通过如下三种初等变换使得 A 化为 I:

形如 I \mathbf{x}=\mathbf{b'} 的方程显然可解。

矩阵求逆

初等变换本质是对矩阵的线性变换,其可以用初等矩阵 E 表示,且 E 可逆。

在 Guass-Jordan 消元的过程中,我们得到 E_k E_{k-1} \cdots E_1A = I。

因此有 A^{-1}=E_k E_{k-1} \cdots E_1。称为 A 的初等矩阵分解。

实际上,在消元过程中记录矩阵 B,每次初等变换时对 B 进行同样的操作,最终即有 B=A^{-1}。复杂度 O(n^3)。

行列式

定义

\det (A)=\sum (-1)^{\operatorname{inv}(p)} \prod_{i=1}^n A_{i,p_i}

其中 p 是一个 1 \sim n 的排列,\operatorname{inv}(p) 为逆序对数。暴力计算复杂度 O(n \times n!)。

结论:

由如上结论,在 Guass-Jordan 消元时,对于每一次初等变换记录行列式的变化即可计算,复杂度 O(n^3)。

积和式

定义

\operatorname{per}(A)=\sum \prod_{i=1}^n A_{i,p_i}

其中 p 是一个 1 \sim n 的排列。计算一般矩阵的积和式是 #P-complete 问题。

组合意义是排列计数 / 二分图完美匹配计数。有 \operatorname{per}(A) \equiv \det (A) \pmod 2。

Ryser 公式给出一个 O(n^2 2^n) 的求解方法:

\operatorname{per}(A) =(-1)^n \sum _{S \subseteq \{1,2,\cdots,n\}} (-1)^{|S|} \prod_{i=1}^n \sum_{j \in S} A_{i,j}

Matrix-Tree 定理

对于无向图 G,定义:

Matrix Tree 定理指出,图 G 的生成树个数等于 \det (L'),L' 是 L 丢掉任意一行 / 列的矩阵。

如果无向图 G 的边带权,则 \det (L')=\sum \limits_{T} \prod \limits_{e \in T} w_e。此时度数变为出边边权和,邻接矩阵需要记边权。

扩展:如果 G 是有向图,则 \det (L')=\sum \limits_{T} \prod \limits_{e \in T} w_e。设 D 是入度矩阵,L' 是 L 丢掉 u 行 u 列的矩阵,则 L' 算的是以 u 为根的根向树数目。

如果要算的是 \sum \limits_{T} \sum\limits_{e \in T} w_e,则可以令 G_{i,j}=1+w_{i,j} \times x,其中 x 为形式幂级数的占位符,实现化积为和的效果。

BEST 定理

设 G 是有向欧拉图,则 G 的欧拉回路总数为

t^{\text{root}}(G,k) \prod_{v \in V} (\text{deg}_v-1)!

其中,t^{\text{root}}(G,k) 表示以 k 为根的根向生成树数目,k 可任取。

LGV 引理

在有向无环图上,记 \omega(P)=\prod\limits_{e \in P} w_e,e(u,v)=\sum\limits_{P:u \to v} \omega(P)。构造

M=\begin{bmatrix} e(A_1,B_1) & e(A_1,B_2) & \cdots & e(A_1,B_n)\\ e(A_2,B_1) & e(A_2,B_2) & \cdots & e(A_2,B_n)\\ \vdots & \vdots & \ddots & \vdots\\ e(A_n,B_1) & e(A_n,B_2) & \cdots & e(A_n,B_n)\\ \end{bmatrix}

矩阵 M 的行列式

\det M=\sum_{S : A \to B} (-1)^{\text{inv}(\sigma(S))} \prod_{i=1}^n \omega(S_i)

这刻画了 A \to B 的不相交路径 S 的带符号和。

注意 \det M 的组合意义是,存在偶数个交点的路径组权值减去存在奇数格交点的路径组权值。在特殊图上,如果有交路径必有奇数交点,则 \det M 计算的就是不交路径组权值和。

板子

::::info[代码]

template <class mint, int n, int m = n>
struct matrix {
    mint v[n][m];
    matrix() : v{} {}
    matrix(initializer_list<initializer_list<mint>> a) : v{} {
        int i = 0, j = 0;
        for (const auto& r : a) {
            j = 0;
            for (const auto& c : r) {
                if (i < n && j < m) v[i][j] = c;
                j++;
            } i++;
        }
    }
    mint* operator[] (int i) {return v[i];}
    const mint* operator[] (int i) const {return v[i];}
    matrix& operator+= (const matrix& o) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) v[i][j] += o[i][j];
        return *this;
    }
    matrix& operator-= (const matrix& o) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) v[i][j] -= o[i][j];
        return *this;
    }
    matrix& operator* (const mint& o) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) v[i][j] *= o;
        return *this;
    }
    matrix operator+ (const matrix& o) const {return matrix(*this) += o;}
    matrix operator- (const matrix& o) const {return matrix(*this) -= o;}
    matrix operator* (const mint& o) const {return matrix(*this) *= o;}
    friend matrix operator* (mint x, const matrix& a) {return a * x;}
    template <int k> matrix<mint, n, k> 
    operator* (const matrix<mint, m, k>& o) const {
        matrix<mint, n, k> r;
        for (int a = 0; a < n; a++)
            for (int c = 0; c < m; c++)
                for (int b = 0; b < k; b++)
                    r[a][b] += v[a][c] * o[c][b];
        return r;
    }
    matrix& operator*= (const matrix& o) {
        static_assert(n == m, "");
        return *this = *this * o;
    }
    static matrix I() {
        static_assert(n == m, "");
        matrix r;
        for (int i = 0; i < n; i++) r[i][i] = 1;
        return r;
    } 
    bool operator== (const matrix& o) const {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) 
                if (v[i][j] != o[i][j]) return false;
        return true;
    }
    bool operator!= (const matrix& o) const {return !(*this == o);}
    pair<bool, matrix> inv(int _n = n) const {
        matrix A = *this, R = I();
        for (int i = 0; i < _n; i++) {
            int p = -1;
            for (int j = i; j < _n; j++) 
                if (A[j][i] != 0) {
                    p = j; break;
                }
            if (p == -1) return {0, R};
            if (i != p) for (int j = 0; j < _n; j++) 
                swap(A[i][j], A[p][j]), swap(R[i][j], R[p][j]);
            mint ip = ~A[i][i];
            for (int j = 0; j < _n; j++) A[i][j] *= ip, R[i][j] *= ip;
            for (int k = 0; k < _n; k++) {
                if (k == i || A[k][i] == 0) continue;
                mint t = A[k][i];
                for (int j = 0; j < _n; j++) A[k][j] -= t * A[i][j], R[k][j] -= t * R[i][j];
            }
        }
        return {1, R};
    }
    mint det(int _n = n) const {
        matrix A = *this; mint res = 1;
        for (int i = 0; i < _n; i++) {
            int p = -1;
            for (int j = i; j < _n; j++) 
                if (A[j][i] != 0) {
                    p = j; break;
                }
            if (p == -1) return 0;
            if (i != p) {
                res = -res;
                for (int j = 0; j < _n; j++) swap(A[i][j], A[p][j]);
            }
            for (int k = i + 1; k < _n; k++) 
                while (A[k][i] != 0) {
                    mint t = A[i][i].val / A[k][i].val;
                    for (int j = i; j < _n; j++) A[i][j] -= t * A[k][j];
                    for (int j = i; j < _n; j++) swap(A[i][j], A[k][j]);
                    res = -res;
                }
            res *= A[i][i];
        }
        return res;
    }
};

::::