今天学到一个非常魔怔的东西啊，求任意矩阵的伴随矩阵（在模数为质数的情况下）
首先你也许知道求非奇异矩阵的伴随矩阵的方法，设这个矩阵是 \(A\) ，称它的伴随矩阵是 \(A^*\) ，则我们有 \(A^*=|A|A^{-1}\)
但是问题是当 \(|A|=0\) 时，\(A^{-1}\) 就不存在了，咋办？
我们现在做的矩阵求逆，相当于是找到一个矩阵 \(P\) 使得 \(AP=I\) ，但是由于不一定存在这样的矩阵 \(P\) ，所以我们扩展一下，找到两个非奇异矩阵 \(P,Q\) 满足 \(PAQ=I_r\) ，其中 \(r\) 是矩阵的秩， \(I_{r_{i,j}}=[i = j \le r]\)
那么由于 \((AB)^*=B^*A^*\) ，得出 \((PAQ)^*=Q^*A^*P^*=|P||Q|Q^{-1}A^*P^{-1}\) ，于是我们有 \(A^*=\frac{Q I_r^* P}{|P||Q|}\)
于是需要求 \(P,Q\) ，还是类似求矩阵逆，先初始化 \(P=Q=I\) ，然后尝试把 \(A\) 消成 \(I_r\)，每次对 \(A\) 做行变换的时候就对 \(P\) 做相同操作，做列变换（由于是任意矩阵，秩不一定为 \(0\) ，于是可能需要做一些列变换）就对 \(Q\) 做相同操作，于是就得到了 \(P,Q\) （至于为什么要用两个矩阵，大概是因为行变换容易用左乘表达，而列变换相反）。而且由于初等行/列变换要么不改变行列式，要么把行列式变为相反数（交换两行或两列），所以 \(|P|\ne 0, |Q|\ne 0\) ，这说明了我们得到的 \(P,Q\) 确实是非奇异矩阵
然后还有最后一步，求 \(I_r^*\) ，这个其实很弱智啊，当 \(r\le n-2\) 的时候就是全 \(0\) 的矩阵，当 \(r=n-1\) 就只有 \(I_{r_{n,n}}^*=1\) ，如果 \(r=n\) 就对角线上全为 \(1\)
求出上面这些，最后的式子就很好算了，时间复杂度 \(O(n^3)\)
标签：PAQ,变换,矩阵,伴随,奇异,任意 From： https://www.cnblogs.com/fanjambot3663/p/18255088