ZROI 暑期高端峰会 A班 Day2 线性代数

印度阿三17 2019-08-20

展开全文

高斯消元

很普及组，不讲了

当主元没有逆的时候可以辗转相除。

如果也没有带余数除法……没救了

逆矩阵

我们定义矩阵 $A$ 的逆矩阵为 $A^{-1}$，满足 $AA^{-1}=A^{-1}A=I$。

有些矩阵可逆，有些不可逆。

求逆矩阵可以用类似高斯消元的方式。就是想象 $A$ 矩阵的右边是个逆矩阵，等式右边是个单位矩阵，我们就是要解出这个逆矩阵。

具体可以把 $A$ 消成单位矩阵，那么右边的逆矩阵应该和等式右边的矩阵一样，就求完了。

CF446D

$n$ 个点的图，$k$ 个是关键点，要求出从第 $i(1\le i\le n)$ 个点开始随机游走，第一个碰到的关键点是 $j(1\le j\le n)$ 的概率。

$n\le 500$

（欸，题意真的是这样？）

$g_i$ 表示期望经过多少次 $i$ 点。

\[g_i=\sum_{j=1}^np_{j\rightarrow i}g_j [i=s]\]

把 $g$ 和 $p$ 写成矩阵 $g$ 和 $P$（注意 $g$ 其实是个向量）

\[g=P\times g \begin{bmatrix}0\\0\\\dots\\1\\0\\\dots\end{bmatrix}\]

\[(I-P)\times g=\dots\]

求逆即可。

矩阵快速幂

更普及组，不讲了

不过有个有趣的东西：

给定 $n\times n$ 矩阵 $A$，$T$ 组询问，每次给定正整数 $m$ 和向量 $b$，求 $A^m\times b$。

大家应该都会 $O(Tn^3\log m)$。

但是有更快的做法：

预处理出 $A^{2^i}$。这一部分 $O(n^3\log m)$。

每次询问发现就是 $A^{2^{i_1}}\times A^{2^{i_2}}\cdots\times b$。

从右往左乘可以做到 $O(Tn^2\log m)$。

行列式

定义：一个 $n\times n$ 矩阵 $A$ 的行列式是：

\[\sum\limits_{G\in S_n}(-1)^{\mathrm{sgn}(G)}\prod A_{i,G_i}\]

$G$ 是 $1$ 到 $n$ 的排列（或者说置换），$\mathrm{sgn}(G)$ 表示 $G$ 是偶置换则是 $0$ 否则是 $1$。

有性质：$\det(AB)=\det(A)\det(B)$，其中 $A,B$ 都是 $n\times n$ 矩阵。

行列式的代数余子式：$C_{i,j}=(-1)^{i j}M_{i,j}$

余子式：$M_{i,j}$ 表示去掉第 $i$ 行和第 $j$ 列后剩下的 $(n-1)\times (n-1)$ 矩阵的行列式。

行列式可以按行展开 $\det(A)=\sum\limits_{j=1}^na_{i,j}C_{i,j}$。

有什么用？可以用来求 $n$ 维?()&)!$()#@>的体积。

比如，以二维为例，一个平行四边形的邻边向量 $a,b$，那么它的面积是 $\det\begin{bmatrix}a.x&a.y\\b.x&b.y\end{bmatrix}$。

三维同理，一个立方体的？？？向量 $a,b,c$，体积是 $\det\begin{bmatrix}a\\b\\c\\\end{bmatrix}$。

发现一个三角形的面积是对应的平行四边形的 $\frac{1}{2}=\frac{1}{2!}$，一个三棱锥的面积是对应的四棱柱的 $\frac{1}{6}=\frac{1}{3!}$。

那么有推论：$x_i\ge 0,\sum\limits_{i=1}^{d}x_d\le s$ 在 $d$ 维坐标系上的体积是 $\dfrac{s^d}{d!}$。因为 $\begin{bmatrix}s&0&0&\dots&0\\0&s&0&\dots&0\\\dots\\0&0&0&\dots&s\end{bmatrix}$ 的行列式是 $s^d$。

行列式怎么求？对于一个上三角矩阵，行列式是对角线所有数的乘积。

交换两行，行列式不变。一行加上另一行的若干倍，行列式不变。交换两行，行列式变成相反数。

高斯消元即可。

THUPC 2017 E

给 $n-1$ 维空间中的 $n 1$ 个点，求他们凸包的体积。

$n\le 35$，点的每一维坐标都是 $0$ 或 $1$。

如果是 $n$ 个点，那就是上面的问题，求个行列式走人。

但是是 $n 1$ 个点。

有个结论：随便选 $n$ 个点（$n 1$ 种选法），求出凸包的体积，它们的和再除以 $2$ 就是答案。

感受一下发现很对，交了一发也过了（？？？），那就这样了。

矩阵树定理

一个图的生成树个数是度数矩阵减去邻接矩阵，然后去掉一行一列（哪行哪列随便选，但是必须得是第 $i$ 行第 $i $ 列）的行列式。

推论：完全图的生成树个数是 $n^{n-2}$。

对于以 $i$ 为根的向外树形图个数，变成入度矩阵减去邻接矩阵，去掉第 $i$ 行第 $i$ 列的行列式。向内的树形图就变成出度矩阵减邻接矩阵。

Best Theorem

$n$ 个点的有向图的欧拉回路条数为任意一个点的树形图个数*(所有点出度-1)!的乘积。

UOJ226

$n$ 个点，边不超过 $n$ 条的无向连通图，每条边重复 $t_i$ 次，问欧拉回路个数。

$n,t\le 1000$。

对于树的情况，先定向，因为欧拉回路，所以出去的边和回来的边数量相等，那么方案数就是 $\prod\binom{t_i}{t_i/2}$。

用上面的定理，随便指定一个根，就是 $\prod\binom{t_i}{t_i/2}t_i/2\prod(deg_u-1)!$。

如果有一个环，那么不在环上的边很简单，然后随便选环上一条边，枚举这条边有多少往左多少往右，就能推出来环上所有的边多少向左，多少向右。

$O(nt)$。

Band 矩阵

主对角线和左右 $d$ 条对角线有数，其他都是 $0$ 的矩阵。

消元可以做到 $O(nd^2)$。

例题

$n\times m$ 的矩阵，求生成树个数。

直接做复杂度太高。发现矩阵实际上是类似 Band 矩阵的，可以稍微优化一下。

CF963E

在平面上走，一开始在原点，每次随机一个方向走 $1$（上下左右的概率给定），问走到离原点距离超过 $r$ 的步数期望。

$r\le 50$

弄个矩阵，发现和 Band 矩阵也很像，直接上即可。$O(r^4)$。

还有一种更快的方式，给在左半圆周上的每个期望都设个元，那么往右推能用这些元表示每个点的期望。

那么在最右半周上，就可以有一些等式，消元就好了。复杂度变成 $O(n^3)$。

线性空间

在一个数域上，关于加减法和数乘的一个封闭空间。

生成空间：对于一个向量组 $x_i$，那么其生成空间是 $\sum a_ix_i(a_i\in \text{向量组定义在的数域})$。

线性无关：不存在 $a_i$（不全为 $0$），使得 $\sum a_ix_i=0$。

基：极大线性无关组。

维数：基的大小。

秩：生成的线性空间的维数（不就是维数？）（dls：当成一样的应该问题不大）

小结论：$\bmod p$ 意义下，如果维数是 $d$，那么有 $p^d$ 个元素。

定理：矩阵的行向量的秩（称为行秩）等于列向量的秩（称为列秩）。

求一个矩阵的秩：直接高斯消元，消完后非零向量的个数就是秩。

线性基

数域是 $F_2$，每个元素是 $d$ 维向量的线性空间的基。

以类似高斯消元的方式构造。

那么秩不会超过 $d$。

拟阵

md 不想管了……咕了。

看洛咕日报去。

拟阵是二元组 $(V,I)$，$V$ 是元素集合，$I$ 是 $V$ 的一些子集的集合。

[WC2011]XOR

相信大家都会。

HDU多校1B

……

肯定线性基。对于每个终点都维护一个。

线性基的元素改一改，二元组 $(val,pos)$，$val$ 就是值，$pos$ 是异或出 $val$ 所用到的数的位置的最小值的最大值。

每次插入一个数，当一位上没有数时，随便搞；当一位上有数时，比较，如果更优就替代，把没那么优的往下继续消。

SRM 620 Hard

……

设一堆变量表示 $(i,j)$ 选不选，然后可以每行列个方程，每列列个方程，每个质因子列个方程。

答案是 $2^{\text{阶}-\text{秩}}$。

Cramer 法则

方程组的解 $x_i=\dfrac{\det(A\text{的第}i\text{列都换成等号右边的东西})}{\det(A)}$。

伴随矩阵

$A$ 的余子矩阵……字面意思，$C$

$A$ 的伴随矩阵 $\mathrm{adj}(A)=C^{T}$

性质：$A\mathrm{adj}(A)=\mathrm{adj}(A)A=\det(A)I$

实际上 $(A\mathrm{adj}(A))_{i,i}=\sum\limits_{j=1}^na_{i,j}C_{i,j}=\det(A),(A\mathrm{adj}(A))_{i,j}=\sum\limits_{k=1}^na_{i,k}C_{j,k}=0(i\ne j)$。

（前面是上面的推论，后面相当于把第 $j$ 行变得和第 $i$ 行一样，此时行列式一定为 $0$）

所以，一个矩阵可逆当且仅当其行列式在该数域中可逆。

因为如果 $A$ 可逆，那么 $1=\det(I)=\det(AA^{-1})=\det(A)\det(A^{-1})$，那么 $A^{-1}=\det(A)^{-1}\mathrm{adj}(A)$。

……（以后来补）

Schwartz–Zippel 引理

一个多项式在模 $p$ 意义下，如果每个值都是随机的，那么整个 $=0$ 的概率不超过次数 $/p$

二分图是否存在完备匹配？

（一个矩阵的积和式 $\mathrm{perm}(A)=\sum\limits_{G\in S_n}\prod\limits_{i=1}^nA_{i,G_i}$，和行列式相比少乘了符号）

如果把每条边看成一个变量，边 $(u,v)$ 在矩阵第 $u$ 行第 $v$ 列加一个 $x_i$，那么有完备匹配当且仅当积和式不是 $0$。

很好理解，积和式是枚举了每个排列。

如果可以快速算积和式，那么不停给每个变量随机赋值，随机若干次之后若积和式始终为 $0$，就没有，否则有。

但是积和式没法快速算。

可以改一下，求行列式。随机交换行列，再计算，抵消成 $0$ 的概率不大。（是这样吗？？？没听清……）

（这东西和这引理有半毛钱关系吗……）

Tutte 矩阵

定义一个图的 Tutte 矩阵（那个符号不会写，不管了） $(\widetilde{A}(G))_{i,j}=\begin{cases}x_{i,j}&e_{i,j}=1,i<j\\-x_{j,i}&e_{j,i}=1,i>j\\0&other\end{cases}$。

图 $G$ 有完备匹配当且仅当 $\det \widetilde{A}(G)\ne 0$。

设 $G$ 是个有完备匹配的图，那么将点 $i,j$ 从 $G$ 删掉后仍有完备匹配当且仅当 $(\widetilde{A}(G)^{-1})_{i,j}\ne 0$。

图 $G$ 的最大匹配大小是 $\frac{1}{2}\mathrm{rank}(\widetilde{A}(G))$。

Sherman–Morrison 公式

$A$ 是 $n\times n$ 矩阵，$u,v$ 是 $n$ 维列向量。那么 $A uv^{T}$ 可逆当且仅当 $1 v^{T}A^{-1}u\ne 0$。此时 $(A uv^{T})^{-1}=A^{-1}-\frac{A^{-1}uv^{T}A^{-1}}{1 v^{T}A^{-1}u}$。

$A$ 是 $n\times n$ 矩阵，$U$ 是 $n\times k$ 矩阵，$V$ 是 $k\times n$ 矩阵，$B=A UV$，那么，当 $(I_k VA^{-1}U)$ 可逆时，$B^{-1}=A^{-1}-A^{-1}U(I_k VA^{-1}U)^{-1}VA^{-1}$。

所以可以在 $O(n^2k)$ 复杂度内将原矩阵加上一个秩为 $k$ 的矩阵，动态维护逆矩阵。（蛤？咋搞？）

（这种东西毒瘤都不一定会考……）

（咕了）

动态图传递闭包

支持加边删边，和问一点是否可达另一点（就是传递闭包）

设邻接矩阵为 $A$，那么传递闭包后邻接矩阵是 $I A A^2 A^3 \dots=\frac{1}{1-A}$，所以就是动态逆，用上面的方法解决。

ICPC2018 Nanjing F

有向图，随机游走，每条边有概率，对每对点求出期望步数。

$n\le 500$

$f_{i,j}$ 表示从 $i$ 走到 $j$ 的期望步数。特别的，$f_{i,i}=0$，这样可以避免重复走来走去的问题。

$f_{i,j}=1 \sum\limits_{k=1}^np_{i,k}f_{k,j}$

$g_i$ 表示从 $i$ 走回 $i$ 的期望步数。

$g_i=1 \sum\limits_{k=1}^np_{i,k}f_{k,i}$

写成矩阵的形式：（$J$ 是全 $1$ 矩阵）

$F=J-G PF$

$(I-P)F=J-G$

现在就是要求 $G$。

令 $q_{k,i}$ 表示从 $i$ 走 $k$ 步后停在 $i$ 的概率。

令 $\Pi_i=\lim\limits_{k\rightarrow \infty}q_{k,i}$。（稳定分布）

此时从 $i$ 走再走回 $i$ 期望已经趋于稳定（emmm...dls：不够严谨但的确是对的），所以 $\lim\limits_{k\rightarrow \infty}q_{k,i}g_i=1$。

所以 $g_i=\frac{1}{\Pi_i}$。

但是 $\mathrm{rank}(I-P)=n-1$，不可逆。

没事，继续消元，那么消出来前 $n-1$ 行前 $n-1$ 列，

（不管了不管了…………………………………………………………………………………………）

咕了。

特征值和特征向量

对于 $n\times n$ 的矩阵 $A$，如果存在数 $\lambda$ 和非零列向量 $x$ 满足 $Ax=\lambda x$，那么 $\lambda$ 是 $A$ 的特征值，$x$ 是 $A$ 的特征向量。

那么 $Ax=\lambda I x$。$(\lambda I-A)x=0$。因为 $x$ 不为零向量，所以 $\det(\lambda I-A)=0$，也就是 $\lambda I-A$ 不满秩。

我们称 $\det(\lambda I-A)=0$ 为 $A$ 的特征多项式，元是 $\lambda$。特征多项式是 $n$ 次的，他的 $n$ 个根就是 $A$ 的所有特征值。（可能有相等的根）

对于上三角矩阵，所有的特征值就是主对角线上的所有值。

如果有 $n$ 个线性无关的特征向量 $x_i$（当且仅当 $A$ 满秩），那么有 $A\begin{bmatrix}x_1&x_2&\cdots&x_n\end{bmatrix}=\begin{bmatrix}x_1&x_2&\cdots&x_n\end{bmatrix}\begin{bmatrix}\lambda_1&0&0&\cdots&0\\0&\lambda_2&0&\cdots&0\\\cdots\\0&0&0&\cdots&\lambda_n\end{bmatrix}$。