觉得应该开一个，所以就开了。
特征多项式和零化多项式
经典应用是常系数齐次线性递推。特征多项式是$\det(A-xI)$，零化多项式是$f(A)=0$。cayley-hamilton定理说明特征多项式是一个零化多项式。
常系数齐次线性递推中，转移矩阵的特征多项式就是递推式，求这一矩阵的幂$A^n$，可以把它对零化多项式取膜，变成矩阵大小内的次数的线性组合这样的。
特征向量和矩阵乘向量
如果一个矩阵的特征向量们是满秩的，那么它在乘一个向量的时候，可以把这个向量分解为特征向量的线性组合。不满秩也可能可以分解。
jordan标准型
矩阵可以分解为$A=PDP^{-1}$，其中$D$是特征值组成的对角矩阵，$P$是特征向量按相同顺序组成的矩阵。计算特征向量可以直接代入特征值得到一个方程组，主要问题还是怎么求特征多项式的根(这不弱于因式分解)。
$2\times 2$矩阵求逆!
主对角线交换，副对角线取反，全部除行列式。
stochastic matrix的无穷次幂
或译 马尔可夫矩阵。常见于概率期望相关dp或递推的转移矩阵。其性质是特征多项式的根的绝对值都在$(-1,1]$中，所以无穷次幂是收敛的。
这个题见于xix open cup gp of bytedance C。这里是$2\times 2$的情况。进行jordan分解，由于特征多项式是二次的，而我们已经知道了一个根，所以就得到另一个，对于高次的，根可能在膜意义下不存在，需要扩域。
幺模矩阵，格的三角基/hermite标准型
由一组向量的整系数线性组合得到的向量集合称为格。一组向量可以被消成一个hermite标准型，如果我们使用列向量，它大概就是一个下三角基。hermite标准型可以看成有限环线性基在所有整数上的推广。
幺模矩阵是行列式为$\pm 1$的矩阵。我们把一组向量拼成一个矩阵，那么乘一个幺模矩阵不改变它张成的格，因为幺模矩阵和矩阵乘法构成一个群，如果$Ax=y$，那么$AUU^{-1}x=y$，其中$A$是一组向量拼成的矩阵，$x$是一个系数向量，$y$是我们想要张出的向量，$U$是幺模的。
注意到，在gauss消元中用到的初等变换(把一行/列取负，交换两行/列，把一行/列的整数倍加到另一行/列)都是幺模的。所以我们可以进行辗转相除，但是很不幸，这会造成恐怖的中间表示膨胀，膨胀出来的东西的长度也是指数级的。
好消息是我们有一些办法。我们考虑对某些东西取膜，发现比如我们有$m$个向量，可以使用任何一个$m\times m$满秩子方阵的行列式的绝对值，设为$d$。把一个主对角线全是$d$的矩阵接在左边，那么我们每次进行一个操作之后，都可以用一次幺模的列变换给一个数取膜，具体可以看我画图，但是我还没画图，等我放假了我会画的/oh，不过你想看可能需要在放假的时候提醒我。
然后它的正确性在于我们可以用幺模变换把补的部分凑出来。设那个子方阵是$A$，那么根据伴随矩阵的结论有$dA^{-1}$是整数矩阵，并且它必然也是幺模的，所以有$dAA^{-1}=dI$，所以我们加的这些列必然可以由前面的列初等变换得到。选子方阵可以用有理数消一次，然后选择每个向量的第一个非零位所在的行，这个东西好像叫gram-schmidt orthogonalization。
现在考虑如果不满秩怎么做。我们把每一维当成一个向量，在上面消一下，最后只有若干维非零，对这些维跑上面的东西，然后根据消的时候的系数还原出剩下的维度即可。由于一个被消掉的维度必然是前面的维度在消它，所以这个东西确实是下三角的。这里和gram-schmidt是一致的。
但是这玩意中间用到的数长度还是太炸了，因为我们需要消一次，消一次，消一次，看起来只有矩阵大小实在是非常小的时候会用到它(比如poi2001 r1 A. superknight，二维的情况)。不过即便如此它还是很好的理论基础。
lattice basic reduce, the lll algorithm
好像被认为是多元的exgcd，但是多数情况下还是挺没用吧。也许以后闲着没事会学。据说和椭球法有关。
正交补
在一个线性空间中，一个子空间的正交补定义为所有和其中每个元素点积都为$0$的元素组成的集合。
正交补是线性代数中的某种对偶。考虑对偶的时候可以考虑一下这个。
在$\mathbf{F}_2$上的一些数数问题中看起来比较有效，考虑如下结论 :
引理 $\mathbf{F}_2$上秩为$r$的线性空间$A$的集合幂级数$F$，其法哇塔$\hat{F}$等于正交补的集合幂级数的$2^r$倍。
记$i\cdot j=\mathrm{parity}(i\operatorname{and}j)$，当然这里$\mathrm{parity}=\mathrm{popcnt}\bmod{2}$，那么法哇塔即为$[z^i]\hat{F}=\sum\limits_{j\in A}(-1)^{i\cdot j}$。如果存在$j\in A$使得$i\cdot j=1$，则对于任意$k$，$i\cdot k,i\cdot j\operatorname{xor}k$分别是$0,1$，于是$[z^i]\hat{F}=0$。否则$[z^i]\hat{F}=2^r$。这就是正交补的定义。
考虑如何求出$\mathbf{F}_2$上线性空间的正交补，我们跑一个线性基，消成这样的
\[\begin{bmatrix}{}I_r&X\end{bmatrix}\]，那么它的正交补是
\[\begin{bmatrix}X^\mathrm{T}&I_{m-r}\end{bmatrix}\]。证明考虑
\[\begin{bmatrix}I_r&X\end{bmatrix}\begin{bmatrix}X^\mathrm{T}\\I_{m-r}\end{bmatrix}=I_rX+XI_{m-r}=\mathbb{0}\]，而点积有分配律，所以所有$A$和所有$A^\perp$张出的向量都是正交的。所以我们也知道$m$维空间中秩为$r$的线性空间，其正交补秩为$2^{m-r}$。
cf1336e Chiori and Doll Picking
给一堆$m$维$01$向量和$k$，求选择若干个xor起来，有多少种方案使得popcnt是$k$。要求复杂度$O(2^\frac{m}{2})$。
考虑先跑个线性基，设大小为$r$。根号分治，如果$r\leq \frac{m}{2}$，直接跑。如果$r>\frac{m}{2}$，考虑做到$2^{m-r}$。
考虑设$F$是这些向量生成的空间$A$的集合幂级数，$G$是popcnt为$k$的向量的集合幂级数，那么要求即为$[z^0]FG$，其中乘法是对称差卷积。
根据刚才的引理，非零的位置都是$2^r$，并且它们就是$A$的正交补$A^\perp$，所以它们只有$2^{m-r}$个。
于是回去拆法哇塔。答案是$2^{-m}\sum\limits_i(-1)^{\mathrm{popcnt}(i)}[z^i]\hat{F}\hat{G}$，那么注意到$[z^i]\hat{G}$只和$\mathrm{popcnt}(i)$有关，于是我们只关心$\mathrm{popcnt}$为某个数的$[z^i]\hat{F}$之和。搜完$\hat{F}$中一共$2^{m-r}$个数之后，剩下的部分就是多项式复杂度了。
环空间，割空间
把图的点集划分成两部分，割是它们之间的边的集合。
每一条边看成一个维度，那么每个边集是$\mathbf{F}_2^m$上的向量。一个图的所有非树边确定的环(选择非树边和它端点在树上的链)称为基础环，树边确定的割(选择树边和所有跨过它的非树边)称为基础割。基础环通过xor生成所有的(不经过重边的)环，基础割通过xor生成所有的割。证明分别考虑其上的非树边和树边，归纳即可。
环空间和割空间互为正交补。证明考虑只需要证明基础环和基础割点积总是$0$，如果一个基础环和一个基础割不交那么点积是$0$，否则考虑如果交在一条树边，则必然也交在一条非树边，并且除此之外没有别的交了。
dzy loves chinese
无向图，每次删不超过$15$条边，求是否连通。
也就是判断有没有一个子集在割空间中。考虑转化到其正交补，环空间上，那么根据正交补的定义和点积的分配律，一个向量在割空间中当且仅当它和所有基础环点积为$0$，而它和所有基础环的点积又可以拆成它的每条边和所有基础环的点积之和。给一条边分配它和所有基础环的点积组成的向量作为权值，那么如果出现两条边的权值线性相关，它们就构成了一个和所有基础环点积为$0$的集合，于是这是一个割。但是基础环很多，注意到删边很少，所以我们给每个基础环随机赋一个$64$位向量，它有很大概率是保持秩的。
dzy loves chinese 改
无向图，每次删不超过$15$个点，求是否连通。
不是很会。
线性基交
感觉很多问题可以归结为这个。
现在有线性基$A,B$，我们尝试用$A$中元素$u$依次表示$B$中每个元素$v$，如果不能表示则把$v$插入$A$，否则设表示为$v=u_1+…+u_k+v_1+…+v_t$，就把$u_1,…,u_k$全都插入答案，而不插入$v_1,…,v_t$。复杂度是$O(\log^2 v)$。
考虑证明，答案显然可以被$A,B$表示，而我们每次不能用$A$表示一个$v$的时候，它确实不在交中，这里$A$中来自$B$的向量，相当于凑出了$B$的任意线性组合(已经被插入答案的是可以被凑出来的)，如果凑不出来说明真的没救。
先补一点抽代内容。
群的除法定义为，一个群$G$可以除掉它的一个子群$N$变成一个集合$G/H$，这个集合合并了满足$aN=bN$的$a,b$。当且仅当$N$满足对于所有$g\in G$都有$gN=Ng$时，这个集合是一个群，我们将这样的$N$称为正规子群。证明考虑只需要在每个等价类选择一个代表元，根据结合律有$a(bN)=(ab)N$，所以我们只要证明代表元的选择不影响乘法的结果，设有$a_1,a_2,b_1,b_2$，满足$a_1N=a_2N,b_1N=b_2N$，那么$a_1b_1N=a_1b_2N=a_1Nb_2=a_2Nb_2=a_2b_2N$。
群同态基本定理指出，如果存在$G\rightarrow H$的同态映射$f$，那么被映射到$H$中单位元的元素组成$G$的正规子群，称为$f$的核 $\mathrm{ker}(f)$，并且$f(G)$同构于$G/\mathrm{ker}(f)$。
拉格朗日定理指出，如果$G/N=H$，那么$\vert G\vert/\vert N\vert=\vert H\vert$。
线性群
一般线性群是所有可逆矩阵和矩阵乘法构成的群。特殊线性群是所有行列式为$1$的矩阵和矩阵乘法构成的群。
$\mathbf{F} _ q$上$n$维一般线性群的大小是$\prod\limits _ {i=0}^{n-1}(q^n-q^i)= n! _ q (q-1)^n q^\binom{n}{2}$，也就是第$i$个向量可以选择不在前面向量张成空间中的任何向量。特殊线性群，注意到行列式是一般线性群到乘法群的同态，
矩阵乘法
矩阵乘法可以看成左边的行点积右边的列，也可以看成右边的列作为系数表示左边的列的线性组合。并且在真正的线代题上后者往往更深刻。
code festival 2016 grand final H. AB=C Problem
给$C$，求有多少$A,B$满足$AB=C$。
考虑固定$A$，那么$B$的第$i$列表示$A$的各列的一个线性组合，这一线性组合是$C$的第$i$列。那么$A$的各列应该可以表示$C$的各列，如果可以表示那么$B$的每一列方案数都是$2^{n-\mathrm{rank}(A)}$，所以问题变成某个秩的超空间计数。猜测答案只和$r=\mathrm{rank}(C)$有关，证明考虑我们两边同时在两边分别乘两个可逆矩阵$P,Q$，有$AB=C\Leftrightarrow PABQ=PCQ$，可以转而计算$PA,BQ$的对数，由于$P,Q$可逆这是双射，所以只需要计算$AB=PCQ$的对数，而使用初等行列变换可以把$C$变成等价标准型。
考虑一个dp，设$dp(i,j,k)$表示$A$的前$i$列，秩为$j$，和$C$的列空间交的秩为$k$，转移考虑有$2^j$种方案让$j,k$都不变，有$2^n-2^j$种方案让$j$增加$1$，其中有一些让$k$也增加$1$，考虑线性基交的结论，我们考虑$C$中一个不能被$A$表示的元素，这有$2^{r-k}-1$种方案，然后它可以和$A$中的元素任意线性组合，由于它不能被$A$表示，这有$2^j$种方案，所以总方案数是$2^j(2^{r-k}-1)$。复杂度$O(n^3)$。
或者直接计算，枚举$k=\mathrm{rank}(A)$，设$n$个向量秩为$k$的方案数是$f(n,k)$，每个秩为$k$的线性空间包含$\binom{k}{r}_2$个秩为$r$的子空间，所以答案是$\frac{f(n,k)\binom{n}{r}_2}{\binom{k}{r}_2}$。复杂度$O(\frac{n^3}{w})$，瓶颈在求rank。
不如说群是均匀的。
集训队胡策22 R5 C. 核
对于$\mathbf{F} _ q$上的$n\times n$矩阵$B$，如果有$c$个$n\times n$矩阵$A$满足$AB=A$，那么它的贡献是$3^c$。求所有非奇异矩阵贡献和，膜$998244353$。$n\leq 10^5$。
$A$的每行是独立的。只需要考虑行向量，称为$a$好了。
如果$aB=a$，那么$a$是$B$的一个特征值$1$对应的特征向量对吧。众所周知一个特征值$\lambda$对应的特征向量构成一个线性空间，所以如果$B$的特征值$1$对应的特征空间维数是$d$，贡献就是$(3^{q^d})^n$。
于是考虑对每个$d$算有多少个非奇异矩阵。考虑特征值$1$对应的特征空间，它是特征值$1$对应的特征空间当且仅当$B$作为一个变换作用于它的效果和$I$相同，那么找一个基使得其中前$d$维张成这个特征空间，$B$的前$d$列就确定了，这个基具体是啥是不重要的。需要容斥一下减去实际上不止$d$维的情况，设确定后$n-d$列的方案数是$g(n-d)$，因为这个基具体是啥不重要，我们可以枚举多了$t$个维度，让这个基的接下来$t$维张成这些维度，$q$-二项式系数选出这个子空间，那么这$t$列也确定了，剩下的方案数就是$g(n-d-t)$。也就是
\[g(k)=\prod_{i=n-k}^{n-1}(q^n-q^i)-\sum_t\binom{k}{t}_qg(k-t)\]那么答案就是$\sum \binom{n}{k}_qg(n-k)$。
类似于egf地拆开$q$-二项式系数，就是一个卷积了。复杂度$O(n\log n)$。
为了做到$n\leq 10^7$，需要一些$q$-analog基础，你可能希望阅读 数数从入门到直僵僵地镶嵌在门框里 中的相关内容。
让我们看看现在它长啥样。
\[\frac{g(k)}{(q;q)_k}=\frac{f(k)}{(q;q)_k}-\sum_t\frac{1}{(q;q)_t}\frac{g(k-t)}{(q;q)_{k-t}}\]把$\frac{z^k}{(q;q)_k}$称为$E$好了，那么也就是说$G-F=-(E-1)G,G=\frac{F}{E}$。
要做到线性，大概要搞一个整式递推出来。先考虑$\frac{1}{E}$，毕竟比较好看嘛!
这个东西称为 子空间反演，好比$e^z$的逆是$e^{-z}$称为 二项式反演。$q$-analog的主要想法就是扰动，考虑$[z^k]zE(z)=\frac{1}{(q;q){k-1}}=(1-q^k)\frac{1}{(q;q)_k}$，所以我们知道$zE(z)=E(z)-E(qz)$。也就是说$E(z)=\frac{E(qz)}{1-z}$，那么又有$E(qz)=\frac{E(q^2z)}{1-qz}$，不停地展开下去，就有$E(z)=\lim\limits{k\rightarrow\infty}\frac{E(q^kz)}{(1-z)(1-qz)…(1-q^{k-1}z)}$。劲爆的事情是这玩意提取$z$不收敛但是提取$q$是收敛的，所以我们就提取$q$以说明$E(q^\infty z)$是没有贡献的，这给出$E(z)=\frac{1}{(z;q)\infty}$。所以$\frac{1}{E(z)}=(z;q)\infty$。
取$[z^k]$不收敛其实没有关系，因为我们知道它肯定其实是存在的啊，根据形式幂级数那套基本理论，如果关于$q$的操作都在形式上正确，那么所有收敛的东西算出来的必然是同一个正确结果，比如说提取$z^1$项得到$q^0+q^1+…$，它不收敛，但是它等于$\frac{1}{1-q}$，这玩意收敛。
还是扰动，有$z^0\infty=1$，$(z;q)\infty=(1-z)(qz;q)\infty$，也就是说$z^k\infty=q^kz^k\infty-q^{k-1}z^{k-1}\infty$，那么$z^k\infty=-\frac{q^{k-1}}{1-q^k}z^{k-1}\infty=\frac{(-1)^kq^\binom{k}{2}}{(q;q)_k}$。看起来非常劲爆!当然没必要求出通项，我们只是需要一个整式递推。
接下来考虑$[z^k]F=\frac{\prod\limits_{i=n-k}^{n-1}(q^n-q^i)}{(q;q)k}$。考虑$[z^k]zF(z)=\frac{\prod\limits{i=n-k+1}^{n-1}(q^n-q^i)}{(q;q)_{k-1}}=\frac{1-q^k}{q^n-q^{n-k}}[z^k]F(z)$，那么提一个$\frac{1}{q^n}$，系数就是$\frac{1-q^k}{1-q^{-k}}$。分母不太好凑，不过我们可以把它乘到那一边去，于是我们知道$q^n(zF(z)-\frac{z}{q}F(\frac{z}{q}))=F(z)-F(qz)$，也就是$F(z)=\frac{F(qz)-q^{n-1}zF(\frac{z}{q})}{1-q^nz}$。
但是类似于整式递推，在这里我们希望先把参数里形如$qz$的东西凑好，所以我们希望总是用高次代换掉低次，所以希望方程中左边是$q$的次数最小的。用$qz$代换$z$以避免$\frac{z}{q}$这种东西，得到$q^n(qzF(qz)-zF(z))=F(qz)-F(q^2z),F(z)=\frac{(1-q^{n+1}z)F(qz)-F(q^2z)}{q^nz}$。这里有一个$\frac{1}{z}$但是可以看到上面确实没有常数项。
然后既然我们要算积的方程，为了简单一点设$T(z)=F(z)(z;q)\infty$，就把两个方程乘起来对吧，有$F(z)(z;q)\infty=\frac{1-z}{q^nz}((1-q^{n+1}z)F(qz)(qz;q)\infty-F(q^2z)(qz;q)\infty)$。继续代换掉后面那个$(qz;q)\infty$，得到$F(z)(z;q)\infty=\frac{1-z}{q^nz}((1-q^{n+1}z)F(qz)(qz;q)\infty-(1-qz)F(q^2z)(q^2z;q)\infty)$，那么也就是说$T(z)=\frac{1-z}{q^nz}((1-q^{n+1}z)T(qz)-(1-qz)T(q^2z))$。这就结束了。
题解好像和我这个不太一样。不过没有关系，推完了就不管了!
低秩扰动
sdptt R8 D1收录了一个加秩为$1$的矩阵维护逆的做法。
伴随矩阵
$AA^\ast=(\det A)I$。为什么是这样的呢?
\[(AA^\ast)_{i,j}=\sum_kA_{i,k}\left(\begin{array}{cc}\hat{j}\\\hat{k}\end{array}\right)\]相当于认为第$j$行是第$i$行，并枚举选了啥算行列式。如果$i\neq j$，那么有两行相同，行列式是$0$。否则就是原矩阵的行列式。
对于秩为$n$的矩阵，可以通过求逆求伴随矩阵。
对于秩为$n-1$的矩阵，其伴随矩阵秩必然为$1$，因为$I$的秩为$n$。设它是$uv^T$，那么$Auv^T=0$，劲爆的是还有$uv^T\neq 0$，解出任何一个合法的$u,v$，然后算两次行列式就可以得到$u,v$。
然后既然我们要算积的方程，为了简单一点设$T(z)=F(z)(z;q)\infty$，就把两个方程乘起来对吧，有$F(z)(z;q)\infty=\frac{1-z}{q^nz}((1-q^{n+1}z)F(qz)(qz;q)\infty-F(q^2z)(qz;q)\infty)$。继续代换掉后面那个$(qz;q)\infty$，得到$F(z)(z;q)\infty=\frac{1-z}{q^nz}((1-q^{n+1}z)F(qz)(qz;q)\infty-(1-qz)F(q^2z)(q^2z;q)\infty)$，那么也就是说$T(z)=\frac{1-z}{q^nz}((1-q^{n+1}z)T(qz)-(1-qz)T(q^2z))$。这就结束了。
题解好像和我这个不太一样。不过没有关系，推完了就不管了!