代数问题

Published: October 20, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• 拉格朗日定理
• $rank(A^TA)=rank(A)$
• 实对称矩阵特征向量两两正交
• 奇异值分解存在性证明
• 两个相似矩阵的特征多项式相同
• 特征多项式
• Cayley-Hamilton定理
• 无向无环图的邻接矩阵的秩
• 计算二分图匹配数的奇偶性
• 矩阵快速幂多点求值
• 参考资料

拉格朗日定理

拉格朗日定理：对于任意有限群$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$，有

$$\begin{aligned} &A^TAx=0\\ \Rightarrow &x^TA^TAx=0\\ \Rightarrow &(Ax)^T(Ax)=0\\ \Rightarrow &\|Ax\|^2=0\\ \Rightarrow &Ax=0 \end{aligned}$$

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

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

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

$$\left\{ \begin{array}{c} Ax=\lambda_1x\\ Ay=\lambda_2y \end{array} \right.$$

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

$$\begin{aligned} &y^TAx=\lambda_1y^Tx\\ \Rightarrow &\lambda_2 y^Tx=\lambda_1 y^Tx \end{aligned}$$

这意味着，$\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$为某个方阵。那么

$$\begin{aligned} |xI-PAP^{-1}|&=|PxP^{-1}-PAP^{-1}|\\ &=|P(xI-A)P^{-1}|\\ &=|P|\cdot|xI-A|\cdot |P^{-1}|\\ &=|xI-A| \end{aligned}$$

特征多项式

考虑某个交换环$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$。

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

无向无环图（即森林）的邻接矩阵的秩为$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\pmod 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)$。

参考资料

《生成树的计数和应用》