A simple case:
We let $p=2017$ and look for a "modulus" polynomial $f$ of degree $m=5$ which is irreducible over $F=\mathbb F_p$, associate
its companion matrix $U$ as in loc. cit.
https://rua.ua.es/dspace/bitstream/10045/27320/1/Tesis_Diaz_Cardell.pdf ,
and the number field $K=F(a)$ generated by $a$ with $f(a)=0$ in $K$,
and define the map
$$ \psi:K\to M_{m\times m}(F)\ ,$$
to the full space of matrices, which takes $a$ to $U$. So the codomain is bigger in the implementation, but the true image is
the one generated by the powers of $U$. We will test that $\psi$ is a map of rings on some random elements.
The code realizing this situation is as follows:
p = 2017
F = GF(p)
R.<X> = PolynomialRing( F )
m = 5
f = R.irreducible_element(m, algorithm='first_lexicographic')
U = companion_matrix(f, format='right')
K.<a> = GF( p**m, modulus=f )
M = MatrixSpace(F, m, m)
psi = K.Hom(M, Rings())(U)
This is all needed to define $\psi$ in sage.
Let us investigate the constructed structure in a dialog with the sage interpreter.
sage: p
2017
sage: F
Finite Field of size 2017
sage: f
X^5 + X + 11
sage: f.is_irreducible()
True
sage: U
[ 0 0 0 0 2006]
[ 1 0 0 0 2016]
[ 0 1 0 0 0]
[ 0 0 1 0 0]
[ 0 0 0 1 0]
sage: K
Finite Field in a of size 2017^5
sage: K.modulus()
x^5 + x + 11
sage: psi
Ring morphism:
From: Finite Field in a of size 2017^5
To: Full MatrixSpace of 5 by 5 dense matrices over Finite Field of size 2017
Defn: a |--> [ 0 0 0 0 2006]
[ 1 0 0 0 2016]
[ 0 1 0 0 0]
[ 0 0 1 0 0]
[ 0 0 0 1 0]
sage:
Now we will pick some random elements in $K$ and test the compatibility of $F$ w.r.t. the structures of
an $F$-algebra on $K$ and $M$.
s = F.random_element() # some element in 0, 1, ... , 2016
k1 = K.random_element() # some random element in K
k2 = K.random_element() # an other random element in K... maybe
print "s = %s" % s
print "k1 = %s" % k1
print "k2 = %s" % k2
print "Is psi(s*k1) == s*psi(k1) ? %s" % bool( psi(s*k1) == s*psi(k1) )
print "Is psi(s*k2) == s*psi(k2) ? %s" % bool( psi(s*k2) == s*psi(k2) )
print "Is psi(k1+k2) == psi(k1) + psi(k2) ? %s" % bool( psi(k1+k2) == psi(k1) + psi(k2) )
print "Is psi(k1*k2) == psi(k1) * psi(k2) ? %s" % bool( psi(k1*k2) == psi(k1) * psi(k2) )
This gives (this time):
s = 422
k1 = 1679*a^4 + 611*a^3 + 639*a^2 + 228*a + 1823
k2 = 242*a^4 + 968*a^3 + 1389*a^2 + 1838*a + 84
Is psi(s*k1) == s*psi(k1) ? True
Is psi(s*k2) == s*psi(k2) ? True
Is psi(k1+k2) == psi(k1) + psi(k2) ? True
Is psi(k1*k2) == psi(k1) * psi(k2) ? True
Above, we have for instance:
sage: psi(k1)
[1823 1701 1347 1039 1526]
[ 228 144 1090 708 811]
[ 639 228 144 1090 708]
[ 611 639 228 144 1090]
[1679 611 639 228 144]
Note that the space $F[U]$ is a subspace of dimension $m$ inside the full matrix space, in our case it is generated
by the $m$ matrices:
sage: for power in range(m):
....: print "U^%s is\n%s\n" % ( power, U^power )
....:
U^0 is
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
U^1 is
[ 0 0 0 0 2006]
[ 1 0 0 0 2016]
[ 0 1 0 0 0]
[ 0 0 1 0 0]
[ 0 0 0 1 0]
U^2 is
[ 0 0 0 2006 0]
[ 0 0 0 2016 2006]
[ 1 0 0 0 2016]
[ 0 1 0 0 0]
[ 0 0 1 0 0]
U^3 is
[ 0 0 2006 0 0]
[ 0 0 2016 2006 0]
[ 0 0 0 2016 2006]
[ 1 0 0 0 2016]
[ 0 1 0 0 0]
U^4 is
[ 0 2006 0 0 0]
[ 0 2016 2006 0 0]
[ 0 0 2016 2006 0]
[ 0 0 0 2016 2006]
[ 1 0 0 0 2016]
sage:
Add-on:
A real problem may be to realize a situation as the given one in sage for $q$ not a prime number.
Please do not downgrade the answer for the reason of dilution or deviation.
(Mathematically, there is one field of dimension $q$ up to isomorphism, so we pick the one. Practically, we need the isomorphism(s)...)
We have to fix the "alpha", which will become again an $a$ and in code an a in my case.
And we have to construct it in such a way that we know its minimal polynomial over a choice of a
field $\mathbb F_q$. (The situation is not completely trivial when $q$ is not a prime. So my choice will be with $q=2^5=32$.)
We introduce $F=\mathbb F_q=\mathbb F_2(s)$ for an element $s$ of a small degree, $3$ or $5$ say, over $\mathbb F_2$.
Then we pick an irreducible polynomial of degree $m$ over $F$.
m = 3
q = 2**3 # feel free to take an other q
F.<s> = GF(q)
R.<X> = PolynomialRing( F )
f = R.irreducible_element(m, algorithm='first_lexicographic')
This gives so far:
sage: f
X^3 + s*X + s^2
We also want the minimal polynomial of $s$, the "modulus" of $F$, we will maybe need it:
sage: s.minpoly()
x^3 + x + 1
Now we have to introduce the field $K$ with $q^m$ elements. There are two ways to do this in sage:
- Either as
K.<a> = F.extension( modulus ), we know its modulus, but in this case we do not have a method vector_space for K! - Or as
K.<a> = GF( q^m, modulus=? ), and we have to know the modulus of "the same $a$" over $\mathbb F_2$. In this case we can easily get K.vector_space(), this makes it easy to proceed in our case.
(Real problems when dealing with real situations.)
So we will give a solution via K.<a> = GF( q^m, modulus=? ), my choice since the vector_space method makes for me things easier.
Which is the modulus, the minimal polynomial over $\mathbb F_q$ of $a$? The following code finds it, using the first method to find the initial data for the second one.
q, m = 2**3, 3
F.<s> = GF(q)
R8.<X> = PolynomialRing( F )
modulus = R.irreducible_element(m, algorithm='first_lexicographic')
K.<a> = F.extension( modulus )
R2.<y> = PolynomialRing( GF(2) )
for f, multiplicity in (y^(2^9)-y).factor():
if f.degree() != 9:
continue
if f(a) == 0:
print f
break
This gives the polynomial y^9 + y^5 + y^4 + y + 1 very quickly. But in case of a slightly bigger $q,m$ situation, e.g. $q=2^5, m=5$, this
is already a test of patience. This is no longer the question, so i will take this case, we still have to find the place of $s$
in the new incarnation of the one field $K=\mathbb F_{2^9}$.
R2.<y> = PolynomialRing( GF(2) )
K.<a> = GF( 2**9, modulus = y^9 + y^5 + y^4 + y + 1 )
R512.<S> = PolynomialRing( K )
factor( a^3 + S*a + S^2 )
This gives:
(S + a^7 + a^6 + a^5 + 1) * (S + a^7 + a^6 + a^5 + a + 1)
Note that:
sage: (a^7 + a^6 + a^5 + 1).minpoly()
x^9 + x^7 + x^6 + x^4 + 1
sage: (a^7 + a^6 + a^5 + a + 1).minpoly()
x^3 + x + 1
so the second root has to be taken "as a pendant for $s$".
Now we can realize the morphism $\psi$
R.<y> = PolynomialRing( GF(2) )
K.<a> = GF( 2**9, modulus = y^9 + y^5 + y^4 + y + 1 )
F.<s> = GF( 2**3, modulus = y^3 + y + 1 )
ks = a^7 + a^6 + a^5 + a + 1
R.<X> = PolynomialRing( F )
f = X^3 + s*X + s^2
U = companion_matrix(f, format='right')
M = MatrixSpace(F, 3, 3)
psi = K.Hom(M, Rings())(U)
We can test again the compatibility with the $F$--algebra structure.
incl = F.Hom(K, Fields())( ks ) # F -> K, s -> ks
t = F.random_element() # some element in F
k1 = K.random_element() # some random element in K
k2 = K.random_element() # an other random element in K... maybe
kt = incl(t)
print "t = %s" % t
print "kt = %s" % kt
print "k1 = %s" % k1
print "k2 = %s" % k2
print "Is psi(kt*k1) == t*psi(k1) ? %s" % bool( psi(kt*k1) == t*psi(k1) )
print "Is psi(kt*k2) == t*psi(k2) ? %s" % bool( psi(kt*k2) == t*psi(k2) )
print "Is psi(k1+k2) == psi(k1) + psi(k2) ? %s" % bool( psi(k1+k2) == psi(k1) + psi(k2) )
print "Is psi(k1*k2) == psi(k1) * psi(k2) ? %s" % bool( psi(k1*k2) == psi(k1) * psi(k2) )
getting:
t = s^2 + s + 1
kt = a^8 + a^5 + a^3 + a^2
k1 = a^6 + a^5 + a^4 + a^3 + a^2
k2 = a^8 + a^7 + a^3
Is psi(kt*k1) == t*psi(k1) ? True
Is psi(kt*k2) == t*psi(k2) ? True
Is psi(k1+k2) == psi(k1) + psi(k2) ? True
Is psi(k1*k2) == psi(k1) * psi(k2) ? True
Here, again, the codomain is full matrix space, but the image of $\psi$ is generated over $F=\mathbb F_2(s)$ by
sage: U^0, U^1, U^2
(
[1 0 0] [ 0 0 s^2] [ 0 s^2 0]
[0 1 0] [ 1 0 s] [ 0 s s^2]
[0 0 1], [ 0 1 0], [ 1 0 s]
)
Here, what is $\mathbb F_q[U]$? Is it a subspace of the matrices of type $m\times m$ over $\mathbb F_q$? Can we take the whole space instead?
An explicit example of $\alpha$ and $U$ (that match) would make things easier.
https://rua.ua.es/dspace/bitstream/10045/27320/1/Tesis_Diaz_Cardell.pdf (link text) can you please check Theorem 3.3 in page 51