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: 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]

>>> 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]

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: 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

>>> 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

AUTHORS:

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

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

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: 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]

>>> 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]