Checking matrix-invertibility in finite fields

Question

Suppose the finite field $F=GF(2^d)$ contains all $p$-th roots of unity, where $p$ is a prime and $\omega\in F$ is the principal $p$-th root of unity. Let $V=(\omega^{ij})$ be a $p\times p$ Vandermonde matrix.

Let $v:=V(I,J)$ be a submatrix of $V$ whose rows and columns are indexed by $I$ and $J$, respectively. I am interested in checking whether $v$ is singular. I am doing so by computing the determinant. The computation is performed using the FiniteFields package.

Problem I need to test invertibility for all rows/columns subsets for a given $p$. However, it takes a lot of time to compute a single determinant.

For example, for some index-subsets rows and cols with length t, the functionVandermondeDetGF[13, rows, cols] takes 0.89 sec when t = 10, 2.31 sec when t = 11, and doesn't even terminate when t = 12. Similar things happen with other values of t and p: it is too slow for even double-digit p and t.

Questions:

1. What am I doing wrong?
2. What is the right way to efficiently check matrix-invertibility in finite fields? Can we do LU decomposition?
3. Why is it this slow?

Thanks in advance.

Code

(* The dimension of the GF(2) extension containing q roots of unity *)
DimExtOverGF2[qRootsOfUnity_] := 
  DimExtOverGF2[qRootsOfUnity] =
   Block[{sol},
    sol = Reduce[Mod[2^n, qRootsOfUnity] == 1, n, Integers];
    Association[ToRules[sol /. {C[1] -> 1}]][n]
    ];

(* A single entry, v_{ij} *)
VandermondeEntryGF[gf_, power_] :=
  VandermondeEntryGF[gf, power] =
   FieldExp[gf, power];

(* The matrix V *)
VandermondeMatrixGF[gf_, rows_, cols_] :=
 VanderMondeMatrixGF[gf, rows, cols] = Block[{size},
   size = Length@disks;
   Array[VandermondeEntryGF[gf, rows[[#1]] cols[[#2]]] &,
    {size, size}]]

(* Compute the determinant*)
VandermondeDetGF[prime_, rows_, cols_, t_: 1] :=
  VandermondeDetGF[prime, rows, cols, t] =
   Block[{gf, v, dim, size},
    dim = DimExtOverGF2[prime]; (* find dimension*)
    gf = GF[2, dim]; (* create finite field *)

    (* initialize power table *)
    If[PowerListQ@gf == False,
     PowerListQ[GF[2, dim]] = True];
    Assert[Length@disks == Length@slants];

    (* compute determinat of the Vandermonde submatrix*)
    v = VanderMondeMatrixGF[gf, rows, cols];
    Det[v]
    ];

Answer 1

I would not use the FiniteFields package for this. It is dated and not so likely to work well for this. Instead maybe find a primitive polynomial in some variable x and use a suitable power of x for the primitive root of unity. I show an example below. We will work in the field of 2^11 elements.

primpoly = x^11 + x^2 + 1;

Confirm primitivity (I already did which is why I know it works).

PrimitivePolynomialQ[primpoly, 2]

(* Out[172]= True *)

Find primes that have roots of unity.

FactorInteger[2^11 - 1]

(* Out[174]= {{23, 1}, {89, 1}} *)

We see 23 is one such prime. Create a 23rd root of unity. Use it to make a Vandermonde matrix.

n = 23;
rootn = x^89;
vdmMat = Table[x^Mod[(j*k), n], {j, 0, n - 1}, {k, 0, n - 1}];

Check that the determinant is nonzero. We must reduce modulo characteristic and relation that x^(#elements)+x==0.

AbsoluteTiming[
 dd = PolynomialMod[Det[vdmMat], {2, x^(2^11) + x}];]

(* Out[170]= {15.465528, Null} *)

It's not zero:

dd

Out[171]= x^22 + x^32 + x^36 + x^40 + x^44 + x^46 + x^50 + x^70 + \
x^72 + x^74 + x^76 + x^78 + x^86 + x^88 + x^98 + x^100 + x^104 + \
x^106 + x^108 + x^112 + x^114 + x^120 + x^128 + x^130 + x^132 + x^138 \
+ x^150 + x^152 + x^154 + x^158 + x^166 + x^170 + x^174 + x^176 + \
x^184 + x^186 + x^194 + x^198 + x^202 + x^204 + x^206 + x^218 + x^220 \
+ x^222 + x^232 + x^234 + x^236 + x^238 + x^244 + x^248 + x^250 + \
x^252 + x^254 + x^256 + x^258 + x^262 + x^268 + x^270 + x^272 + x^274 \
+ x^284 + x^286 + x^288 + x^300 + x^302 + x^304 + x^308 + x^312 + \
x^320 + x^322 + x^330 + x^332 + x^336 + x^340 + x^348 + x^352 + x^354 \
+ x^356 + x^368 + x^374 + x^376 + x^378 + x^386 + x^392 + x^394 + \
x^398 + x^400 + x^402 + x^406 + x^408 + x^418 + x^420 + x^428 + x^430 \
+ x^432 + x^434 + x^436 + x^456 + x^460 + x^462 + x^466 + x^470 + \
x^474 + x^484 *)