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]