Dense matrices over \(\Zmod{n}\) for \(n < 2^{64}\) using FLINT

This file implements matrices over \(\Zmod{n}\) for \(n < 2^{64}\) (or \(n < 2^{32}\) on 32-bit systems). It also adds some capabilities for composite \(n\) that are not present in FLINT.

AUTHORS:

  • Edgar Costa, David Roe (2021) Initial version.

  • Vincent Macri (2026) Cleaned up and updated old unmerged code.

class sage.matrix.matrix_modn_dense_flint.Matrix_modn_dense_flint[source]

Bases: Matrix_dense

Matrices modulo \(n\) for \(n < 2^{64}\) (or \(n < 2^{32}\) on 32-bit systems).

EXAMPLES:

sage: A = matrix(Zmod(36), 3, 3, range(9))
sage: type(A)
<class 'sage.matrix.matrix_modn_dense_flint.Matrix_modn_dense_flint'>

>>> from sage.all import *
>>> A = matrix(Zmod(Integer(36)), Integer(3), Integer(3), range(Integer(9)))
>>> type(A)
<class 'sage.matrix.matrix_modn_dense_flint.Matrix_modn_dense_flint'>

A = matrix(Zmod(36), 3, 3, range(9))
type(A)
charpoly(var='x', algorithm=None)[source]

Return the characteristic polynomial of this matrix, as a polynomial over the base ring.

INPUT:

  • var – a string, the variable name for the polynomial returned.

  • algorithm – either "flint", "lift", "crt", or "linbox".

    In the first case, use FLINT’s characteristic polynomial function, in the second case, lift to the integers and compute there, in the third form, compute the hessenberg form for each prime power dividing the modulus. In the last, converts to a linbox matrix and computes the charpoly there. If not given, defaults to "crt" when not over a field, to "linbox" when the dimension is large, and "flint" otherwise.

EXAMPLES:

sage: A = matrix(Zmod(36), [[28, 32, 19], [25, 24, 2], [15, 11, 30]])
sage: A.charpoly()
x^3 + 26*x^2 + 9*x + 35
sage: A = matrix(Zmod(43^10), 6, [0, 5664461354126771, 12212357361910300, 15947020959157478, 0, 16792952041597449, 14690359073749623, 11237259451999884, 5117434014428142, 15157488677243483, 9004103062307752, 20761679499270441, 4620722392655416, 5445142895231681, 6605357538252496, 7608812697273777, 18542817615638637, 18194689690271501, 0, 20341333098836812, 12117922812876054, 1270149214447437, 0, 10999401748338075, 4620722392655416, 10891113386038365, 956055025271903, 2162842206467093, 18542817615638637, 1143972982339214, 13128267973348003, 15817056104759912, 20531311511260484, 13598045280630823, 7585782589268305, 14053895308766769])
sage: A.charpoly()
x^6 + 13124967810747524*x^5 + 20067912494391006*x^4 + 11204731077775359*x^3

sage: for N in [5, 625, 36, 2^24, 2^6*3^9, 2^63-1]:
....:     for n in [3, 6]:
....:         A = random_matrix(Zmod(N), n, n)
....:         assert A.charpoly(algorithm='crt') == A.charpoly(algorithm='lift')

sage: A = random_matrix(GF(73), 6)
sage: fs = [A.charpoly(algorithm=alg) for alg in ['flint', 'linbox', 'crt', 'lift', 'hessenberg', 'df']]
sage: len(set(fs))
1
sage: A = random_matrix(Zmod(1728), 6)
sage: fs = [A.charpoly(algorithm=alg) for alg in ['crt', 'lift', 'df']]
sage: len(set(fs))
1

>>> from sage.all import *
>>> A = matrix(Zmod(Integer(36)), [[Integer(28), Integer(32), Integer(19)], [Integer(25), Integer(24), Integer(2)], [Integer(15), Integer(11), Integer(30)]])
>>> A.charpoly()
x^3 + 26*x^2 + 9*x + 35
>>> A = matrix(Zmod(Integer(43)**Integer(10)), Integer(6), [Integer(0), Integer(5664461354126771), Integer(12212357361910300), Integer(15947020959157478), Integer(0), Integer(16792952041597449), Integer(14690359073749623), Integer(11237259451999884), Integer(5117434014428142), Integer(15157488677243483), Integer(9004103062307752), Integer(20761679499270441), Integer(4620722392655416), Integer(5445142895231681), Integer(6605357538252496), Integer(7608812697273777), Integer(18542817615638637), Integer(18194689690271501), Integer(0), Integer(20341333098836812), Integer(12117922812876054), Integer(1270149214447437), Integer(0), Integer(10999401748338075), Integer(4620722392655416), Integer(10891113386038365), Integer(956055025271903), Integer(2162842206467093), Integer(18542817615638637), Integer(1143972982339214), Integer(13128267973348003), Integer(15817056104759912), Integer(20531311511260484), Integer(13598045280630823), Integer(7585782589268305), Integer(14053895308766769)])
>>> A.charpoly()
x^6 + 13124967810747524*x^5 + 20067912494391006*x^4 + 11204731077775359*x^3

>>> for N in [Integer(5), Integer(625), Integer(36), Integer(2)**Integer(24), Integer(2)**Integer(6)*Integer(3)**Integer(9), Integer(2)**Integer(63)-Integer(1)]:
...     for n in [Integer(3), Integer(6)]:
...         A = random_matrix(Zmod(N), n, n)
...         assert A.charpoly(algorithm='crt') == A.charpoly(algorithm='lift')

>>> A = random_matrix(GF(Integer(73)), Integer(6))
>>> fs = [A.charpoly(algorithm=alg) for alg in ['flint', 'linbox', 'crt', 'lift', 'hessenberg', 'df']]
>>> len(set(fs))
1
>>> A = random_matrix(Zmod(Integer(1728)), Integer(6))
>>> fs = [A.charpoly(algorithm=alg) for alg in ['crt', 'lift', 'df']]
>>> len(set(fs))
1

A = matrix(Zmod(36), [[28, 32, 19], [25, 24, 2], [15, 11, 30]])
A.charpoly()
A = matrix(Zmod(43^10), 6, [0, 5664461354126771, 12212357361910300, 15947020959157478, 0, 16792952041597449, 14690359073749623, 11237259451999884, 5117434014428142, 15157488677243483, 9004103062307752, 20761679499270441, 4620722392655416, 5445142895231681, 6605357538252496, 7608812697273777, 18542817615638637, 18194689690271501, 0, 20341333098836812, 12117922812876054, 1270149214447437, 0, 10999401748338075, 4620722392655416, 10891113386038365, 956055025271903, 2162842206467093, 18542817615638637, 1143972982339214, 13128267973348003, 15817056104759912, 20531311511260484, 13598045280630823, 7585782589268305, 14053895308766769])
A.charpoly()
for N in [5, 625, 36, 2^24, 2^6*3^9, 2^63-1]:
    for n in [3, 6]:
        A = random_matrix(Zmod(N), n, n)
        assert A.charpoly(algorithm='crt') == A.charpoly(algorithm='lift')
A = random_matrix(GF(73), 6)
fs = [A.charpoly(algorithm=alg) for alg in ['flint', 'linbox', 'crt', 'lift', 'hessenberg', 'df']]
len(set(fs))
A = random_matrix(Zmod(1728), 6)
fs = [A.charpoly(algorithm=alg) for alg in ['crt', 'lift', 'df']]
len(set(fs))
determinant(algorithm=None)[source]

Return the determinant of this matrix.

INPUT:

  • algorithm – a string, one of flint, charpoly, linbox or lift

EXAMPLES:

sage: A = matrix(ZZ, 3, [1, 6, 11, -2, 3, 1, 3, 1, 0])
sage: all(A.change_ring(Zmod(N)).det() == A.det() for N in range(2, 100))
True

sage: A = random_matrix(Zmod(36), 6)
sage: all(A.det()^n == (A^n).det() for n in range(2, 10))
True
sage: A.det("charpoly") == A.det("lift")
True
sage: B = random_matrix(Zmod(36), 6)
sage: while not B.is_unit():
....:     B = random_matrix(Zmod(36), 6)
sage: A.det() == (~B * A * B).det()
True

sage: A = random_matrix(Zmod(73), 6)
sage: a = A.det("flint")
sage: b = A.det("linbox")
sage: c = A.det("lift")
sage: d = A.det("charpoly")
sage: a == b == c == d
True

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(3), [Integer(1), Integer(6), Integer(11), -Integer(2), Integer(3), Integer(1), Integer(3), Integer(1), Integer(0)])
>>> all(A.change_ring(Zmod(N)).det() == A.det() for N in range(Integer(2), Integer(100)))
True

>>> A = random_matrix(Zmod(Integer(36)), Integer(6))
>>> all(A.det()**n == (A**n).det() for n in range(Integer(2), Integer(10)))
True
>>> A.det("charpoly") == A.det("lift")
True
>>> B = random_matrix(Zmod(Integer(36)), Integer(6))
>>> while not B.is_unit():
...     B = random_matrix(Zmod(Integer(36)), Integer(6))
>>> A.det() == (~B * A * B).det()
True

>>> A = random_matrix(Zmod(Integer(73)), Integer(6))
>>> a = A.det("flint")
>>> b = A.det("linbox")
>>> c = A.det("lift")
>>> d = A.det("charpoly")
>>> a == b == c == d
True

A = matrix(ZZ, 3, [1, 6, 11, -2, 3, 1, 3, 1, 0])
all(A.change_ring(Zmod(N)).det() == A.det() for N in range(2, 100))
A = random_matrix(Zmod(36), 6)
all(A.det()^n == (A^n).det() for n in range(2, 10))
A.det("charpoly") == A.det("lift")
B = random_matrix(Zmod(36), 6)
while not B.is_unit():
    B = random_matrix(Zmod(36), 6)
A.det() == (~B * A * B).det()
A = random_matrix(Zmod(73), 6)
a = A.det("flint")
b = A.det("linbox")
c = A.det("lift")
d = A.det("charpoly")
a == b == c == d
echelonize(algorithm='default', **kwds)[source]

Transform this matrix into echelon form in place, over the same base ring.

Note

Over a field, transforms to standard reduced row echelon form. Otherwise, uses Howell form, which may increase the number of nonzero rows. In this case, we require that the number of rows is at least the number of columns.

INPUT:

  • algorithm – a string, either “default”, “flint” or “linbox”

  • transformation – boolean. Whether to return a matrix \(T\) so that left multiplication by \(T\) transforms the original matrix into echelon form.

OUTPUT:

This matrix is put into echelon form. Nothing is returned unless the keyword option transformation=True is specified, in which case the transformation matrix is returned.

EXAMPLES:

sage: A = matrix(Zmod(625), 4, 3, [[404, 355, 133], [375, 482, 448], [506, 115,  77], [370, 384, 66]])
sage: A
[404 355 133]
[375 482 448]
[506 115  77]
[370 384  66]
sage: A.echelonize()
sage: A
[1 0 2]
[0 1 4]
[0 0 5]
[0 0 0]

>>> from sage.all import *
>>> A = matrix(Zmod(Integer(625)), Integer(4), Integer(3), [[Integer(404), Integer(355), Integer(133)], [Integer(375), Integer(482), Integer(448)], [Integer(506), Integer(115),  Integer(77)], [Integer(370), Integer(384), Integer(66)]])
>>> A
[404 355 133]
[375 482 448]
[506 115  77]
[370 384  66]
>>> A.echelonize()
>>> A
[1 0 2]
[0 1 4]
[0 0 5]
[0 0 0]

A = matrix(Zmod(625), 4, 3, [[404, 355, 133], [375, 482, 448], [506, 115,  77], [370, 384, 66]])
A
A.echelonize()
A
hessenberg_form()[source]

The Hessenberg form of a matrix is almost upper triangular, and allows for efficient computation of the characteristic polynomial.

Requires that the base ring have prime power modulus.

EXAMPLES:

sage: A = matrix(Zmod(125), 4, [2,1,1,-2,2,2,-1,-1,-1,1,2,3,4,5,6,7])
sage: H = A.hessenberg_form(); H
[  2  59  88   1]
[  2  63  34 124]
[  0  15 104   8]
[  0   0  90  94]
sage: H.charpoly() == A.charpoly()
True

>>> from sage.all import *
>>> A = matrix(Zmod(Integer(125)), Integer(4), [Integer(2),Integer(1),Integer(1),-Integer(2),Integer(2),Integer(2),-Integer(1),-Integer(1),-Integer(1),Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6),Integer(7)])
>>> H = A.hessenberg_form(); H
[  2  59  88   1]
[  2  63  34 124]
[  0  15 104   8]
[  0   0  90  94]
>>> H.charpoly() == A.charpoly()
True

A = matrix(Zmod(125), 4, [2,1,1,-2,2,2,-1,-1,-1,1,2,3,4,5,6,7])
H = A.hessenberg_form(); H
H.charpoly() == A.charpoly()
hessenbergize()[source]

Transform this matrix into Hessenberg form.

The hessenberg form of a matrix \(A\) is a matrix that is similar to \(A\), so has the same characteristic polynomial as \(A\), and is upper triangular except possible for entries right below the diagonal.

Requires that the base ring have prime power modulus.

The algorithm is a modification of the standard one over fields, where rather than swapping in an arbitrary nonzero element in each column one instead picks an element of minimal valuation.

EXAMPLES:

sage: A = matrix(Zmod(125), 4, [2,1,1,-2,2,2,-1,-1,-1,1,2,3,4,5,6,7])
sage: A.hessenbergize(); A
[  2  59  88   1]
[  2  63  34 124]
[  0  15 104   8]
[  0   0  90  94]

>>> from sage.all import *
>>> A = matrix(Zmod(Integer(125)), Integer(4), [Integer(2),Integer(1),Integer(1),-Integer(2),Integer(2),Integer(2),-Integer(1),-Integer(1),-Integer(1),Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6),Integer(7)])
>>> A.hessenbergize(); A
[  2  59  88   1]
[  2  63  34 124]
[  0  15 104   8]
[  0   0  90  94]

A = matrix(Zmod(125), 4, [2,1,1,-2,2,2,-1,-1,-1,1,2,3,4,5,6,7])
A.hessenbergize(); A

You cannot Hessenbergize an immutable matrix:

sage: A = matrix(Zmod(125), 3, range(9))
sage: A.set_immutable()
sage: A.hessenbergize()
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M).

>>> from sage.all import *
>>> A = matrix(Zmod(Integer(125)), Integer(3), range(Integer(9)))
>>> A.set_immutable()
>>> A.hessenbergize()
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M).

A = matrix(Zmod(125), 3, range(9))
A.set_immutable()
A.hessenbergize()
howell_form()[source]

Return the Howell form of this matrix.

The Howell form is an echelon form with a few additional properties that make it unique and useful for solving equations modulo \(N\).

For a matrix \(A\), let \(S(A)\) be the module spanned by the rows, and \(S_j(A)\) the submodule consisting of vectors with the first \(j\) entries zero. Recall that elements \(a, b\) of a ring \(R\) are associates if there is a unit \(u \in R\) with \(a = ub\); this is an equivalence relation. We can choose a set \(X\) of representatives in \(\ZZ/N\ZZ\) by taking all products of the primes dividing \(N\), raised to arbitrary powers.

The Howell form of \(A\) is a matrix \(H\) with the same number of columns as \(A\) so that

  • it is an echelon form: the zero rows are at the bottom, and the leading entries (pivots) in each row each occur down and to the right of the previous.

  • Each pivot lies in \(X\), and the entries above a pivot are smaller (as in Hermite normal form).

  • If \((i, j_i)\) is the location of a pivot, then rows \(i+1\), … generate \(S_{j_i}(A)\).

if \(r\) is the number of nonzero rows of \(H\), then the first \(r\) rows

of \(H\) are nonzero

Note

The Howell form will always have at least as many rows as columns.

EXAMPLES:

sage: entries = [624, 353, 352, 497, 182, 374, 556, 365, 271, 557, 203, 327]
sage: A = matrix(Zmod(625), 3, 4, entries)
sage: A.howell_form()
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0 25]
[ 0  0  0  0]

>>> from sage.all import *
>>> entries = [Integer(624), Integer(353), Integer(352), Integer(497), Integer(182), Integer(374), Integer(556), Integer(365), Integer(271), Integer(557), Integer(203), Integer(327)]
>>> A = matrix(Zmod(Integer(625)), Integer(3), Integer(4), entries)
>>> A.howell_form()
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0 25]
[ 0  0  0  0]

entries = [624, 353, 352, 497, 182, 374, 556, 365, 271, 557, 203, 327]
A = matrix(Zmod(625), 3, 4, entries)
A.howell_form()

The following example illustrates why the number of rows needs to be increased:

sage: A = matrix(Zmod(625), [125, 25, 5, 1])
sage: A.howell_form()
[125  25   5   1]
[  0 125  25   5]
[  0   0 125  25]
[  0   0   0 125]

>>> from sage.all import *
>>> A = matrix(Zmod(Integer(625)), [Integer(125), Integer(25), Integer(5), Integer(1)])
>>> A.howell_form()
[125  25   5   1]
[  0 125  25   5]
[  0   0 125  25]
[  0   0   0 125]

A = matrix(Zmod(625), [125, 25, 5, 1])
A.howell_form()
howellize(transformation=False)[source]

Transform this matrix in place into its Howell form.

See howell_form() for the definition.

Since the Howell form may have more rows than \(A\), to transform \(A\) in place we require that it has at least as many rows as columns.

EXAMPLES:

sage: entries = [624, 353, 352, 497, 182, 374, 556, 365, 271, 557, 203, 327, 181, 102, 283, 237]
sage: A = matrix(Zmod(625), 4, entries)
sage: A.howellize(); A
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0 25]
[ 0  0  0  0]

>>> from sage.all import *
>>> entries = [Integer(624), Integer(353), Integer(352), Integer(497), Integer(182), Integer(374), Integer(556), Integer(365), Integer(271), Integer(557), Integer(203), Integer(327), Integer(181), Integer(102), Integer(283), Integer(237)]
>>> A = matrix(Zmod(Integer(625)), Integer(4), entries)
>>> A.howellize(); A
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0 25]
[ 0  0  0  0]

entries = [624, 353, 352, 497, 182, 374, 556, 365, 271, 557, 203, 327, 181, 102, 283, 237]
A = matrix(Zmod(625), 4, entries)
A.howellize(); A
inverse_of_unit(algorithm=None)[source]

Return the inverse of this matrix.

Raises a ZeroDivisionError if the determinant is not a unit, and raises an ArithmeticError if the inverse doesn’t exist because the matrix is nonsquare.

INPUT:

  • algorithm – either "crt" or "lift".

    In the first case, CRT is used to assemble results from prime powers dividing the modulus, with quadratic Hensel lifting for prime powers. In the second case, the inverse is computed over the integers and then reduced.

EXAMPLES:

sage: A = matrix(Zmod(36), [[28, 32, 19], [25, 24, 2], [15, 11, 30]])
sage: A.inverse_of_unit()
[14  5  4]
[ 0 15 23]
[23 28 16]

sage: for N in [5, 625, 36, 2^24, 2^6*3^9, 2^63-1]:
....:     algs = ["flint", "linbox", "lift"] if N == 5 else ["crt", "lift"]
....:     for n in [3, 6]:
....:         A = random_matrix(Zmod(N), n, n)
....:         while not A.det().is_unit():
....:             A = random_matrix(Zmod(N), n, n)
....:         Is = [A.inverse_of_unit(alg) for alg in algs]
....:         for I in Is: I.set_immutable()
....:         assert len(set(Is)) == 1

sage: matrix(Zmod(36), [[2, 0], [0, 2]]).inverse_of_unit()
Traceback (most recent call last):
...
ZeroDivisionError: input matrix must be nonsingular
sage: matrix(Zmod(36), [[2], [2]]).inverse_of_unit()
Traceback (most recent call last):
...
ArithmeticError: inverse only defined for square matrix

>>> from sage.all import *
>>> A = matrix(Zmod(Integer(36)), [[Integer(28), Integer(32), Integer(19)], [Integer(25), Integer(24), Integer(2)], [Integer(15), Integer(11), Integer(30)]])
>>> A.inverse_of_unit()
[14  5  4]
[ 0 15 23]
[23 28 16]

>>> for N in [Integer(5), Integer(625), Integer(36), Integer(2)**Integer(24), Integer(2)**Integer(6)*Integer(3)**Integer(9), Integer(2)**Integer(63)-Integer(1)]:
...     algs = ["flint", "linbox", "lift"] if N == Integer(5) else ["crt", "lift"]
...     for n in [Integer(3), Integer(6)]:
...         A = random_matrix(Zmod(N), n, n)
...         while not A.det().is_unit():
...             A = random_matrix(Zmod(N), n, n)
...         Is = [A.inverse_of_unit(alg) for alg in algs]
...         for I in Is: I.set_immutable()
...         assert len(set(Is)) == Integer(1)

>>> matrix(Zmod(Integer(36)), [[Integer(2), Integer(0)], [Integer(0), Integer(2)]]).inverse_of_unit()
Traceback (most recent call last):
...
ZeroDivisionError: input matrix must be nonsingular
>>> matrix(Zmod(Integer(36)), [[Integer(2)], [Integer(2)]]).inverse_of_unit()
Traceback (most recent call last):
...
ArithmeticError: inverse only defined for square matrix

A = matrix(Zmod(36), [[28, 32, 19], [25, 24, 2], [15, 11, 30]])
A.inverse_of_unit()
for N in [5, 625, 36, 2^24, 2^6*3^9, 2^63-1]:
    algs = ["flint", "linbox", "lift"] if N == 5 else ["crt", "lift"]
    for n in [3, 6]:
        A = random_matrix(Zmod(N), n, n)
        while not A.det().is_unit():
            A = random_matrix(Zmod(N), n, n)
        Is = [A.inverse_of_unit(alg) for alg in algs]
        for I in Is: I.set_immutable()
        assert len(set(Is)) == 1
matrix(Zmod(36), [[2, 0], [0, 2]]).inverse_of_unit()
matrix(Zmod(36), [[2], [2]]).inverse_of_unit()
minpoly(var='x', algorithm='flint', proof=None)[source]

Returns the minimal polynomial of this matrix.

Note that, in general, the minimal polynomial of a matrix over a ring with composite modulus is not well defined.

INPUT:

  • var – the variable name for the polynomial ring

  • algorithm – ignored, always uses flint

  • proof – boolean, whether to check that the answer computed by using a minimal polynomial is correct. If not specified, uses the linear algebra default proof state. Currently ignored as we simply raise an error if a minimal polynomial cannot be found.

EXAMPLES:

sage: A = matrix(Zmod(17), 6, 6, 1)
sage: A.minpoly()
x + 16
sage: A.minpoly('t')
t + 16
sage: B = random_matrix(Zmod(101), 10, 10)
sage: m = B.minpoly()
sage: m(B).is_zero()
True

>>> from sage.all import *
>>> A = matrix(Zmod(Integer(17)), Integer(6), Integer(6), Integer(1))
>>> A.minpoly()
x + 16
>>> A.minpoly('t')
t + 16
>>> B = random_matrix(Zmod(Integer(101)), Integer(10), Integer(10))
>>> m = B.minpoly()
>>> m(B).is_zero()
True

A = matrix(Zmod(17), 6, 6, 1)
A.minpoly()
A.minpoly('t')
B = random_matrix(Zmod(101), 10, 10)
m = B.minpoly()
m(B).is_zero()
pivots()[source]

Return the columns containing a leading 1 in the echelon form of this matrix.

When the base ring is not a field, there may be other rows with leading entries a zero divisor. These columns are available using the _pivots() method.

EXAMPLES:

sage: R = Zmod(625)
sage: A = matrix(Zmod(625), 3, 4, [1, 2, 3, 4, 0, 5, 5, 6, 0, 0, 0, 25])
sage: A
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0 25]
sage: A.pivots()
(0,)

>>> from sage.all import *
>>> R = Zmod(Integer(625))
>>> A = matrix(Zmod(Integer(625)), Integer(3), Integer(4), [Integer(1), Integer(2), Integer(3), Integer(4), Integer(0), Integer(5), Integer(5), Integer(6), Integer(0), Integer(0), Integer(0), Integer(25)])
>>> A
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0 25]
>>> A.pivots()
(0,)

R = Zmod(625)
A = matrix(Zmod(625), 3, 4, [1, 2, 3, 4, 0, 5, 5, 6, 0, 0, 0, 25])
A
A.pivots()
rank()[source]

Return the rank of this matrix.

When the base ring is not a field, this is defined as the number of leading 1 pivots. This choice has the benefit that a square matrix will be invertible exactly when the rank is the same as the number of rows.

EXAMPlES:

sage: entries = [1, 2, 3, 4, 0, 5, 5, 6, 0, 0, 0, 25]
sage: A = matrix(GF(17), 3, 4, entries)
sage: A
[1 2 3 4]
[0 5 5 6]
[0 0 0 8]
sage: A.rank()
3
sage: A = matrix(Zmod(625), 3, 4, entries)
sage: A
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0 25]
sage: A.rank()
1

>>> from sage.all import *
>>> entries = [Integer(1), Integer(2), Integer(3), Integer(4), Integer(0), Integer(5), Integer(5), Integer(6), Integer(0), Integer(0), Integer(0), Integer(25)]
>>> A = matrix(GF(Integer(17)), Integer(3), Integer(4), entries)
>>> A
[1 2 3 4]
[0 5 5 6]
[0 0 0 8]
>>> A.rank()
3
>>> A = matrix(Zmod(Integer(625)), Integer(3), Integer(4), entries)
>>> A
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0 25]
>>> A.rank()
1

entries = [1, 2, 3, 4, 0, 5, 5, 6, 0, 0, 0, 25]
A = matrix(GF(17), 3, 4, entries)
A
A.rank()
A = matrix(Zmod(625), 3, 4, entries)
A
A.rank()
strong_echelon_form()[source]

Strong echelon form of this matrix.

This is obtained from the Howell form (the form used as echelon form when not over a field) by permuting rows: rather than having all zero rows at the bottom, they are placed so that the pivots occur on the diagonal.

The result will always have at least as many rows as columns, with zero rows added if necessary to accomplish this.

EXAMPLES:

sage: entries = [624, 353, 352, 497, 182, 374, 556, 365, 271, 557, 203, 327]
sage: A = matrix(Zmod(625), 3, 4, entries)
sage: A.strong_echelon_form()
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0  0]
[ 0  0  0 25]

>>> from sage.all import *
>>> entries = [Integer(624), Integer(353), Integer(352), Integer(497), Integer(182), Integer(374), Integer(556), Integer(365), Integer(271), Integer(557), Integer(203), Integer(327)]
>>> A = matrix(Zmod(Integer(625)), Integer(3), Integer(4), entries)
>>> A.strong_echelon_form()
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0  0]
[ 0  0  0 25]

entries = [624, 353, 352, 497, 182, 374, 556, 365, 271, 557, 203, 327]
A = matrix(Zmod(625), 3, 4, entries)
A.strong_echelon_form()
strong_echelonize()[source]

Transform this matrix in place into its strong echelon form.

The strong echelon form obtained from the Howell form by permuting rows: rather than having all zero rows at the bottom, they are placed so that the pivots occur on the diagonal.

The input must have at least as many rows as columns.

EXAMPLES:

sage: entries = [1, 2, 3, 4, 0, 5, 5, 6, 0, 0, 0, 25, 0, 0, 0, 0]
sage: A = matrix(Zmod(625), 4, entries); A
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0 25]
[ 0  0  0  0]
sage: A.strong_echelonize(); A
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0  0]
[ 0  0  0 25]

>>> from sage.all import *
>>> entries = [Integer(1), Integer(2), Integer(3), Integer(4), Integer(0), Integer(5), Integer(5), Integer(6), Integer(0), Integer(0), Integer(0), Integer(25), Integer(0), Integer(0), Integer(0), Integer(0)]
>>> A = matrix(Zmod(Integer(625)), Integer(4), entries); A
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0 25]
[ 0  0  0  0]
>>> A.strong_echelonize(); A
[ 1  2  3  4]
[ 0  5  5  6]
[ 0  0  0  0]
[ 0  0  0 25]

entries = [1, 2, 3, 4, 0, 5, 5, 6, 0, 0, 0, 25, 0, 0, 0, 0]
A = matrix(Zmod(625), 4, entries); A
A.strong_echelonize(); A
trace()[source]

Return the trace of this matrix, which is the sum of the diagonal entries.

The input must be square.

EXAMPLES:

sage: A = matrix(ZZ, 3, [1, 6, 11, -2, 3, 1, 3, 1, 0])
sage: all(A.change_ring(Zmod(N)).trace() == A.trace() for N in range(2, 100))
True

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(3), [Integer(1), Integer(6), Integer(11), -Integer(2), Integer(3), Integer(1), Integer(3), Integer(1), Integer(0)])
>>> all(A.change_ring(Zmod(N)).trace() == A.trace() for N in range(Integer(2), Integer(100)))
True

A = matrix(ZZ, 3, [1, 6, 11, -2, 3, 1, 3, 1, 0])
all(A.change_ring(Zmod(N)).trace() == A.trace() for N in range(2, 100))

If the characteristic polynomial is known, negating the second coefficient is used to recover the trace:

sage: A = matrix(Zmod(36), 3, [12, 12, 10, 6, 23, 24, 35, 24, 30])
sage: A.charpoly()
x^3 + 7*x^2 + 4*x + 22
sage: A.trace()
29

>>> from sage.all import *
>>> A = matrix(Zmod(Integer(36)), Integer(3), [Integer(12), Integer(12), Integer(10), Integer(6), Integer(23), Integer(24), Integer(35), Integer(24), Integer(30)])
>>> A.charpoly()
x^3 + 7*x^2 + 4*x + 22
>>> A.trace()
29

A = matrix(Zmod(36), 3, [12, 12, 10, 6, 23, 24, 35, 24, 30])
A.charpoly()
A.trace()
transpose()[source]

Return the transpose of this matrix, without changing this matrix.

EXAMPLES:

sage: A = matrix(Zmod(36), 2, 2, [0, 1, 0, 0])
sage: A.transpose()
[0 0]
[1 0]

>>> from sage.all import *
>>> A = matrix(Zmod(Integer(36)), Integer(2), Integer(2), [Integer(0), Integer(1), Integer(0), Integer(0)])
>>> A.transpose()
[0 0]
[1 0]

A = matrix(Zmod(36), 2, 2, [0, 1, 0, 0])
A.transpose()