代数问题

Published: by Creative Commons Licence

  • Tags:

拉格朗日定理

拉格朗日定理:对于任意有限群$G$以及其某个子群$H$,都有$|G|$ 能被$|H|$ 整除。

证明:

当$G=H$时,定理显然成立,下面考虑$G\neq H$,此时有$|H|<|G|$。

考虑$H$在$G$中的补集中的任意元素$x_1$,我们构建$H$的左陪集:

\[x_1H=\{x_1*h|h\in H\}\]

下面我们证明$H$的这些左陪集与$H$的交集为空,假设存在交集,即:$h_i=x_1*h_j$

那么我们可以直接推出:$x_1=h_i*h_j^{-1}\in H$

而这与$x_1$不属于$H$的前提相悖,因此证明完成。

如果$H$与$xH$的并集不等于$G$,那么就存在额外的元素$x_2$,落在$H$和$xH$之外。于是我们继续构建$H$的左陪集$x_2H$。

重复这个流程,直到得到左陪集与$H$的并集等于$G$为止。假设这时候我们得到的左陪集为$x_1H,x_2H,\ldots, x_kH$。

下面我们证明这些左陪集也是互不相交的,假设$x_iH$与$x_jH$($i < j$)交集非空,那么有: \(x_ih_i=x_jh_j\Rightarrow x_j=x_ih_ih_j^{- 1}\Rightarrow x_j\in x_iH\)

,这与我们之前的$x_j \notin x_iH$前提相悖,因此证明成立。

可以发现这k个左陪集与$H$都拥有$|H|$个元素,且互不相交,且并为$G$。因此可以得出:$(k+1)|H|=|G|$ ,因此$|H|$能够整除$|G|$,命题成立。

$rank(A^TA)=rank(A)$

对于任意$m\times n$矩阵$A$,都有$rank(A^TA)=rank(A)$。

证明:

考虑对于$A^TA$零空间中的向量$x$,有

\[A^TAx=0\\ \Rightarrow x^TA^TAx=0\\ \Rightarrow (Ax)^T(Ax)=0\\ \Rightarrow \|Ax\|^2=0\\ \Rightarrow Ax=0\]

因此,$A^TA$和$A$具有相同的零空间,$A$的零空间的秩为$rank(N(A))$,那么$A^TA$的秩为$rank(A^TA)=m-rank(N(A))=rank(A)$。

实对称矩阵特征向量两两正交

考虑对称矩阵$A$,以及其某个特征向量$x$和$y$。有

\[Ax=\lambda_1x\\ Ay=\lambda_2y\]

将第一个式子的左右两端都乘上$y^T$,可以得到:

\[y^TAx=\lambda_1y^Tx\\ \Rightarrow \lambda_2 y^Tx=\lambda_1 y^Tx\]

这意味着,$\lambda_1\neq \lambda_2\Rightarrow y^Tx=0$。

奇异值分解存在性证明

奇异值分解是指对于任意$n\times m$矩阵$A$,我们都能将其分解为如下形式$A=U\Sigma V^T$的形式,其中$U$和$V$是标准正交矩阵,而$\Sigma$是对角线矩阵。

首先我们对矩阵$A^TA$做奇异值分解,得到$A^TA=V\Lambda V^T$,因此我们直接得到了一个标准正交矩阵。接下来我们证明两个$V$中的正交向量列$v_i$和$v_j$在$A$的线性变换下依旧正交。

\[(Av_i)^T(Av_j)=v_i^T(A^TAv_j)=v_i^T\lambda v_j=\lambda v_i^Tv_j=0\]

因此我们得到了正交矩阵$AV$。但是这里$AV$不一定是标准化的。我们可以将$AV$右乘一个对角矩阵帮助其标准化:

\[AV\Sigma^{-1}=U\\ \Rightarrow AV=U\Sigma\\ \Rightarrow A=U\Sigma V^-1 \\ \Rightarrow A=U\Sigma V^T\]

两个相似矩阵的特征多项式相同

证明非常简单,设$P$为某个可逆矩阵,$A$为某个方阵。那么

\[|xI-PAP^{-1}| =|PxP^{-1}-PAP^{-1}|\\ =|P(xI-A)P^{-1}|=|P|\cdot|xI-A|\cdot |P^{-1}|\\ =|xI-A|\]

特征多项式

考虑某个交换环$R$上的$n\times n$矩阵$A$,我们定义它的特征多项式为:$f(x)=|xI-A|$,其中$x\in R$。考虑到行列式的定义,显然$A$的特征多项式是$n$阶多项式。

要计算$A$的特征多项式,我们可以用插值法,找出特征多项式在$0,1,2,\ldots n$的取值,之后用插值法插出多项式即可。后面的步骤需要的时间为$O(n^2)$,因此瓶颈在于如何快速得到特征多项式在$O(n)$个点的取值。

由于两个相似矩阵的特征多项式相同,因此我们可以通过计算$A$的某个相似矩阵来加速行列式的计算。由于每个矩阵都相似与某个上海森堡矩阵相似,因此我们可以将$A$化为某个上海森堡矩阵,上海森堡矩阵长相为:

\[\left( \begin{array}{cccccc} a_{1,1} & a_{1,2} & a_{1,3} & \ldots & a_{1,n-1} & a_{1,n}\\ a_{2,1} & a_{2,2} & a_{2,3} & \ldots & a_{2,n-1} & a_{2,n}\\ 0 & a_{3,2} & a_{3,3} & \ldots & a_{3,n-1} & a_{3,n}\\ 0 & 0 & a_{4,3} & \ldots & a_{4,n-1} & a_{4,n}\\ 0 & 0 & 0 & \ldots & a_{5,n-1} & a_{5,n}\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots\\ 0 & 0 & 0 & \ldots & a_{n,n-1} & a_{n,n} \end{array} \right)\]

即对于任意$i>j+1$,都有$a_{i,j}=0$。

花费$O(n^3)$时间复杂度就可以将$A$化为上海森堡矩阵。

接下来我们直接认为$A$是一个上海森堡矩阵。容易发现通过消元法求$f(x)$,其中$x$是给定值,所需要的时间复杂度仅为$O(n^2)$。因此计算$f$在$O(n)$个点上的特征函数值需要的总时间复杂度为$O(n^3)$。

这里总的时间复杂度为$O(n^3)$。

Cayley-Hamilton定理

任意交换环上的方阵$A$和其特征多项式$f$,都满足$f(A)=0$。

Berlekamp Massey算法的应用

要了解Berlekamp-Massey算法,推荐看一下论文

这里只是提一下怎么使用BM算法。

考虑有存在一组长度为$n$的向量序列$v_0,v_1,…$,其中$v_i=Av_{i-1}$,$A$是一个$n\times n$方阵,而$v_0$是给定值。问题要求你求$v_k$的第$t$个元素$v_k(t)$。

一般主流的做法就是对矩阵$A$进行快速幂,这个需要的时间复杂度为$O(n^3\log_2k)$。但是假如$n\leq 1000$呢,该怎么办。假如矩阵比较稀疏,比如我们从$v_i$中得到$v_{i+1}$只需要$O(n)$的时间复杂度的话,我们就可以用下面的方式在$O(n^2\log_2n)$的时间复杂度内得到结果。

另外一种方式就是求矩阵$A$的特征方程,之后利用特征方程进行快速求解,但是求特征方程需要的时间复杂度是$O(n^3)$。

事实上,我们之所以会选择$A$的特征方程,是因为特征方程一定是$A$的零化多项式。而我们在线性函数和线性递推关系一节中已经说过${A^i}$序列满足的线性递推关系,${v_i}$也是满足的,实际上:

\[A^{i}=-c_1A^{i-1}-c_2A^{i-2}-\ldots-c_nA^{i-n}\\ \Rightarrow A^{i}v_0=-c_1A^{i-1}v_0-c_2A^{i-2}v_0-\ldots-c_nA^{i-n}v_0\\ \Rightarrow v_i=-c_1v_{i-1}-c_2v_{i-2}-\ldots-c_nv_{i-n}\]

自然${v_i(t)}$也是满足的,

我们可以通过直接计算${v_i}$序列的前面几项$v_0,v_1,\ldots, v_m$,之后利用BM算法在$V(t)={v_0(t),v_1(t),\ldots, v_m(t)}$组成的序列中推出最短线性递推关系,由于$A$的特征方程也一定是该序列的一个递推关系,因此${A^i}$,${v_i}$,${v_i(t)}$的最短线性递推关系最多是$n$项。

那么我们到底该怎么选择$m$,能保证BM推出的线性关系没有问题呢?假设我们用BM算法处理了$m$个数值,之后如果由于最短递推关系不再满足而发生重构,那么重构后的递推关系不小于$\lceil \frac{m+1}{2} \rceil$,但是我们提过整个序列的最短递推关系不会超出$n$项,因此假如我们选择$m=2n$就足够了。

如果我们需要计算整个$v_k$而非仅仅是$v_k(t)$,那么我们就不能使用BM算法了(当然如果你要使用BM算法,那你需要对列向量的每个维度跑一遍BM才行,因为两个维度的线性递推关系可能是不同的)。我们可以通过直接算$A$的特征方程来进行加速,整个过程的时间复杂度是$O(n^3)$,依旧会优于通常的$O(n^3\log_2n)$的做法。

这里有一个不错的题目

矩阵树定理

行列式

先回忆下行列式的定义。

对于一个1~n的排列p,其中逆序对的数目记作$\delta(p)$。

记1~n的所有排列的集合为$P_n$,记排列$p$的第$i$个元素为$p_i$。

方阵的行列式定义为

\[|A|=detA=\sum_{p\in P_n}\delta(p)\prod_{i=1}^nA_{ip_i}\]

通过定义求行列式值的时间复杂度为$O(n!)$,在n较大时是不可行的。由于矩阵i行加上j行乘上某个常数,不会改变矩阵的行列式值,因此我们可以利用高斯消元法将矩阵转换为上三角矩阵,再通过计算对角线元素的乘积和得到行列式值,时间复杂度为$O(n^3)$。

矩阵树定理

设G是一个有n个顶点的无向图,定义度数矩阵$D(G)$为:

\[D_{ii}(G)=\deg(i),D_{ij}=0,i\neq j\]

定义$e(i,j)$为点i与点j之间边的数目,定义邻接矩阵$A$为:

\[A_{ij}(G)=e(i,j)\]

定义拉普拉斯矩阵$L$为:

\[L(G)=D(G)-A(G)\]

记图G的生成树个数为$t(G)$。

命题1:L(G)的行列式值为0。

证明:

L(G)所有列的和都是0,因此矩阵的行向量是线性相关的,故矩阵的秩小于n,矩阵的行列式值为0。

记$A/i$表示矩阵A删除第i行i列得到的n-1阶主子式。

命题2:如果G是不连通的,那么L(G)的n-1阶主子式的行列式值为0。

图G至少可以分为两个连通分块$G_1$,$G_2$,设$G_1$中含有$m$个顶点。我们将其$L(G)$行列式化作如下形式:

\[\left| \begin{array}{ccc} |L(G_1)/m| & 0\\ 0 & |G_2| \end{array} \right|=\sum_{p\in P_{m-1}}\delta(p)\prod_{i=1}^{m-1}A_{ip_i}|G_2|=0\]

命题3:如果G是一个树,那么L(G)的任意n-1阶主子式为行列式值为1。

当G只有两个顶点的时候,命题很显然成立。

利用归纳法,假设命题在G少于n个时始终成立,现在考虑G正好有n个顶点的时候的情况。

将顶点1视作根,设x任意一个叶结点,y是x的父亲。我们通过换行换列将第x行(列)和第n行(列)交换,将y行(列)与n-1行(列)交换。由于是偶数次交换,因此行列式值不变。此时行列式形式如下:

\[\left| \begin{array}{ccc} \ldots & \ldots & \ldots & 0\\ \ldots & \ldots & \ldots & \ldots\\ \ldots & \ldots & \ldots & -1\\ 0 & \ldots & -1 & 1 \end{array} \right|\]

删除第n行n列后的行列式值后得到的$L(G)/n$,为图G删除了顶点x后新图$G'$,除了y的度数额外多1。

\[|L(G)/n|=|L(G')|+|L(G')/n-1|=0+1=1\]

定理1:对于任意1<=r<=n,L(G)移除后第r行r列后得到的n-1阶主子式$L(G)/r$的行列式绝对值等于$t(G)$

我们观察矩阵B,矩阵B为n行m列矩阵,n是图的点数,m是图的边数。初始时B全为0,之后对于边$e_j=(u,v)$,我们将$B_{uj}$和$B_{vj}$一个设为1,一个设为-1,顺序不重要。

之后我们考虑$BB^T$,对于$i\neq j$其第i行第j列的值是$B$的第i行和第j行的点积,为点i和点j之间边的数目取反。当$i=j$时,其值为点i的度数。

同理可得$|L(G)/r|=|(B/r)(B/r)^T|$。根据Binet-Cauchy公式可以得到: \(|L(G)/r|=|(B/r)(B/r)^T|=\sum_{x\in E,|x|=n-1}|B_{1..n,x}/r||(B_{1..n,x}/r)^T|\\ =\sum_{x\in E,|x|=n-1}|B_{1..n,x}/r|^2\)

上面的$B_{1..n,x}$是指B的1~n行,x列的子矩阵。$|B_{1..n,x}/r|$是1当且仅当x形成G的生成树,否则均为0。

因此定理得证。

无向无环图的邻接矩阵的秩

无向无环图(即森林)的邻接矩阵的秩为$2M$,其中$M$是森林的最大匹配。

我们考虑森林的邻接矩阵,知道矩阵的秩等于这个矩阵的最大行列式非0的子式的大小。特别的是,对于对称矩阵,我们可以选择相同的行列,得到行列式非0的最大子式。

而相同行列组成的子式,在图论中实际上是导出子图的概念。即我们仅考虑一部分顶点的导出子图以及它们的邻接矩阵。下面我们来考虑如果计算导出子图的邻接矩阵的行列式是否为0,考虑行列式的定义:

\[\sum_{\pi}f(\pi)\prod_{i}a_{i,\pi_i}\]

考虑乘积的部分,如果它非零,意味着置换$\pi$分解后的每个循环,对应的图中也存在这样一个环。由于图是无向无环图,因此不存在长度非2的环(长度为2的环存在,因为是无向边)。即当且仅当整个置换都被分解为长度为2的环的时候,乘积部分非0。这相当与所有顶点的一个完美匹配。由于对于树,如果有完美匹配,那么匹配一定唯一,因此,树上的完美匹配一定仅贡献一次,即森林的矩阵行列式非0当且仅当森林存在完美匹配。

因此考虑原来森林的最大匹配,以及匹配的顶点所对应的导出子图,这个导出子图的邻接矩阵一定是森林的邻接矩阵的最大行列式非0子式 。即得出了我们的结论:无向无环图的邻接矩阵的秩等于该图上最大匹配乘2。

这里是codeforces的一道原题。它要求我们计算无向无环图的邻接矩阵的秩的期望。这等价于要求我们计算无向无环图的最大匹配的期望。

由于期望满足线性性质,且森林最大匹配的计算可以采取贪心算法,因此,我们可以记指示变量$X_i$表示第$i$条边是否会被放入最大匹配中。因此期望为$\sum_{i}E[X_i]$。而$E[X_i]=p_i$,其中$p_i$为第$i$条边被选入匹配的概率。利用这些现在在树上遍历即可。

计算二分图匹配数的奇偶性

问题1:给定一个左右各$n$个结点的二分图,要求计算二分图匹配数的奇偶性,其中$n\leq 2\times 10^3$

如果我们将左边的结点视作$1$到$n$的标号,而右边的$n$个结点视作位置,则我们实际上要求的是有多少置换,其中如果存在边$(i,j)$,则表示标号$i$可以放在位置$j$上。

谈到置换数,实际上是没有什么办法可以算的(除非状压,但是在这里是不现实的)。但是需要注意到我们只需要关注结果的奇偶性即可,即结果需要模$2$。

用矩阵$A$来描述二分图的边,$A_{i,j}=1$当且仅当在左边第$i$个结点和右边第$j$个结点之间存在一条边。考虑矩阵的秩的定义:$\det(A)=\sum_{\sigma}(-1)^{r(\sigma)}\prod_iA_{i,\sigma(i)}$

其中$\sigma$是置换,而$r(\sigma)$统计置换$\sigma$中的逆序对数目。由于是在模2意义下的,因此有$(-1)^{r(\sigma)}=1\mod 2$。这时候行列式为:$\det(A)=\sum_{\sigma}\prod_iA_{i,\sigma(i)}$,其实际上就是在统计所有的可能的置换。

因此我们只需要计算$\det(A)$就可以得到结果。这里可以使用bitset来优化时间复杂度,最终的结果为$O(\frac{n^3}{32})$。

问题2:给定一个左右各$n$个结点的二分图,要求对所有边判断,如果删除这条边,计算匹配总数的奇偶性,其中$n\leq 2\times 10^3$

首先我们用问题1的方式得出二分图的匹配数的奇偶性。这里时间复杂度为$O(\frac{n^3}{32})$。

接下来我们考虑余子式的定义。矩阵$A$在$(i,j)$处的余子式$M_{i,j}$表示从$A$中删除第$i$行和第$j$列后矩阵的行列式。而矩阵$A$在$(i,j)$处的代数余子式为$C_{i,j}=(-1)^{i+j}M_{i,j}$。同时有$\det(A)=\sum_{j=1}^nA_{i,j}C_{i,j}$。因此考虑删除边$(i,j)$,对应的就是将邻接矩阵$A$的第$i$行第$j$列元素设置为$0$。这时候对行列式奇偶性的影响为$C_{i,j}$。

因此我们需要对所有$(i,j)$,计算$C_{i,j}$,这不是一个小工作量。

继续我们考虑$A$的伴随矩阵$adj(A)$,其中$adj(A){i,j}=C{j,i}$。$A$与$adj(A)$的关联在于$A^{-1}=\frac{adj(A)}{\det(A)}$。

我们可以$O(\frac{n^3}{32})$求出$A^{-1}$,之后将其乘上$\det(A)$就可以得到伴随矩阵了。

提供一道题目

问题3:给定一个左右各$n$个结点的二分图,要求对所有边判断,如果必须匹配这条边,计算匹配总数的奇偶性,其中$n\leq 2\times 10^3$

这个问题和问题2实际上是一样的,考虑所有的匹配,仅可以分为两类,一类是第$i$条边被匹配,一类是第$i$条边被禁用。因此只需要知道禁用这条边后的奇偶性和原奇偶性就可以求出必选某条边的奇偶性了。

矩阵快速幂多点求值

问题1:给定一个$n\times n$矩阵$A$,并且给出$m$个请求,第$i$个请求要求计算$A^{c_i}x_i$。其中$n\leq 100, m\leq 100, c_i\leq 10^9$。

很显然可以想到矩阵快速幂,但是这样的时间复杂度为$O(n^3\sum_{i=1}^m\log_2c_i)$,太慢了。

有两种方法,先讲复杂的,我们可以直接求出矩阵的特征多项式,之后利用特征多项式在$O(n^3+n^2\sum_{i=1}^m\log_2c_i)$内求解,这是可行的,就是比较复杂。

还有一种方法,就是我们预处理出$A^{2^0},A^{2^1},\ldots, A^{2^{30}}$共31个矩阵,与处理的时间复杂度为$O(31n^3)$。

之后对于第$i$个情感,我们可以利用$x_i$去乘最多$O(\log_2c_i)$个矩阵,注意到矩阵乘法是满足结合性的,因此我们可以先计算矩阵之间的乘法,也可以先计算矩阵和向量之间的乘法,而后者实际上只需要$O(n^2)$的时间复杂度,因此回答请求的部分,每个请求都可以以$O(n^2\log_2c_i)$回答,因此总的时间复杂度为$O(31n^3+n^2\sum_{i=1}^m\log_2c_i)$。

参考资料

《生成树的计数和应用》