Computing the basis of the Frobenius function fixed point space

edit

Let $f\in GF_{q}[x]$ be a squarefree univariate polynomial with coefficients in a finite field, and $\bar{Fr}: \frac{F_q}{(f)}\to \frac{F_q}{(f)}: \bar h \mapsto \bar h^q$ the Frobenius application over $GF_q$ elevated to the cocient $\frac{F_q}{(f)}$.

Then we can see $\frac{F_q}{(f)}$ as a vector space over $GF_q$, and the space of fixed points of $\bar{Fr}$, that is $W = {\bar h \in \frac{F_q}{(f)} : \bar h ^q = q }$ is a linear subspace.

The question: how do I compute the basis of $W$ in sagemath?

EDIT:

Inspired by @rburing I wrote some (incomplete) code:

def berlekamp_basis(f):
    """
    INPUT: f a monic squarefree polynomial in F_q[x]
    OUTPUT: a list of polynomials hi in F_q[x] that represent
            a basis of the Berlekamp algebra associated to f
    """
    n = f.degree()
    GFX = f.parent()
    GFX_quo_f = GFX.quotient(f)
    g = []
    for k in range(n):
        basic_image = GFX(GFX_quo_f(x)^(q*k)) - GFX(x)^k
        g.append(basic_image)
    H = ???
    return H

So I have collected in g the images of a basis of GFX_quo_f under $\bar {Fr} - \bar {id}$. How do I compel sagemath to use this information to compute the kernel of this linear application?

EDIT 2:

Following the technical hints from @rburing below, I scrapped together this code:

def berlekamp_basis(f):
    """
    INPUT: f a monic squarefree polynomial in F_q[x]
    OUTPUT: a list of polynomials hi in F_q[x] that represent
            a basis of the Berlekamp algebra associated to f
    """
    n = f.degree()
    GFX = f.parent()
    x = GFX.gen()
    q = GFX.base().order()
    GFX_quo_f = GFX.quotient(f)
    g = []
    for k in range(n):
        basic_image = GFX_quo_f(x^(q*k)- x^k)
        g.append(vector(basic_image))
    H = matrix(g).right_kernel().basis()
    H = [GFX(h) for h in H]
    return H

When I run the following test:

GF9.<a> = GF(3^2)
GF9X.<x> = GF9[x]
f = x**3 + x**2 + x - a
assert(f.is_squarefree())
berlekamp_basis(f)

I get a big scary error:

Error in lines 42-42
Traceback (most recent call last):
  File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
    flags=compile_flags) in namespace, locals
  File "", line 1, in <module>
  File "", line 17, in berlekamp_basis
  File "sage/structure/parent.pyx", line 921, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9679)
    return mor._call_(x)
  File "sage/structure/coerce_maps.pyx", line 145, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4574)
    raise
  File "sage/structure/coerce_maps.pyx", line 140, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4442)
    return C._element_constructor(x)
  File "/ext/sage/sage-8.4_1804/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_ring.py", line 460, in _element_constructor_
    return C(self, x, check, is_gen, construct=construct, **kwds)
  File "sage/rings/polynomial/polynomial_zz_pex.pyx", line 145, in sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX.__init__ (build/cythonized/sage/rings/polynomial/polynomial_zz_pex.cpp:15712)
    Polynomial_template.__init__(self, parent, x, check, is_gen, construct)
  File "sage/rings/polynomial/polynomial_template.pxi", line 176, in sage.rings.polynomial.polynomial_zz_pex.Polynomial_template.__init__ (build/cythonized/sage/rings/polynomial/polynomial_zz_pex.cpp:8595)
    x = parent.base_ring()(x)
  File "sage/structure/parent.pyx", line 921, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9679)
    return mor._call_(x)
  File "sage/structure/coerce_maps.pyx", line 145, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4574)
    raise
  File "sage/structure/coerce_maps.pyx", line 140, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4442)
    return C._element_constructor(x)
  File "/ext/sage/sage-8.4_1804/local/lib/python2.7/site-packages/sage/rings/finite_rings/finite_field_givaro.py", line 370, in _element_constructor_
    return self._cache.element_from_data(e)
  File "sage/rings/finite_rings/element_givaro.pyx", line 318, in sage.rings.finite_rings.element_givaro.Cache_givaro.element_from_data (build/cythonized/sage/rings/finite_rings/element_givaro.cpp:7809)
    cpdef FiniteField_givaroElement element_from_data(self, e):
  File "sage/rings/finite_rings/element_givaro.pyx", line 407, in sage.rings.finite_rings.element_givaro.Cache_givaro.element_from_data (build/cythonized/sage/rings/finite_rings/element_givaro.cpp:6166)
    raise TypeError("e.parent must match self.vector_space")
TypeError: e.parent must match self.vector_space