python - 如何列出有限域上的所有可逆矩阵？

Question

给定一个奇数素数 p 和整数 n 和 m，我想快速列出所有可逆 mxm 矩阵，其条目来自大小为 p^n 的有限域。什么是有效的方法来做到这一点？

我可以列出所有可能的 (p^n)^(mxm) 矩阵并过滤具有非零行列式的矩阵，但这似乎很浪费，因为它涉及计算许多行列式。

通过列出所有下对角线 (L)、对角线 (D) 和上对角线矩阵 (U)，我可以列出具有因式分解 LDU 的矩阵，但这些矩阵的对角线上永远不会有零。

有没有一种简单有效的方法来列出所有条目来自有限域的可逆方阵？

谢谢！

Answer 1

我不认为过滤所有矩阵是一个坏策略。非奇异矩阵的分数是

(1 - q) (1 - q^2) ... (1 - q^m) > 1 - q - q^2 - ... - q^m > 1 - q/(1 - q),

哪里q = 1/(p^n)。除非p^n = 2，这至少是其中的一半（我敢打赌，我们可以得到更好的界限p^n = 2）。

话虽如此，您可以在遍历搜索树时对每个传入行进行部分高斯消除，这将节省一个Theta(m)字段操作因素。