1
$\begingroup$

Here's my problem: I have a commutative $n$-dimensional finite algebra over a field $K$, with the elements represented as vectors in $K^n$ and a set of $n$ $nxn$ matrices that define how to multiply by each of the $n$ basis elements.

We know that it's isomorphic to a direct product of fields. If it's not a field itself, we can compute a primary decomposition and mod out by its maximal ideals to get its constituent fields that way.

So, assuming w.l.o.g. that it's a field, and thus an algebraic extension of $K$ (since it's finite dimensional as a vector space), how can we find a generator of the field extension?

Some ideas that I've thought of:

  1. Trial run through all of the elements until we find a generator.

  2. Each basis element is the generator of a subfield, but none of them have to generate the entire extension field. Computing a generator of the entire extension field is the primitive element problem.

    2a. Yokoyama et al showed how to use bounds on the absolute values of the embeddings into $\mathbb{C}$ to find a primitive element that generates the entire extension field.

  3. Treat the $n$ defining matrices as a (2,1) tensor (see the third sentence in the fourth section of [2]) and try to run some kind of classification algorithm, like in [3]? Get it into some kind of standard form from which you could read off a generator?

Obvious problems with them:

  1. If $K$ is infinite, then I'm not sure how to order the elements to make sure that I eventually get one that works.

  2. sounds best at the moment

    2a. Computing embeddings in $\mathbb{C}$ sounds computationally expensive.

  3. is just a sketch of a rough idea

Can anybody offer some advice?


[1] Yokoyama, Kazuhiro; Noro, Masayuki; Takeshima, Taku, Computing primitive elements of extension fields, J. Symb. Comput. 8, No. 6, 553-580 (1989). ZBL0697.68054.

[2] Belitskii, Genrich R.; Sergeichuk, Vladimir V., Complexity of matrix problems, Linear Algebra Appl. 361, 203-222 (2003). ZBL1030.15011.

[3] Sergeichuk, Vladimir V., Canonical matrices for linear matrix problems, Linear Algebra Appl. 317, No. 1-3, 53-102 (2000). ZBL0967.15007.

$\endgroup$
1
  • $\begingroup$ The non-generators will be a subvariety of positive codimension, so if $K$ is infinite then almost every element will be a generator. So you should pick an element $a$ at random, express $\{a^i:0\leq i<n\}$ in terms of your basis, calculate the determinant and observe that it is almost surely nonzero. Even if $K$ is finite, you should find a generator after testing a small number of randomly chosen elements. $\endgroup$ Nov 27, 2019 at 12:21

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.