Modular algorithm to compute Hermite normal forms of integer matrices

AUTHORS:

  • Clement Pernet and William Stein (2008-02-07): initial version

sage.matrix.matrix_integer_dense_hnf.add_column(B, H_B, a, proof)[source]

The add column procedure.

INPUT:

  • B – a square matrix (may be singular)

  • H_B – the Hermite normal form of B

  • a – an n x 1 matrix, where B has n rows

  • proof – boolean; whether to prove result correct, in case we use fallback method

OUTPUT:

  • x – a vector such that H’ = H_B.augment(x) is the HNF of A = B.augment(a)

EXAMPLES:

sage: B = matrix(ZZ, 3, 3, [1,2,5, 0,-5,3, 1,1,2])
sage: H_B = B.echelon_form()
sage: a = matrix(ZZ, 3, 1, [1,8,-2])
sage: import sage.matrix.matrix_integer_dense_hnf as hnf
sage: x = hnf.add_column(B, H_B, a, True); x
[18]
[ 3]
[23]
sage: H_B.augment(x)
[ 1  0 17 18]
[ 0  1  3  3]
[ 0  0 18 23]
sage: B.augment(a).echelon_form()
[ 1  0 17 18]
[ 0  1  3  3]
[ 0  0 18 23]

>>> from sage.all import *
>>> B = matrix(ZZ, Integer(3), Integer(3), [Integer(1),Integer(2),Integer(5), Integer(0),-Integer(5),Integer(3), Integer(1),Integer(1),Integer(2)])
>>> H_B = B.echelon_form()
>>> a = matrix(ZZ, Integer(3), Integer(1), [Integer(1),Integer(8),-Integer(2)])
>>> import sage.matrix.matrix_integer_dense_hnf as hnf
>>> x = hnf.add_column(B, H_B, a, True); x
[18]
[ 3]
[23]
>>> H_B.augment(x)
[ 1  0 17 18]
[ 0  1  3  3]
[ 0  0 18 23]
>>> B.augment(a).echelon_form()
[ 1  0 17 18]
[ 0  1  3  3]
[ 0  0 18 23]

B = matrix(ZZ, 3, 3, [1,2,5, 0,-5,3, 1,1,2])
H_B = B.echelon_form()
a = matrix(ZZ, 3, 1, [1,8,-2])
import sage.matrix.matrix_integer_dense_hnf as hnf
x = hnf.add_column(B, H_B, a, True); x
H_B.augment(x)
B.augment(a).echelon_form()
sage.matrix.matrix_integer_dense_hnf.add_column_fallback(B, a, proof)[source]

Simplistic version of add_column, in case the powerful clever one fails (e.g., B is singular).

INPUT:

  • B – a square matrix (may be singular)

  • a – an n x 1 matrix, where B has n rows

  • proof – boolean; whether to prove result correct

OUTPUT: x; a vector such that H' = H_B.augment(x) is the HNF of A = B.augment(a)

EXAMPLES:

sage: B = matrix(ZZ,3, [-1, -1, 1, -3, 8, -2, -1, -1, -1])
sage: a = matrix(ZZ,3,1, [1,2,3])
sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: matrix_integer_dense_hnf.add_column_fallback(B, a, True)
[-3]
[-7]
[-2]
sage: matrix_integer_dense_hnf.add_column_fallback(B, a, False)
[-3]
[-7]
[-2]
sage: B.augment(a).hermite_form()
[ 1  1  1 -3]
[ 0 11  1 -7]
[ 0  0  2 -2]

>>> from sage.all import *
>>> B = matrix(ZZ,Integer(3), [-Integer(1), -Integer(1), Integer(1), -Integer(3), Integer(8), -Integer(2), -Integer(1), -Integer(1), -Integer(1)])
>>> a = matrix(ZZ,Integer(3),Integer(1), [Integer(1),Integer(2),Integer(3)])
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> matrix_integer_dense_hnf.add_column_fallback(B, a, True)
[-3]
[-7]
[-2]
>>> matrix_integer_dense_hnf.add_column_fallback(B, a, False)
[-3]
[-7]
[-2]
>>> B.augment(a).hermite_form()
[ 1  1  1 -3]
[ 0 11  1 -7]
[ 0  0  2 -2]

B = matrix(ZZ,3, [-1, -1, 1, -3, 8, -2, -1, -1, -1])
a = matrix(ZZ,3,1, [1,2,3])
import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
matrix_integer_dense_hnf.add_column_fallback(B, a, True)
matrix_integer_dense_hnf.add_column_fallback(B, a, False)
B.augment(a).hermite_form()
sage.matrix.matrix_integer_dense_hnf.add_row(A, b, pivots, include_zero_rows)[source]

The add row procedure.

INPUT:

  • A – a matrix in Hermite normal form with n column

  • b – an n x 1 row matrix

  • pivots – sorted list of integers; the pivot positions of A

OUTPUT:

  • H – the Hermite normal form of A.stack(b)

  • new_pivots – the pivot columns of H

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as hnf
sage: A = matrix(ZZ, 2, 3, [-21, -7, 5, 1,20,-7])
sage: b = matrix(ZZ, 1,3, [-1,1,-1])
sage: hnf.add_row(A, b, A.pivots(), True)
(
[ 1  6 29]
[ 0  7 28]
[ 0  0 46], [0, 1, 2]
)
sage: A.stack(b).echelon_form()
[ 1  6 29]
[ 0  7 28]
[ 0  0 46]

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as hnf
>>> A = matrix(ZZ, Integer(2), Integer(3), [-Integer(21), -Integer(7), Integer(5), Integer(1),Integer(20),-Integer(7)])
>>> b = matrix(ZZ, Integer(1),Integer(3), [-Integer(1),Integer(1),-Integer(1)])
>>> hnf.add_row(A, b, A.pivots(), True)
(
[ 1  6 29]
[ 0  7 28]
[ 0  0 46], [0, 1, 2]
)
>>> A.stack(b).echelon_form()
[ 1  6 29]
[ 0  7 28]
[ 0  0 46]

import sage.matrix.matrix_integer_dense_hnf as hnf
A = matrix(ZZ, 2, 3, [-21, -7, 5, 1,20,-7])
b = matrix(ZZ, 1,3, [-1,1,-1])
hnf.add_row(A, b, A.pivots(), True)
A.stack(b).echelon_form()
sage.matrix.matrix_integer_dense_hnf.benchmark_hnf(nrange, bits=4)[source]

Run benchmark program.

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as hnf
sage: hnf.benchmark_hnf([10,25],32)
('sage', 10, 32, ...),
('sage', 25, 32, ...),

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as hnf
>>> hnf.benchmark_hnf([Integer(10),Integer(25)],Integer(32))
('sage', 10, 32, ...),
('sage', 25, 32, ...),

import sage.matrix.matrix_integer_dense_hnf as hnf
hnf.benchmark_hnf([10,25],32)
sage.matrix.matrix_integer_dense_hnf.benchmark_magma_hnf(nrange, bits=4)[source]

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as hnf
sage: hnf.benchmark_magma_hnf([50,100],32)     # optional - magma
('magma', 50, 32, ...),
('magma', 100, 32, ...),

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as hnf
>>> hnf.benchmark_magma_hnf([Integer(50),Integer(100)],Integer(32))     # optional - magma
('magma', 50, 32, ...),
('magma', 100, 32, ...),

import sage.matrix.matrix_integer_dense_hnf as hnf
hnf.benchmark_magma_hnf([50,100],32)     # optional - magma
sage.matrix.matrix_integer_dense_hnf.det_from_modp_and_divisor(A, d, p, z_mod, moduli, z_so_far=1, N_so_far=1)[source]

This is used for internal purposes for computing determinants quickly (with the hybrid \(p\)-adic / multimodular algorithm).

INPUT:

  • A – a square matrix

  • d – a divisor of the determinant of A

  • p – a prime

  • z_mod – values of det/d (mod …)

  • moduli – the moduli so far

  • z_so_far – for a modulus p in the list moduli, (z_so_far mod p) is the determinant of A modulo p

  • N_so_far – N_so_far is the product over the primes in the list moduli

OUTPUT:

  • A triple (det bound, new z_so_far, new N_so_far).

EXAMPLES:

sage: a = matrix(ZZ, 3, [6, 1, 2, -56, -2, -1, -11, 2, -3])
sage: factor(a.det())
-1 * 13 * 29
sage: d = 13
sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: matrix_integer_dense_hnf.det_from_modp_and_divisor(a, d, 97, [], [])
(-377, -29, 97)
sage: a.det()
-377

>>> from sage.all import *
>>> a = matrix(ZZ, Integer(3), [Integer(6), Integer(1), Integer(2), -Integer(56), -Integer(2), -Integer(1), -Integer(11), Integer(2), -Integer(3)])
>>> factor(a.det())
-1 * 13 * 29
>>> d = Integer(13)
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> matrix_integer_dense_hnf.det_from_modp_and_divisor(a, d, Integer(97), [], [])
(-377, -29, 97)
>>> a.det()
-377

a = matrix(ZZ, 3, [6, 1, 2, -56, -2, -1, -11, 2, -3])
factor(a.det())
d = 13
import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
matrix_integer_dense_hnf.det_from_modp_and_divisor(a, d, 97, [], [])
a.det()
sage.matrix.matrix_integer_dense_hnf.det_given_divisor(A, d, proof=True, stabilize=2)[source]

Given a divisor d of the determinant of A, compute the determinant of A.

INPUT:

  • A – square integer matrix

  • d – nonzero integer that is assumed to divide the determinant of A

  • proof – boolean (default: True); compute det modulo enough primes so that the determinant is computed provably correctly (via the Hadamard bound). It would be VERY hard for det() to fail even when proof is False.

  • stabilize – integer (default: 2); if proof = False, then compute the determinant modulo \(p\) until stabilize successive modulo determinant computations stabilize.

OUTPUT: integer; determinant

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: a = matrix(ZZ,3,[-1, -1, -1, -20, 4, 1, -1, 1, 2])
sage: matrix_integer_dense_hnf.det_given_divisor(a, 3)
-30
sage: matrix_integer_dense_hnf.det_given_divisor(a, 3, proof=False)
-30
sage: matrix_integer_dense_hnf.det_given_divisor(a, 3, proof=False, stabilize=1)
-30
sage: a.det()
-30

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> a = matrix(ZZ,Integer(3),[-Integer(1), -Integer(1), -Integer(1), -Integer(20), Integer(4), Integer(1), -Integer(1), Integer(1), Integer(2)])
>>> matrix_integer_dense_hnf.det_given_divisor(a, Integer(3))
-30
>>> matrix_integer_dense_hnf.det_given_divisor(a, Integer(3), proof=False)
-30
>>> matrix_integer_dense_hnf.det_given_divisor(a, Integer(3), proof=False, stabilize=Integer(1))
-30
>>> a.det()
-30

import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
a = matrix(ZZ,3,[-1, -1, -1, -20, 4, 1, -1, 1, 2])
matrix_integer_dense_hnf.det_given_divisor(a, 3)
matrix_integer_dense_hnf.det_given_divisor(a, 3, proof=False)
matrix_integer_dense_hnf.det_given_divisor(a, 3, proof=False, stabilize=1)
a.det()

Here we illustrate proof=False giving a wrong answer:

sage: p = matrix_integer_dense_hnf.max_det_prime(2)
sage: q = previous_prime(p)
sage: a = matrix(ZZ, 2, [p, 0, 0, q])
sage: p * q
70368442188091
sage: matrix_integer_dense_hnf.det_given_divisor(a, 1, proof=False, stabilize=2)
0

>>> from sage.all import *
>>> p = matrix_integer_dense_hnf.max_det_prime(Integer(2))
>>> q = previous_prime(p)
>>> a = matrix(ZZ, Integer(2), [p, Integer(0), Integer(0), q])
>>> p * q
70368442188091
>>> matrix_integer_dense_hnf.det_given_divisor(a, Integer(1), proof=False, stabilize=Integer(2))
0

p = matrix_integer_dense_hnf.max_det_prime(2)
q = previous_prime(p)
a = matrix(ZZ, 2, [p, 0, 0, q])
p * q
matrix_integer_dense_hnf.det_given_divisor(a, 1, proof=False, stabilize=2)

This still works, because we do not work modulo primes that divide the determinant bound, which is found using a \(p\)-adic algorithm:

sage: a.det(proof=False, stabilize=2)
70368442188091

>>> from sage.all import *
>>> a.det(proof=False, stabilize=Integer(2))
70368442188091

a.det(proof=False, stabilize=2)

3 primes is enough:

sage: matrix_integer_dense_hnf.det_given_divisor(a, 1, proof=False, stabilize=3)
70368442188091
sage: matrix_integer_dense_hnf.det_given_divisor(a, 1, proof=False, stabilize=5)
70368442188091
sage: matrix_integer_dense_hnf.det_given_divisor(a, 1, proof=True)
70368442188091

>>> from sage.all import *
>>> matrix_integer_dense_hnf.det_given_divisor(a, Integer(1), proof=False, stabilize=Integer(3))
70368442188091
>>> matrix_integer_dense_hnf.det_given_divisor(a, Integer(1), proof=False, stabilize=Integer(5))
70368442188091
>>> matrix_integer_dense_hnf.det_given_divisor(a, Integer(1), proof=True)
70368442188091

matrix_integer_dense_hnf.det_given_divisor(a, 1, proof=False, stabilize=3)
matrix_integer_dense_hnf.det_given_divisor(a, 1, proof=False, stabilize=5)
matrix_integer_dense_hnf.det_given_divisor(a, 1, proof=True)
sage.matrix.matrix_integer_dense_hnf.det_padic(A, proof=True, stabilize=2)[source]

Return the determinant of A, computed using a \(p\)-adic/multimodular algorithm.

INPUT:

  • A – a square matrix

  • proof – boolean

  • stabilize – (default: 2) if proof False, number of successive primes so that CRT det must stabilize

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as h
sage: a = matrix(ZZ, 3, [1..9])
sage: h.det_padic(a)
0
sage: a = matrix(ZZ, 3, [1,2,5,-7,8,10,192,5,18])
sage: h.det_padic(a)
-3669
sage: a.determinant(algorithm='ntl')
-3669

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as h
>>> a = matrix(ZZ, Integer(3), (ellipsis_range(Integer(1),Ellipsis,Integer(9))))
>>> h.det_padic(a)
0
>>> a = matrix(ZZ, Integer(3), [Integer(1),Integer(2),Integer(5),-Integer(7),Integer(8),Integer(10),Integer(192),Integer(5),Integer(18)])
>>> h.det_padic(a)
-3669
>>> a.determinant(algorithm='ntl')
-3669

import sage.matrix.matrix_integer_dense_hnf as h
a = matrix(ZZ, 3, [1..9])
h.det_padic(a)
a = matrix(ZZ, 3, [1,2,5,-7,8,10,192,5,18])
h.det_padic(a)
a.determinant(algorithm='ntl')
sage.matrix.matrix_integer_dense_hnf.double_det(A, b, c, proof)[source]

Compute the determinants of the stacked integer matrices A.stack(b) and A.stack(c).

INPUT:

  • A – an (n-1) x n matrix

  • b – a 1 x n matrix

  • c – a 1 x n matrix

  • proof – whether or not to compute the det modulo enough times to provably compute the determinant

OUTPUT: a pair of two integers

EXAMPLES:

sage: from sage.matrix.matrix_integer_dense_hnf import double_det
sage: A = matrix(ZZ, 2, 3, [1,2,3, 4,-2,5])
sage: b = matrix(ZZ, 1, 3, [1,-2,5])
sage: c = matrix(ZZ, 1, 3, [8,2,10])
sage: A.stack(b).det()
-48
sage: A.stack(c).det()
42
sage: double_det(A, b, c, False)
(-48, 42)

>>> from sage.all import *
>>> from sage.matrix.matrix_integer_dense_hnf import double_det
>>> A = matrix(ZZ, Integer(2), Integer(3), [Integer(1),Integer(2),Integer(3), Integer(4),-Integer(2),Integer(5)])
>>> b = matrix(ZZ, Integer(1), Integer(3), [Integer(1),-Integer(2),Integer(5)])
>>> c = matrix(ZZ, Integer(1), Integer(3), [Integer(8),Integer(2),Integer(10)])
>>> A.stack(b).det()
-48
>>> A.stack(c).det()
42
>>> double_det(A, b, c, False)
(-48, 42)

from sage.matrix.matrix_integer_dense_hnf import double_det
A = matrix(ZZ, 2, 3, [1,2,3, 4,-2,5])
b = matrix(ZZ, 1, 3, [1,-2,5])
c = matrix(ZZ, 1, 3, [8,2,10])
A.stack(b).det()
A.stack(c).det()
double_det(A, b, c, False)
sage.matrix.matrix_integer_dense_hnf.extract_ones_data(H, pivots)[source]

Compute ones data and corresponding submatrices of H.

This is used to optimized the add_row() function.

INPUT:

  • H – a matrix in HNF

  • pivots – list of all pivot column positions of H

OUTPUT:

C, D, E, onecol, onerow, non_onecol, non_onerow where onecol, onerow, non_onecol, non_onerow are as for the ones function, and C, D, E are matrices:

  • C – submatrix of all non-onecol columns and onecol rows

  • D – all non-onecol columns and other rows

  • E – inverse of D

If D is not invertible or there are 0 or more than 2 non onecols, then C, D, and E are set to None.

EXAMPLES:

sage: H = matrix(ZZ, 3, 4, [1, 0, 0, 7, 0, 1, 5, 2, 0, 0, 6, 6])
sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: matrix_integer_dense_hnf.extract_ones_data(H, [0,1,2])
(
[0]
[5], [6], [1/6], [0, 1], [0, 1], [2], [2]
)

>>> from sage.all import *
>>> H = matrix(ZZ, Integer(3), Integer(4), [Integer(1), Integer(0), Integer(0), Integer(7), Integer(0), Integer(1), Integer(5), Integer(2), Integer(0), Integer(0), Integer(6), Integer(6)])
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> matrix_integer_dense_hnf.extract_ones_data(H, [Integer(0),Integer(1),Integer(2)])
(
[0]
[5], [6], [1/6], [0, 1], [0, 1], [2], [2]
)

H = matrix(ZZ, 3, 4, [1, 0, 0, 7, 0, 1, 5, 2, 0, 0, 6, 6])
import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
matrix_integer_dense_hnf.extract_ones_data(H, [0,1,2])
Here we get None’s since the (2,2) position submatrix is not invertible.

sage: H = matrix(ZZ, 3, 5, [1, 0, 0, 45, -36, 0, 1, 0, 131, -107, 0, 0, 0, 178, -145]); H [ 1 0 0 45 -36] [ 0 1 0 131 -107] [ 0 0 0 178 -145] sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf sage: matrix_integer_dense_hnf.extract_ones_data(H, [0,1,3]) (None, None, None, [0, 1], [0, 1], [2], [2])

sage.matrix.matrix_integer_dense_hnf.hnf(A, include_zero_rows=True, proof=True)[source]

Return the Hermite Normal Form of a general integer matrix A, along with the pivot columns.

INPUT:

  • A – an n x m matrix A over the integers

  • include_zero_rows – boolean (default: True); whether or not to include zero rows in the output matrix

  • proof – whether or not to prove the result correct

OUTPUT: tuple of:

  • matrix – the Hermite normal form of A

  • pivots – the pivot column positions of A

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: a = matrix(ZZ,3,5,[-2, -6, -3, -17, -1, 2, -1, -1, -2, -1, -2, -2, -6, 9, 2])
sage: matrix_integer_dense_hnf.hnf(a)
(
[   2    0   26  -75  -10]
[   0    1   27  -73   -9]
[   0    0   37 -106  -13], [0, 1, 2]
)
sage: matrix_integer_dense_hnf.hnf(a.transpose())
(
[1 0 0]
[0 1 0]
[0 0 1]
[0 0 0]
[0 0 0], [0, 1, 2]
)
sage: matrix_integer_dense_hnf.hnf(a.transpose(), include_zero_rows=False)
(
[1 0 0]
[0 1 0]
[0 0 1], [0, 1, 2]
)

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> a = matrix(ZZ,Integer(3),Integer(5),[-Integer(2), -Integer(6), -Integer(3), -Integer(17), -Integer(1), Integer(2), -Integer(1), -Integer(1), -Integer(2), -Integer(1), -Integer(2), -Integer(2), -Integer(6), Integer(9), Integer(2)])
>>> matrix_integer_dense_hnf.hnf(a)
(
[   2    0   26  -75  -10]
[   0    1   27  -73   -9]
[   0    0   37 -106  -13], [0, 1, 2]
)
>>> matrix_integer_dense_hnf.hnf(a.transpose())
(
[1 0 0]
[0 1 0]
[0 0 1]
[0 0 0]
[0 0 0], [0, 1, 2]
)
>>> matrix_integer_dense_hnf.hnf(a.transpose(), include_zero_rows=False)
(
[1 0 0]
[0 1 0]
[0 0 1], [0, 1, 2]
)

import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
a = matrix(ZZ,3,5,[-2, -6, -3, -17, -1, 2, -1, -1, -2, -1, -2, -2, -6, 9, 2])
matrix_integer_dense_hnf.hnf(a)
matrix_integer_dense_hnf.hnf(a.transpose())
matrix_integer_dense_hnf.hnf(a.transpose(), include_zero_rows=False)
sage.matrix.matrix_integer_dense_hnf.hnf_square(A, proof)[source]

INPUT:

  • A – a nonsingular n x n matrix over the integers

OUTPUT: the Hermite normal form of A

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as hnf
sage: A = matrix(ZZ, 3, [-21, -7, 5, 1,20,-7, -1,1,-1])
sage: hnf.hnf_square(A, False)
[ 1  6 29]
[ 0  7 28]
[ 0  0 46]
sage: A.echelon_form()
[ 1  6 29]
[ 0  7 28]
[ 0  0 46]

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as hnf
>>> A = matrix(ZZ, Integer(3), [-Integer(21), -Integer(7), Integer(5), Integer(1),Integer(20),-Integer(7), -Integer(1),Integer(1),-Integer(1)])
>>> hnf.hnf_square(A, False)
[ 1  6 29]
[ 0  7 28]
[ 0  0 46]
>>> A.echelon_form()
[ 1  6 29]
[ 0  7 28]
[ 0  0 46]

import sage.matrix.matrix_integer_dense_hnf as hnf
A = matrix(ZZ, 3, [-21, -7, 5, 1,20,-7, -1,1,-1])
hnf.hnf_square(A, False)
A.echelon_form()
sage.matrix.matrix_integer_dense_hnf.hnf_with_transformation(A, proof=True)[source]

Compute the HNF H of A along with a transformation matrix U such that U*A = H.

INPUT:

  • A – an n x m matrix A over the integers

  • proof – whether or not to prove the result correct

OUTPUT: tuple of:

  • matrix – the Hermite normal form H of A

  • U – a unimodular matrix such that U * A = H

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: A = matrix(ZZ, 2, [1, -5, -10, 1, 3, 197]); A
[  1  -5 -10]
[  1   3 197]
sage: H, U = matrix_integer_dense_hnf.hnf_with_transformation(A)
sage: H
[  1   3 197]
[  0   8 207]
sage: U
[ 0  1]
[-1  1]
sage: U*A
[  1   3 197]
[  0   8 207]

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> A = matrix(ZZ, Integer(2), [Integer(1), -Integer(5), -Integer(10), Integer(1), Integer(3), Integer(197)]); A
[  1  -5 -10]
[  1   3 197]
>>> H, U = matrix_integer_dense_hnf.hnf_with_transformation(A)
>>> H
[  1   3 197]
[  0   8 207]
>>> U
[ 0  1]
[-1  1]
>>> U*A
[  1   3 197]
[  0   8 207]

import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
A = matrix(ZZ, 2, [1, -5, -10, 1, 3, 197]); A
H, U = matrix_integer_dense_hnf.hnf_with_transformation(A)
H
U
U*A
sage.matrix.matrix_integer_dense_hnf.hnf_with_transformation_tests(n=10, m=5, trials=10)[source]

Use this to randomly test that hnf with transformation matrix is working.

EXAMPLES:

sage: from sage.matrix.matrix_integer_dense_hnf import hnf_with_transformation_tests
sage: hnf_with_transformation_tests(n=15, m=10, trials=10)
0 1 2 3 4 5 6 7 8 9

>>> from sage.all import *
>>> from sage.matrix.matrix_integer_dense_hnf import hnf_with_transformation_tests
>>> hnf_with_transformation_tests(n=Integer(15), m=Integer(10), trials=Integer(10))
0 1 2 3 4 5 6 7 8 9

from sage.matrix.matrix_integer_dense_hnf import hnf_with_transformation_tests
hnf_with_transformation_tests(n=15, m=10, trials=10)
sage.matrix.matrix_integer_dense_hnf.interleave_matrices(A, B, cols1, cols2)[source]

INPUT:

  • A, B – matrices with the same number of rows

  • cols1, cols2 – disjoint lists of integers

OUTPUT:

construct a new matrix C by sticking the columns of A at the positions specified by cols1 and the columns of B at the positions specified by cols2.

EXAMPLES:

sage: A = matrix(ZZ, 2, [1,2,3,4]); B = matrix(ZZ, 2, [-1,5,2,3])
sage: A
[1 2]
[3 4]
sage: B
[-1  5]
[ 2  3]
sage: import sage.matrix.matrix_integer_dense_hnf as hnf
sage: hnf.interleave_matrices(A, B, [1,3], [0,2])
[-1  1  5  2]
[ 2  3  3  4]

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(2), [Integer(1),Integer(2),Integer(3),Integer(4)]); B = matrix(ZZ, Integer(2), [-Integer(1),Integer(5),Integer(2),Integer(3)])
>>> A
[1 2]
[3 4]
>>> B
[-1  5]
[ 2  3]
>>> import sage.matrix.matrix_integer_dense_hnf as hnf
>>> hnf.interleave_matrices(A, B, [Integer(1),Integer(3)], [Integer(0),Integer(2)])
[-1  1  5  2]
[ 2  3  3  4]

A = matrix(ZZ, 2, [1,2,3,4]); B = matrix(ZZ, 2, [-1,5,2,3])
A
B
import sage.matrix.matrix_integer_dense_hnf as hnf
hnf.interleave_matrices(A, B, [1,3], [0,2])
sage.matrix.matrix_integer_dense_hnf.is_in_hnf_form(H, pivots)[source]

Return whether the matrix H is in Hermite normal form with given pivot columns.

INPUT:

  • H – matrix

  • pivots – sorted list of integers

OUTPUT: boolean

EXAMPLES:

sage: a = matrix(ZZ,3,5,[-2, -6, -3, -17, -1, 2, -1, -1, -2, -1, -2, -2, -6, 9, 2])
sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: matrix_integer_dense_hnf.is_in_hnf_form(a,range(3))
False
sage: e = a.hermite_form(); p = a.pivots()
sage: matrix_integer_dense_hnf.is_in_hnf_form(e, p)
True

>>> from sage.all import *
>>> a = matrix(ZZ,Integer(3),Integer(5),[-Integer(2), -Integer(6), -Integer(3), -Integer(17), -Integer(1), Integer(2), -Integer(1), -Integer(1), -Integer(2), -Integer(1), -Integer(2), -Integer(2), -Integer(6), Integer(9), Integer(2)])
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> matrix_integer_dense_hnf.is_in_hnf_form(a,range(Integer(3)))
False
>>> e = a.hermite_form(); p = a.pivots()
>>> matrix_integer_dense_hnf.is_in_hnf_form(e, p)
True

a = matrix(ZZ,3,5,[-2, -6, -3, -17, -1, 2, -1, -1, -2, -1, -2, -2, -6, 9, 2])
import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
matrix_integer_dense_hnf.is_in_hnf_form(a,range(3))
e = a.hermite_form(); p = a.pivots()
matrix_integer_dense_hnf.is_in_hnf_form(e, p)
sage.matrix.matrix_integer_dense_hnf.max_det_prime(n)[source]

Return the largest prime so that it is reasonably efficient to compute modulo that prime with n x n matrices in LinBox.

INPUT:

  • n – positive integer

OUTPUT: a prime number

EXAMPLES:

sage: from sage.matrix.matrix_integer_dense_hnf import max_det_prime
sage: max_det_prime(10000)
8388593
sage: max_det_prime(1000)
8388593
sage: max_det_prime(10)
8388593

>>> from sage.all import *
>>> from sage.matrix.matrix_integer_dense_hnf import max_det_prime
>>> max_det_prime(Integer(10000))
8388593
>>> max_det_prime(Integer(1000))
8388593
>>> max_det_prime(Integer(10))
8388593

from sage.matrix.matrix_integer_dense_hnf import max_det_prime
max_det_prime(10000)
max_det_prime(1000)
max_det_prime(10)
sage.matrix.matrix_integer_dense_hnf.ones(H, pivots)[source]

Find all 1 pivot columns of the matrix H in Hermite form, along with the corresponding rows, and also the non 1 pivot columns and non-pivot rows. Here a 1 pivot column is a pivot column so that the leading bottom entry is 1.

INPUT:

  • H – matrix in Hermite form

  • pivots – list of integers (all pivot positions of H)

OUTPUT:

4-tuple of integer lists: onecol, onerow, non_oneol, non_onerow

EXAMPLES:

sage: H = matrix(ZZ, 3, 5, [1, 0, 0, 45, -36, 0, 1, 0, 131, -107, 0, 0, 0, 178, -145]); H
[   1    0    0   45  -36]
[   0    1    0  131 -107]
[   0    0    0  178 -145]
sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: matrix_integer_dense_hnf.ones(H, [0,1,3])
([0, 1], [0, 1], [2], [2])

>>> from sage.all import *
>>> H = matrix(ZZ, Integer(3), Integer(5), [Integer(1), Integer(0), Integer(0), Integer(45), -Integer(36), Integer(0), Integer(1), Integer(0), Integer(131), -Integer(107), Integer(0), Integer(0), Integer(0), Integer(178), -Integer(145)]); H
[   1    0    0   45  -36]
[   0    1    0  131 -107]
[   0    0    0  178 -145]
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> matrix_integer_dense_hnf.ones(H, [Integer(0),Integer(1),Integer(3)])
([0, 1], [0, 1], [2], [2])

H = matrix(ZZ, 3, 5, [1, 0, 0, 45, -36, 0, 1, 0, 131, -107, 0, 0, 0, 178, -145]); H
import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
matrix_integer_dense_hnf.ones(H, [0,1,3])
sage.matrix.matrix_integer_dense_hnf.pad_zeros(A, nrows)[source]

Add zeros to the bottom of A so that the resulting matrix has nrows.

INPUT:

  • A – a matrix

  • nrows – integer that is at least as big as the number of rows of A

OUTPUT: a matrix with nrows rows

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: a = matrix(ZZ, 2, 4, [1, 0, 0, 7, 0, 1, 5, 2])
sage: matrix_integer_dense_hnf.pad_zeros(a, 4)
[1 0 0 7]
[0 1 5 2]
[0 0 0 0]
[0 0 0 0]
sage: matrix_integer_dense_hnf.pad_zeros(a, 2)
[1 0 0 7]
[0 1 5 2]

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> a = matrix(ZZ, Integer(2), Integer(4), [Integer(1), Integer(0), Integer(0), Integer(7), Integer(0), Integer(1), Integer(5), Integer(2)])
>>> matrix_integer_dense_hnf.pad_zeros(a, Integer(4))
[1 0 0 7]
[0 1 5 2]
[0 0 0 0]
[0 0 0 0]
>>> matrix_integer_dense_hnf.pad_zeros(a, Integer(2))
[1 0 0 7]
[0 1 5 2]

import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
a = matrix(ZZ, 2, 4, [1, 0, 0, 7, 0, 1, 5, 2])
matrix_integer_dense_hnf.pad_zeros(a, 4)
matrix_integer_dense_hnf.pad_zeros(a, 2)
sage.matrix.matrix_integer_dense_hnf.pivots_of_hnf_matrix(H)[source]

Return the pivot columns of a matrix H assumed to be in HNF.

INPUT:

  • H – a matrix that must be HNF

OUTPUT: list of pivots

EXAMPLES:

sage: H = matrix(ZZ, 3, 5, [1, 0, 0, 45, -36, 0, 1, 0, 131, -107, 0, 0, 0, 178, -145]); H
[   1    0    0   45  -36]
[   0    1    0  131 -107]
[   0    0    0  178 -145]
sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: matrix_integer_dense_hnf.pivots_of_hnf_matrix(H)
[0, 1, 3]

>>> from sage.all import *
>>> H = matrix(ZZ, Integer(3), Integer(5), [Integer(1), Integer(0), Integer(0), Integer(45), -Integer(36), Integer(0), Integer(1), Integer(0), Integer(131), -Integer(107), Integer(0), Integer(0), Integer(0), Integer(178), -Integer(145)]); H
[   1    0    0   45  -36]
[   0    1    0  131 -107]
[   0    0    0  178 -145]
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> matrix_integer_dense_hnf.pivots_of_hnf_matrix(H)
[0, 1, 3]

H = matrix(ZZ, 3, 5, [1, 0, 0, 45, -36, 0, 1, 0, 131, -107, 0, 0, 0, 178, -145]); H
import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
matrix_integer_dense_hnf.pivots_of_hnf_matrix(H)
sage.matrix.matrix_integer_dense_hnf.probable_hnf(A, include_zero_rows, proof)[source]

Return the HNF of A or raise an exception if something involving the randomized nature of the algorithm goes wrong along the way.

Calling this function again a few times should result it in it working, at least if proof=True.

INPUT:

  • A – a matrix

  • include_zero_rows – boolean

  • proof – boolean

OUTPUT:

the Hermite normal form of A. cols – pivot columns

EXAMPLES:

sage: a = matrix(ZZ,4,3,[-1, -1, -1, -20, 4, 1, -1, 1, 2,1,2,3])
sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: matrix_integer_dense_hnf.probable_hnf(a, True, True)
(
[1 0 0]
[0 1 0]
[0 0 1]
[0 0 0], [0, 1, 2]
)
sage: matrix_integer_dense_hnf.probable_hnf(a, False, True)
(
[1 0 0]
[0 1 0]
[0 0 1], [0, 1, 2]
)
sage: matrix_integer_dense_hnf.probable_hnf(a, False, False)
(
[1 0 0]
[0 1 0]
[0 0 1], [0, 1, 2]
)

>>> from sage.all import *
>>> a = matrix(ZZ,Integer(4),Integer(3),[-Integer(1), -Integer(1), -Integer(1), -Integer(20), Integer(4), Integer(1), -Integer(1), Integer(1), Integer(2),Integer(1),Integer(2),Integer(3)])
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> matrix_integer_dense_hnf.probable_hnf(a, True, True)
(
[1 0 0]
[0 1 0]
[0 0 1]
[0 0 0], [0, 1, 2]
)
>>> matrix_integer_dense_hnf.probable_hnf(a, False, True)
(
[1 0 0]
[0 1 0]
[0 0 1], [0, 1, 2]
)
>>> matrix_integer_dense_hnf.probable_hnf(a, False, False)
(
[1 0 0]
[0 1 0]
[0 0 1], [0, 1, 2]
)

a = matrix(ZZ,4,3,[-1, -1, -1, -20, 4, 1, -1, 1, 2,1,2,3])
import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
matrix_integer_dense_hnf.probable_hnf(a, True, True)
matrix_integer_dense_hnf.probable_hnf(a, False, True)
matrix_integer_dense_hnf.probable_hnf(a, False, False)
sage.matrix.matrix_integer_dense_hnf.probable_pivot_columns(A)[source]

INPUT:

  • A – a matrix

OUTPUT: a tuple of integers

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: a = matrix(ZZ,3,[0, -1, -1, 0, -20, 1, 0, 1, 2])
sage: a
[  0  -1  -1]
[  0 -20   1]
[  0   1   2]
sage: matrix_integer_dense_hnf.probable_pivot_columns(a)
(1, 2)

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> a = matrix(ZZ,Integer(3),[Integer(0), -Integer(1), -Integer(1), Integer(0), -Integer(20), Integer(1), Integer(0), Integer(1), Integer(2)])
>>> a
[  0  -1  -1]
[  0 -20   1]
[  0   1   2]
>>> matrix_integer_dense_hnf.probable_pivot_columns(a)
(1, 2)

import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
a = matrix(ZZ,3,[0, -1, -1, 0, -20, 1, 0, 1, 2])
a
matrix_integer_dense_hnf.probable_pivot_columns(a)
sage.matrix.matrix_integer_dense_hnf.probable_pivot_rows(A)[source]

Return rows of A that are very likely to be pivots.

This really finds the pivots of A modulo a random prime.

INPUT:

  • A – a matrix

OUTPUT: a tuple of integers

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: a = matrix(ZZ,3,[0, -1, -1, 0, -20, 1, 0, 1, 2])
sage: a
[  0  -1  -1]
[  0 -20   1]
[  0   1   2]
sage: matrix_integer_dense_hnf.probable_pivot_rows(a)
(0, 1)

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> a = matrix(ZZ,Integer(3),[Integer(0), -Integer(1), -Integer(1), Integer(0), -Integer(20), Integer(1), Integer(0), Integer(1), Integer(2)])
>>> a
[  0  -1  -1]
[  0 -20   1]
[  0   1   2]
>>> matrix_integer_dense_hnf.probable_pivot_rows(a)
(0, 1)

import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
a = matrix(ZZ,3,[0, -1, -1, 0, -20, 1, 0, 1, 2])
a
matrix_integer_dense_hnf.probable_pivot_rows(a)
sage.matrix.matrix_integer_dense_hnf.sanity_checks(times=50, n=8, m=5, proof=True, stabilize=2, check_using_magma=True)[source]

Run random sanity checks on the modular \(p\)-adic HNF with tall and wide matrices both dense and sparse.

INPUT:

  • times – number of times to randomly try matrices with each shape

  • n – number of rows

  • m – number of columns

  • proof – test with proof true

  • stabilize – parameter to pass to hnf algorithm when proof is False

  • check_using_magma – if True use Magma instead of PARI to check correctness of computed HNF’s. Since PARI’s HNF is buggy and slow (as of 2008-02-16 non-pivot entries sometimes are not normalized to be nonnegative) the default is Magma.

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
sage: matrix_integer_dense_hnf.sanity_checks(times=5, check_using_magma=False)
small 8 x 5
0 1 2 3 4  (done)
big 8 x 5
0 1 2 3 4  (done)
small 5 x 8
0 1 2 3 4  (done)
big 5 x 8
0 1 2 3 4  (done)
sparse 8 x 5
0 1 2 3 4  (done)
sparse 5 x 8
0 1 2 3 4  (done)
ill conditioned -- 1000*A -- 8 x 5
0 1 2 3 4  (done)
ill conditioned -- 1000*A but one row -- 8 x 5
0 1 2 3 4  (done)

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
>>> matrix_integer_dense_hnf.sanity_checks(times=Integer(5), check_using_magma=False)
small 8 x 5
0 1 2 3 4  (done)
big 8 x 5
0 1 2 3 4  (done)
small 5 x 8
0 1 2 3 4  (done)
big 5 x 8
0 1 2 3 4  (done)
sparse 8 x 5
0 1 2 3 4  (done)
sparse 5 x 8
0 1 2 3 4  (done)
ill conditioned -- 1000*A -- 8 x 5
0 1 2 3 4  (done)
ill conditioned -- 1000*A but one row -- 8 x 5
0 1 2 3 4  (done)

import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
matrix_integer_dense_hnf.sanity_checks(times=5, check_using_magma=False)
sage.matrix.matrix_integer_dense_hnf.solve_system_with_difficult_last_row(B, a)[source]

Solve B*x = a when the last row of \(B\) contains huge entries using a clever trick that reduces the problem to solve C*x = a where \(C\) is \(B\) but with the last row replaced by something small, along with one easy null space computation. The latter are both solved \(p\)-adically.

INPUT:

  • B – a square n x n nonsingular matrix with painful big bottom row

  • a – an n x 1 column matrix

OUTPUT: the unique solution to B*x = a

EXAMPLES:

sage: from sage.matrix.matrix_integer_dense_hnf import solve_system_with_difficult_last_row
sage: B = matrix(ZZ, 3, [1,2,4, 3,-4,7, 939082,2930982,132902384098234])
sage: a = matrix(ZZ,3,1, [1,2,5])
sage: z = solve_system_with_difficult_last_row(B, a)
sage: z
[ 106321906985474/132902379815497]
[132902385037291/1329023798154970]
[        -5221794/664511899077485]
sage: B*z
[1]
[2]
[5]

>>> from sage.all import *
>>> from sage.matrix.matrix_integer_dense_hnf import solve_system_with_difficult_last_row
>>> B = matrix(ZZ, Integer(3), [Integer(1),Integer(2),Integer(4), Integer(3),-Integer(4),Integer(7), Integer(939082),Integer(2930982),Integer(132902384098234)])
>>> a = matrix(ZZ,Integer(3),Integer(1), [Integer(1),Integer(2),Integer(5)])
>>> z = solve_system_with_difficult_last_row(B, a)
>>> z
[ 106321906985474/132902379815497]
[132902385037291/1329023798154970]
[        -5221794/664511899077485]
>>> B*z
[1]
[2]
[5]

from sage.matrix.matrix_integer_dense_hnf import solve_system_with_difficult_last_row
B = matrix(ZZ, 3, [1,2,4, 3,-4,7, 939082,2930982,132902384098234])
a = matrix(ZZ,3,1, [1,2,5])
z = solve_system_with_difficult_last_row(B, a)
z
B*z