给定一个奇数素数、p 和整数 n 和 m，我想快速列出所有可逆的 m x m 矩阵，其条目来自大小为 p^n 的有限域。什么是有效的方法？
我可以列出所有可能的 (p^n(^(m x m( 矩阵并过滤那些具有非零行列式的矩阵，但这似乎很浪费，因为它涉及计算许多行列式。
通过列出所有下对角线 (L(、对角线 (D( 和上对角矩阵 (U(，我可以列出具有因式分解 LDU 的矩阵，但这些矩阵在对角线上永远不会有零。
有没有一种简单有效的方法来列出所有条目来自有限域的可逆平方矩阵？
谢谢！
我不认为过滤所有矩阵是一个糟糕的策略。非奇异矩阵的分数为
(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)字段操作的因子。