# Saturation over ZZ#

sage.matrix.matrix_integer_dense_saturation.index_in_saturation(A, proof=True)[source]#

The index of A in its saturation.

INPUT:

• A – matrix over $$\ZZ$$

• proof – boolean (True or False)

OUTPUT:

An integer

EXAMPLES:

sage: from sage.matrix.matrix_integer_dense_saturation import index_in_saturation
sage: A = matrix(ZZ, 2, 2, [3,2,3,4]); B = matrix(ZZ, 2,3,[1,2,3,4,5,6]); C = A*B; C
[11 16 21]
[19 26 33]
sage: index_in_saturation(C)
18
sage: W = C.row_space()
sage: S = W.saturation()
sage: W.index_in(S)
18

>>> from sage.all import *
>>> from sage.matrix.matrix_integer_dense_saturation import index_in_saturation
>>> A = matrix(ZZ, Integer(2), Integer(2), [Integer(3),Integer(2),Integer(3),Integer(4)]); B = matrix(ZZ, Integer(2),Integer(3),[Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6)]); C = A*B; C
[11 16 21]
[19 26 33]
>>> index_in_saturation(C)
18
>>> W = C.row_space()
>>> S = W.saturation()
>>> W.index_in(S)
18


For any zero matrix the index in its saturation is 1 (see Issue #13034):

sage: m = matrix(ZZ, 3)
sage: m
[0 0 0]
[0 0 0]
[0 0 0]
sage: m.index_in_saturation()
1
sage: m = matrix(ZZ, 2, 3)
sage: m
[0 0 0]
[0 0 0]
sage: m.index_in_saturation()
1

>>> from sage.all import *
>>> m = matrix(ZZ, Integer(3))
>>> m
[0 0 0]
[0 0 0]
[0 0 0]
>>> m.index_in_saturation()
1
>>> m = matrix(ZZ, Integer(2), Integer(3))
>>> m
[0 0 0]
[0 0 0]
>>> m.index_in_saturation()
1

sage.matrix.matrix_integer_dense_saturation.p_saturation(A, p, proof=True)[source]#

INPUT:

• A – a matrix over ZZ

• p – a prime

• proof – bool (default: True)

OUTPUT:

The p-saturation of the matrix A, i.e., a new matrix in Hermite form whose row span a ZZ-module that is p-saturated.

EXAMPLES:

sage: from sage.matrix.matrix_integer_dense_saturation import p_saturation
sage: A = matrix(ZZ, 2, 2, [3,2,3,4]); B = matrix(ZZ, 2,3,[1,2,3,4,5,6])
sage: A.det()
6
sage: C = A*B; C
[11 16 21]
[19 26 33]
sage: C2 = p_saturation(C, 2); C2
[ 1  8 15]
[ 0  9 18]
sage: C2.index_in_saturation()
9
sage: C3 = p_saturation(C, 3); C3
[ 1  0 -1]
[ 0  2  4]
sage: C3.index_in_saturation()
2

>>> from sage.all import *
>>> from sage.matrix.matrix_integer_dense_saturation import p_saturation
>>> A = matrix(ZZ, Integer(2), Integer(2), [Integer(3),Integer(2),Integer(3),Integer(4)]); B = matrix(ZZ, Integer(2),Integer(3),[Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6)])
>>> A.det()
6
>>> C = A*B; C
[11 16 21]
[19 26 33]
>>> C2 = p_saturation(C, Integer(2)); C2
[ 1  8 15]
[ 0  9 18]
>>> C2.index_in_saturation()
9
>>> C3 = p_saturation(C, Integer(3)); C3
[ 1  0 -1]
[ 0  2  4]
>>> C3.index_in_saturation()
2

sage.matrix.matrix_integer_dense_saturation.random_sublist_of_size(k, n)[source]#

INPUT:

• k – an integer

• n – an integer

OUTPUT:

a randomly chosen sublist of range(k) of size n.

EXAMPLES:

sage: import sage.matrix.matrix_integer_dense_saturation as s
sage: l = s.random_sublist_of_size(10, 3)
sage: len(l)
3
sage: l_check = [-1] + l + [10]
sage: all(l_check[i] < l_check[i+1] for i in range(4))
True
sage: l = s.random_sublist_of_size(10, 7)
sage: len(l)
7
sage: l_check = [-1] + l + [10]
sage: all(l_check[i] < l_check[i+1] for i in range(8))
True

>>> from sage.all import *
>>> import sage.matrix.matrix_integer_dense_saturation as s
>>> l = s.random_sublist_of_size(Integer(10), Integer(3))
>>> len(l)
3
>>> l_check = [-Integer(1)] + l + [Integer(10)]
>>> all(l_check[i] < l_check[i+Integer(1)] for i in range(Integer(4)))
True
>>> l = s.random_sublist_of_size(Integer(10), Integer(7))
>>> len(l)
7
>>> l_check = [-Integer(1)] + l + [Integer(10)]
>>> all(l_check[i] < l_check[i+Integer(1)] for i in range(Integer(8)))
True

sage.matrix.matrix_integer_dense_saturation.saturation(A, proof=True, p=0, max_dets=5)[source]#

Compute a saturation matrix of A.

INPUT:

• A – a matrix over ZZ

• proof – bool (default: True)

• p – int (default: 0); if not 0 only guarantees that output is p-saturated

• max_dets – int (default: 4) max number of dets of submatrices to compute.

OUTPUT:

matrix – saturation of the matrix A.

EXAMPLES:

sage: from sage.matrix.matrix_integer_dense_saturation import saturation
sage: A = matrix(ZZ, 2, 2, [3,2,3,4]); B = matrix(ZZ, 2,3,[1,2,3,4,5,6]); C = A*B
sage: C
[11 16 21]
[19 26 33]
sage: C.index_in_saturation()
18
sage: S = saturation(C); S
[11 16 21]
[-2 -3 -4]
sage: S.index_in_saturation()
1
sage: saturation(C, proof=False)
[11 16 21]
[-2 -3 -4]
sage: saturation(C, p=2)
[11 16 21]
[-2 -3 -4]
sage: saturation(C, p=2, max_dets=1)
[11 16 21]
[-2 -3 -4]

>>> from sage.all import *
>>> from sage.matrix.matrix_integer_dense_saturation import saturation
>>> A = matrix(ZZ, Integer(2), Integer(2), [Integer(3),Integer(2),Integer(3),Integer(4)]); B = matrix(ZZ, Integer(2),Integer(3),[Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6)]); C = A*B
>>> C
[11 16 21]
[19 26 33]
>>> C.index_in_saturation()
18
>>> S = saturation(C); S
[11 16 21]
[-2 -3 -4]
>>> S.index_in_saturation()
1
>>> saturation(C, proof=False)
[11 16 21]
[-2 -3 -4]
>>> saturation(C, p=Integer(2))
[11 16 21]
[-2 -3 -4]
>>> saturation(C, p=Integer(2), max_dets=Integer(1))
[11 16 21]
[-2 -3 -4]

sage.matrix.matrix_integer_dense_saturation.solve_system_with_difficult_last_row(B, A)[source]#

Solve the matrix equation B*Z = A when the last row of $$B$$ contains huge entries.

INPUT:

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

• A – an n x k matrix.

OUTPUT:

the unique solution to B*Z = A.

EXAMPLES:

sage: from sage.matrix.matrix_integer_dense_saturation import solve_system_with_difficult_last_row
sage: B = matrix(ZZ, 3, [1,2,3, 3,-1,2,939239082,39202803080,2939028038402834]); A = matrix(ZZ,3,2,[1,2,4,3,-1,0])
sage: X = solve_system_with_difficult_last_row(B, A); X
[  290668794698843/226075992027744         468068726971/409557956572]
[-226078357385539/1582531944194208       1228691305937/2866905696004]
[      2365357795/1582531944194208           -17436221/2866905696004]
sage: B*X == A
True

>>> from sage.all import *
>>> from sage.matrix.matrix_integer_dense_saturation import solve_system_with_difficult_last_row
>>> B = matrix(ZZ, Integer(3), [Integer(1),Integer(2),Integer(3), Integer(3),-Integer(1),Integer(2),Integer(939239082),Integer(39202803080),Integer(2939028038402834)]); A = matrix(ZZ,Integer(3),Integer(2),[Integer(1),Integer(2),Integer(4),Integer(3),-Integer(1),Integer(0)])
>>> X = solve_system_with_difficult_last_row(B, A); X
[  290668794698843/226075992027744         468068726971/409557956572]
[-226078357385539/1582531944194208       1228691305937/2866905696004]
[      2365357795/1582531944194208           -17436221/2866905696004]
>>> B*X == A
True