Implementing linear maps and their inverses in SageMath and Magma

[Sai Chandhrasekhar]

Cross-post from: https://ask.sagemath.org/question/80862/implementing-linear-maps-and-their-inverses-in-sagemath-and-magma/

I am currently trying to implement the linear maps in this post:
https://math.stackexchange.com/questions/5015461/computing-the-inverses-of-two-linear-maps in Magma and SageMath. So far I have successfully implemented the maps in Magma and am currently trying to implement `X` in SageMath.

My Magma code for `X`:

```

k := 8;
    Fq := GF(2^k);
    F := FunctionField(Fq);
    places := Places(F, 1);
    G := &+[places[i]: i in [2..k]];
    B1 := Basis(G);
    places := [places[i]: i in [k+1..2*k]];
    X_matrix := Matrix([[Evaluate(f, P): P in places]: f in B1]);
    X := function(f)
      return Vector([Evaluate(f, P) : P in places]);
    end function;
    X_inv := function(v)
       coeffs:= Solution(X_matrix, v);
       return &+[coeffs[i] * B1[i]: i in [1..k]];
    end function;

``` 

My SageMath code for `X`:
```
    k = 8
    m = 16
    Fq = GF(2^k)
    F.<x> = FunctionField(Fq)
    places = F.places()
    G = sum(places[i] for i in range(1,k))
    B1 = list(reversed(G.basis_function_space()))
    places = places[k:2*k]
    X_matrix = matrix([[f.evaluate(p) for p in places] for f in B1])
    def X(f):
        return vector([f.evaluate(p) for p in places])
    def X_inv(v):
        coeffs = X_matrix.solve_right(v)
        return sum(coeff * b for coeff, b in zip(coeffs, B1))

```

`X` does not work correctly in SageMath. I have noticed that `v`, `B1`, and `X_matrix` are symbolically represented in Magma with `F`'s generator inside `X_inv` rather than `Fq`'s as they are outside. 

`v`:

outside `X_inv`:
```
    (1  Fq.1^25  Fq.1^50 Fq.1^198 Fq.1^223 Fq.1^238 Fq.1^104  Fq.1^75)
```
inside `X_inv`:
```
    (1  $.1^25  $.1^50 $.1^198 $.1^223 $.1^238 $.1^104  $.1^75)
```
`B1`:

outside `X_inv`:
```
    [
        ($.1)^-1 * ($.1 + Fq.1)^-1 * ($.1 + Fq.1^2)^-1 * ($.1 + Fq.1^3)^-1 * ($.1 +
            Fq.1^4)^-1 * ($.1 + Fq.1^5)^-1 * ($.1 + Fq.1^6)^-1,
        ($.1 + Fq.1)^-1 * ($.1 + Fq.1^2)^-1 * ($.1 + Fq.1^3)^-1 * ($.1 + Fq.1^4)^-1
        * ($.1 + Fq.1^5)^-1 * ($.1 + Fq.1^6)^-1,
        ($.1) * ($.1 + Fq.1)^-1 * ($.1 + Fq.1^2)^-1 * ($.1 + Fq.1^3)^-1 * ($.1 +
            Fq.1^4)^-1 * ($.1 + Fq.1^5)^-1 * ($.1 + Fq.1^6)^-1,
        ($.1)^2 * ($.1 + Fq.1)^-1 * ($.1 + Fq.1^2)^-1 * ($.1 + Fq.1^3)^-1 * ($.1 +
            Fq.1^4)^-1 * ($.1 + Fq.1^5)^-1 * ($.1 + Fq.1^6)^-1,
        ($.1)^3 * ($.1 + Fq.1)^-1 * ($.1 + Fq.1^2)^-1 * ($.1 + Fq.1^3)^-1 * ($.1 +
            Fq.1^4)^-1 * ($.1 + Fq.1^5)^-1 * ($.1 + Fq.1^6)^-1,
        ($.1)^4 * ($.1 + Fq.1)^-1 * ($.1 + Fq.1^2)^-1 * ($.1 + Fq.1^3)^-1 * ($.1 +
            Fq.1^4)^-1 * ($.1 + Fq.1^5)^-1 * ($.1 + Fq.1^6)^-1,
        ($.1)^5 * ($.1 + Fq.1)^-1 * ($.1 + Fq.1^2)^-1 * ($.1 + Fq.1^3)^-1 * ($.1 +
            Fq.1^4)^-1 * ($.1 + Fq.1^5)^-1 * ($.1 + Fq.1^6)^-1,
        ($.1)^6 * ($.1 + Fq.1)^-1 * ($.1 + Fq.1^2)^-1 * ($.1 + Fq.1^3)^-1 * ($.1 +
            Fq.1^4)^-1 * ($.1 + Fq.1^5)^-1 * ($.1 + Fq.1^6)^-1
    ]
```

inside `X_inv`:
```
    [
        ($.1)^-1 * ($.1 + $.1)^-1 * ($.1 + $.1^2)^-1 * ($.1 + $.1^3)^-1 * ($.1 +
            $.1^4)^-1 * ($.1 + $.1^5)^-1 * ($.1 + $.1^6)^-1,
        ($.1 + $.1)^-1 * ($.1 + $.1^2)^-1 * ($.1 + $.1^3)^-1 * ($.1 + $.1^4)^-1 *
        ($.1 + $.1^5)^-1 * ($.1 + $.1^6)^-1,
        ($.1) * ($.1 + $.1)^-1 * ($.1 + $.1^2)^-1 * ($.1 + $.1^3)^-1 * ($.1 +
            $.1^4)^-1 * ($.1 + $.1^5)^-1 * ($.1 + $.1^6)^-1,
        ($.1)^2 * ($.1 + $.1)^-1 * ($.1 + $.1^2)^-1 * ($.1 + $.1^3)^-1 * ($.1 +
            $.1^4)^-1 * ($.1 + $.1^5)^-1 * ($.1 + $.1^6)^-1,
        ($.1)^3 * ($.1 + $.1)^-1 * ($.1 + $.1^2)^-1 * ($.1 + $.1^3)^-1 * ($.1 +
            $.1^4)^-1 * ($.1 + $.1^5)^-1 * ($.1 + $.1^6)^-1,
        ($.1)^4 * ($.1 + $.1)^-1 * ($.1 + $.1^2)^-1 * ($.1 + $.1^3)^-1 * ($.1 +
            $.1^4)^-1 * ($.1 + $.1^5)^-1 * ($.1 + $.1^6)^-1,
        ($.1)^5 * ($.1 + $.1)^-1 * ($.1 + $.1^2)^-1 * ($.1 + $.1^3)^-1 * ($.1 +
            $.1^4)^-1 * ($.1 + $.1^5)^-1 * ($.1 + $.1^6)^-1,
        ($.1)^6 * ($.1 + $.1)^-1 * ($.1 + $.1^2)^-1 * ($.1 + $.1^3)^-1 * ($.1 +
            $.1^4)^-1 * ($.1 + $.1^5)^-1 * ($.1 + $.1^6)^-1
    ]
```

`X_matrix`:

outside `X_inv`:
```
    [ Fq.1^10 Fq.1^177  Fq.1^26 Fq.1^128 Fq.1^206  Fq.1^98 Fq.1^161 Fq.1^173]
    [ Fq.1^17 Fq.1^185  Fq.1^35 Fq.1^138 Fq.1^217 Fq.1^110 Fq.1^174 Fq.1^187]
    [ Fq.1^24 Fq.1^193  Fq.1^44 Fq.1^148 Fq.1^228 Fq.1^122 Fq.1^187 Fq.1^201]
    [ Fq.1^31 Fq.1^201  Fq.1^53 Fq.1^158 Fq.1^239 Fq.1^134 Fq.1^200 Fq.1^215]
    [ Fq.1^38 Fq.1^209  Fq.1^62 Fq.1^168 Fq.1^250 Fq.1^146 Fq.1^213 Fq.1^229]
    [ Fq.1^45 Fq.1^217  Fq.1^71 Fq.1^178   Fq.1^6 Fq.1^158 Fq.1^226 Fq.1^243]
    [ Fq.1^52 Fq.1^225  Fq.1^80 Fq.1^188  Fq.1^17 Fq.1^170 Fq.1^239   Fq.1^2]
    [ Fq.1^59 Fq.1^233  Fq.1^89 Fq.1^198  Fq.1^28 Fq.1^182 Fq.1^252  Fq.1^16]
```

inside `X_inv`:
```
    [ $.1^10 $.1^177  $.1^26 $.1^128 $.1^206  $.1^98 $.1^161 $.1^173]
    [ $.1^17 $.1^185  $.1^35 $.1^138 $.1^217 $.1^110 $.1^174 $.1^187]
    [ $.1^24 $.1^193  $.1^44 $.1^148 $.1^228 $.1^122 $.1^187 $.1^201]
    [ $.1^31 $.1^201  $.1^53 $.1^158 $.1^239 $.1^134 $.1^200 $.1^215]
    [ $.1^38 $.1^209  $.1^62 $.1^168 $.1^250 $.1^146 $.1^213 $.1^229]
    [ $.1^45 $.1^217  $.1^71 $.1^178   $.1^6 $.1^158 $.1^226 $.1^243]
    [ $.1^52 $.1^225  $.1^80 $.1^188  $.1^17 $.1^170 $.1^239   $.1^2]
    [ $.1^59 $.1^233  $.1^89 $.1^198  $.1^28 $.1^182 $.1^252  $.1^16]
```
I have figured out how to symbolically represent `X_matrix` and `v` similarly in SageMath but am unsure how to do so with `B1`.

`B1` in SageMath:
```
    [
    1/(x^7 + (z8^6 + z8^5 + z8^4 + z8^3 + z8^2 + z8)*x^6 + z8^2*x^5 + (z8^7 + z8^4 + z8^3 + z8^2 + z8)*x^4 + (z8^5 + z8^4 + z8^3 + z8)*x^3 + (z8^5 + z8^4 + 1)*x^2 + (z8^6 + z8^5 + z8^4 + z8^2 + 1)*x),
    1/(x^6 + (z8^6 + z8^5 + z8^4 + z8^3 + z8^2 + z8)*x^5 + z8^2*x^4 + (z8^7 + z8^4 + z8^3 + z8^2 + z8)*x^3 + (z8^5 + z8^4 + z8^3 + z8)*x^2 + (z8^5 + z8^4 + 1)*x + z8^6 + z8^5 + z8^4 + z8^2 + 1),
    x/(x^6 + (z8^6 + z8^5 + z8^4 + z8^3 + z8^2 + z8)*x^5 + z8^2*x^4 + (z8^7 + z8^4 + z8^3 + z8^2 + z8)*x^3 + (z8^5 + z8^4 + z8^3 + z8)*x^2 + (z8^5 + z8^4 + 1)*x + z8^6 + z8^5 + z8^4 + z8^2 + 1),
    x^2/(x^6 + (z8^6 + z8^5 + z8^4 + z8^3 + z8^2 + z8)*x^5 + z8^2*x^4 + (z8^7 + z8^4 + z8^3 + z8^2 + z8)*x^3 + (z8^5 + z8^4 + z8^3 + z8)*x^2 + (z8^5 + z8^4 + 1)*x + z8^6 + z8^5 + z8^4 + z8^2 + 1),
    x^3/(x^6 + (z8^6 + z8^5 + z8^4 + z8^3 + z8^2 + z8)*x^5 + z8^2*x^4 + (z8^7 + z8^4 + z8^3 + z8^2 + z8)*x^3 + (z8^5 + z8^4 + z8^3 + z8)*x^2 + (z8^5 + z8^4 + 1)*x + z8^6 + z8^5 + z8^4 + z8^2 + 1),
    x^4/(x^6 + (z8^6 + z8^5 + z8^4 + z8^3 + z8^2 + z8)*x^5 + z8^2*x^4 + (z8^7 + z8^4 + z8^3 + z8^2 + z8)*x^3 + (z8^5 + z8^4 + z8^3 + z8)*x^2 + (z8^5 + z8^4 + 1)*x + z8^6 + z8^5 + z8^4 + z8^2 + 1),
    x^5/(x^6 + (z8^6 + z8^5 + z8^4 + z8^3 + z8^2 + z8)*x^5 + z8^2*x^4 + (z8^7 + z8^4 + z8^3 + z8^2 + z8)*x^3 + (z8^5 + z8^4 + z8^3 + z8)*x^2 + (z8^5 + z8^4 + 1)*x + z8^6 + z8^5 + z8^4 + z8^2 + 1),
    x^6/(x^6 + (z8^6 + z8^5 + z8^4 + z8^3 + z8^2 + z8)*x^5 + z8^2*x^4 + (z8^7 + z8^4 + z8^3 + z8^2 + z8)*x^3 + (z8^5 + z8^4 + z8^3 + z8)*x^2 + (z8^5 + z8^4 + 1)*x + z8^6 + z8^5 + z8^4 + z8^2 + 1)
    ]
```
Any help would be much appreciated.

[Kwankyu]

X_matrix = matrix([[f.evaluate(p) for p in places] for f in B1]).transpose()

will work for you.

[Sai Chandhrasekhar]

The solution you proposed worked. What is the explanation for why it worked?

I am now trying to implement Y in SageMath. 

B2 = (2*G).basis_function_space()

R.<y> = Fq[]
Q = R.irreducible_element(16)
L.<z> = Fq.extension(Q)
div = Q(x).divisor()
P = None;
for place in div.support():
    if(place.degree() == 16):
        P = place

Y_matrix = matrix([morph(a).list() for a in [f.evaluate(P) for f in B2]]).transpose()

def Y(f):
    return morph(f.evaluate(P))

def Y_inv(alpha):
    coeffs = Y_matrix.solve_right(vector(alpha.list()))
    print(len(coeffs))
    #return sum(coeff * b for coeff, b in zip(coeffs, B2))

However, Y_matrix.solve_right() has no solutions. I created the morphism in order to get a result of length 16.   

My Magma code for Y:

m := 16;
P := RandomPlace(F, m);
Fqm := ResidueClassField(P);
Y_matrix := Matrix([Eltseq(a): a in [Evaluate(f, P): f in B2]]);
Y := function(f)
    return Evaluate(f, P);
end function;
Y_inv := function(alpha)
    coeffs := Solution(Y_matrix, Vector(Eltseq(alpha)));
    return &+[coeffs[i] * B2[i]: i in [1..#B2]];
end function;

[Kwankyu]

On Friday, January 3, 2025 at 1:27:47 PM UTC+9 skchandh...@gmail.com wrote:

The solution you proposed worked. What is the explanation for why it worked?

Just linear algebra. You may use solve_left() instead if the method exists.

[Sai Chandhrasekhar]

I tried to use solve_left with the 15x16 tau_matrix and the 1x16 alpha.list() and still got no solutions. 

[Sai Chandhrasekhar]

Is there anyone else here who could help me with this? I am really stuck. 

[Lubabalo ngxale]

Tnx

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/sage-support/62646890-e3b7-4ef0-b492-5bd16d1f9bffn%40googlegroups.com.

[Sai Chandhrasekhar]

Y_matrix is not square. Its dimensions are 15x16, so the system of equations is underdetermined. Does anyone have an idea of why this has no solution in Sage but does in Magma?