18.2 Matrices

Module: sage.matrix.matrix

Elements of matrix spaces are of class Matrix. They can be either sparse or dense, and can be defined over any base ring.

We create the $ 2\times 3$ matrix

$\displaystyle \left(\begin{matrix}1&2&3 4&5&6 \end{matrix}\right)
$

as an element of a matrix space over $ \mathbf{Q}$ :

sage: M = MatrixSpace(RationalField(),2,3)
sage: A = M([1,2,3, 4,5,6])
sage: A
[1 2 3]
[4 5 6]
sage: A.parent()
Full MatrixSpace of 2 by 3 dense matrices over Rational Field

We next change the top-right entry of $ A$ . Note that matrix indexing is 0 -based in SAGE, so the top right entry is $ (0,2)$ , which should be thought of as ``row number 0 , column number 2''.

sage: A[0,2] = 389
sage: A
[  1   2 389]
[  4   5   6]

Also notice how matrices print. All columns have the same width and entries in a given column are right justified. Next we compute the reduced row echelon form of $ A$ .

sage: A.echelon_form()
[      1       0 -1933/3]
[      0       1  1550/3]

MUTABILITY: Matrices are either immutable or not. When initially created, matrices are typically mutable, so one can change their entries. However, nothing about mutable matrices is cached. Once a matrix $ A$ is made immutable using A.set_immutable() the entries of $ A$ cannot be changed. However, properies of $ A$ such as its rank, characteristic polynomial, etc., are all cached so computations involving $ A$ may be more efficient. Once $ A$ is made immutable it cannot be changed back. However, one can obtain a mutable copy of $ A$ using A.copy().

The echelon form method always returns immutable matrices with known rank.

Module-level Functions

_combinations( sequence, number)

Generate all combinations of number elements from list sequence.

Based on code from test/test_generators.py.

Author: Jaap Spies (2006-02-18)

_convert_dense_entries_to_list( entries)

_convert_sparse_entries_to_dict( entries)

_parimatrix_to_reversed_strlist( A)

_parimatrix_to_strlist( A)

_sparse_dot_product( v, w)

v and w are dictionaries with integer keys.

is_Matrix( x)

Class: Matrix

class Matrix
The Matrix class is the base class for all matrix classes. To create a Matrix, first create a MatrixSpace, then coerce a list of elements into the MatrixSpace. See the documentation of MatrixSpace for more details.
Matrix( self, parent)

sage: import sage.matrix.matrix
sage: A = sage.matrix.matrix.Matrix(MatrixSpace(QQ,2))
sage: type(A)
<class 'sage.matrix.matrix.Matrix'>

Functions: act_on_polynomial,$  $ add_multiple_of_column,$  $ add_multiple_of_row,$  $ adjoint,$  $ augment,$  $ block_sum,$  $ change_ring,$  $ characteristic_polynomial,$  $ column,$  $ columns,$  $ commutator,$  $ copy,$  $ dense_matrix,$  $ dense_row,$  $ det,$  $ determinant,$  $ get,$  $ is_dense,$  $ is_sparse,$  $ is_square,$  $ iterates,$  $ lift,$  $ linear_combination_of_columns,$  $ linear_combination_of_rows,$  $ list,$  $ lllgram,$  $ matrix_from_columns,$  $ matrix_from_rows,$  $ matrix_from_rows_and_columns,$  $ matrix_space,$  $ minimal_polynomial,$  $ Mod,$  $ ncols,$  $ new_matrix,$  $ nonpivots,$  $ nonzero_positions,$  $ nonzero_positions_in_column,$  $ nonzero_positions_in_row,$  $ nrows,$  $ per,$  $ permanent,$  $ permanental_minor,$  $ prod_of_row_sums,$  $ rescale_row,$  $ rook_vector,$  $ row,$  $ rows,$  $ set,$  $ set_row_to_multiple_of_row,$  $ sparse_columns,$  $ sparse_matrix,$  $ sparse_rows,$  $ stack,$  $ swap_columns,$  $ swap_rows,$  $ trace,$  $ vector_matrix_multiply

act_on_polynomial( self, f)

Returns the polynomial f(self*x).

INPUT:
    self -- an nxn matrix
    f -- a polynomial in n variables x=(x1,...,xn)

OUTPUT:
    The polynomial f(self*x).

sage: R = MPolynomialRing(RationalField(), 2, ['x','y'])
sage: x, y = R.gens()
sage: f = x**2 - y**2
sage: M = MatrixSpace(RationalField(),2)
sage: A = M([1,2,3,4])
sage: A.act_on_polynomial(f)
-12*y^2 - 20*x*y - 8*x^2

add_multiple_of_column( self, i, j, s)

Replace column i by s times column j.

add_multiple_of_row( self, i, j, s)

Replace row i by s times row j.

adjoint( self)

Returns the adjoint matrix of self (matrix of cofactors).

INPUT:
    M -- a square matrix

OUTPUT:
    N -- the adjoint matrix, such that

N * M = M * N = M.parent(M.det())

ALGORITHM: Use PARI

sage: M = Matrix(ZZ,2,2,[5,2,3,4]) ; M
[5 2]
[3 4]
sage: N = M.adjoint() ; N
[ 4 -2]
[-3  5]
sage: M * N
[14  0]
[ 0 14]
sage: N * M
[14  0]
[ 0 14]
sage: M = Matrix(QQ,2,2,[5/3,2/56,33/13,41/10]) ; M
[  5/3  1/28]
[33/13 41/10]
sage: N = M.adjoint() ; N
[ 41/10  -1/28]
[-33/13    5/3]
sage: M * N
[7363/1092         0]
[        0 7363/1092]

BUGS: only implemented for matrices over ZZ or QQ PARI can deal with more general base rings

augment( self, other)

Return the augmented matrix of the form [self | other].

sage: M = MatrixSpace(RationalField(),2,2)
sage: A = M([1,2, 3,4])
sage: A
[1 2]
[3 4]
sage: N = MatrixSpace(RationalField(),2,1)
sage: B = N([9,8])
sage: B
[9]
[8]
sage: A.augment(B)
[1 2 9]
[3 4 8]
sage: B.augment(A)
[9 1 2]
[8 3 4]
sage: M = MatrixSpace(RationalField(),3,4)
sage: A = M([1,2,3,4, 0,9,8,7, 2/3,3/4,4/5,9/8])
sage: A
[  1   2   3   4]
[  0   9   8   7]
[2/3 3/4 4/5 9/8]
sage: N = MatrixSpace(RationalField(),3,2)
sage: B = N([1,2, 3,4, 4,5])
sage: B
[1 2]
[3 4]
[4 5]
sage: A.augment(B)
[  1   2   3   4   1   2]
[  0   9   8   7   3   4]
[2/3 3/4 4/5 9/8   4   5]
sage: B.augment(A)
[  1   2   1   2   3   4]
[  3   4   0   9   8   7]
[  4   5 2/3 3/4 4/5 9/8]

Author: Naqi Jaffery (2006-01-24): examples

block_sum( self, other)

Return the block matrix that has self and other on the diagonal: [self | 0 ] [ 0 | other ]

change_ring( self, ring)

Return the matrix obtained by coercing the entries of this matrix into the given ring.

characteristic_polynomial( self)

Synonym for self.charpoly(...).

column( self, i)

Return the i-th column of this matrix.

columns( self)

Returns the list of columns of self, as vectors.

sage: A = MatrixSpace(RationalField(), 2,3) (xrange(6))
sage: A
[0 1 2]
[3 4 5]
sage: A.columns()
[(0, 3), (1, 4), (2, 5)]

commutator( self, other)

Return the commutator self*other - other*self.

copy( self)

Return a copy of this matrix. Changing the entries of the copy will not change the entries of this matrix.

dense_matrix( self)

If this matrix is sparse, return a dense matrix with the same entries. If this matrix is dense, return this matrix (not a copy).

NOTE: The definition of"dense" and "sparse" in SAGE have nothing to do with the number of nonzero entries. Sparse and dense are properties of the underlying representation of the matrix.

sage: A = MatrixSpace(RationalField(),2, sparse=True)([1,2,0,1])
sage: A.is_sparse()
True
sage: B = A.dense_matrix()
sage: B.is_sparse()
False
sage: A*B
[1 4]
[0 1]
sage: A.parent()
Full MatrixSpace of 2 by 2 sparse matrices over Rational Field
sage: B.parent()
Full MatrixSpace of 2 by 2 dense matrices over Rational Field
sage: (A*B).parent()
Full MatrixSpace of 2 by 2 sparse matrices over Rational Field
sage: (B*A).parent()
Full MatrixSpace of 2 by 2 dense matrices over Rational Field

det( self)

Synonym for self.determinant(...).

sage: A = MatrixSpace(Integers(8),3)([1,7,3, 1,1,1, 3,4,5])
sage: A.det()
6

determinant( self)

Return the determinant of self.

ALGORITHM: This is computed using a naive generic algorithm. For matrices over more most rings more sophisticated algorithms can be used. (Type A.determinant? to see what is done for a specific matrix A.) If you're actually using the algorithm below, you should probably clamor for something better to be implemented for your base ring.

sage: A = MatrixSpace(Integers(8),3)([1,7,3, 1,1,1, 3,4,5])
sage: A.determinant()
6
sage: A.determinant() is A.determinant()
False
sage: A.set_immutable()
sage: A.determinant() is A.determinant()
True

get( self, ij)

Entry access, but potentially faster since it might be without bounds checking.

INPUT:
    ij -- tuple (i,j) with i, j ints

sage: A = Matrix(Integers(2006),2,2,[-1,2,3,4])
sage: A.get(0,1)
Traceback (most recent call last):
...
TypeError: get() takes exactly 2 arguments (3 given)
sage: A.get((0,1))
2

iterates( self, v, n)

Let $ A$ be this matrix and $ v$ be a free module element. Return a vector whose rows are the entries of the following vectors:

$\displaystyle v, v A, v A^2, \ldots, v A^{n-1}.
$

INPUT:
    v -- free module element
    n -- nonnegative integer

sage: A = MatrixSpace(IntegerRing(), 2)([1,1,3,5]); A
[1 1]
[3 5]
sage: v = FreeModule(IntegerRing(), 2)([1,0])
sage: A.iterates(v,0)
[]
sage: A.iterates(v,5)
[  1   0]
[  1   1]
[  4   6]
[ 22  34]
[124 192]

lift( self)

sage: M = Matrix(ZZ/7, 2, 2, [5, 9, 13, 15]) ; M
[5 2]
[6 1]
sage: M.lift()
[5 2]
[6 1]
sage: parent(M.lift())
Full MatrixSpace of 2 by 2 dense matrices over Integer Ring

lllgram( self)

LLL reduction of the lattice whose gram matrix is self.

INPUT:
    M -- gram matrix of a definite quadratic form

OUTPUT:
    U -- unimodular transformation matrix such that

U.transpose() * M * U

is LLL-reduced

ALGORITHM: Use PARI

sage: M = Matrix(ZZ, 2, 2, [-5,3,3,-2]) ; M
[-5  3]
[ 3 -2]
sage: U = M.lllgram() ; U
[1 1]
[1 2]
sage: U.transpose() * M * U
[-1  0]
[ 0 -1]
sage: M = Matrix(QQ,2,2,[269468, -199019/2, -199019/2, 36747]) ; M
[   269468 -199019/2]
[-199019/2     36747]
sage: U = M.lllgram() ; U
[-113  -24]
[-306  -65]
sage: U.transpose() * M * U
[  2 1/2]
[1/2   3]

Semidefinite and indefinite forms raise a ValueError:

sage: Matrix(ZZ,2,2,[2,6,6,3]).lllgram()
Traceback (most recent call last):
...
ValueError: not a definite matrix
sage: Matrix(ZZ,2,2,[1,0,0,-1]).lllgram()
Traceback (most recent call last):
...
ValueError: not a definite matrix

BUGS: should work for semidefinite forms (PARI is ok)

matrix_from_columns( self, columns)

Return the matrix constructed from self using columns with indices in the columns list.

sage: M = MatrixSpace(Integers(8),3,3)
sage: A = M(range(9)); A
[0 1 2]
[3 4 5]
[6 7 0]
sage: A.matrix_from_columns([2,1])
[2 1]
[5 4]
[0 7]

matrix_from_rows( self, rows)

Return the matrix constructed from self using rows with indices in the rows list.

sage: M = MatrixSpace(Integers(8),3,3)
sage: A = M(range(9)); A
[0 1 2]
[3 4 5]
[6 7 0]
sage: A.matrix_from_rows([2,1])
[6 7 0]
[3 4 5]

matrix_from_rows_and_columns( self, rows, columns)

Return the matrix constructed from self from the given rows and columns.

sage: M = MatrixSpace(Integers(8),3,3)
sage: A = M(range(9)); A
[0 1 2]
[3 4 5]
[6 7 0]
sage: A.matrix_from_rows_and_columns([1], [0,2])
[3 5]
sage: A.matrix_from_rows_and_columns([1,2], [1,2])
[4 5]
[7 0]

Note that row and column indices can be reordered or repeated:

sage: A.matrix_from_rows_and_columns([2,1], [2,1])
[0 7]
[5 4]

For example here we take from row 1 columns 2 then 0 twice, and do this 3 times.

sage: A.matrix_from_rows_and_columns([1,1,1],[2,0,0])
[5 3 3]
[5 3 3]
[5 3 3]

Author: Jaap Spies (2006-02-18)

minimal_polynomial( self)

Synonym for self.charpoly(...).

Mod( self, p)

sage: M = Matrix(ZZ, 2, 2, [5, 9, 13, 15])
sage: M.Mod(7)
[5 2]
[6 1]
sage: parent(M.Mod(7))
Full MatrixSpace of 2 by 2 dense matrices over Ring of integers modulo 7

ncols( self)

Return the number of rows of this matrix.

sage: M = MatrixSpace(QQ, 2, 3)
sage: A = M([1,2,3, 4,5,6])
sage: A
[1 2 3]
[4 5 6]
sage: A.ncols()
3
sage: A.nrows()
2

Author: Naqi Jaffery (2006-01-24): examples

new_matrix( self, [nrows=None], [ncols=True], [entries=True], [coerce_entries=0], [copy=None], [sparse=None])

Create a matrix in the parent of this space with the given number of rows, columns, etc.

WARNING: This function called with no arguments returns the 0 matrix by default, not the matrix self.

nonpivots( self)

Return the list of i such that the i-th column of self is NOT a pivot column of the reduced row echelon form of self.

OUTPUT: list - sorted list of integers

nonzero_positions( self)

Returns the set of pairs (i,j) such that self[i,j] != 0.

nonzero_positions_in_column( self, i)

Return the integers j such that self[j,i] is nonzero, i.e., such that the j-th position of the i-th column is nonzero.

nonzero_positions_in_row( self, i)

Return the integers j such that self[i,j] is nonzero, i.e., such that the j-th position of the i-th row is nonzero.

nrows( self)

Return the number of rows of this matrix.

sage: M = MatrixSpace(RationalField(),6,7)
sage: A = M([1,2,3,4,5,6,7, 22,3/4,34,11,7,5,3, 99,65,1/2,2/3,3/5,4/5,5/6, 9,8/9, 9/8,7/6,6/7,76,4, 0,9,8,7,6,5,4, 123,99,91,28,6,1024,1])
sage: A
[   1    2    3    4    5    6    7]
[  22  3/4   34   11    7    5    3]
[  99   65  1/2  2/3  3/5  4/5  5/6]
[   9  8/9  9/8  7/6  6/7   76    4]
[   0    9    8    7    6    5    4]
[ 123   99   91   28    6 1024    1]
sage: A.ncols()
7
sage: A.nrows()
6

Author: Naqi Jaffery (2006-01-24): examples

per( self)

Synonym for self.permanent(...).

sage: A = MatrixSpace(Integers(8),3)([1,7,3, 1,1,1, 3,4,5])
sage: A.per()
6

permanent( self)

Calculate and return the permanent of this $ m \times n$ matrix using Ryser's algorithm.

Let $ A = (a_{i,j})$ be an $ m \times n$ matrix over any commutative ring, with $ m \le n$ . The permanent of $ A$ is

   per$\displaystyle (A) = \sum_\pi a_{1,\pi(1)}a_{2,\pi(2)} \cdots a_{m pi(m)}
$

where the summation extends over all one-to-one functions $ \pi$ from $ \{1, \ldots, m\}$ to $ \{1, \ldots, n\}$ .

The product $ a_{1,\pi(1)}a_{2,\pi(2)} \cdots a_{m,\pi(m)}$ is called diagonal product. So the permanent of an $ m \times n$ matrix $ A$ is the sum of all the diagonal products of $ A$ .

Modification of theorem 7.1.1. from Brualdi and Ryser: Combinatorial Matrix Theory. Instead of deleting columns from $ A$ , we choose columns from $ A$ and calculate the product of the row sums of the selected submatrix.

INPUT:
    A -- matrix of size m x n with m <= n 

OUTPUT:
    permanent of matrix A

sage: M = MatrixSpace(ZZ,4,4)
sage: A = M([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1])
sage: A.permanent()
24

sage: M = MatrixSpace(QQ,3,6)
sage: A = M([1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1])
sage: A.permanent()
36

sage: M = MatrixSpace(RR,3,6)
sage: A = M([1.0,1.0,1.0,1.0,0,0,0,1.0,1.0,1.0,1.0,0,0,0,1.0,1.0,1.0,1.0])
sage: A.permanent()
36.000000000000000

See Sloane's sequence OEIS A079908(3) = 36, "The Dancing School Problems"

sage: print sloane_sequence(79908)                # optional (internet connection)
Searching Sloane's online database...
[79908, 'Solution to the Dancing School Problem with 3 girls: f(3,n).', [1,
4, 14, 36, 76, 140, 234, 364, 536, 756, 1030, 1364, 1764, 2236, 2786, 3420,
4144, 4964, 5886, 6916, 8060, 9324, 10714, 12236, 13896, 15700, 17654,
19764, 22036, 24476, 27090, 29884, 32864, 36036, 39406, 42980, 46764,
50764, 54986, 59436]]

sage: M = MatrixSpace(ZZ,4,5)
sage: A = M([1,1,0,1,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0])
sage: A.permanent()
32

See Minc: Permanents, Example 2.1, p. 5.

sage: M = MatrixSpace(QQ,2,2)
sage: A = M([1/5,2/7,3/2,4/5])
sage: A.permanent()
103/175

sage: R = PolynomialRing(IntegerRing(),'a'); a = R.gen()
sage: A = MatrixSpace(R,2)([[a,1], [a,a+1]])
sage: A.permanent()
a^2 + 2*a

sage: R = MPolynomialRing(IntegerRing(),2); x,y = R.gens()
sage: A = MatrixSpace(R,2)([x, y, x^2, y^2])
sage: A.permanent()
x0*x1^2 + x0^2*x1

Author Log:

permanental_minor( self, k)

Calculates the permanental $ k$ -minor of a $ m \times n$ matrix.

This is the sum of the permanents of all possible $ k$ by $ k$ submatices of $ A$ .

See Brualdi and Ryser: Combinatorial Matrix Theory, p. 203. Note the typo $ p_0(A) = 0$ in that reference! For applications see Theorem 7.2.1 and Theorem 7.2.4.

Note that the permanental $ m$ -minor equals $ per(A)$ .

For a (0,1)-matrix $ A$ the permanental $ k$ -minor counts the number of different selections of $ k$ 1's of $ A$ with no two of the 1's on the same line.

INPUT:
    self -- matrix of size m x n with m <= n 

OUTPUT:
    permanental k-minor of matrix A

sage: M = MatrixSpace(ZZ,4,4)
sage: A = M([1,0,1,0,1,0,1,0,1,0,10,10,1,0,1,1])
sage: A.permanental_minor(2)
114

sage: M = MatrixSpace(ZZ,3,6)
sage: A = M([1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1])
sage: A.permanental_minor(0)
1
sage: A.permanental_minor(1)
12
sage: A.permanental_minor(2)
40
sage: A.permanental_minor(3)
36

Note that if k == m the permanental k-minor equals per(A)

sage: A.permanent()
36

sage: A.permanental_minor(5)
0

For C the "complement" of A:

sage: M = MatrixSpace(ZZ,3,6)
sage: C = M([0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0])
sage: m, n = 3, 6
sage: sum([(-1)^k * C.permanental_minor(k)*factorial(n-k)/factorial(n-m) for k in range(m+1)])
36

See Theorem 7.2.1 of Brualdi: and Ryser: Combinatorial Matrix Theory: per(A)

Author: Jaap Spies (2006-02-19)

prod_of_row_sums( self, cols)

Calculate the product of all row sums of a submatrix of $ A$ for a list of selected columns cols.

Author: Jaap Spies (2006-02-18)

rescale_row( self, i, s)

Replace i-th row of self by s times i-th row of self.

rook_vector( self, [check=False])

Returns rook vector of this matrix.

Let $ A$ be a general $ m$ by $ n$ (0,1)-matrix with $ m \le n$ . We identify $ A$ with a chessboard where rooks can be placed on the fields corresponding with $ a_{ij} = 1$ . The number $ r_k =
p_k(A)$ (the permanental $ k$ -minor) counts the number of ways to place $ k$ rooks on this board so that no two rooks can attack another.

The rook vector is the list consisting of $ r_0, r_1, \ldots, r_m$ .

The rook polynomial is defined by $ r(x) = \sum_{k=0}^m r_k x^k$ .

INPUT:
    self -- m by n matrix with m <= n 
    check -- True or False (default), optional

OUTPUT:
    rook vector

sage: M = MatrixSpace(ZZ,3,6)
sage: A = M([1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1])
sage: A.rook_vector()
[1, 12, 40, 36]

sage: x = PolynomialRing(IntegerRing(),'x').gen()
sage: rv = A.rook_vector()
sage: rook_polynomial = sum([rv[k] * x^k for k in range(len(rv))])
sage: rook_polynomial
36*x^3 + 40*x^2 + 12*x + 1

Author: Jaap Spies (2006-02-24)

row( self, i)

Return the i-th row of this matrix.

rows( self)

Return a list of the rows of this matrix.

set( self, ij, x)

Set entry, but potentially faster because it might be without bounds checking.

INPUT:
    ij -- tuple (i,j) with i, j ints
    x -- object

sage: A = Matrix(Integers(2006),2,2,[-1,2,3,4])
sage: A.set(0, 1, 5)
Traceback (most recent call last):
...
TypeError: set() takes exactly 3 arguments (4 given)
sage: A.set((0,1), 5)
sage: A
[2005    5]
[   3    4]

set_row_to_multiple_of_row( self, i, j, s)

Set row i equal to s times row j.

sparse_matrix( self)

If this matrix is dense, return a sparse matrix with the same entries. If this matrix is sparse, return this matrix (not a copy).

NOTE: The definition of "dense" and "sparse" in SAGE have nothing to do with the number of nonzero entries. Sparse and dense are properties of the underlying representation of the matrix.

sage: A = MatrixSpace(RationalField(),2, sparse=False)([1,2,0,1])
sage: A.is_sparse()
False
sage: B = A.sparse_matrix()
sage: B.is_sparse()
True
sage: A
[1 2]
[0 1]
sage: B
[1 2]
[0 1]
sage: A*B
[1 4]
[0 1]
sage: A.parent()
Full MatrixSpace of 2 by 2 dense matrices over Rational Field
sage: B.parent()
Full MatrixSpace of 2 by 2 sparse matrices over Rational Field
sage: (A*B).parent()
Full MatrixSpace of 2 by 2 dense matrices over Rational Field
sage: (B*A).parent()
Full MatrixSpace of 2 by 2 sparse matrices over Rational Field

stack( self, other)

Return the augmented matrix self on top of other: [ self ] [ other ]

sage: M = Matrix(RationalField(), 2, 3, range(6))
sage: N = Matrix(RationalField(), 1, 3, [10,11,12])
sage: M.stack(N)
[ 0  1  2]
[ 3  4  5]
[10 11 12]

swap_columns( self, c1, c2)

Swap columns c1 and c2 of self.

sage: M = MatrixSpace(QQ,3,3)
sage: A = M([1,9,-7,4/5,4,3,6,4,3])
sage: A
[  1   9  -7]
[4/5   4   3]
[  6   4   3]
sage: A.swap_columns(1,2); A
[  1  -7   9]
[4/5   3   4]
[  6   3   4]

swap_rows( self, r1, r2)

Swap rows r1 and r2 of self.

sage: M = MatrixSpace(QQ,3,3)
sage: A = M([1,9,-7,4/5,4,3,6,4,3])
sage: A
[  1   9  -7]
[4/5   4   3]
[  6   4   3]
sage: A.swap_rows(0,2); A
[  6   4   3]
[4/5   4   3]
[  1   9  -7]

trace( self)

Return the trace of self, which is the sum of the diagonal entries of self.

INPUT:
    self -- a square matrix
OUTPUT:
    element of the base ring of self

vector_matrix_multiply( self, v)

Returns the vector times matrix product.

INPUT:
     v -- a free module element.

OUTPUT:
    The the vector times matrix product v*A.

sage: MS = MatrixSpace(RationalField(), 2,2)
sage: B = MS.matrix([1,2,1,2])
sage: V = VectorSpace(RationalField(), 2)
sage: v = V([1,2])
sage: B.vector_matrix_multiply(v)     # computes v*B
(3, 6)
sage: Bt = B.transpose()
sage: Bt.vector_matrix_multiply(v)    # computes B*v
(5, 5)

Special Functions: __abs__,$  $ __cmp__,$  $ __getitem__,$  $ __mod__,$  $ __mul__,$  $ __neg__,$  $ __pos__,$  $ __pow__,$  $ __repr__,$  $ __rmul__,$  $ __setitem__,$  $ __str__,$  $ _add_,$  $ _dict,$  $ _div_,$  $ _entries,$  $ _gap_init_,$  $ _latex_,$  $ _latex_sparse,$  $ _magma_init_,$  $ _matrix_,$  $ _Matrix__is_compatible,$  $ _pari_init_,$  $ _right_scalar_multiply,$  $ _scalar_multiply,$  $ _set_row_to_negative_of_row_of_A_using_subset_of_columns,$  $ _sub_

__getitem__( self, ij)

Return element or row of self.

INPUT:
    ij -- tuple (i,j) with i, j ints
or
    ij -- int

USAGE: A[i, j] - the i,j of A, and A[i] - the i-th row of A.

sage: A = Matrix(Integers(2006),2,2,[-1,2,3,4])
sage: A[0,0]
2005
sage: A[0]
(2005, 2)

__mod__( self, p)

Return matrix mod $ p$ , returning again a matrix over the same base ring.

Note: Use A.Mod(p) to obtain a matrix over the residue class ring modulo $ p$ .

sage: M = Matrix(ZZ, 2, 2, [5, 9, 13, 15])
sage: M % 7
[5 2]
[6 1]
sage: parent(M % 7)
Full MatrixSpace of 2 by 2 dense matrices over Integer Ring

__pow__( self, n)

sage: MS = MatrixSpace(RationalField(), 3, 3)
sage: A = MS([0, 0, 1, 1, 0, '-2/11', 0, 1, '-3/11'])
sage: A * A**(-1) == 1
True
sage: A**4
[      -3/11     -13/121   1436/1331]
[    127/121   -337/1331 -4445/14641]
[    -13/121   1436/1331 -8015/14641]

__setitem__( self, ij, x)

INPUT:
    ij -- tuple
    x -- object

USAGE: A[i, j] = x - set the (i,j) entry of A A[i] = x - set the ith row of A

sage: A = Matrix(Integers(2006),2,2,[-1,2,3,4]); A
[2005    2]
[   3    4]
sage: A[0,0] = 5; A
[5 2]
[3 4]
sage: A[0] = [2,3]
sage: A
[2 3]
[3 4]
sage: A.set_immutable()
sage: A[0,0] = 7
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.

_entries( self)

This must be defined in the derived class. It is the underlying representation of elements, which may be a list or dict or something else.

_gap_init_( self)

sage: A = MatrixSpace(QQ,3)([1,2,3,4/3,5/3,6/4,7,8,9])
sage: g = gap(A); g
[ [ 1, 2, 3 ], [ 4/3, 5/3, 3/2 ], [ 7, 8, 9 ] ]
sage: g.IsMatrix()
true

_latex_sparse( self, [variable=x])

Return a latex string that represents this matrix as a sparse matrix. The rows are printed as sums sum a_i x_i, where x is the variable.

_magma_init_( self)

We first coerce a square matrix.

sage: A = MatrixSpace(QQ,3)([1,2,3,4/3,5/3,6/4,7,8,9])
sage: B = magma(A); B                       # optional
[  1   2   3]
[4/3 5/3 3/2]
[  7   8   9]
sage: B.Type()                              # optional
AlgMatElt
sage: B.Parent()                            # optional
Full Matrix Algebra of degree 3 over Rational Field

We coerce a non-square matrix over $ \mathbf{Z}/8\mathbf{Z}$ .

sage: A = MatrixSpace(Integers(8),2,3)([-1,2,3,4,4,-2])   
sage: B = magma(A); B                       # optional
[7 2 3]
[4 4 6]
sage: B.Type()                              # optional
ModMatRngElt
sage: B.Parent()                            # optional
Full RMatrixSpace of 2 by 3 matrices over IntegerRing(8)

Class: Matrix_dense_integer

class Matrix_dense_integer
Dense matrix over the integers.

This type is implemented mostly in Python using generic machinery, hence not very optimized.

Matrix_dense_integer( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Class: Matrix_dense_rational

class Matrix_dense_rational
The Matrix_dense_rational class derives from Matrix_field, and defines functionality for dense matrices over the field $ \mathbf{Q}$ of rational numbers.
Matrix_dense_rational( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Functions: charpoly,$  $ echelon_form,$  $ hessenberg_form,$  $ iterates,$  $ list,$  $ prod_of_row_sums,$  $ set_row_to_multiple_of_row,$  $ transpose

charpoly( self, [bound=None])

Return the characteristic polynomial of this matrix.

INPUT:
    bound -- integer

ALGORITHM: Use a multi-modular Hessenberg form algorithm. This multimodular algorithm works by first computing a bound B, then computing the characteristic polynomial (using Hessenberg form mod p) modulo enough primes so that their product is bigger than B. We then uses the Chinese Remainder Theorem to recover the characteristic polynomial. If the optional bound is specified, that bound is used for B instead of a potentially much worse general bound.

sage: A = Matrix(QQ, 4, 4, [0, 1, -1, 0, 0, 1, -1, 1, -1, 2, -2, 1, -1, 1, 0, -1])
sage: f = A.charpoly(); f
x^4 + 2*x^3 - x^2 - 2*x + 1
sage: f.factor()
(x^2 + x - 1)^2

Next we compute a charpoly using too low of a bound, and get an incorrect answer.

sage: A = 100*Matrix(QQ, 3, 3, range(9))
sage: A.charpoly(10)
x^3 - 1200*x^2 + 5348*x

Note that the incorrect answer is cached, but only with that bound:

sage: A.charpoly()         # gives correct answer
x^3 - 1200*x^2 - 180000*x
sage: A.charpoly(10)       # cached incorrect answer
x^3 - 1200*x^2 + 5348*x

echelon_form( self, [height_guess=True], [include_zero_rows=None])

Return the echelon form of this matrix over the rational numbers, computed using a multi-modular algorithm.

sage: A = MatrixSpace(QQ, 3)(range(9))
sage: A.echelon_form()
[ 1  0 -1]
[ 0  1  2]
[ 0  0  0]

hessenberg_form( self)

Return the Hessenberg form of this matrix.

sage: A = Matrix(QQ, 3, 3, range(9))
sage: A
[0 1 2]
[3 4 5]
[6 7 8]
sage: A.hessenberg_form()
[ 0  5  2]
[ 3 14  5]
[ 0 -5 -2]

iterates( self, v, n)

Let A be this matrix. Return a matrix with rows

$\displaystyle v, v*A, v*A^2, ..., v*A^(n-1).
$

list( self)

Return a list of all the elements of this matrix.

The elements of the list are the rows concatenated together.

sage: A = MatrixSpace(QQ,3)(range(9))
sage: v = A.list(); v 
[0, 1, 2, 3, 4, 5, 6, 7, 8]

The returned list is a copy, and can be safely modified without changing self.

sage: v[0] = 9999
sage: A
[0 1 2]
[3 4 5]
[6 7 8]

prod_of_row_sums( self, cols)

Calculate the product of all row sums of a submatrix of $ A$ for a list of selected columns cols.

This is done in C so very fast.

Author: William Stein 2006-03-05

set_row_to_multiple_of_row( self, i, j, s)

Set row i equal to s times row j.

sage: A = MatrixSpace(QQ,3)(range(9))
sage: A.set_row_to_multiple_of_row(0,1, 10)
sage: A
[30 40 50]
[ 3  4  5]
[ 6  7  8]

transpose( self)

Return the transpose of this matrix.

sage: A = MatrixSpace(QQ,3)(range(9))
sage: A.transpose()
[0 3 6]
[1 4 7]
[2 5 8]

Special Functions: __getitem__,$  $ __mul__,$  $ __setitem__,$  $ _dense_matrix_mpq_,$  $ _entries

__getitem__( self, ij)

Use A[i,j] to obtain the the $ (i,j)$ th entry of $ A$ , and A[i] to obtain the $ i$ -th row of $ A$ .

__setitem__( self, ij, x)

Use A[i,j]=x to set the $ (i,j)$ th entry of $ A$ to $ x$ , and A[i]=v to set the $ i$ th row of $ A$ to the entries of $ v$ .

_dense_matrix_mpq_( self)

Return underlying GMP-based matrix used to implement some functionality for this object. (Mainly for internal use.)

Class: Matrix_domain

class Matrix_domain
Matrix_domain( self, parent)

Functions: charpoly,$  $ determinant,$  $ is_invertible,$  $ matrix_over_field,$  $ numeric_array

charpoly( self)

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

ALGORITHM: Use self.matrix_over_field() to obtain the corresponding matrix over a field, then call the charpoly function on it.

First a matrix over $ \mathbf{Z}$ :

sage: A = MatrixSpace(IntegerRing(),2)( [[1,2], [3,4]] )
sage: f = A.charpoly()
sage: f
x^2 - 5*x - 2
sage: f.parent()
Univariate Polynomial Ring in x over Integer Ring

We compute the characteristic polynomial of a matrix over the polynomial ring $ \mathbf{Z}[a]$ :

sage: R = PolynomialRing(IntegerRing(),'a'); a = R.gen()
sage: M = MatrixSpace(R,2)([[a,1], [a,a+1]])
sage: M
[    a     1]
[    a a + 1]
sage: f = M.charpoly()
sage: f
x^2 + (-2*a - 1)*x + a^2
sage: f.parent()
Univariate Polynomial Ring in x over Univariate Polynomial Ring in a over
Integer Ring
sage: M.trace()
2*a + 1
sage: M.determinant()
a^2

We compute the characteristic polynomial of a matrix over the multi-variate polynomial ring $ \mathbf{Z}[x,y]$ :

sage: R = MPolynomialRing(IntegerRing(),2); x,y = R.gens()
sage: A = MatrixSpace(R,2)([x, y, x^2, y^2])
sage: f = A.charpoly()
sage: f
x^2 + (-1*x1^2 - x0)*x + x0*x1^2 - x0^2*x1

It's a little difficult to distinguish the variables. To fix this, we rename the indeterminate $ Z$ :

sage: f.parent().assign_names("Z")
sage: f
Z^2 + (-1*x1^2 - x0)*Z + x0*x1^2 - x0^2*x1

We can pass parameters in, which are passed on to the charpoly function for matrices over a field.

sage: A = 1000*MatrixSpace(ZZ,10)(range(100))
sage: A.charpoly(bound=2)
x^10 + 14707*x^9 - 21509*x^8
sage: A = 1000*MatrixSpace(ZZ,10)(range(100))
sage: A.charpoly()
x^10 - 495000*x^9 - 8250000000*x^8

determinant( self)

Return the determinant of this matrix.

INPUT:
    -- a square matrix

ALGORITHM: Find the characteristic polynomial and take its constant term (up to sign).

We create a matrix over $ \mathbf{Z}[x,y]$ and compute its determinant.

sage: R = MPolynomialRing(IntegerRing(),2); x,y = R.gens()
sage: A = MatrixSpace(R,2)([x, y, x**2, y**2])
sage: A.determinant()
x0*x1^2 - x0^2*x1

is_invertible( self)

Return True if this matrix is invertible.

The following matrix is invertible over $ \mathbf{Q}$ but not over $ \mathbf{Z}$ .

sage: A = MatrixSpace(IntegerRing(), 2)(range(4))
sage: A.is_invertible()
False
sage: A.matrix_over_field().is_invertible()
True

The inverse function is a constructor for matrices over the fraction field, so it can work even if A is not invertible.

sage: ~A   # inverse of A
[-3/2  1/2]
[   1    0]

The next matrix is invertible over $ \mathbf{Z}$ .

sage: A = MatrixSpace(IntegerRing(),2)([1,10,0,-1])
sage: A.is_invertible()
True
sage: ~A                # compute the inverse
[ 1 10]
[ 0 -1]

The following nontrivial matrix is invertible over $ \mathbf{Z}[x]$ .

sage: R = PolynomialRing(IntegerRing())
sage: x = R.gen()
sage: A = MatrixSpace(R,2)([1,x,0,-1])
sage: A.is_invertible()
True
sage: ~A
[ 1  x]
[ 0 -1]

matrix_over_field( self)

Return this matrix, but with entries viewed as elements of the fraction field of the base ring.

sage: A = MatrixSpace(IntegerRing(),2)([1,2,3,4])
sage: B = A.matrix_over_field()
sage: B
[1 2]
[3 4]
sage: B.parent()
Full MatrixSpace of 2 by 2 dense matrices over Rational Field

numeric_array( self, [typecode=None])

Return the Numeric array associated to this field, if possible, and Numeric is installed.

Special Functions: __invert__

__invert__( self)

Return this inverse of this matrix, as a matrix over the fraction field.

Raises a ZeroDivisionError if the matrix has zero determinant, and raises an ArithmeticError, if the inverse doesn't exist because the matrix is nonsquare.

sage: A = MatrixSpace(IntegerRing(), 2)([1,1,3,5])
sage: ~A
[ 5/2 -1/2]
[-3/2  1/2]

Even if the inverse lies in the base field, the result is still a matrix over the fraction field.

sage: I = MatrixSpace(IntegerRing(),2)( 1 )  # identity matrix
sage: ~I
[1 0]
[0 1]
sage: (~I).parent()
Full MatrixSpace of 2 by 2 dense matrices over Rational Field

Class: Matrix_field

class Matrix_field
Matrix_field( self, parent)

Functions: charpoly,$  $ column_space,$  $ decomposition_of_subspace,$  $ denominator,$  $ echelon_form,$  $ fcp,$  $ hessenberg_form,$  $ integer_kernel,$  $ is_invertible,$  $ kernel,$  $ maxspin,$  $ nullity,$  $ pivots,$  $ rank,$  $ restrict,$  $ restrict_domain,$  $ row_space,$  $ row_span,$  $ wiedemann

charpoly( self)

Return the characteristic polynomial of this matrix.

ALGORITHM: Compute the Hessenberg form of the matrix and read off the characteristic polynomial from that. The result is cached.

sage: A = MatrixSpace(RationalField(),3)(range(9))
sage: A.charpoly()
x^3 - 12*x^2 - 18*x
sage: A.trace()
12
sage: A.determinant()
0

column_space( self)

Return the vector space over the base ring spanned by the columns of this matrix.

sage: M = MatrixSpace(QQ,3,3)
sage: A = M([1,9,-7,4/5,4,3,6,4,3])        
sage: A.column_space()
Vector space of degree 3 and dimension 3 over Rational Field
Basis matrix:
[1 0 0]
[0 1 0]
[0 0 1]
sage: W = MatrixSpace(CC,2,2)
sage: B = W([1, 2+3*i,4+5*i,9]); B
[                       1.0000000000000000 2.0000000000000000 +
3.0000000000000000*I]
[4.0000000000000000 + 5.0000000000000000*I                       
9.0000000000000000]
sage: B.column_space()
Vector space of degree 2 and dimension 2 over Complex Field with 53 bits of
precision
Basis matrix:
[                                                       1.0000000000000000
0.00000000000000044408920985006262 + 0.00000000000000088817841970012523*I]
[                                                                        0 
0.99999999999999978 - 0.000000000000000055511151231257827*I]

decomposition_of_subspace( self, M, [is_diagonalizable=False])

Suppose the right action of self on M leaves M invariant. Return the decomposition of M as a list of pairs (W, is_irred) where is_irred is True if the charpoly of self acting on the factor W is irreducible.

denominator( self)

Return the least common multiple of the denominators of the elements of self.

If there is no denominator function for the base field, or no LCM function for the denominators, raise a TypeError.

sage: A = MatrixSpace(RationalField(),2)(['1/2', '1/3', '1/5', '1/7'])
sage: A.denominator()
210

Denominators are note defined for real numbers:

sage: A = MatrixSpace(RealField(),2)([1,2,3,4])
sage: A.denominator()
Traceback (most recent call last):
...
TypeError: denominator not defined for elements of the base ring

We can even compute the denominator of matrix over the fraction field of $ \mathbf{Z}[x]$ .

sage: K = FractionField(PolynomialRing(IntegerRing()))
sage: x = K.gen()
sage: A = MatrixSpace(K,2)([1/x, 2/(x+1), 1, 5/(x**3)])
sage: A.denominator()
x^4 + x^3

echelon_form( self, [include_zero_rows=True])

Returns the reduced row echelon form of self.

INPUT:
    matrix -- an element A of a MatrixSpace

OUTPUT:
    matrix -- The reduced row echelon form of A.
    Note that self is *not* changed by this command.

sage: MS = MatrixSpace(RationalField(),2,3)
sage: C = MS.matrix([1,2,3,4,5,6])
sage: C.rank()
2
sage: C.nullity()
1
sage: C.echelon_form()
[ 1  0 -1]
[ 0  1  2]

fcp( self)

Return the factorization of the characteristic polynomial of self.

sage: M = MatrixSpace(QQ,3,3)
sage: A = M([1,9,-7,4/5,4,3,6,4,3])
sage: A.fcp()
(x^3 - 8*x^2 + 209/5*x - 286)
sage: A = M([3, 0, -2, 0, -2, 0, 0, 0, 0])
sage: A.fcp()
(x - 3) * x * (x + 2)

hessenberg_form( self)

Return the Hessenberg form of self.

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.

ALGORITHM: See Henri Cohen's first book.

sage: A = MatrixSpace(RationalField(),3)([2, 1, 1, -2, 2, 2, -1, -1, -1])
sage: A.hessenberg_form()
[  2 3/2   1]
[ -2   3   2]
[  0  -3  -2]

sage: A = MatrixSpace(RationalField(),4)([2, 1, 1, -2, 2, 2, -1, -1, -1,1,2,3,4,5,6,7])
sage: A.hessenberg_form()
[    2  -7/2 -19/5    -2]
[    2   1/2 -17/5    -1]
[    0  25/4  15/2   5/2]
[    0     0  58/5     3]

integer_kernel( self)

Return the integral kernel of this matrix.

Assume that the base field of this matrix has a numerator and denominator functions for its elements, e.g., it is the rational numbers or a fraction field. This function computes a basis over the integers for the kernel of self.

When kernels are implemented for matrices over general PID's, this function will compute kernels over PID's of matrices over the fraction field of the PID. (todo)

sage: A = MatrixSpace(QQ, 4)(range(16))
sage: A.integer_kernel()
Free module of degree 4 and rank 2 over Integer Ring
Echelon basis matrix:
[ 1  0 -3  2]
[ 0  1 -2  1]

The integer kernel even makes sense for matrices with fractional entries:

sage: A = MatrixSpace(QQ, 2)(['1/2',0,  0, 0])
sage: A.integer_kernel()
Free module of degree 2 and rank 1 over Integer Ring
Echelon basis matrix:
[0 1]

is_invertible( self)

Return True if this matrix is invertible.

sage: M = MatrixSpace(QQ,3,3)
sage: A = M([1,9,-7,4/5,4,3,6,4,3])
sage: A.is_invertible()
True
sage: W = MatrixSpace(CC,2,2)
sage: B = W([1, 2+3*i, 4+5*i, 9])
sage: B.is_invertible()
True
sage: N = MatrixSpace(QQ,2,2)
sage: C = N([2,1,2,1])
sage: C.is_invertible()
False

kernel( self)

Return the kernel of this matrix, as a vector space.

INPUT:
    -- all additional arguments to the kernel function
       are passed directly onto the echelon call.

ALGORITHM: Elementary row operations don't change the kernel, since they are just right multiplication by an invertible matrix, so we instead compute kernel of the column echelon form. More precisely, there is a basis vector of the kernel that corresponds to each non-pivot row. That vector has a 1 at the non-pivot row, 0's at all other non-pivot rows, and for each pivot row, the negative of the entry at the non-pivot row in the column with that pivot element.

Note: Since we view matrices as acting on the right, but have functions for reduced row echelon forms, we instead compute the reduced row echelon form of the transpose of this matrix, which is the reduced column echelon form.

A kernel of dimension one over $ \mathbf{Q}$ :x

sage: A = MatrixSpace(QQ, 3)(range(9))
sage: A.kernel()
Vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[ 1 -2  1]

A trivial kernel:

sage: A = MatrixSpace(QQ, 2)([1,2,3,4])
sage: A.kernel()
Vector space of degree 2 and dimension 0 over Rational Field
Basis matrix:
[]

Kernel of a zero matrix:

sage: A = MatrixSpace(QQ, 2)(0)
sage: A.kernel()
Vector space of degree 2 and dimension 2 over Rational Field
Basis matrix:
[1 0]
[0 1]

Kernel of a non-square matrix:

sage: A = MatrixSpace(QQ,3,2)(range(6))
sage: A.kernel()
Vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[ 1 -2  1]

The 2-dimensional kernel of a matrix over a cyclotomic field:

sage: K = CyclotomicField(12); a=K.0
sage: M = MatrixSpace(K,4,2)([1,-1, 0,-2, 0,-a**2-1, 0,a**2-1])
sage: M
[             1             -1]
[             0             -2]
[             0 -zeta12^2 - 1]
[             0  zeta12^2 - 1]
sage: M.kernel()
Vector space of degree 4 and dimension 2 over Cyclotomic Field of order 12
and degree 4
Basis matrix:
[               0                1                0     -2*zeta12^2]
[               0                0                1 -2*zeta12^2 + 1]

A nontrivial kernel over a complicated base field.

sage: K = FractionField(MPolynomialRing(QQ, 2))
sage: M = MatrixSpace(K, 2)([[K.1, K.0], [K.1, K.0]])
sage: M
[x1 x0]
[x1 x0]
sage: M.kernel()
Vector space of degree 2 and dimension 1 over Fraction Field of Polynomial
Ring in x0, x1 over Rational Field
Basis matrix:
[ 1 -1]

maxspin( self, v)

Computes the largest integer n such that the list of vectors $ S=[v, A(v), ..., A^n(v)]$ are linearly independent, and returns that list.

INPUT:
    self -- Matrix
    v -- Vector
OUTPUT:
    list -- list of Vectors

ALGORITHM: The current implementation just adds vectors to a vector space until the dimension doesn't grow. This could be optimized by directly using matrices and doing an efficient Echelon form. Also, when the base is Q, maybe we could simultaneously keep track of what is going on in the reduction modulo p, which might make things much faster.

pivots( self)

Return the i such that the i-th column of self is a pivot column of the reduced row echelon form of self.

OUTPUT: list - sorted list of integers

restrict( self, V, [check=True])

Returns the matrix that defines the action of self on the chosen basis for the invariant subspace V. If V is an ambient, returns self (not a copy of self).

INPUT:
    V -- vector subspace
    check -- (optional) default: True; if False may not check
             that V is invariant (hence can be faster). 
OUTPUT:
    a matrix

WARNING: This function returns an nxn matrix, where V has dimension n. It does not check that V is in fact invariant under self, unless check is True (not the default).

sage: V = VectorSpace(QQ, 3)
sage: M = MatrixSpace(QQ, 3)
sage: A = M([1,2,0, 3,4,0, 0,0,0])
sage: W = V.subspace([[1,0,0], [0,1,0]])
sage: A.restrict(W)
[1 2]
[3 4]
sage: A.restrict(W, check=True)
[1 2]
[3 4]

We illustrate the warning about invariance not being checked by default, by giving a non-invariant subspace. With the default check=False this function returns the 'restriction' matrix, which is meaningless as check=True reveals.

sage: W2 = V.subspace([[1,0,0], [0,1,1]])
sage: A.restrict(W2, check=False)
[1 2]
[3 4]
sage: A.restrict(W2, check=True)
Traceback (most recent call last):
...
ArithmeticError: subspace is not invariant under matrix

restrict_domain( self, V)

Compute the matrix relative to the basis for V on the domain obtained by restricting self to V, but not changing the codomain of the matrix. This is the matrix whose rows are the images of the basis for V.

INPUT:
    V -- vector space (subspace of ambient space on which self acts)

SEE ALSO: restrict()

sage: V = VectorSpace(QQ, 3)
sage: M = MatrixSpace(QQ, 3)
sage: A = M([1,2,0, 3,4,0, 0,0,0])
sage: W = V.subspace([[1,0,0], [1,2,3]])
sage: A.restrict_domain(W)
[1 2 0]
[3 4 0]
sage: W2 = V.subspace_with_basis([[1,0,0], [1,2,3]])
sage: A.restrict_domain(W2)
[ 1  2  0]
[ 7 10  0]

row_space( self)

Return the vector space over the base field spanned by the rows of self.

sage: A = MatrixSpace(QQ, 2,2)([1,2,3,4])
sage: A.row_space()
Vector space of degree 2 and dimension 2 over Rational Field
Basis matrix:
[1 0]
[0 1]
sage: A.row_span(IntegerRing())
Free module of degree 2 and rank 2 over Integer Ring
Echelon basis matrix:
[1 0]
[0 2]

row_span( self, [R=None])

Return the R-module spanned by the rows of self.

INPUT:
    R -- (optional) principal ideal ring, such that the
         entries of self coerce into R.  The default
         is the base ring.
OUTPUT:
    a free R-module.

We define a $ 2\times 3$ matrix over $ \mathbf{Q}$ , then consider its row span over both $ \mathbf{Q}$ and $ \mathbf{Z}$ .

sage: A = MatrixSpace(QQ, 2,3)([1,2,3, '1/3', 4, 2])
sage: A
[  1   2   3]
[1/3   4   2]
sage: M1 = A.row_span(); M1
Vector space of degree 3 and dimension 2 over Rational Field
Basis matrix:
[   1    0 12/5]
[   0    1 3/10]
sage: M2 = A.row_span(IntegerRing()); M2
Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[1/3   4   2]
[  0  10   3]

Note that the determinants of the inner product matrices are different, though their discriminants differ by a square:

sage: M1.inner_product_matrix()
[ 169/25   18/25]
[  18/25 109/100]
sage: d1 = M1.discriminant(); d1
137/20
sage: d2 = M2.discriminant(); d2
685/9
sage: d2/d1
100/9

wiedemann( self, i, [t=0])

Application of Wiedemann's algorithm to the i-th standard basis vector.

If the optimal parameter t is nonzero, use only the first t linear recurrence relations.

Special Functions: __invert__,$  $ _set_pivots,$  $ _set_rank

__invert__( self)

Return this inverse of this matrix.

Raises a ZeroDivisionError if the matrix has zero determinant, and raises an ArithmeticError, if the inverse doesn't exist because the matrix is nonsquare.

Class: Matrix_generic_dense

class Matrix_generic_dense
The Matrix_generic_dense class derives from Matrix, and defines functionality for dense matrices over any base ring. Matrices are represented by a list of elements in the base ring, and element access operations are implemented in this class.
Matrix_generic_dense( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Functions: antitranspose,$  $ list,$  $ transpose

transpose( self)

Returns the transpose of self, without changing self.

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

sage: M = MatrixSpace(QQ,  2)
sage: A = M([1,2,3,4])
sage: B = A.transpose()
sage: print B
[1 3]
[2 4]
sage: print A
[1 2]
[3 4]

Special Functions: __getitem__,$  $ __setitem__,$  $ _entries

__getitem__( self, ij)

INPUT:
    A[i, j] -- the i,j of A, and
    A[i]    -- the i-th row of A.

__setitem__( self, ij, value)

INPUT:
    A[i, j] = value -- set the (i,j) entry of A
    A[i] = value    -- set the ith row of A

Class: Matrix_generic_dense_domain

class Matrix_generic_dense_domain
Matrix_generic_dense_domain( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Special Functions: _singular_

_singular_( self, [singular=Singular])

Tries to coerce this matrix to a singular matrix.

Class: Matrix_generic_dense_field

class Matrix_generic_dense_field
Matrix_generic_dense_field( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Class: Matrix_generic_dense_pid

class Matrix_generic_dense_pid
Matrix_generic_dense_pid( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Class: Matrix_generic_sparse

class Matrix_generic_sparse
The Matrix_generic_sparse class derives from Matrix, and defines functionality for dense matrices over any base ring. A generic sparse matrix is represented using a dictionary with keys pairs $ (i,j)$ and values in the base ring.
Matrix_generic_sparse( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Functions: denominator,$  $ get,$  $ hessenberg_form,$  $ matrix_from_columns,$  $ matrix_from_rows,$  $ nonzero_positions,$  $ set,$  $ sparse_columns,$  $ sparse_rows,$  $ swap_rows,$  $ transpose

get( self, ij)

Like __getitem__ but with no type or bounds checking. For (i,j) access, returns 0 if access is out of bounds.

hessenberg_form( self)

Return the Hessenberg form of this matrix.

matrix_from_columns( self, columns)

Return the submatrix of self of columns col[i] for i in the list of columns.

matrix_from_rows( self, rows)

Return the submatrix of self of rows row[i] for i in the list of rows.

nonzero_positions( self)

Returns the set of pairs (i,j) such that self[i,j] != 0.

set( self, ij, x)

Like __setitem__ but with no type or bounds checking. Only works for single entries, not whole rows.

swap_rows( self, r1, r2)

Swap rows r1 and r2 of self.

transpose( self)

Returns the transpose of self, without changing self.

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

sage: M = MatrixSpace(QQ,  2, sparse=True)
sage: A = M([1,2,3,4])
sage: B = A.transpose()
sage: print B
[1 3]
[2 4]
sage: print A
[1 2]
[3 4]

Special Functions: __getitem__,$  $ __mul__,$  $ __rmul__,$  $ __setitem__,$  $ _dict,$  $ _entries

__getitem__( self, ij)

INPUT:
    A[i, j] -- the i,j of A, and
    A[i]    -- the i-th row of A.

__setitem__( self, ij, value)

INPUT:
    A[i, j] = value -- set the (i,j) entry of A
    A[i] = value    -- set the ith row of A

Class: Matrix_generic_sparse_domain

class Matrix_generic_sparse_domain
Matrix_generic_sparse_domain( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Special Functions: _singular_

_singular_( self, [singular=Singular])

Tries to coerce this matrix to a singular matrix.

Class: Matrix_generic_sparse_field

class Matrix_generic_sparse_field
Matrix_generic_sparse_field( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Class: Matrix_generic_sparse_pid

class Matrix_generic_sparse_pid
Matrix_generic_sparse_pid( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Class: Matrix_integer

class Matrix_integer
Matrix_integer( self, parent)

Functions: echelon_form,$  $ elementary_divisors,$  $ frobenius,$  $ kernel,$  $ rank,$  $ smith_form

echelon_form( self, [include_zero_rows=True])

Return the echelon form of this matrix over the integers.

sage: A = MatrixSpace(IntegerRing(),2)([1,2,3,4])
sage: A.echelon_form()
[1 0]
[0 2]

sage: A = MatrixSpace(IntegerRing(),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]

elementary_divisors( self)

Return the elementary divisors of self, in order.

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.

INPUT:
    matrix
OUTPUT:
    list of int's

sage: A = MatrixSpace(IntegerRing(), 3)(range(9))
sage: A.elementary_divisors()
[0, 3, 1]

SEE ALSO: smith_form

frobenius( self, [flag=0])

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

If flag is 1, return only the elementary divisors. If flag is 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} F B$ .

INPUT:
   flag -- 0 (default), 1 or 2 as described above

ALGORITHM: uses pari's matfrobenius()

sage: A = MatrixSpace(IntegerRing(), 3)(range(9))
sage: A.frobenius(0)
[ 0  0  0]
[ 1  0 18]
[ 0  1 12]
sage: A.frobenius(1)
[x^3 - 12*x^2 - 18*x]
sage: A.frobenius(2)
([ 0  0  0]
[ 1  0 18]
[ 0  1 12],
[    -1      2     -1]
[     0  23/15 -14/15]
[     0  -2/15   1/15])

Author: 2006-04-02: Martin Albrecht

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.

kernel( self, [LLL=False])

Return the kernel of this matrix, as a module over the integers.

INPUT:
   LLL -- bool (default: False); if True the basis is an LLL
          reduced basis; otherwise, it is an echelon basis.

sage: M = MatrixSpace(IntegerRing(),4,2)(range(8))
sage: M.kernel()
Free module of degree 4 and rank 2 over Integer Ring
Echelon basis matrix:
[ 1  0 -3  2]
[ 0  1 -2  1]

rank( self)

Return the rank of self, which is the rank of the space spanned by the rows of self.

smith_form( self, [transformation=False])

Returns matrices S, U, and V such that S = U*self*V, and S is in Smith normal form. Thus S is diagonal with diagonal entries the ordered elementary divisors of S.

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.

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

It also makes sense for nonsquare matrices:

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

SEE ALSO: elementary_divisors

Special Functions: _adjoint,$  $ _lllgram

_adjoint( self)
assumes self is a square matrix (checked in adjoint)

_lllgram( self)
assumes self is a square matrix (checked in lllgram)

Class: Matrix_pid

class Matrix_pid
Matrix_pid( self, parent)

Functions: column_module,$  $ decomposition,$  $ echelon_form,$  $ image,$  $ kernel_on,$  $ row_module

column_module( self)

Return the free module over the base ring spanned by the columns of this matrix.

decomposition( self, [is_diagonalizable=False], [dual=False])

Returns the decomposition of the free module on which this matrix acts from the right, 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.

Let A be the matrix acting from the on the vector space V of column vectors. Assume that A is square. This function computes maximal subspaces W_1, ..., W_n corresponding to Galois conjugacy classes of eigenvalues of A. More precisely, let f(X) be the characteristic polynomial of A. This function computes the subspace $ W_i = ker(g_(A)^n)$ , where g_i(X) is an irreducible factor of f(X) and g_i(X) exactly divides f(X). If the optional parameter is_diagonalizable is True, then we let W_i = ker(g(A)), since then we know that ker(g(A)) = $ ker(g(A)^n)$ .

If dual is True, also returns the corresponding decomposition of V under the action of the transpose of A. The factors are guarenteed to correspond.

OUTPUT: list - list of pairs (V,t), where V is a vector spaces and t is a bool, and t is True exactly when the charpoly of self on V is irreducible.

(optional) list - list of pairs (W,t), where W is a vector space and t is a bool, and t is True exactly when the charpoly of the transpose of self on W is irreducible.

echelon_form( self, [include_zero_rows=True])

Return the echelon form of this matrix over the integers.

This is a matrix over the base ring (a PID) which is, by definition, what is also called the Hermite normal form.

image( self)

Return the image of the homomorphism on rows defined by this matrix.

kernel_on( self, V, [poly=False], [check=None])

Return the kernel of self restricted to the invariant subspace V. The result is a vector subspace of V, which is also a subspace of the ambient space.

INPUT:
    V -- vector subspace
    check -- (optional) default: False
    poly -- (optional) default: None; if not None, compute instead
            the kernel of poly(self) on V. 
    
OUTPUT:
    a subspace

WARNING: This function does not check that V is in fact invariant under self, unless check is True (not the default).

row_module( self)

Return the free module over the base ring spanned by the rows of self.

sage: A = MatrixSpace(IntegerRing(), 2)([1,2,3,4])
sage: A.row_module()
Free module of degree 2 and rank 2 over Integer Ring
Echelon basis matrix:
[1 0]
[0 2]

Class: Matrix_rational

class Matrix_rational
Matrix_rational( self, parent)

Special Functions: _adjoint,$  $ _lllgram

_adjoint( self)
assumes self is a square matrix (checked in adjoint)

_lllgram( self)
assumes self is a square matrix (checked in lllgram)

Class: Matrix_sparse_integer

class Matrix_sparse_integer
Matrix_sparse_integer( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Class: Matrix_sparse_rational

class Matrix_sparse_rational
The Matrix_sparse_rational class derives from Matrix, and defines functionality for sparse matrices over the field $ \mathbf{Q}$ of rational numbers.
Matrix_sparse_rational( self, parent, [entries=True], [coerce_entries=True], [copy=0])

Functions: charpoly,$  $ dense_matrix,$  $ echelon_form,$  $ hessenberg_form,$  $ set_row_to_multiple_of_row,$  $ transpose

charpoly( self, [bound=None])

Return the characteristic polynomial of this matrix.

See the documentation for self.dense_matrix().charpoly for more details.

ALGORITHM: Compute the charpoly of the corresponding dense matrix, obtained using self.dense_matrix().

sage: A = MatrixSpace(QQ,4, sparse=True)(range(16))
sage: A.charpoly()
x^4 - 30*x^3 - 80*x^2

dense_matrix( self)

Return the dense matrix with the same entries as this sparse matrix.

echelon_form( self, [height_guess=True], [include_zero_rows=True], [proof=None])

Return the echelon form of this sparse matrix over the rational numbers, computed using a sparse multi-modular algorithm.

INPUT:
    height_guess --
    proof -- bool (default: True)

The height guess is a guess for a bound on the height of the entries of the echelon form. If you know for some reason that the entries of the echelon form are bounded, giving a good height bound can speed up this function. At the end of the computation the result is checked for correctness and the height bound increased if necessary, so giving too small of a guess will not lead to incorrect results (though it may slow down the algorithm).

sage: A = MatrixSpace(QQ, 3, sparse=True)(range(9))
sage: A.echelon_form()
[ 1  0 -1]
[ 0  1  2]
[ 0  0  0]
sage: A = 9999999*MatrixSpace(QQ, 3, sparse=True)(range(9))
sage: A
[       0  9999999 19999998]
[29999997 39999996 49999995]
[59999994 69999993 79999992]
sage: A.echelon_form(height_guess=1)
[ 1  0 -1]
[ 0  1  2]
[ 0  0  0]

hessenberg_form( self)

Return the Hessenberg form of this sparse matrix.

ALGORITHM: Compute the Hessenberg form of the corresponding dense matrix, obtained using self.dense_matrix()

sage: A = MatrixSpace(QQ, 3, sparse=True)(range(9))
sage: H = A.hessenberg_form(); H
[ 0  5  2]
[ 3 14  5]
[ 0 -5 -2]
sage: H.is_sparse()
True

Special Functions: __cmp__,$  $ __getitem__,$  $ __mul__,$  $ __setitem__,$  $ _set_row_to_negative_of_row_of_A_using_subset_of_columns,$  $ _sparse_matrix_mpq_

See About this document... for information on suggesting changes.