王展鹏在 年集训队论文中提出了一种计算模合数伴随矩阵,以及交换环上矩阵行列式的做法。今天我们讨论一个综合一点的情况:模合数多项式。
设给定一个 n×nn\times nn×n 的 mmm 次多项式构成的矩阵,求行列式的 0∼m0\sim m0∼m 次项且 m≪nm\ll nm≪n。系数对 MMM 取模。
我们首先做个 CRT,将模数 MMM 分解为若干 pkp^kpk 之乘积,将问题逐一解决。
当 k>1k>1k>1 的时候,由于不是域,我们会遇到类似下面的无法直接消元的情形:
[p+x⋯x⋯]\begin{bmatrix} p + x & \cdots\\ x & \cdots \end{bmatrix} [p+xx⋯⋯]
因此我们尝试摒弃「将整个下三角消为 000」的想法。但是首先应当让尽量多的位置被消成 000。
对于矩阵 M\mathbf MM,若其中有一项的常数项不是 ppp 的倍数,那么我们将其交换到左上角,这一项是可逆的,因此可以直接消掉本列的其余元素。那么我们直接消耗 Θ(n2M(m))\Theta(n^2 \mathsf{M}(m))Θ(n2M(m)) 的时间,规约到剩下的一个 (n−1)×(n−1)(n-1)\times(n-1)(n−1)×(n−1) 的矩阵 M′\mathbf M'M′ 的行列式。
那么现在这个过程已经进行不下去了,我们得到的一个矩阵所有常数项均为 ppp 的倍数。但是注意到对于 0≤j≤i0\leq j\leq i0≤j≤i,iii 个形如这样的多项式的乘积,其 xjx^jxj 项系数是 pi−jp^{i-j}pi−j 的倍数,因此不难归纳证明,如果矩阵的大小 ≥k+m\ge k+m≥k+m,那么我们所求范围的行列式必然完全是 000,我们直接结束就行。否则我们还有一般情况下的算法!
由此,我们可以在 Θ(n3M(m)+poly(k+m))\Theta(n^3\mathsf M(m) + \operatorname{poly}(k+m))Θ(n3M(m)+poly(k+m)) 的时间完成计算。
同时,注意到求伴随矩阵就是考虑 B→[x1]det(A+Bx)\mathbf B \rightarrow [x^1]\det(\mathbf A + \mathbf Bx)B→[x1]det(A+Bx) 的这么一个关于 B\mathbf BB 的所有输入的线性变换的转置,那么上述的算法少加修改就能得到一个关于 B\mathbf BB 的线性算法,将其转置就得到了一个较为简单的伴随矩阵求法。