线性代数简记
stripe_python · · 算法·理论
Guass-Jordan 消元
考虑线性方程组
- 交换两行;
- 某一行乘上非零数
k ; - 某一行乘上数
k 加到另一行。
形如
矩阵求逆
初等变换本质是对矩阵的线性变换,其可以用初等矩阵
在 Guass-Jordan 消元的过程中,我们得到
因此有
实际上,在消元过程中记录矩阵
行列式
定义
其中
结论:
-
- 矩阵
A 可逆当且仅当\det (A) \ne 0 ,此时\det(A^{-1})=\det^{-1}(A) ; - 上三角矩阵的行列式等于对角线元素之积。
由如上结论,在 Guass-Jordan 消元时,对于每一次初等变换记录行列式的变化即可计算,复杂度
积和式
定义
其中
组合意义是排列计数 / 二分图完美匹配计数。有
Ryser 公式给出一个
Matrix-Tree 定理
对于无向图
- 度数矩阵
D :D_{i,i} 为节点i 的度数,其它位置为0 ; - 邻接矩阵
G :D_{i,j} 为1 当且仅当i,j 有边,否则为0 。 - Laplace 矩阵:
L=D-G 。
Matrix Tree 定理指出,图
如果无向图
扩展:如果
如果要算的是
BEST 定理
设
其中,
LGV 引理
在有向无环图上,记
矩阵
这刻画了
注意
板子
::::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;
}
};
::::