1
$\begingroup$

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]
    ];
$\endgroup$
1
$\begingroup$

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 *)
$\endgroup$
  • $\begingroup$ Thanks. Note that you have to check, where you set rootn = x^89, that it does not become a generator for any subgroup. In your case, it works because 89 is a prime. $\endgroup$ – Saad Quader Aug 25 '17 at 23:41
  • 1
    $\begingroup$ It was selected specifically to be a (multiplicative) generator of a subgroup of 23 elements, that is, a root of unity of degree 23. $\endgroup$ – Daniel Lichtblau Aug 26 '17 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.