Hermite form computation for function fields

This module provides an optimized implementation of the algorithm computing Hermite forms of matrices over polynomials. This is the workhorse of the function field machinery of Sage.

EXAMPLES:

Sage

sage: P.<x> = PolynomialRing(QQ)
sage: A = matrix(P,3,[-(x-1)^((i-j+1) % 3) for i in range(3) for j in range(3)])
sage: A
[        -x + 1             -1 -x^2 + 2*x - 1]
[-x^2 + 2*x - 1         -x + 1             -1]
[            -1 -x^2 + 2*x - 1         -x + 1]
sage: from sage.rings.function_field.hermite_form_polynomial import reversed_hermite_form
sage: B = copy(A)
sage: U = reversed_hermite_form(B, transformation=True)
sage: U * A == B
True
sage: B
[x^3 - 3*x^2 + 3*x - 2                     0                     0]
[                    0 x^3 - 3*x^2 + 3*x - 2                     0]
[        x^2 - 2*x + 1                 x - 1                     1]

Python

>>> from sage.all import *
>>> P = PolynomialRing(QQ, names=('x',)); (x,) = P._first_ngens(1)
>>> A = matrix(P,Integer(3),[-(x-Integer(1))**((i-j+Integer(1)) % Integer(3)) for i in range(Integer(3)) for j in range(Integer(3))])
>>> A
[        -x + 1             -1 -x^2 + 2*x - 1]
[-x^2 + 2*x - 1         -x + 1             -1]
[            -1 -x^2 + 2*x - 1         -x + 1]
>>> from sage.rings.function_field.hermite_form_polynomial import reversed_hermite_form
>>> B = copy(A)
>>> U = reversed_hermite_form(B, transformation=True)
>>> U * A == B
True
>>> B
[x^3 - 3*x^2 + 3*x - 2                     0                     0]
[                    0 x^3 - 3*x^2 + 3*x - 2                     0]
[        x^2 - 2*x + 1                 x - 1                     1]

Sage Live

P.<x> = PolynomialRing(QQ)
A = matrix(P,3,[-(x-1)^((i-j+1) % 3) for i in range(3) for j in range(3)])
A
from sage.rings.function_field.hermite_form_polynomial import reversed_hermite_form
B = copy(A)
U = reversed_hermite_form(B, transformation=True)
U * A == B
B

The function reversed_hermite_form() computes the reversed hermite form, which is reversed both row-wise and column-wise from the usual hermite form. Let us check it:

Sage

sage: A.reverse_rows_and_columns()
sage: C = copy(A.hermite_form())
sage: C.reverse_rows_and_columns()
sage: C
[x^3 - 3*x^2 + 3*x - 2                    0                     0]
[                    0 x^3 - 3*x^2 + 3*x - 2                     0]
[        x^2 - 2*x + 1                 x - 1                     1]
sage: C == B
True

Python

>>> from sage.all import *
>>> A.reverse_rows_and_columns()
>>> C = copy(A.hermite_form())
>>> C.reverse_rows_and_columns()
>>> C
[x^3 - 3*x^2 + 3*x - 2                    0                     0]
[                    0 x^3 - 3*x^2 + 3*x - 2                     0]
[        x^2 - 2*x + 1                 x - 1                     1]
>>> C == B
True

Sage Live

A.reverse_rows_and_columns()
C = copy(A.hermite_form())
C.reverse_rows_and_columns()
C
C == B

AUTHORS:

• Kwankyu Lee (2021-05-21): initial version

sage.rings.function_field.hermite_form_polynomial.reversed_hermite_form(mat, transformation=False)

Transform the matrix in place to reversed hermite normal form and optionally return the transformation matrix.

INPUT:

• transformation – boolean (default: False); if True, return the transformation matrix

EXAMPLES:

Sage

sage: from sage.rings.function_field.hermite_form_polynomial import reversed_hermite_form
sage: P.<x> = PolynomialRing(QQ)
sage: A = matrix(P,3,[-(x-1)^((i-2*j) % 4) for i in range(3) for j in range(3)])
sage: A
[                    -1         -x^2 + 2*x - 1                     -1]
[                -x + 1 -x^3 + 3*x^2 - 3*x + 1                 -x + 1]
[        -x^2 + 2*x - 1                     -1         -x^2 + 2*x - 1]
sage: B = copy(A)
sage: U = reversed_hermite_form(B, transformation=True)
sage: U * A == B
True
sage: B
[                        0                         0                         0]
[                        0 x^4 - 4*x^3 + 6*x^2 - 4*x                         0]
[                        1             x^2 - 2*x + 1                         1]

Python

>>> from sage.all import *
>>> from sage.rings.function_field.hermite_form_polynomial import reversed_hermite_form
>>> P = PolynomialRing(QQ, names=('x',)); (x,) = P._first_ngens(1)
>>> A = matrix(P,Integer(3),[-(x-Integer(1))**((i-Integer(2)*j) % Integer(4)) for i in range(Integer(3)) for j in range(Integer(3))])
>>> A
[                    -1         -x^2 + 2*x - 1                     -1]
[                -x + 1 -x^3 + 3*x^2 - 3*x + 1                 -x + 1]
[        -x^2 + 2*x - 1                     -1         -x^2 + 2*x - 1]
>>> B = copy(A)
>>> U = reversed_hermite_form(B, transformation=True)
>>> U * A == B
True
>>> B
[                        0                         0                         0]
[                        0 x^4 - 4*x^3 + 6*x^2 - 4*x                         0]
[                        1             x^2 - 2*x + 1                         1]

Sage Live

from sage.rings.function_field.hermite_form_polynomial import reversed_hermite_form
P.<x> = PolynomialRing(QQ)
A = matrix(P,3,[-(x-1)^((i-2*j) % 4) for i in range(3) for j in range(3)])
A
B = copy(A)
U = reversed_hermite_form(B, transformation=True)
U * A == B
B

Make live