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.

Improve this question
$\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$
    – Neil Strickland
    Commented Nov 27, 2019 at 12:21

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .