Как перечислить все обратимые матрицы над конечным полем?

Учитывая нечетное простое число p и целые числа n и m, я хотел бы быстро перечислить все обратимые mxm-матрицы, элементы которых происходят из конечного поля размера p^n. Каков эффективный способ сделать это?

Я мог бы перечислить все возможные матрицы (p ^ n) ^ (m x m) и отфильтровать те, у которых определитель не равен нулю, но это кажется расточительным, поскольку требует вычисления многих определителей.

Перечисляя все матрицы нижней диагонали (L), диагональной (D) и верхней диагонали (U), я могу перечислить матрицы с факторизацией LDU, но у них никогда не будет нулей на диагонали.

Существует ли простой и эффективный способ перечислить все обратимые квадратные матрицы, элементы которых происходят из конечного поля?

Благодарю вас!


python algorithm matrix linear-algebra finite-field
person doogrammargood    schedule 07.07.2020    source источник
comment
Какие библиотеки вы используете? Если у вас есть SageMath/Maxima, это должно быть легким (хотя я сам не слишком знаком с ними).   -  person Lambda Fairy    schedule 07.07.2020
comment
Я написал свой собственный класс конечного поля на основе многочленов Конвея. Если есть способ сделать это в Sage, это было бы полезно.   -  person doogrammargood    schedule 07.07.2020
comment
Да в Sage просто: for g in GL(2,GF(3)): print(g)   -  person doogrammargood    schedule 07.07.2020

Ответы (1)


arrow_upward
0
arrow_downward

Я не думаю, что фильтрация всех матриц — плохая стратегия. Доля невырожденных матриц равна

(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) полевых операций.

person David Eisenstat    schedule 07.07.2020