Dense matrices over the integer ring¶

AUTHORS:

William Stein
Robert Bradshaw
Marc Masdeu (August 2014). Implemented using FLINT, see Issue #16803.
Jeroen Demeyer (October 2014): lots of fixes, see Issue #17090 and Issue #17094.
Vincent Delecroix (February 2015): make it faster, see Issue #17822.
Vincent Delecroix (May 2017): removed duplication of entries and cleaner linbox interface

EXAMPLES:

Sage

sage: a = matrix(ZZ, 3,3, range(9)); a
[0 1 2]
[3 4 5]
[6 7 8]
sage: a.det()
0
sage: a[0,0] = 10; a.det()
-30
sage: a.charpoly()
x^3 - 22*x^2 + 102*x + 30
sage: b = -3*a
sage: a == b
False
sage: b < a
True

Python

>>> from sage.all import *
>>> a = matrix(ZZ, Integer(3),Integer(3), range(Integer(9))); a
[0 1 2]
[3 4 5]
[6 7 8]
>>> a.det()
0
>>> a[Integer(0),Integer(0)] = Integer(10); a.det()
-30
>>> a.charpoly()
x^3 - 22*x^2 + 102*x + 30
>>> b = -Integer(3)*a
>>> a == b
False
>>> b < a
True

Sage Live

a = matrix(ZZ, 3,3, range(9)); a
a.det()
a[0,0] = 10; a.det()
a.charpoly()
b = -3*a
a == b
b < a

class sage.matrix.matrix_integer_dense.Matrix_integer_dense[source]¶

Bases: Matrix_dense

Matrix over the integers, implemented using FLINT.

On a 32-bit machine, they can have at most \(2^{32}-1\) rows or columns. On a 64-bit machine, matrices can have at most \(2^{64}-1\) rows or columns.

EXAMPLES:

Sage

sage: a = MatrixSpace(ZZ,3)(2); a
[2 0 0]
[0 2 0]
[0 0 2]
sage: a = matrix(ZZ,1,3, [1,2,-3]); a
[ 1  2 -3]
sage: a = MatrixSpace(ZZ,2,4)(2); a
Traceback (most recent call last):
...
TypeError: nonzero scalar matrix must be square

Python

>>> from sage.all import *
>>> a = MatrixSpace(ZZ,Integer(3))(Integer(2)); a
[2 0 0]
[0 2 0]
[0 0 2]
>>> a = matrix(ZZ,Integer(1),Integer(3), [Integer(1),Integer(2),-Integer(3)]); a
[ 1  2 -3]
>>> a = MatrixSpace(ZZ,Integer(2),Integer(4))(Integer(2)); a
Traceback (most recent call last):
...
TypeError: nonzero scalar matrix must be square

Sage Live

a = MatrixSpace(ZZ,3)(2); a
a = matrix(ZZ,1,3, [1,2,-3]); a
a = MatrixSpace(ZZ,2,4)(2); a

BKZ(delta=None, algorithm='fpLLL', fp=None, block_size=10, prune=0, use_givens=False, precision=0, proof=None, **kwds)[source]¶

Return the result of running Block Korkin-Zolotarev reduction on self interpreted as a lattice.

INPUT:

delta – (default: 0.99) LLL parameter
algorithm – (default: 'fpLLL') 'fpLLL' or "NTL"
fp – floating point number implementation
- None – NTL’s exact reduction or fpLLL’s wrapper (default)
- 'fp' – double precision: NTL’s FP or fpLLL’s double
- 'ld' – long doubles (fpLLL only)
- 'qd' – NTL’s QP
- 'qd1' – quad doubles: Uses quad_float precision to compute Gram-Schmidt, but uses double precision in the search phase of the block reduction algorithm. This seems adequate for most purposes, and is faster than 'qd', which uses quad_float precision uniformly throughout (NTL only).
- 'xd' – extended exponent: NTL’s XD or fpLLL’s dpe
- 'rr' – arbitrary precision: NTL’RR or fpLLL’s MPFR
block_size – (default: 10) specifies the size of the blocks in the reduction. High values yield shorter vectors, but the running time increases double exponentially with block_size. block_size should be between 2 and the number of rows of self.
proof – (default: same as proof.linear_algebra()) Insist on full BKZ reduction. If disabled and fplll is called, reduction is much faster but the result is not fully BKZ reduced.

NTL SPECIFIC INPUT:

prune – (default: 0) the optional parameter prune can be set to any positive number to invoke the Volume Heuristic from [SH1995]. This can significantly reduce the running time, and hence allow much bigger block size, but the quality of the reduction is of course not as good in general. Higher values of prune mean better quality, and slower running time. When prune is 0, pruning is disabled. Recommended usage: for block_size==30, set 10 <= prune <=15.
use_givens – use Givens orthogonalization. Only applies to approximate reduction using NTL. This is a bit slower, but generally much more stable, and is really the preferred orthogonalization strategy. For a nice description of this, see Chapter 5 of [GL1996].

fpLLL SPECIFIC INPUT:

precision – (default: 0 for automatic choice) bit precision to use if fp='rr' is set
**kwds – keywords to be passed to fpylll; see fpylll.BKZ.Param for details

Also, if the verbose level is at least \(2\), some output is printed during the computation.

EXAMPLES:

Sage

sage: A = Matrix(ZZ,3,3,range(1,10))
sage: A.BKZ()
[ 0  0  0]
[ 2  1  0]
[-1  1  3]

sage: A = Matrix(ZZ,3,3,range(1,10))
sage: A.BKZ(use_givens=True)
[ 0  0  0]
[ 2  1  0]
[-1  1  3]

sage: A = Matrix(ZZ,3,3,range(1,10))
sage: A.BKZ(fp='fp')
[ 0  0  0]
[ 2  1  0]
[-1  1  3]

Python

>>> from sage.all import *
>>> A = Matrix(ZZ,Integer(3),Integer(3),range(Integer(1),Integer(10)))
>>> A.BKZ()
[ 0  0  0]
[ 2  1  0]
[-1  1  3]

>>> A = Matrix(ZZ,Integer(3),Integer(3),range(Integer(1),Integer(10)))
>>> A.BKZ(use_givens=True)
[ 0  0  0]
[ 2  1  0]
[-1  1  3]

>>> A = Matrix(ZZ,Integer(3),Integer(3),range(Integer(1),Integer(10)))
>>> A.BKZ(fp='fp')
[ 0  0  0]
[ 2  1  0]
[-1  1  3]

Sage Live

A = Matrix(ZZ,3,3,range(1,10))
A.BKZ()
A = Matrix(ZZ,3,3,range(1,10))
A.BKZ(use_givens=True)
A = Matrix(ZZ,3,3,range(1,10))
A.BKZ(fp='fp')

ALGORITHM:

Calls either NTL or fpLLL.

LLL(delta=None, eta=None, algorithm='fpLLL:wrapper', fp=None, prec=0, early_red=False, use_givens=False, use_siegel=False, transformation=False, **kwds)[source]¶

Return LLL-reduced or approximated LLL reduced matrix \(R\) of the lattice generated by the rows of self.

A set of vectors \((b_1, b_2, ..., b_d)\) is \((\delta, \eta)\)-LLL-reduced if the two following conditions hold:

For any \(i > j\), we have \(\lvert \mu_{i,j} \rvert \leq \eta\).
For any \(i < d\), we have \(\delta \lvert b_i^* \rvert^2 \leq \lvert b_{i + 1}^* + \mu_{i+1, i} b_i^* \rvert^2\),

where \(\mu_{i,j} = \langle b_i, b_j^* \rangle / \langle b_j^*, b_j^* \rangle\) and \(b_i^*\) is the \(i\)-th vector of the Gram-Schmidt orthogonalisation of \((b_1, b_2, ..., b_d)\).

The default reduction parameters are \(\delta = 0.99\) and \(\eta = 0.501\). The parameters \(\delta\) and \(\eta\) must satisfy \(0.25 < \delta \leq 1.0\) and \(0.5 \leq \eta < \sqrt{\delta}\). Polynomial time complexity is only guaranteed for \(\delta < 1\). Not every algorithm admits the case \(\delta = 1\).

If the matrix has a nonzero kernel, the LLL-reduced matrix will contain zero rows, so that the output has the same dimensions as the input. The transformation matrix is always invertible over the integers.

Also the rank of self is cached if it is computed during the reduction. Note that in general this only happens when self.rank() == self.ncols() and the exact algorithm is used.

INPUT:

delta – (default: 0.99) \(\delta\) parameter as described above, ignored by pari
eta – (default: 0.501) \(\eta\) parameter as described above, ignored by NTL and pari
algorithm – string; one of the algorithms listed below (default: 'fpLLL:wrapper')
fp – floating point number implementation, ignored by pari:
- None – NTL’s exact reduction or fpLLL’s wrapper
- 'fp' – double precision: NTL’s FP or fpLLL’s double
- 'ld' – long doubles (fpLLL only)
- 'qd' – NTL’s QP
- 'xd' – extended exponent: NTL’s XD or fpLLL’s dpe
- 'rr' – arbitrary precision: NTL’s RR or fpLLL’s MPFR
prec – (default: auto choose) precision, ignored by NTL and pari
early_red – boolean (default: False); perform early reduction, ignored by NTL and pari
use_givens – boolean (default: False); use Givens orthogonalization. Only applies to approximate reduction using NTL. This is slower but generally more stable.
use_siegel – boolean (default: False); use Siegel’s condition instead of Lovász’s condition, ignored by NTL and pari
transformation – boolean (default: False); also return transformation matrix
**kwds – keywords to be passed to fpylll; see fpylll.LLL.reduction() for details

Also, if the verbose level is at least \(2\), some output is printed during the computation.

AVAILABLE ALGORITHMS:

'NTL:LLL' – NTL’s LLL + choice of fp
'fpLLL:heuristic' – fpLLL’s heuristic + choice of fp
'fpLLL:fast' – fpLLL’s fast + choice of fp
'fpLLL:proved' – fpLLL’s proved + choice of fp
'fpLLL:wrapper' – fpLLL’s automatic choice (default)
'pari' – pari’s qflll

OUTPUT: a matrix over the integers

EXAMPLES:

Sage

sage: A = Matrix(ZZ,3,3,range(1,10))
sage: A.LLL()
[ 0  0  0]
[ 2  1  0]
[-1  1  3]

Python

>>> from sage.all import *
>>> A = Matrix(ZZ,Integer(3),Integer(3),range(Integer(1),Integer(10)))
>>> A.LLL()
[ 0  0  0]
[ 2  1  0]
[-1  1  3]

Sage Live

A = Matrix(ZZ,3,3,range(1,10))
A.LLL()

We compute the extended GCD of a list of integers using LLL, this example is from the Magma handbook:

Sage

sage: Q = [ 67015143, 248934363018, 109210, 25590011055, 74631449,
....:       10230248, 709487, 68965012139, 972065, 864972271 ]
sage: n = len(Q)
sage: S = 100
sage: X = Matrix(ZZ, n, n + 1)
sage: for i in range(n):
....:     X[i, i + 1] = 1
sage: for i in range(n):
....:     X[i, 0] = S * Q[i]
sage: L = X.LLL()
sage: M = L.row(n-1).list()[1:]
sage: M
[-3, -1, 13, -1, -4, 2, 3, 4, 5, -1]
sage: add(Q[i]*M[i] for i in range(n))
-1

Python

>>> from sage.all import *
>>> Q = [ Integer(67015143), Integer(248934363018), Integer(109210), Integer(25590011055), Integer(74631449),
...       Integer(10230248), Integer(709487), Integer(68965012139), Integer(972065), Integer(864972271) ]
>>> n = len(Q)
>>> S = Integer(100)
>>> X = Matrix(ZZ, n, n + Integer(1))
>>> for i in range(n):
...     X[i, i + Integer(1)] = Integer(1)
>>> for i in range(n):
...     X[i, Integer(0)] = S * Q[i]
>>> L = X.LLL()
>>> M = L.row(n-Integer(1)).list()[Integer(1):]
>>> M
[-3, -1, 13, -1, -4, 2, 3, 4, 5, -1]
>>> add(Q[i]*M[i] for i in range(n))
-1

Sage Live

Q = [ 67015143, 248934363018, 109210, 25590011055, 74631449,
      10230248, 709487, 68965012139, 972065, 864972271 ]
n = len(Q)
S = 100
X = Matrix(ZZ, n, n + 1)
for i in range(n):
    X[i, i + 1] = 1
for i in range(n):
    X[i, 0] = S * Q[i]
L = X.LLL()
M = L.row(n-1).list()[1:]
M
add(Q[i]*M[i] for i in range(n))

The case \(\delta = 1\) is not always supported:

Sage

sage: L = X.LLL(delta=2)
Traceback (most recent call last):
...
TypeError: delta must be <= 1
sage: L = X.LLL(delta=1)    # not tested, will eat lots of ram
Traceback (most recent call last):
...
RuntimeError: infinite loop in LLL
sage: L = X.LLL(delta=1, algorithm='NTL:LLL')
sage: L[-1]
(-100, -3, -1, 13, -1, -4, 2, 3, 4, 5, -1)

Python

>>> from sage.all import *
>>> L = X.LLL(delta=Integer(2))
Traceback (most recent call last):
...
TypeError: delta must be <= 1
>>> L = X.LLL(delta=Integer(1))    # not tested, will eat lots of ram
Traceback (most recent call last):
...
RuntimeError: infinite loop in LLL
>>> L = X.LLL(delta=Integer(1), algorithm='NTL:LLL')
>>> L[-Integer(1)]
(-100, -3, -1, 13, -1, -4, 2, 3, 4, 5, -1)

Sage Live

L = X.LLL(delta=2)
L = X.LLL(delta=1)    # not tested, will eat lots of ram
L = X.LLL(delta=1, algorithm='NTL:LLL')
L[-1]

We return the transformation matrix:

Sage

sage: A = random_matrix(ZZ, 10, 20)
sage: R, U = A.LLL(transformation=True)
sage: U * A == R
True

sage: R, U = A.LLL(algorithm='NTL:LLL', transformation=True)
sage: U * A == R
True

sage: R, U = A.LLL(algorithm='pari', transformation=True)
sage: U * A == R
True

Python

>>> from sage.all import *
>>> A = random_matrix(ZZ, Integer(10), Integer(20))
>>> R, U = A.LLL(transformation=True)
>>> U * A == R
True

>>> R, U = A.LLL(algorithm='NTL:LLL', transformation=True)
>>> U * A == R
True

>>> R, U = A.LLL(algorithm='pari', transformation=True)
>>> U * A == R
True

Sage Live

A = random_matrix(ZZ, 10, 20)
R, U = A.LLL(transformation=True)
U * A == R
R, U = A.LLL(algorithm='NTL:LLL', transformation=True)
U * A == R
R, U = A.LLL(algorithm='pari', transformation=True)
U * A == R

Example with a nonzero kernel:

Sage

sage: M = matrix(4,3,[1,2,3,2,4,6,7,0,1,-1,-2,-3])
sage: M.LLL()[0:2]
[0 0 0]
[0 0 0]

sage: M.LLL(algorithm="NTL:LLL")[0:2]
[0 0 0]
[0 0 0]

sage: M.LLL(algorithm='pari')[0:2]
[0 0 0]
[0 0 0]

Python

>>> from sage.all import *
>>> M = matrix(Integer(4),Integer(3),[Integer(1),Integer(2),Integer(3),Integer(2),Integer(4),Integer(6),Integer(7),Integer(0),Integer(1),-Integer(1),-Integer(2),-Integer(3)])
>>> M.LLL()[Integer(0):Integer(2)]
[0 0 0]
[0 0 0]

>>> M.LLL(algorithm="NTL:LLL")[Integer(0):Integer(2)]
[0 0 0]
[0 0 0]

>>> M.LLL(algorithm='pari')[Integer(0):Integer(2)]
[0 0 0]
[0 0 0]

Sage Live

M = matrix(4,3,[1,2,3,2,4,6,7,0,1,-1,-2,-3])
M.LLL()[0:2]
M.LLL(algorithm="NTL:LLL")[0:2]
M.LLL(algorithm='pari')[0:2]

Note

See sage.libs.ntl.ntl_mat_ZZ.ntl_mat_ZZ.LLL and fpylll.fplll.lll for details on the algorithms used.

Although LLL is a deterministic algorithm, the output for different implementations and CPUs (32-bit vs. 64-bit) may vary, while still being correct.

antitranspose()[source]¶

Return the antitranspose of self, without changing self.

EXAMPLES:

Sage

sage: A = matrix(2,3,range(6))
sage: type(A)
<class 'sage.matrix.matrix_integer_dense.Matrix_integer_dense'>
sage: A.antitranspose()
[5 2]
[4 1]
[3 0]
sage: A
[0 1 2]
[3 4 5]

sage: A.subdivide(1,2); A
[0 1|2]
[---+-]
[3 4|5]
sage: A.antitranspose()
[5|2]
[-+-]
[4|1]
[3|0]

Python

>>> from sage.all import *
>>> A = matrix(Integer(2),Integer(3),range(Integer(6)))
>>> type(A)
<class 'sage.matrix.matrix_integer_dense.Matrix_integer_dense'>
>>> A.antitranspose()
[5 2]
[4 1]
[3 0]
>>> A
[0 1 2]
[3 4 5]

>>> A.subdivide(Integer(1),Integer(2)); A
[0 1|2]
[---+-]
[3 4|5]
>>> A.antitranspose()
[5|2]
[-+-]
[4|1]
[3|0]

Sage Live

A = matrix(2,3,range(6))
type(A)
A.antitranspose()
A
A.subdivide(1,2); A
A.antitranspose()

augment(right, subdivide=False)[source]¶

Return a new matrix formed by appending the matrix (or vector) right on the right side of self.

INPUT:

right – a matrix, vector or free module element, whose dimensions are compatible with self
subdivide – (default: False) request the resulting matrix to have a new subdivision, separating self from right

OUTPUT:

A new matrix formed by appending right onto the right side of self. If right is a vector (or free module element) then in this context it is appropriate to consider it as a column vector. (The code first converts a vector to a 1-column matrix.)

EXAMPLES:

Sage

sage: A = matrix(ZZ, 4, 5, range(20))
sage: B = matrix(ZZ, 4, 3, range(12))
sage: A.augment(B)
[ 0  1  2  3  4  0  1  2]
[ 5  6  7  8  9  3  4  5]
[10 11 12 13 14  6  7  8]
[15 16 17 18 19  9 10 11]

Python

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(4), Integer(5), range(Integer(20)))
>>> B = matrix(ZZ, Integer(4), Integer(3), range(Integer(12)))
>>> A.augment(B)
[ 0  1  2  3  4  0  1  2]
[ 5  6  7  8  9  3  4  5]
[10 11 12 13 14  6  7  8]
[15 16 17 18 19  9 10 11]

Sage Live

A = matrix(ZZ, 4, 5, range(20))
B = matrix(ZZ, 4, 3, range(12))
A.augment(B)

A vector may be augmented to a matrix.

Sage

sage: A = matrix(ZZ, 3, 5, range(15))
sage: v = vector(ZZ, 3, range(3))
sage: A.augment(v)
[ 0  1  2  3  4  0]
[ 5  6  7  8  9  1]
[10 11 12 13 14  2]

Python

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(3), Integer(5), range(Integer(15)))
>>> v = vector(ZZ, Integer(3), range(Integer(3)))
>>> A.augment(v)
[ 0  1  2  3  4  0]
[ 5  6  7  8  9  1]
[10 11 12 13 14  2]

Sage Live

A = matrix(ZZ, 3, 5, range(15))
v = vector(ZZ, 3, range(3))
A.augment(v)

The subdivide option will add a natural subdivision between self and right. For more details about how subdivisions are managed when augmenting, see sage.matrix.matrix1.Matrix.augment().

Sage

sage: A = matrix(ZZ, 3, 5, range(15))
sage: B = matrix(ZZ, 3, 3, range(9))
sage: A.augment(B, subdivide=True)
[ 0  1  2  3  4| 0  1  2]
[ 5  6  7  8  9| 3  4  5]
[10 11 12 13 14| 6  7  8]

Python

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(3), Integer(5), range(Integer(15)))
>>> B = matrix(ZZ, Integer(3), Integer(3), range(Integer(9)))
>>> A.augment(B, subdivide=True)
[ 0  1  2  3  4| 0  1  2]
[ 5  6  7  8  9| 3  4  5]
[10 11 12 13 14| 6  7  8]

Sage Live

A = matrix(ZZ, 3, 5, range(15))
B = matrix(ZZ, 3, 3, range(9))
A.augment(B, subdivide=True)

Errors are raised if the sizes are incompatible.

Sage

sage: A = matrix(ZZ, [[1, 2],[3, 4]])
sage: B = matrix(ZZ, [[10, 20], [30, 40], [50, 60]])
sage: A.augment(B)
Traceback (most recent call last):
...
TypeError: number of rows must be the same, not 2 != 3

Python

>>> from sage.all import *
>>> A = matrix(ZZ, [[Integer(1), Integer(2)],[Integer(3), Integer(4)]])
>>> B = matrix(ZZ, [[Integer(10), Integer(20)], [Integer(30), Integer(40)], [Integer(50), Integer(60)]])
>>> A.augment(B)
Traceback (most recent call last):
...
TypeError: number of rows must be the same, not 2 != 3

Sage Live

A = matrix(ZZ, [[1, 2],[3, 4]])
B = matrix(ZZ, [[10, 20], [30, 40], [50, 60]])
A.augment(B)

charpoly(var='x', algorithm=None)[source]¶

Note

The characteristic polynomial is defined as \(\det(xI-A)\).

INPUT:

var – a variable name
algorithm – (default: 'linbox') either 'generic', 'flint' or 'linbox'

EXAMPLES:

Sage

sage: A = matrix(ZZ,6, range(36))
sage: f = A.charpoly(); f
x^6 - 105*x^5 - 630*x^4
sage: f(A) == 0
True
sage: g = A.charpoly(algorithm='flint')
sage: f == g
True
sage: n=20; A = Mat(ZZ,n)(range(n^2))
sage: A.charpoly()
x^20 - 3990*x^19 - 266000*x^18
sage: A.minpoly()
x^3 - 3990*x^2 - 266000*x

Python

>>> from sage.all import *
>>> A = matrix(ZZ,Integer(6), range(Integer(36)))
>>> f = A.charpoly(); f
x^6 - 105*x^5 - 630*x^4
>>> f(A) == Integer(0)
True
>>> g = A.charpoly(algorithm='flint')
>>> f == g
True
>>> n=Integer(20); A = Mat(ZZ,n)(range(n**Integer(2)))
>>> A.charpoly()
x^20 - 3990*x^19 - 266000*x^18
>>> A.minpoly()
x^3 - 3990*x^2 - 266000*x

Sage Live

A = matrix(ZZ,6, range(36))
f = A.charpoly(); f
f(A) == 0
g = A.charpoly(algorithm='flint')
f == g
n=20; A = Mat(ZZ,n)(range(n^2))
A.charpoly()
A.minpoly()

On non square matrices, this method raises an ArithmeticError:

Sage

sage: matrix(ZZ, 2, 1).charpoly()
Traceback (most recent call last):
...
ArithmeticError: only valid for square matrix

Python

>>> from sage.all import *
>>> matrix(ZZ, Integer(2), Integer(1)).charpoly()
Traceback (most recent call last):
...
ArithmeticError: only valid for square matrix

Sage Live

matrix(ZZ, 2, 1).charpoly()

column(i, from_list=False)[source]¶

Return the \(i\)-th column of this matrix as a dense vector.

INPUT:

i – integer
from_list – ignored

EXAMPLES:

Sage

sage: m = matrix(ZZ, 3, 2, [1, -2, 3, 4, -1, 0])
sage: m.column(1)
(-2, 4, 0)
sage: m.column(1, from_list=True)
(-2, 4, 0)
sage: m.column(-1)
(-2, 4, 0)
sage: m.column(-2)
(1, 3, -1)

sage: m.column(2)
Traceback (most recent call last):
...
IndexError: column index out of range
sage: m.column(-3)
Traceback (most recent call last):
...
IndexError: column index out of range

Python

>>> from sage.all import *
>>> m = matrix(ZZ, Integer(3), Integer(2), [Integer(1), -Integer(2), Integer(3), Integer(4), -Integer(1), Integer(0)])
>>> m.column(Integer(1))
(-2, 4, 0)
>>> m.column(Integer(1), from_list=True)
(-2, 4, 0)
>>> m.column(-Integer(1))
(-2, 4, 0)
>>> m.column(-Integer(2))
(1, 3, -1)

>>> m.column(Integer(2))
Traceback (most recent call last):
...
IndexError: column index out of range
>>> m.column(-Integer(3))
Traceback (most recent call last):
...
IndexError: column index out of range

Sage Live

m = matrix(ZZ, 3, 2, [1, -2, 3, 4, -1, 0])
m.column(1)
m.column(1, from_list=True)
m.column(-1)
m.column(-2)
m.column(2)
m.column(-3)

decomposition(**kwds)[source]¶

Return the decomposition of the free module on which this matrix A acts from the right (i.e., the action is x goes to x A), along with whether this matrix acts irreducibly on each factor. The factors are guaranteed to be sorted in the same way as the corresponding factors of the characteristic polynomial, and are saturated as ZZ modules.

INPUT:

self – a matrix over the integers
**kwds – these are passed onto to the decomposition over QQ command

EXAMPLES:

Sage

sage: t = ModularSymbols(11,sign=1).hecke_matrix(2)
sage: w = t.change_ring(ZZ)
sage: w
[ 3 -2]
[ 0 -2]
sage: w.charpoly().factor()
(x - 3) * (x + 2)
sage: w.decomposition()
[
(Free module of degree 2 and rank 1 over Integer Ring
Echelon basis matrix:
[ 5 -2], True),
(Free module of degree 2 and rank 1 over Integer Ring
Echelon basis matrix:
[0 1], True)
]

Python

>>> from sage.all import *
>>> t = ModularSymbols(Integer(11),sign=Integer(1)).hecke_matrix(Integer(2))
>>> w = t.change_ring(ZZ)
>>> w
[ 3 -2]
[ 0 -2]
>>> w.charpoly().factor()
(x - 3) * (x + 2)
>>> w.decomposition()
[
(Free module of degree 2 and rank 1 over Integer Ring
Echelon basis matrix:
[ 5 -2], True),
(Free module of degree 2 and rank 1 over Integer Ring
Echelon basis matrix:
[0 1], True)
]

Sage Live

t = ModularSymbols(11,sign=1).hecke_matrix(2)
w = t.change_ring(ZZ)
w
w.charpoly().factor()
w.decomposition()

determinant(algorithm='default', proof=None, stabilize=2)[source]¶

Return the determinant of this matrix.

INPUT:

algorithm
- 'default' – use flint
- 'flint' – let flint do the determinant
- 'padic' – uses a \(p\)-adic / multimodular algorithm that relies on code in IML and linbox
- 'linbox' – calls linbox det (you must set proof=False to use this!)
- 'ntl' – calls NTL’s det function
- 'pari' – uses PARI
proof – boolean or None; if None use proof.linear_algebra(); only relevant for the padic algorithm

Note

It would be VERY VERY hard for det to fail even with proof=False.
stabilize – if proof is False, require det to be the same for this many CRT primes in a row. Ignored if proof is True.

ALGORITHM: The \(p\)-adic algorithm works by first finding a random vector v, then solving \(Ax = v\) and taking the denominator \(d\). This gives a divisor of the determinant. Then we compute \(\det(A)/d\) using a multimodular algorithm and the Hadamard bound, skipping primes that divide \(d\).

EXAMPLES:

Sage

sage: A = matrix(ZZ,8,8,[3..66])
sage: A.determinant()
0

Python

>>> from sage.all import *
>>> A = matrix(ZZ,Integer(8),Integer(8),(ellipsis_range(Integer(3),Ellipsis,Integer(66))))
>>> A.determinant()
0

Sage Live

A = matrix(ZZ,8,8,[3..66])
A.determinant()

Sage

sage: A = random_matrix(ZZ,20,20)
sage: D1 = A.determinant()
sage: A._clear_cache()
sage: D2 = A.determinant(algorithm='ntl')
sage: D1 == D2
True

Python

>>> from sage.all import *
>>> A = random_matrix(ZZ,Integer(20),Integer(20))
>>> D1 = A.determinant()
>>> A._clear_cache()
>>> D2 = A.determinant(algorithm='ntl')
>>> D1 == D2
True

Sage Live

A = random_matrix(ZZ,20,20)
D1 = A.determinant()
A._clear_cache()
D2 = A.determinant(algorithm='ntl')
D1 == D2

Python

>>> from sage.all import *
>>> A = random_matrix(ZZ,Integer(20),Integer(20))
>>> D1 = A.determinant()
>>> A._clear_cache()
>>> D2 = A.determinant(algorithm='ntl')
>>> D1 == D2
True

Sage Live

A = random_matrix(ZZ,20,20)
D1 = A.determinant()
A._clear_cache()
D2 = A.determinant(algorithm='ntl')
D1 == D2

We have a special-case algorithm for 4 x 4 determinants:

Sage

sage: A = matrix(ZZ,4,[1,2,3,4,4,3,2,1,0,5,0,1,9,1,2,3])
sage: A.determinant()
270

Python

>>> from sage.all import *
>>> A = matrix(ZZ,Integer(4),[Integer(1),Integer(2),Integer(3),Integer(4),Integer(4),Integer(3),Integer(2),Integer(1),Integer(0),Integer(5),Integer(0),Integer(1),Integer(9),Integer(1),Integer(2),Integer(3)])
>>> A.determinant()
270

Sage Live

A = matrix(ZZ,4,[1,2,3,4,4,3,2,1,0,5,0,1,9,1,2,3])
A.determinant()

Next we try the Linbox det. Note that we must have proof=False.

Sage

sage: A = matrix(ZZ,5,[1,2,3,4,5,4,6,3,2,1,7,9,7,5,2,1,4,6,7,8,3,2,4,6,7])
sage: A.determinant(algorithm='linbox')
Traceback (most recent call last):
...
RuntimeError: you must pass the proof=False option to the determinant command to use LinBox's det algorithm
sage: A.determinant(algorithm='linbox', proof=False)
-21
sage: A._clear_cache()
sage: A.determinant()
-21

Python

>>> from sage.all import *
>>> A = matrix(ZZ,Integer(5),[Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(4),Integer(6),Integer(3),Integer(2),Integer(1),Integer(7),Integer(9),Integer(7),Integer(5),Integer(2),Integer(1),Integer(4),Integer(6),Integer(7),Integer(8),Integer(3),Integer(2),Integer(4),Integer(6),Integer(7)])
>>> A.determinant(algorithm='linbox')
Traceback (most recent call last):
...
RuntimeError: you must pass the proof=False option to the determinant command to use LinBox's det algorithm
>>> A.determinant(algorithm='linbox', proof=False)
-21
>>> A._clear_cache()
>>> A.determinant()
-21

Sage Live

A = matrix(ZZ,5,[1,2,3,4,5,4,6,3,2,1,7,9,7,5,2,1,4,6,7,8,3,2,4,6,7])
A.determinant(algorithm='linbox')
A.determinant(algorithm='linbox', proof=False)
A._clear_cache()
A.determinant()

Try the other algorithms on the same example:

Sage

sage: A._clear_cache(); A.determinant(algorithm='padic')
-21
sage: A._clear_cache(); A.determinant(algorithm='pari')
-21
sage: A._clear_cache(); A.determinant(algorithm='ntl')
-21
sage: A._clear_cache(); A.determinant(algorithm='padic')
-21

Python

>>> from sage.all import *
>>> A._clear_cache(); A.determinant(algorithm='padic')
-21
>>> A._clear_cache(); A.determinant(algorithm='pari')
-21
>>> A._clear_cache(); A.determinant(algorithm='ntl')
-21
>>> A._clear_cache(); A.determinant(algorithm='padic')
-21

Sage Live

A._clear_cache(); A.determinant(algorithm='padic')
A._clear_cache(); A.determinant(algorithm='pari')
A._clear_cache(); A.determinant(algorithm='ntl')
A._clear_cache(); A.determinant(algorithm='padic')

A bigger example:

Sage

sage: A = random_matrix(ZZ,30)
sage: d = A.determinant()
sage: A._clear_cache()
sage: A.determinant(algorithm='linbox',proof=False) == d
True

Python

>>> from sage.all import *
>>> A = random_matrix(ZZ,Integer(30))
>>> d = A.determinant()
>>> A._clear_cache()
>>> A.determinant(algorithm='linbox',proof=False) == d
True

Sage Live

A = random_matrix(ZZ,30)
d = A.determinant()
A._clear_cache()
A.determinant(algorithm='linbox',proof=False) == d

echelon_form(algorithm='default', proof=None, include_zero_rows=True, transformation=False, D=None)[source]¶

Return the echelon form of this matrix over the integers, also known as the hermite normal form (HNF).

INPUT:

algorithm – string; the algorithm to use. Valid options are:
- 'default' – let Sage pick an algorithm (default). Up to 75 rows or columns with no transformation matrix, use pari with flag 0; otherwise, use flint.
- 'flint' – use flint
- 'ntl' – use NTL (only works for square matrices of full rank!)
- 'padic' – an asymptotically fast \(p\)-adic modular algorithm, If your matrix has large coefficients and is small, you may also want to try this.
- 'pari' – use PARI with flag 1
- 'pari0' – use PARI with flag 0
- 'pari1' – use PARI with flag 1
- 'pari4' – use PARI with flag 4 (use heuristic LLL)
proof – (default: True) if proof=False certain determinants are computed using a randomized hybrid \(p\)-adic multimodular strategy until it stabilizes twice (instead of up to the Hadamard bound). It is incredibly unlikely that one would ever get an incorrect result with proof=False.
include_zero_rows – boolean (default: True); if False, don’t include zero rows
transformation – if given, also compute transformation matrix; only valid for flint and padic algorithm
D – (default: None) if given and the algorithm is 'ntl', then D must be a multiple of the determinant and this function will use that fact

OUTPUT:

The Hermite normal form (=echelon form over \(\ZZ\)) of self as an immutable matrix.

EXAMPLES:

Sage

sage: A = MatrixSpace(ZZ,2)([1,2,3,4])
sage: A.echelon_form()
[1 0]
[0 2]
sage: A = MatrixSpace(ZZ,5)(range(25))
sage: A.echelon_form()
[  5   0  -5 -10 -15]
[  0   1   2   3   4]
[  0   0   0   0   0]
[  0   0   0   0   0]
[  0   0   0   0   0]

Python

>>> from sage.all import *
>>> A = MatrixSpace(ZZ,Integer(2))([Integer(1),Integer(2),Integer(3),Integer(4)])
>>> A.echelon_form()
[1 0]
[0 2]
>>> A = MatrixSpace(ZZ,Integer(5))(range(Integer(25)))
>>> A.echelon_form()
[  5   0  -5 -10 -15]
[  0   1   2   3   4]
[  0   0   0   0   0]
[  0   0   0   0   0]
[  0   0   0   0   0]

Sage Live

A = MatrixSpace(ZZ,2)([1,2,3,4])
A.echelon_form()
A = MatrixSpace(ZZ,5)(range(25))
A.echelon_form()

Getting a transformation matrix in the nonsquare case:

Sage

sage: A = matrix(ZZ,5,3,[1..15])
sage: H, U = A.hermite_form(transformation=True, include_zero_rows=False)
sage: H
[1 2 3]
[0 3 6]
sage: U
[  0   0   0   4  -3]
[  0   0   0  13 -10]
sage: U*A == H
True

Python

>>> from sage.all import *
>>> A = matrix(ZZ,Integer(5),Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(15))))
>>> H, U = A.hermite_form(transformation=True, include_zero_rows=False)
>>> H
[1 2 3]
[0 3 6]
>>> U
[  0   0   0   4  -3]
[  0   0   0  13 -10]
>>> U*A == H
True

Sage Live

A = matrix(ZZ,5,3,[1..15])
H, U = A.hermite_form(transformation=True, include_zero_rows=False)
H
U
U*A == H

Note

If ‘ntl’ is chosen for a non square matrix this function raises a ValueError.

Special cases: 0 or 1 rows:

Sage

sage: a = matrix(ZZ, 1,2,[0,-1])
sage: a.hermite_form()
[0 1]
sage: a.pivots()
(1,)
sage: a = matrix(ZZ, 1,2,[0,0])
sage: a.hermite_form()
[0 0]
sage: a.pivots()
()
sage: a = matrix(ZZ,1,3); a
[0 0 0]
sage: a.echelon_form(include_zero_rows=False)
[]
sage: a.echelon_form(include_zero_rows=True)
[0 0 0]

Python

>>> from sage.all import *
>>> a = matrix(ZZ, Integer(1),Integer(2),[Integer(0),-Integer(1)])
>>> a.hermite_form()
[0 1]
>>> a.pivots()
(1,)
>>> a = matrix(ZZ, Integer(1),Integer(2),[Integer(0),Integer(0)])
>>> a.hermite_form()
[0 0]
>>> a.pivots()
()
>>> a = matrix(ZZ,Integer(1),Integer(3)); a
[0 0 0]
>>> a.echelon_form(include_zero_rows=False)
[]
>>> a.echelon_form(include_zero_rows=True)
[0 0 0]

Sage Live

a = matrix(ZZ, 1,2,[0,-1])
a.hermite_form()
a.pivots()
a = matrix(ZZ, 1,2,[0,0])
a.hermite_form()
a.pivots()
a = matrix(ZZ,1,3); a
a.echelon_form(include_zero_rows=False)
a.echelon_form(include_zero_rows=True)

Illustrate using various algorithms.:

Sage

sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari0')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari4')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='padic')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='default')
[1 2 3]
[0 3 6]
[0 0 0]

Python

>>> from sage.all import *
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='pari')
[1 2 3]
[0 3 6]
[0 0 0]
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='pari0')
[1 2 3]
[0 3 6]
[0 0 0]
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='pari4')
[1 2 3]
[0 3 6]
[0 0 0]
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='padic')
[1 2 3]
[0 3 6]
[0 0 0]
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='default')
[1 2 3]
[0 3 6]
[0 0 0]

Sage Live

matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari')
matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari0')
matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari4')
matrix(ZZ,3,[1..9]).hermite_form(algorithm='padic')
matrix(ZZ,3,[1..9]).hermite_form(algorithm='default')

The ‘ntl’ algorithm doesn’t work on matrices that do not have full rank.:

Sage

sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='ntl')
Traceback (most recent call last):
...
ValueError: ntl only computes HNF for square matrices of full rank.
sage: matrix(ZZ,3,[0] +[2..9]).hermite_form(algorithm='ntl')
[1 0 0]
[0 1 0]
[0 0 3]

Python

>>> from sage.all import *
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='ntl')
Traceback (most recent call last):
...
ValueError: ntl only computes HNF for square matrices of full rank.
>>> matrix(ZZ,Integer(3),[Integer(0)] +(ellipsis_range(Integer(2),Ellipsis,Integer(9)))).hermite_form(algorithm='ntl')
[1 0 0]
[0 1 0]
[0 0 3]

Sage Live

matrix(ZZ,3,[1..9]).hermite_form(algorithm='ntl')
matrix(ZZ,3,[0] +[2..9]).hermite_form(algorithm='ntl')

elementary_divisors(algorithm='pari')[source]¶

Return the elementary divisors of self, in order.

Warning

This is MUCH faster than the smith_form() function.

The elementary divisors are the invariants of the finite abelian group that is the cokernel of left multiplication of this matrix. They are ordered in reverse by divisibility.

INPUT:

self – matrix
algorithm – (default: 'pari')
- 'pari' – works robustly, but is slower.
- 'linbox' – use linbox (currently off, broken)

OUTPUT: list of integers

Note

These are the invariants of the cokernel of left multiplication:

Sage

sage: M = Matrix([[3,0,1],[0,1,0]])
sage: M
[3 0 1]
[0 1 0]
sage: M.elementary_divisors()
[1, 1]
sage: M.transpose().elementary_divisors()
[1, 1, 0]

Python

>>> from sage.all import *
>>> M = Matrix([[Integer(3),Integer(0),Integer(1)],[Integer(0),Integer(1),Integer(0)]])
>>> M
[3 0 1]
[0 1 0]
>>> M.elementary_divisors()
[1, 1]
>>> M.transpose().elementary_divisors()
[1, 1, 0]

Sage Live

M = Matrix([[3,0,1],[0,1,0]])
M
M.elementary_divisors()
M.transpose().elementary_divisors()

EXAMPLES:

Sage

sage: matrix(3, range(9)).elementary_divisors()
[1, 3, 0]
sage: matrix(3, range(9)).elementary_divisors(algorithm='pari')
[1, 3, 0]
sage: C = MatrixSpace(ZZ,4)([3,4,5,6,7,3,8,10,14,5,6,7,2,2,10,9])
sage: C.elementary_divisors()
[1, 1, 1, 687]

Python

>>> from sage.all import *
>>> matrix(Integer(3), range(Integer(9))).elementary_divisors()
[1, 3, 0]
>>> matrix(Integer(3), range(Integer(9))).elementary_divisors(algorithm='pari')
[1, 3, 0]
>>> C = MatrixSpace(ZZ,Integer(4))([Integer(3),Integer(4),Integer(5),Integer(6),Integer(7),Integer(3),Integer(8),Integer(10),Integer(14),Integer(5),Integer(6),Integer(7),Integer(2),Integer(2),Integer(10),Integer(9)])
>>> C.elementary_divisors()
[1, 1, 1, 687]

Sage Live

matrix(3, range(9)).elementary_divisors()
matrix(3, range(9)).elementary_divisors(algorithm='pari')
C = MatrixSpace(ZZ,4)([3,4,5,6,7,3,8,10,14,5,6,7,2,2,10,9])
C.elementary_divisors()

Sage

sage: M = matrix(ZZ, 3, [1,5,7, 3,6,9, 0,1,2])
sage: M.elementary_divisors()
[1, 1, 6]

Python

>>> from sage.all import *
>>> M = matrix(ZZ, Integer(3), [Integer(1),Integer(5),Integer(7), Integer(3),Integer(6),Integer(9), Integer(0),Integer(1),Integer(2)])
>>> M.elementary_divisors()
[1, 1, 6]

Sage Live

M = matrix(ZZ, 3, [1,5,7, 3,6,9, 0,1,2])
M.elementary_divisors()

Python

>>> from sage.all import *
>>> M = matrix(ZZ, Integer(3), [Integer(1),Integer(5),Integer(7), Integer(3),Integer(6),Integer(9), Integer(0),Integer(1),Integer(2)])
>>> M.elementary_divisors()
[1, 1, 6]

Sage Live

M = matrix(ZZ, 3, [1,5,7, 3,6,9, 0,1,2])
M.elementary_divisors()

This returns a copy, which is safe to change:

Sage

sage: edivs = M.elementary_divisors()
sage: edivs.pop()
6
sage: M.elementary_divisors()
[1, 1, 6]

Python

>>> from sage.all import *
>>> edivs = M.elementary_divisors()
>>> edivs.pop()
6
>>> M.elementary_divisors()
[1, 1, 6]

Sage Live

edivs = M.elementary_divisors()
edivs.pop()
M.elementary_divisors()

See also

smith_form()

frobenius(*args, **kwds)[source]¶: Deprecated: Use frobenius_form() instead. See Issue #36396 for details.

frobenius_form(flag=0, var='x')[source]¶

Return the Frobenius form (rational canonical form) of this matrix.

INPUT:

flag – 0 (default), 1 or 2 as follows:
- 0 – (default) return the Frobenius form of this
  matrix
- 1 – return only the elementary divisor
  polynomials, as polynomials in var
- 2 – return a two-components vector [F,B] where F
  is the Frobenius form and B is the basis change so that \(M=B^{-1}FB\)
var – string (default: 'x')

ALGORITHM: uses PARI’s pari:matfrobenius

EXAMPLES:

Sage

sage: A = MatrixSpace(ZZ, 3)(range(9))
sage: A.frobenius_form(0)
[ 0  0  0]
[ 1  0 18]
[ 0  1 12]
sage: A.frobenius_form(1)
[x^3 - 12*x^2 - 18*x]
sage: A.frobenius_form(1, var='y')
[y^3 - 12*y^2 - 18*y]
sage: F, B = A.frobenius_form(2)
sage: A == B^(-1)*F*B
True
sage: a=matrix([])
sage: a.frobenius_form(2)
([], [])
sage: a.frobenius_form(0)
[]
sage: a.frobenius_form(1)
[]
sage: B = random_matrix(ZZ,2,3)
sage: B.frobenius_form()
Traceback (most recent call last):
...
ArithmeticError: frobenius matrix of non-square matrix not defined.

Python

>>> from sage.all import *
>>> A = MatrixSpace(ZZ, Integer(3))(range(Integer(9)))
>>> A.frobenius_form(Integer(0))
[ 0  0  0]
[ 1  0 18]
[ 0  1 12]
>>> A.frobenius_form(Integer(1))
[x^3 - 12*x^2 - 18*x]
>>> A.frobenius_form(Integer(1), var='y')
[y^3 - 12*y^2 - 18*y]
>>> F, B = A.frobenius_form(Integer(2))
>>> A == B**(-Integer(1))*F*B
True
>>> a=matrix([])
>>> a.frobenius_form(Integer(2))
([], [])
>>> a.frobenius_form(Integer(0))
[]
>>> a.frobenius_form(Integer(1))
[]
>>> B = random_matrix(ZZ,Integer(2),Integer(3))
>>> B.frobenius_form()
Traceback (most recent call last):
...
ArithmeticError: frobenius matrix of non-square matrix not defined.

Sage Live

A = MatrixSpace(ZZ, 3)(range(9))
A.frobenius_form(0)
A.frobenius_form(1)
A.frobenius_form(1, var='y')
F, B = A.frobenius_form(2)
A == B^(-1)*F*B
a=matrix([])
a.frobenius_form(2)
a.frobenius_form(0)
a.frobenius_form(1)
B = random_matrix(ZZ,2,3)
B.frobenius_form()

AUTHORS:

Martin Albrecht (2006-04-02)

TODO: - move this to work for more general matrices than just over Z. This will require fixing how PARI polynomials are coerced to Sage polynomials.

gcd()[source]¶

Return the gcd of all entries of self; very fast.

EXAMPLES:

Sage

sage: a = matrix(ZZ,2, [6,15,-6,150])
sage: a.gcd()
3

Python

>>> from sage.all import *
>>> a = matrix(ZZ,Integer(2), [Integer(6),Integer(15),-Integer(6),Integer(150)])
>>> a.gcd()
3

Sage Live

a = matrix(ZZ,2, [6,15,-6,150])
a.gcd()

height()[source]¶

Return the height of this matrix, i.e., the max absolute value of the entries of the matrix.

OUTPUT: nonnegative integer

EXAMPLES:

Sage

sage: a = Mat(ZZ,3)(range(9))
sage: a.height()
8
sage: a = Mat(ZZ,2,3)([-17,3,-389,15,-1,0]); a
[ -17    3 -389]
[  15   -1    0]
sage: a.height()
389

Python

>>> from sage.all import *
>>> a = Mat(ZZ,Integer(3))(range(Integer(9)))
>>> a.height()
8
>>> a = Mat(ZZ,Integer(2),Integer(3))([-Integer(17),Integer(3),-Integer(389),Integer(15),-Integer(1),Integer(0)]); a
[ -17    3 -389]
[  15   -1    0]
>>> a.height()
389

Sage Live

a = Mat(ZZ,3)(range(9))
a.height()
a = Mat(ZZ,2,3)([-17,3,-389,15,-1,0]); a
a.height()

hermite_form(algorithm='default', proof=None, include_zero_rows=True, transformation=False, D=None)[source]¶

Return the echelon form of this matrix over the integers, also known as the hermite normal form (HNF).

INPUT:

algorithm – string; the algorithm to use. Valid options are:
- 'default' – let Sage pick an algorithm (default). Up to 75 rows or columns with no transformation matrix, use pari with flag 0; otherwise, use flint.
- 'flint' – use flint
- 'ntl' – use NTL (only works for square matrices of full rank!)
- 'padic' – an asymptotically fast \(p\)-adic modular algorithm, If your matrix has large coefficients and is small, you may also want to try this.
- 'pari' – use PARI with flag 1
- 'pari0' – use PARI with flag 0
- 'pari1' – use PARI with flag 1
- 'pari4' – use PARI with flag 4 (use heuristic LLL)
proof – (default: True) if proof=False certain determinants are computed using a randomized hybrid \(p\)-adic multimodular strategy until it stabilizes twice (instead of up to the Hadamard bound). It is incredibly unlikely that one would ever get an incorrect result with proof=False.
include_zero_rows – boolean (default: True); if False, don’t include zero rows
transformation – if given, also compute transformation matrix; only valid for flint and padic algorithm
D – (default: None) if given and the algorithm is 'ntl', then D must be a multiple of the determinant and this function will use that fact

OUTPUT:

The Hermite normal form (=echelon form over \(\ZZ\)) of self as an immutable matrix.

EXAMPLES:

Sage

sage: A = MatrixSpace(ZZ,2)([1,2,3,4])
sage: A.echelon_form()
[1 0]
[0 2]
sage: A = MatrixSpace(ZZ,5)(range(25))
sage: A.echelon_form()
[  5   0  -5 -10 -15]
[  0   1   2   3   4]
[  0   0   0   0   0]
[  0   0   0   0   0]
[  0   0   0   0   0]

Python

>>> from sage.all import *
>>> A = MatrixSpace(ZZ,Integer(2))([Integer(1),Integer(2),Integer(3),Integer(4)])
>>> A.echelon_form()
[1 0]
[0 2]
>>> A = MatrixSpace(ZZ,Integer(5))(range(Integer(25)))
>>> A.echelon_form()
[  5   0  -5 -10 -15]
[  0   1   2   3   4]
[  0   0   0   0   0]
[  0   0   0   0   0]
[  0   0   0   0   0]

Sage Live

A = MatrixSpace(ZZ,2)([1,2,3,4])
A.echelon_form()
A = MatrixSpace(ZZ,5)(range(25))
A.echelon_form()

Getting a transformation matrix in the nonsquare case:

Sage

sage: A = matrix(ZZ,5,3,[1..15])
sage: H, U = A.hermite_form(transformation=True, include_zero_rows=False)
sage: H
[1 2 3]
[0 3 6]
sage: U
[  0   0   0   4  -3]
[  0   0   0  13 -10]
sage: U*A == H
True

Python

>>> from sage.all import *
>>> A = matrix(ZZ,Integer(5),Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(15))))
>>> H, U = A.hermite_form(transformation=True, include_zero_rows=False)
>>> H
[1 2 3]
[0 3 6]
>>> U
[  0   0   0   4  -3]
[  0   0   0  13 -10]
>>> U*A == H
True

Sage Live

A = matrix(ZZ,5,3,[1..15])
H, U = A.hermite_form(transformation=True, include_zero_rows=False)
H
U
U*A == H

Note

If ‘ntl’ is chosen for a non square matrix this function raises a ValueError.

Special cases: 0 or 1 rows:

Sage

sage: a = matrix(ZZ, 1,2,[0,-1])
sage: a.hermite_form()
[0 1]
sage: a.pivots()
(1,)
sage: a = matrix(ZZ, 1,2,[0,0])
sage: a.hermite_form()
[0 0]
sage: a.pivots()
()
sage: a = matrix(ZZ,1,3); a
[0 0 0]
sage: a.echelon_form(include_zero_rows=False)
[]
sage: a.echelon_form(include_zero_rows=True)
[0 0 0]

Python

>>> from sage.all import *
>>> a = matrix(ZZ, Integer(1),Integer(2),[Integer(0),-Integer(1)])
>>> a.hermite_form()
[0 1]
>>> a.pivots()
(1,)
>>> a = matrix(ZZ, Integer(1),Integer(2),[Integer(0),Integer(0)])
>>> a.hermite_form()
[0 0]
>>> a.pivots()
()
>>> a = matrix(ZZ,Integer(1),Integer(3)); a
[0 0 0]
>>> a.echelon_form(include_zero_rows=False)
[]
>>> a.echelon_form(include_zero_rows=True)
[0 0 0]

Sage Live

a = matrix(ZZ, 1,2,[0,-1])
a.hermite_form()
a.pivots()
a = matrix(ZZ, 1,2,[0,0])
a.hermite_form()
a.pivots()
a = matrix(ZZ,1,3); a
a.echelon_form(include_zero_rows=False)
a.echelon_form(include_zero_rows=True)

Illustrate using various algorithms.:

Sage

sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari0')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari4')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='padic')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='default')
[1 2 3]
[0 3 6]
[0 0 0]

Python

>>> from sage.all import *
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='pari')
[1 2 3]
[0 3 6]
[0 0 0]
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='pari0')
[1 2 3]
[0 3 6]
[0 0 0]
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='pari4')
[1 2 3]
[0 3 6]
[0 0 0]
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='padic')
[1 2 3]
[0 3 6]
[0 0 0]
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='default')
[1 2 3]
[0 3 6]
[0 0 0]

Sage Live

matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari')
matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari0')
matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari4')
matrix(ZZ,3,[1..9]).hermite_form(algorithm='padic')
matrix(ZZ,3,[1..9]).hermite_form(algorithm='default')

The ‘ntl’ algorithm doesn’t work on matrices that do not have full rank.:

Sage

sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='ntl')
Traceback (most recent call last):
...
ValueError: ntl only computes HNF for square matrices of full rank.
sage: matrix(ZZ,3,[0] +[2..9]).hermite_form(algorithm='ntl')
[1 0 0]
[0 1 0]
[0 0 3]

Python

>>> from sage.all import *
>>> matrix(ZZ,Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))).hermite_form(algorithm='ntl')
Traceback (most recent call last):
...
ValueError: ntl only computes HNF for square matrices of full rank.
>>> matrix(ZZ,Integer(3),[Integer(0)] +(ellipsis_range(Integer(2),Ellipsis,Integer(9)))).hermite_form(algorithm='ntl')
[1 0 0]
[0 1 0]
[0 0 3]

Sage Live

matrix(ZZ,3,[1..9]).hermite_form(algorithm='ntl')
matrix(ZZ,3,[0] +[2..9]).hermite_form(algorithm='ntl')

index_in_saturation(proof=None)[source]¶

Return the index of self in its saturation.

INPUT:

proof – (default: use proof.linear_algebra()); if False, the determinant calculations are done with proof=False

OUTPUT: positive integer; the index of the row span of this matrix in its saturation

ALGORITHM:

Use Hermite normal form twice to find an invertible matrix whose inverse transforms a matrix with the same row span as self to its saturation, then compute the determinant of that matrix.

EXAMPLES:

Sage

sage: A = matrix(ZZ, 2,3, [1..6]); A
[1 2 3]
[4 5 6]
sage: A.index_in_saturation()
3
sage: A.saturation()
[1 2 3]
[1 1 1]

Python

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(2),Integer(3), (ellipsis_range(Integer(1),Ellipsis,Integer(6)))); A
[1 2 3]
[4 5 6]
>>> A.index_in_saturation()
3
>>> A.saturation()
[1 2 3]
[1 1 1]

Sage Live

A = matrix(ZZ, 2,3, [1..6]); A
A.index_in_saturation()
A.saturation()

insert_row(index, row)[source]¶

Create a new matrix from self with.

INPUT:

index – integer
row – a vector

EXAMPLES:

Sage

sage: X = matrix(ZZ,3,range(9)); X
[0 1 2]
[3 4 5]
[6 7 8]
sage: X.insert_row(1, [1,5,-10])
[  0   1   2]
[  1   5 -10]
[  3   4   5]
[  6   7   8]
sage: X.insert_row(0, [1,5,-10])
[  1   5 -10]
[  0   1   2]
[  3   4   5]
[  6   7   8]
sage: X.insert_row(3, [1,5,-10])
[  0   1   2]
[  3   4   5]
[  6   7   8]
[  1   5 -10]

Python

>>> from sage.all import *
>>> X = matrix(ZZ,Integer(3),range(Integer(9))); X
[0 1 2]
[3 4 5]
[6 7 8]
>>> X.insert_row(Integer(1), [Integer(1),Integer(5),-Integer(10)])
[  0   1   2]
[  1   5 -10]
[  3   4   5]
[  6   7   8]
>>> X.insert_row(Integer(0), [Integer(1),Integer(5),-Integer(10)])
[  1   5 -10]
[  0   1   2]
[  3   4   5]
[  6   7   8]
>>> X.insert_row(Integer(3), [Integer(1),Integer(5),-Integer(10)])
[  0   1   2]
[  3   4   5]
[  6   7   8]
[  1   5 -10]

Sage Live

X = matrix(ZZ,3,range(9)); X
X.insert_row(1, [1,5,-10])
X.insert_row(0, [1,5,-10])
X.insert_row(3, [1,5,-10])

integer_valued_polynomials_generators()[source]¶

Determine the generators of the ring of integer valued polynomials on this matrix.

OUTPUT:

A pair (mu_B, P) where P is a list of polynomials in \(\QQ[X]\) such that

\[\{f \in \QQ[X] \mid f(B) \in M_n(\ZZ)\} = \mu_B \QQ[X] + \sum_{g\in P} g \ZZ[X]\]

where \(B\) is this matrix.

EXAMPLES:

Sage

sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: B.integer_valued_polynomials_generators()
(x^3 + x^2 - 12*x - 20, [1, 1/4*x^2 + 3/4*x + 1/2])

Python

>>> from sage.all import *
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> B.integer_valued_polynomials_generators()
(x^3 + x^2 - 12*x - 20, [1, 1/4*x^2 + 3/4*x + 1/2])

Sage Live

B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
B.integer_valued_polynomials_generators()

inverse_of_unit()[source]¶

If self is a matrix with determinant \(1\) or \(-1\) return the inverse of self as a matrix over \(ZZ\).

EXAMPLES:

Sage

sage: m = matrix(ZZ, 2, [2,1,1,1]).inverse_of_unit()
sage: m
[ 1 -1]
[-1  2]
sage: parent(m)
Full MatrixSpace of 2 by 2 dense matrices over Integer Ring

sage: matrix(2, [2,1,0,1]).inverse_of_unit()
Traceback (most recent call last):
...
ArithmeticError: non-invertible matrix

Python

>>> from sage.all import *
>>> m = matrix(ZZ, Integer(2), [Integer(2),Integer(1),Integer(1),Integer(1)]).inverse_of_unit()
>>> m
[ 1 -1]
[-1  2]
>>> parent(m)
Full MatrixSpace of 2 by 2 dense matrices over Integer Ring

>>> matrix(Integer(2), [Integer(2),Integer(1),Integer(0),Integer(1)]).inverse_of_unit()
Traceback (most recent call last):
...
ArithmeticError: non-invertible matrix

Sage Live

m = matrix(ZZ, 2, [2,1,1,1]).inverse_of_unit()
m
parent(m)
matrix(2, [2,1,0,1]).inverse_of_unit()

is_LLL_reduced(delta=None, eta=None, algorithm='fpLLL')[source]¶

Return True if this lattice is \((\delta, \eta)\)-LLL reduced. See self.LLL for a definition of LLL reduction.

INPUT:

delta – (default: \(0.99\)) parameter \(\delta\) as described above
eta – (default: \(0.501\)) parameter \(\eta\) as described above
algorithm – either 'fpLLL' (default) or 'sage'

EXAMPLES:

Sage

sage: A = random_matrix(ZZ, 10, 10)
sage: L = A.LLL()
sage: A.is_LLL_reduced()
False
sage: L.is_LLL_reduced()
True

Python

>>> from sage.all import *
>>> A = random_matrix(ZZ, Integer(10), Integer(10))
>>> L = A.LLL()
>>> A.is_LLL_reduced()
False
>>> L.is_LLL_reduced()
True

Sage Live

A = random_matrix(ZZ, 10, 10)
L = A.LLL()
A.is_LLL_reduced()
L.is_LLL_reduced()

The 'sage' algorithm currently does not work for matrices with linearly dependent rows:

Sage

sage: A = matrix(ZZ, [[1, 2, 3], [2, 4, 6]])
sage: A.is_LLL_reduced(algorithm='sage')
Traceback (most recent call last):
...
ValueError: linearly dependent input for module version of Gram-Schmidt

Python

>>> from sage.all import *
>>> A = matrix(ZZ, [[Integer(1), Integer(2), Integer(3)], [Integer(2), Integer(4), Integer(6)]])
>>> A.is_LLL_reduced(algorithm='sage')
Traceback (most recent call last):
...
ValueError: linearly dependent input for module version of Gram-Schmidt

Sage Live

A = matrix(ZZ, [[1, 2, 3], [2, 4, 6]])
A.is_LLL_reduced(algorithm='sage')

is_one()[source]¶

Test whether self is the identity matrix.

EXAMPLES:

Sage

sage: matrix(2, [1,0,0,1]).is_one()
True
sage: matrix(2, [1,1,0,1]).is_one()
False
sage: matrix(2, 3, [1,0,0,0,1,0]).is_one()
False

Python

>>> from sage.all import *
>>> matrix(Integer(2), [Integer(1),Integer(0),Integer(0),Integer(1)]).is_one()
True
>>> matrix(Integer(2), [Integer(1),Integer(1),Integer(0),Integer(1)]).is_one()
False
>>> matrix(Integer(2), Integer(3), [Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0)]).is_one()
False

Sage Live

matrix(2, [1,0,0,1]).is_one()
matrix(2, [1,1,0,1]).is_one()
matrix(2, 3, [1,0,0,0,1,0]).is_one()

is_primitive()[source]¶

Test whether the matrix is primitive.

An integral matrix \(A\) is primitive if all its entries are nonnegative and for some positive integer \(n\) the matrix \(A^n\) has all its entries positive.

EXAMPLES:

Sage

sage: m = matrix(3, [1,1,0,0,0,1,1,0,0])
sage: m.is_primitive()
True
sage: m**4
[3 2 1]
[1 1 1]
[2 1 1]

sage: m = matrix(4, [[1,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]])
sage: m.is_primitive()
True
sage: m**6
[4 3 2 1]
[1 1 1 1]
[2 1 1 1]
[3 2 1 1]

sage: m = matrix(4, [[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]])
sage: m.is_primitive()
False

Python

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

>>> m = matrix(Integer(4), [[Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(0),Integer(1)],[Integer(1),Integer(0),Integer(0),Integer(0)]])
>>> m.is_primitive()
True
>>> m**Integer(6)
[4 3 2 1]
[1 1 1 1]
[2 1 1 1]
[3 2 1 1]

>>> m = matrix(Integer(4), [[Integer(0),Integer(1),Integer(0),Integer(1)],[Integer(1),Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(1),Integer(0),Integer(1)],[Integer(1),Integer(0),Integer(1),Integer(0)]])
>>> m.is_primitive()
False

Sage Live

m = matrix(3, [1,1,0,0,0,1,1,0,0])
m.is_primitive()
m**4
m = matrix(4, [[1,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]])
m.is_primitive()
m**6
m = matrix(4, [[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]])
m.is_primitive()

Testing extremal matrices:

Sage

sage: def matrix1(d):
....:     m = matrix(d)
....:     m[0,0] = 1
....:     for i in range(d-1):
....:         m[i,i+1] = m[i+1,i] = 1
....:     return m
sage: all(matrix1(d).is_primitive() for d in range(2,20))
True

sage: def matrix2(d):
....:     m = matrix(d)
....:     for i in range(d-1):
....:         m[i,i+1] = 1
....:     m[d-1,0] = m[d-1,1] = 1
....:     return m
sage: all(matrix2(d).is_primitive() for d in range(2,20))
True

Python

>>> from sage.all import *
>>> def matrix1(d):
...     m = matrix(d)
...     m[Integer(0),Integer(0)] = Integer(1)
...     for i in range(d-Integer(1)):
...         m[i,i+Integer(1)] = m[i+Integer(1),i] = Integer(1)
...     return m
>>> all(matrix1(d).is_primitive() for d in range(Integer(2),Integer(20)))
True

>>> def matrix2(d):
...     m = matrix(d)
...     for i in range(d-Integer(1)):
...         m[i,i+Integer(1)] = Integer(1)
...     m[d-Integer(1),Integer(0)] = m[d-Integer(1),Integer(1)] = Integer(1)
...     return m
>>> all(matrix2(d).is_primitive() for d in range(Integer(2),Integer(20)))
True

Sage Live

def matrix1(d):
    m = matrix(d)
    m[0,0] = 1
    for i in range(d-1):
        m[i,i+1] = m[i+1,i] = 1
    return m
all(matrix1(d).is_primitive() for d in range(2,20))
def matrix2(d):
    m = matrix(d)
    for i in range(d-1):
        m[i,i+1] = 1
    m[d-1,0] = m[d-1,1] = 1
    return m
all(matrix2(d).is_primitive() for d in range(2,20))

Non-primitive families:

Sage

sage: def matrix3(d):
....:     m = matrix(d)
....:     m[0,0] = 1
....:     for i in range(d-1):
....:         m[i,i+1] = 1
....:     return m
sage: any(matrix3(d).is_primitive() for d in range(2,20))
False

Python

>>> from sage.all import *
>>> def matrix3(d):
...     m = matrix(d)
...     m[Integer(0),Integer(0)] = Integer(1)
...     for i in range(d-Integer(1)):
...         m[i,i+Integer(1)] = Integer(1)
...     return m
>>> any(matrix3(d).is_primitive() for d in range(Integer(2),Integer(20)))
False

Sage Live

def matrix3(d):
    m = matrix(d)
    m[0,0] = 1
    for i in range(d-1):
        m[i,i+1] = 1
    return m
any(matrix3(d).is_primitive() for d in range(2,20))

minpoly(var='x', algorithm=None)[source]¶

INPUT:

var – a variable name
algorithm – either 'linbox' (default) or 'generic'

EXAMPLES:

Sage

sage: A = matrix(ZZ, 6, range(36))
sage: A.minpoly()
x^3 - 105*x^2 - 630*x

sage: A = Mat(ZZ, 6)([k^2 for k in range(36)])
sage: A.minpoly(algorithm='linbox')
x^4 - 2695*x^3 - 257964*x^2 + 1693440*x
sage: A.minpoly(algorithm='generic')
x^4 - 2695*x^3 - 257964*x^2 + 1693440*x

Python

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(6), range(Integer(36)))
>>> A.minpoly()
x^3 - 105*x^2 - 630*x

>>> A = Mat(ZZ, Integer(6))([k**Integer(2) for k in range(Integer(36))])
>>> A.minpoly(algorithm='linbox')
x^4 - 2695*x^3 - 257964*x^2 + 1693440*x
>>> A.minpoly(algorithm='generic')
x^4 - 2695*x^3 - 257964*x^2 + 1693440*x

Sage Live

A = matrix(ZZ, 6, range(36))
A.minpoly()
A = Mat(ZZ, 6)([k^2 for k in range(36)])
A.minpoly(algorithm='linbox')
A.minpoly(algorithm='generic')

On non square matrices, this method raises an ArithmeticError:

Sage

sage: matrix(ZZ, 2, 1).minpoly()
Traceback (most recent call last):
...
ArithmeticError: only valid for square matrix

Python

>>> from sage.all import *
>>> matrix(ZZ, Integer(2), Integer(1)).minpoly()
Traceback (most recent call last):
...
ArithmeticError: only valid for square matrix

Sage Live

matrix(ZZ, 2, 1).minpoly()

null_ideal(b=0)[source]¶

Return the \((b)\)-ideal of this matrix.

Let \(B\) be a \(n \times n\) matrix. The null ideal modulo \(b\), or \((b)\)-ideal, is

\[N_{(b)}(B) = \{f \in \ZZ[X] \mid f(B) \in M_n(b\ZZ)\}.\]

INPUT:

b – an element of \(\ZZ\) (default: 0)

OUTPUT: an ideal in \(\ZZ[X]\)

EXAMPLES:

Sage

sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: B.null_ideal()
Principal ideal (x^3 + x^2 - 12*x - 20) of
    Univariate Polynomial Ring in x over Integer Ring
sage: B.null_ideal(8)
Ideal (8, x^3 + x^2 - 12*x - 20, 2*x^2 + 6*x + 4) of
    Univariate Polynomial Ring in x over Integer Ring
sage: B.null_ideal(6)
Ideal (6, 2*x^3 + 2*x^2 - 24*x - 40, 3*x^2 + 3*x) of
    Univariate Polynomial Ring in x over Integer Ring

Python

>>> from sage.all import *
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> B.null_ideal()
Principal ideal (x^3 + x^2 - 12*x - 20) of
    Univariate Polynomial Ring in x over Integer Ring
>>> B.null_ideal(Integer(8))
Ideal (8, x^3 + x^2 - 12*x - 20, 2*x^2 + 6*x + 4) of
    Univariate Polynomial Ring in x over Integer Ring
>>> B.null_ideal(Integer(6))
Ideal (6, 2*x^3 + 2*x^2 - 24*x - 40, 3*x^2 + 3*x) of
    Univariate Polynomial Ring in x over Integer Ring

Sage Live

B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
B.null_ideal()
B.null_ideal(8)
B.null_ideal(6)

See also

compute_J_ideal, null_ideal()

p_minimal_polynomials(p, s_max=None)[source]¶

Compute \((p^s)\)-minimal polynomials \(\nu_s\) of this matrix.

For \(s \ge 0\), a \((p^s)\)-minimal polynomial of a matrix \(B\) is a monic polynomial \(f \in \ZZ[X]\) of minimal degree such that all entries of \(f(B)\) are divisible by \(p^s\).

Compute a finite subset \(\mathcal{S}\) of the positive integers and \((p^s)\)-minimal polynomials \(\nu_s\) for \(s \in \mathcal{S}\).

For \(0 < t \le \max \mathcal{S}\), a \((p^t)\)-minimal polynomial is given by \(\nu_s\) where \(s = \min\{ r \in \mathcal{S} \mid r\ge t \}\). For \(t > \max\mathcal{S}\), the minimal polynomial of \(B\) is also a \((p^t)\)-minimal polynomial.

INPUT:

p – a prime in \(\ZZ\)
s_max – positive integer (default: None); if set, only \((p^s)\)-minimal polynomials for s <= s_max are computed (see below for details)

OUTPUT:

A dictionary. Keys are the finite set \(\mathcal{S}\), the values are the associated \((p^s)\)-minimal polynomials \(\nu_s\), \(s\in\mathcal{S}\).

Setting s_max only affects the output if s_max is at most \(\max\mathcal{S}\) where \(\mathcal{S}\) denotes the full set. In that case, only those \(\nu_s\) with s <= s_max are returned where s_max is always included even if it is not included in the full set \(\mathcal{S}\).

EXAMPLES:

Sage

sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: B.p_minimal_polynomials(2)
{2: x^2 + 3*x + 2}

Python

>>> from sage.all import *
>>> B = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(1), -Integer(2), -Integer(1)], [Integer(10), Integer(0), Integer(0)]])
>>> B.p_minimal_polynomials(Integer(2))
{2: x^2 + 3*x + 2}

Sage Live

B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
B.p_minimal_polynomials(2)

pivots()[source]¶

Return the pivot column positions of this matrix.

OUTPUT: a tuple of Python integers: the position of the first nonzero entry in each row of the echelon form.

EXAMPLES:

Sage

sage: n = 3; A = matrix(ZZ,n,range(n^2)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: A.pivots()
(0, 1)
sage: A.echelon_form()
[ 3  0 -3]
[ 0  1  2]
[ 0  0  0]

Python

>>> from sage.all import *
>>> n = Integer(3); A = matrix(ZZ,n,range(n**Integer(2))); A
[0 1 2]
[3 4 5]
[6 7 8]
>>> A.pivots()
(0, 1)
>>> A.echelon_form()
[ 3  0 -3]
[ 0  1  2]
[ 0  0  0]

Sage Live

n = 3; A = matrix(ZZ,n,range(n^2)); A
A.pivots()
A.echelon_form()

prod_of_row_sums(cols)[source]¶

Return the product of the sums of the entries in the submatrix of self with given columns.

INPUT:

cols – list (or set) of integers representing columns of self

OUTPUT: integer

EXAMPLES:

Sage

sage: a = matrix(ZZ,2,3,[1..6]); a
[1 2 3]
[4 5 6]
sage: a.prod_of_row_sums([0,2])
40
sage: (1+3)*(4+6)
40
sage: a.prod_of_row_sums(set([0,2]))
40

Python

>>> from sage.all import *
>>> a = matrix(ZZ,Integer(2),Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(6)))); a
[1 2 3]
[4 5 6]
>>> a.prod_of_row_sums([Integer(0),Integer(2)])
40
>>> (Integer(1)+Integer(3))*(Integer(4)+Integer(6))
40
>>> a.prod_of_row_sums(set([Integer(0),Integer(2)]))
40

Sage Live

a = matrix(ZZ,2,3,[1..6]); a
a.prod_of_row_sums([0,2])
(1+3)*(4+6)
a.prod_of_row_sums(set([0,2]))

randomize(density=1, x=None, y=None, distribution=None, nonzero=False)[source]¶

Randomize density proportion of the entries of this matrix, leaving the rest unchanged.

The parameters are the same as the ones for the integer ring’s random_element function.

If x and y are given, randomized entries of this matrix have to be between x and y and have density 1.

INPUT:

self – a mutable matrix over ZZ
density – a float between 0 and 1
x, y – if not None, these are passed to the
ZZ.random_element function as the upper and lower endpoints in the uniform distribution
distribution – would also be passed into ZZ.random_element if given
nonzero – boolean (default: False); whether the new entries are guaranteed to be zero

OUTPUT: None, the matrix is modified in-place

EXAMPLES:

Sage

sage: A = matrix(ZZ, 2,3, [1..6])
sage: ranks = [True, True, True]
sage: while any(ranks):
....:    A.randomize()
....:    ranks[A.rank()] = False

sage: mini = 0
sage: maxi = 0
sage: while mini != -30 and maxi != 30:
....:     A.randomize(x=-30, y=30)
....:     mini = min(min(A.list()), mini)
....:     maxi = min(min(A.list()), maxi)

Python

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(2),Integer(3), (ellipsis_range(Integer(1),Ellipsis,Integer(6))))
>>> ranks = [True, True, True]
>>> while any(ranks):
...    A.randomize()
...    ranks[A.rank()] = False

>>> mini = Integer(0)
>>> maxi = Integer(0)
>>> while mini != -Integer(30) and maxi != Integer(30):
...     A.randomize(x=-Integer(30), y=Integer(30))
...     mini = min(min(A.list()), mini)
...     maxi = min(min(A.list()), maxi)

Sage Live

A = matrix(ZZ, 2,3, [1..6])
ranks = [True, True, True]
while any(ranks):
   A.randomize()
   ranks[A.rank()] = False
mini = 0
maxi = 0
while mini != -30 and maxi != 30:
    A.randomize(x=-30, y=30)
    mini = min(min(A.list()), mini)
    maxi = min(min(A.list()), maxi)

rank(algorithm='modp')[source]¶

Return the rank of this matrix.

INPUT:

algorithm – either 'modp' (default) or 'flint' or 'linbox'

OUTPUT: nonnegative integer – the rank

Note

The rank is cached.

ALGORITHM:

If set to 'modp', first check if the matrix has maximum possible rank by working modulo one random prime. If not, call LinBox’s rank function.

EXAMPLES:

Sage

sage: a = matrix(ZZ,2,3,[1..6]); a
[1 2 3]
[4 5 6]
sage: a.rank()
2
sage: a = matrix(ZZ,3,3,[1..9]); a
[1 2 3]
[4 5 6]
[7 8 9]
sage: a.rank()
2

Python

>>> from sage.all import *
>>> a = matrix(ZZ,Integer(2),Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(6)))); a
[1 2 3]
[4 5 6]
>>> a.rank()
2
>>> a = matrix(ZZ,Integer(3),Integer(3),(ellipsis_range(Integer(1),Ellipsis,Integer(9)))); a
[1 2 3]
[4 5 6]
[7 8 9]
>>> a.rank()
2

Sage Live

a = matrix(ZZ,2,3,[1..6]); a
a.rank()
a = matrix(ZZ,3,3,[1..9]); a
a.rank()

Here is a bigger example - the rank is of course still 2:

Sage

sage: a = matrix(ZZ,100,[1..100^2]); a.rank()
2

Python

>>> from sage.all import *
>>> a = matrix(ZZ,Integer(100),(ellipsis_range(Integer(1),Ellipsis,Integer(100)**Integer(2)))); a.rank()
2

Sage Live

a = matrix(ZZ,100,[1..100^2]); a.rank()

rational_reconstruction(N)[source]¶

Use rational reconstruction to lift self to a matrix over the rational numbers (if possible), where we view self as a matrix modulo N.

INPUT:

N – integer

OUTPUT: matrix over \(\QQ\) or raise a ValueError

EXAMPLES: We create a random 4x4 matrix over ZZ.

Sage

sage: A = matrix(ZZ, 4, [4, -4, 7, 1, -1, 1, -1, -12, -1, -1, 1, -1, -3, 1, 5, -1])

Python

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(4), [Integer(4), -Integer(4), Integer(7), Integer(1), -Integer(1), Integer(1), -Integer(1), -Integer(12), -Integer(1), -Integer(1), Integer(1), -Integer(1), -Integer(3), Integer(1), Integer(5), -Integer(1)])

Sage Live

A = matrix(ZZ, 4, [4, -4, 7, 1, -1, 1, -1, -12, -1, -1, 1, -1, -3, 1, 5, -1])

There isn’t a unique rational reconstruction of it:

Sage

sage: A.rational_reconstruction(11)
Traceback (most recent call last):
...
ValueError: rational reconstruction does not exist

Python

>>> from sage.all import *
>>> A.rational_reconstruction(Integer(11))
Traceback (most recent call last):
...
ValueError: rational reconstruction does not exist

Sage Live

A.rational_reconstruction(11)

We throw in a denominator and reduce the matrix modulo 389 - it does rationally reconstruct.

Sage

sage: B = (A/3 % 389).change_ring(ZZ)
sage: B.rational_reconstruction(389) == A/3
True

Python

>>> from sage.all import *
>>> B = (A/Integer(3) % Integer(389)).change_ring(ZZ)
>>> B.rational_reconstruction(Integer(389)) == A/Integer(3)
True

Sage Live

B = (A/3 % 389).change_ring(ZZ)
B.rational_reconstruction(389) == A/3

row(i, from_list=False)[source]¶

Return the \(i\)-th row of this matrix as a dense vector.

INPUT:

i – integer
from_list – ignored

EXAMPLES:

Sage

sage: m = matrix(ZZ, 2, [1, -2, 3, 4])
sage: m.row(0)
(1, -2)
sage: m.row(1)
(3, 4)
sage: m.row(1, from_list=True)
(3, 4)
sage: m.row(-2)
(1, -2)

sage: m.row(2)
Traceback (most recent call last):
...
IndexError: row index out of range
sage: m.row(-3)
Traceback (most recent call last):
...
IndexError: row index out of range

Python

>>> from sage.all import *
>>> m = matrix(ZZ, Integer(2), [Integer(1), -Integer(2), Integer(3), Integer(4)])
>>> m.row(Integer(0))
(1, -2)
>>> m.row(Integer(1))
(3, 4)
>>> m.row(Integer(1), from_list=True)
(3, 4)
>>> m.row(-Integer(2))
(1, -2)

>>> m.row(Integer(2))
Traceback (most recent call last):
...
IndexError: row index out of range
>>> m.row(-Integer(3))
Traceback (most recent call last):
...
IndexError: row index out of range

Sage Live

m = matrix(ZZ, 2, [1, -2, 3, 4])
m.row(0)
m.row(1)
m.row(1, from_list=True)
m.row(-2)
m.row(2)
m.row(-3)

saturation(p=0, proof=None, max_dets=5)[source]¶

Return a saturation matrix of self, which is a matrix whose rows span the saturation of the row span of self. This is not unique.

The saturation of a \(\ZZ\) module \(M\) embedded in \(\ZZ^n\) is a module \(S\) that contains \(M\) with finite index such that \(\ZZ^n/S\) is torsion free. This function takes the row span \(M\) of self, and finds another matrix of full rank with row span the saturation of \(M\).

INPUT:

p – (default: 0) if nonzero given, saturate only at the prime \(p\), i.e., return a matrix whose row span is a \(\ZZ\)-module \(S\) that contains self and such that the index of \(S\) in its saturation is coprime to \(p\). If \(p\) is None, return full saturation of self.
proof – (default: use proof.linear_algebra()); if False, the determinant calculations are done with proof=False
max_dets – (default: 5) technical parameter - max number of determinant to compute when bounding prime divisor of self in its saturation.

OUTPUT: matrix over ZZ

Note

The result is not cached.

ALGORITHM: 1. Replace input by a matrix of full rank got from a subset of the rows. 2. Divide out any common factors from rows. 3. Check max_dets random dets of submatrices to see if their GCD (with p) is 1 - if so matrix is saturated and we’re done. 4. Finally, use that if A is a matrix of full rank, then \(hnf(transpose(A))^{-1}*A\) is a saturation of A.

EXAMPLES:

Sage

sage: A = matrix(ZZ, 3, 5, [-51, -1509, -71, -109, -593, -19, -341, 4, 86, 98, 0, -246, -11, 65, 217])
sage: A.echelon_form()
[      1       5    2262   20364   56576]
[      0       6   35653  320873  891313]
[      0       0   42993  386937 1074825]
sage: S = A.saturation(); S
[  -51 -1509   -71  -109  -593]
[  -19  -341     4    86    98]
[   35   994    43    51   347]

Python

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(3), Integer(5), [-Integer(51), -Integer(1509), -Integer(71), -Integer(109), -Integer(593), -Integer(19), -Integer(341), Integer(4), Integer(86), Integer(98), Integer(0), -Integer(246), -Integer(11), Integer(65), Integer(217)])
>>> A.echelon_form()
[      1       5    2262   20364   56576]
[      0       6   35653  320873  891313]
[      0       0   42993  386937 1074825]
>>> S = A.saturation(); S
[  -51 -1509   -71  -109  -593]
[  -19  -341     4    86    98]
[   35   994    43    51   347]

Sage Live

A = matrix(ZZ, 3, 5, [-51, -1509, -71, -109, -593, -19, -341, 4, 86, 98, 0, -246, -11, 65, 217])
A.echelon_form()
S = A.saturation(); S

Notice that the saturation spans a different module than A.

Sage

sage: S.echelon_form()
[ 1  2  0  8 32]
[ 0  3  0 -2 -6]
[ 0  0  1  9 25]
sage: V = A.row_space(); W = S.row_space()
sage: V.is_submodule(W)
True
sage: V.index_in(W)
85986
sage: V.index_in_saturation()
85986

Python

>>> from sage.all import *
>>> S.echelon_form()
[ 1  2  0  8 32]
[ 0  3  0 -2 -6]
[ 0  0  1  9 25]
>>> V = A.row_space(); W = S.row_space()
>>> V.is_submodule(W)
True
>>> V.index_in(W)
85986
>>> V.index_in_saturation()
85986

Sage Live

S.echelon_form()
V = A.row_space(); W = S.row_space()
V.is_submodule(W)
V.index_in(W)
V.index_in_saturation()

We illustrate each option:

Sage

sage: S = A.saturation(p=2)
sage: S = A.saturation(proof=False)
sage: S = A.saturation(max_dets=2)

Python

>>> from sage.all import *
>>> S = A.saturation(p=Integer(2))
>>> S = A.saturation(proof=False)
>>> S = A.saturation(max_dets=Integer(2))

Sage Live

S = A.saturation(p=2)
S = A.saturation(proof=False)
S = A.saturation(max_dets=2)

smith_form(transformation=True, integral=None)[source]¶

Return the smith normal form of this matrix, that is the diagonal matrix \(S\) with diagonal entries the ordered elementary divisors of this matrix.

INPUT:

transformation – boolean (default: True); whether to return the transformation matrices \(U\) and \(V\) such that \(S=U\cdot self\cdot V\)
integral – a subring of the base ring or True (default: None); ignored for matrices with integer entries

Note

The elementary_divisors() function, which returns the diagonal entries of \(S\), is VASTLY faster than this function.

The elementary divisors are the invariants of the finite abelian group that is the cokernel of this matrix. They are ordered in reverse by divisibility.

EXAMPLES:

Sage

sage: A = MatrixSpace(IntegerRing(), 3)(range(9))
sage: D, U, V = A.smith_form()
sage: D
[1 0 0]
[0 3 0]
[0 0 0]
sage: U
[ 0  2 -1]
[ 0 -1  1]
[ 1 -2  1]
sage: V
[ 0  0  1]
[-1  2 -2]
[ 1 -1  1]
sage: U*A*V
[1 0 0]
[0 3 0]
[0 0 0]

Python

>>> from sage.all import *
>>> A = MatrixSpace(IntegerRing(), Integer(3))(range(Integer(9)))
>>> D, U, V = A.smith_form()
>>> D
[1 0 0]
[0 3 0]
[0 0 0]
>>> U
[ 0  2 -1]
[ 0 -1  1]
[ 1 -2  1]
>>> V
[ 0  0  1]
[-1  2 -2]
[ 1 -1  1]
>>> U*A*V
[1 0 0]
[0 3 0]
[0 0 0]

Sage Live

A = MatrixSpace(IntegerRing(), 3)(range(9))
D, U, V = A.smith_form()
D
U
V
U*A*V

It also makes sense for nonsquare matrices:

Sage

sage: A = Matrix(ZZ,3,2,range(6))
sage: D, U, V = A.smith_form()
sage: D
[1 0]
[0 2]
[0 0]
sage: U
[ 0  2 -1]
[ 0 -1  1]
[ 1 -2  1]
sage: V
[-1  1]
[ 1  0]
sage: U * A * V
[1 0]
[0 2]
[0 0]

Python

>>> from sage.all import *
>>> A = Matrix(ZZ,Integer(3),Integer(2),range(Integer(6)))
>>> D, U, V = A.smith_form()
>>> D
[1 0]
[0 2]
[0 0]
>>> U
[ 0  2 -1]
[ 0 -1  1]
[ 1 -2  1]
>>> V
[-1  1]
[ 1  0]
>>> U * A * V
[1 0]
[0 2]
[0 0]

Sage Live

A = Matrix(ZZ,3,2,range(6))
D, U, V = A.smith_form()
D
U
V
U * A * V

Empty matrices are handled sensibly (see Issue #3068):

Sage

sage: m = MatrixSpace(ZZ, 2,0)(0); d,u,v = m.smith_form(); u*m*v == d
True
sage: m = MatrixSpace(ZZ, 0,2)(0); d,u,v = m.smith_form(); u*m*v == d
True
sage: m = MatrixSpace(ZZ, 0,0)(0); d,u,v = m.smith_form(); u*m*v == d
True

Python

>>> from sage.all import *
>>> m = MatrixSpace(ZZ, Integer(2),Integer(0))(Integer(0)); d,u,v = m.smith_form(); u*m*v == d
True
>>> m = MatrixSpace(ZZ, Integer(0),Integer(2))(Integer(0)); d,u,v = m.smith_form(); u*m*v == d
True
>>> m = MatrixSpace(ZZ, Integer(0),Integer(0))(Integer(0)); d,u,v = m.smith_form(); u*m*v == d
True

Sage Live

m = MatrixSpace(ZZ, 2,0)(0); d,u,v = m.smith_form(); u*m*v == d
m = MatrixSpace(ZZ, 0,2)(0); d,u,v = m.smith_form(); u*m*v == d
m = MatrixSpace(ZZ, 0,0)(0); d,u,v = m.smith_form(); u*m*v == d

See also

elementary_divisors()

symplectic_form()[source]¶

Find a symplectic basis for self if self is an anti-symmetric, alternating matrix.

Return a pair (F, C) such that the rows of C form a symplectic basis for self and F = C * self * C.transpose().

Raise a ValueError if self is not anti-symmetric, or self is not alternating.

Anti-symmetric means that \(M = -M^t\). Alternating means that the diagonal of \(M\) is identically zero.

A symplectic basis is a basis of the form \(e_1, \ldots, e_j, f_1, \ldots f_j, z_1, \dots, z_k\) such that

\(z_i M v^t = 0\) for all vectors \(v\)
\(e_i M {e_j}^t = 0\) for all \(i, j\)
\(f_i M {f_j}^t = 0\) for all \(i, j\)
\(e_i M {f_i}^t = 1\) for all \(i\)
\(e_i M {f_j}^t = 0\) for all \(i\) not equal
\(j\).

The ordering for the factors \(d_{i} | d_{i+1}\) and for the placement of zeroes was chosen to agree with the output of smith_form().

See the example for a pictorial description of such a basis.

EXAMPLES:

Sage

sage: E = matrix(ZZ, 5, 5, [0, 14, 0, -8, -2, -14, 0, -3, -11, 4, 0, 3, 0, 0, 0, 8, 11, 0, 0, 8, 2, -4, 0, -8, 0]); E
[  0  14   0  -8  -2]
[-14   0  -3 -11   4]
[  0   3   0   0   0]
[  8  11   0   0   8]
[  2  -4   0  -8   0]
sage: F, C = E.symplectic_form()
sage: F
[ 0  0  1  0  0]
[ 0  0  0  2  0]
[-1  0  0  0  0]
[ 0 -2  0  0  0]
[ 0  0  0  0  0]
sage: F == C * E * C.transpose()
True
sage: E.smith_form()[0]
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 2 0 0]
[0 0 0 2 0]
[0 0 0 0 0]

Python

>>> from sage.all import *
>>> E = matrix(ZZ, Integer(5), Integer(5), [Integer(0), Integer(14), Integer(0), -Integer(8), -Integer(2), -Integer(14), Integer(0), -Integer(3), -Integer(11), Integer(4), Integer(0), Integer(3), Integer(0), Integer(0), Integer(0), Integer(8), Integer(11), Integer(0), Integer(0), Integer(8), Integer(2), -Integer(4), Integer(0), -Integer(8), Integer(0)]); E
[  0  14   0  -8  -2]
[-14   0  -3 -11   4]
[  0   3   0   0   0]
[  8  11   0   0   8]
[  2  -4   0  -8   0]
>>> F, C = E.symplectic_form()
>>> F
[ 0  0  1  0  0]
[ 0  0  0  2  0]
[-1  0  0  0  0]
[ 0 -2  0  0  0]
[ 0  0  0  0  0]
>>> F == C * E * C.transpose()
True
>>> E.smith_form()[Integer(0)]
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 2 0 0]
[0 0 0 2 0]
[0 0 0 0 0]

Sage Live

E = matrix(ZZ, 5, 5, [0, 14, 0, -8, -2, -14, 0, -3, -11, 4, 0, 3, 0, 0, 0, 8, 11, 0, 0, 8, 2, -4, 0, -8, 0]); E
F, C = E.symplectic_form()
F
F == C * E * C.transpose()
E.smith_form()[0]

transpose()[source]¶

Return the transpose of self, without changing self.

EXAMPLES:

We create a matrix, compute its transpose, and note that the original matrix is not changed.

Sage

sage: A = matrix(ZZ, 2, 3, range(6))
sage: type(A)
<class 'sage.matrix.matrix_integer_dense.Matrix_integer_dense'>
sage: B = A.transpose()
sage: print(B)
[0 3]
[1 4]
[2 5]
sage: print(A)
[0 1 2]
[3 4 5]

Python

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(2), Integer(3), range(Integer(6)))
>>> type(A)
<class 'sage.matrix.matrix_integer_dense.Matrix_integer_dense'>
>>> B = A.transpose()
>>> print(B)
[0 3]
[1 4]
[2 5]
>>> print(A)
[0 1 2]
[3 4 5]

Sage Live

A = matrix(ZZ, 2, 3, range(6))
type(A)
B = A.transpose()
print(B)
print(A)

.T is a convenient shortcut for the transpose:

Sage

sage: A.T
[0 3]
[1 4]
[2 5]

Python

>>> from sage.all import *
>>> A.T
[0 3]
[1 4]
[2 5]

Sage Live

A.T

Sage

sage: A.subdivide(None, 1); A
[0|1 2]
[3|4 5]
sage: A.transpose()
[0 3]
[---]
[1 4]
[2 5]

Python

>>> from sage.all import *
>>> A.subdivide(None, Integer(1)); A
[0|1 2]
[3|4 5]
>>> A.transpose()
[0 3]
[---]
[1 4]
[2 5]

Sage Live

A.subdivide(None, 1); A
A.transpose()

Python

>>> from sage.all import *
>>> A.subdivide(None, Integer(1)); A
[0|1 2]
[3|4 5]
>>> A.transpose()
[0 3]
[---]
[1 4]
[2 5]

Sage Live

A.subdivide(None, 1); A
A.transpose()