34.7 Base class for matrices, part 2

Module: sage.matrix.matrix2

Base class for matrices, part 2

TESTS:

sage: m = matrix(ZZ['x'], 2, 3, [1..6])
sage: loads(dumps(m)) == m
True

Module-level Functions

cmp_pivots( ): Compare two sequences of pivot columns. If x is shorter than y, return -1, i.e., x < y, "not as good". If x is longer than y, x > y, "better" If the length is the same then x is better, i.e., x > y if the entries of x are correspondingly >= those of y with one being greater.

decomp_seq( )

This function is used internally be the decomposition matrix method. It takes a list of tuples and produces a sequence that is correctly sorted and prints with carriage returns.

sage: from sage.matrix.matrix2 import decomp_seq
sage: V = [(QQ^3, 2), (QQ^2, 1)]
sage: decomp_seq(V)
[
(Vector space of dimension 2 over Rational Field, 1),
(Vector space of dimension 3 over Rational Field, 2)
]

Class: Matrix

class Matrix

Functions: characteristic_polynomial, $\,$ charpoly, $\,$ column_module, $\,$ column_space, $\,$ conjugate, $\,$ decomposition, $\,$ decomposition_of_subspace, $\,$ denominator, $\,$ density, $\,$ det, $\,$ determinant, $\,$ echelon_form, $\,$ echelonize, $\,$ eigenmatrix_left, $\,$ eigenmatrix_right, $\,$ eigenspaces, $\,$ eigenspaces_left, $\,$ eigenspaces_right, $\,$ eigenvalues, $\,$ eigenvectors_left, $\,$ eigenvectors_right, $\,$ fcp, $\,$ find, $\,$ get_subdivisions, $\,$ gram_schmidt, $\,$ hadamard_bound, $\,$ hessenberg_form, $\,$ hessenbergize, $\,$ image, $\,$ integer_kernel, $\,$ inverse, $\,$ is_one, $\,$ is_scalar, $\,$ jordan_form, $\,$ kernel, $\,$ kernel_on, $\,$ left_eigenmatrix, $\,$ left_eigenvectors, $\,$ left_kernel, $\,$ left_nullity, $\,$ matrix_window, $\,$ maxspin, $\,$ minimal_polynomial, $\,$ minors, $\,$ minpoly, $\,$ norm, $\,$ nullity, $\,$ numerical_approx, $\,$ permanent, $\,$ permanental_minor, $\,$ pivot_rows, $\,$ plot, $\,$ prod_of_row_sums, $\,$ randomize, $\,$ restrict, $\,$ restrict_codomain, $\,$ restrict_domain, $\,$ right_eigenmatrix, $\,$ right_eigenspaces, $\,$ right_eigenvectors, $\,$ right_kernel, $\,$ right_nullity, $\,$ rook_vector, $\,$ row_module, $\,$ row_space, $\,$ set_block, $\,$ solve_left, $\,$ solve_right, $\,$ subdivide, $\,$ subdivision, $\,$ subdivision_entry, $\,$ subs, $\,$ symplectic_form, $\,$ tensor_product, $\,$ trace, $\,$ visualize_structure, $\,$ wiedemann

characteristic_polynomial( )

Synonym for self.charpoly(...).

sage: a = matrix(QQ, 2,2, [1,2,3,4]); a
[1 2]
[3 4]
sage: a.characteristic_polynomial('T')
T^2 - 5*T - 2

charpoly( )

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

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

If the base ring of the matrix is a number field, use PARI's charpoly instead.

The result is cached.

Input:

var: - a variable name (default: 'x')
algorithm: - string:
'hessenberg': - default (use Hessenberg form of matrix)

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

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

An example over $\mathbf{Q}$ :

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

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

sage: R.<a> = PolynomialRing(ZZ)
sage: M = MatrixSpace(R,2)([a,1,  a,a+1]); M
[    a     1]
[    a a + 1]
sage: f = M.charpoly('x'); 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.<x,y> = PolynomialRing(ZZ,2)
sage: A = MatrixSpace(R,2)([x, y, x^2, y^2])
sage: f = A.charpoly('x'); f
x^2 + (-y^2 - x)*x - x^2*y + x*y^2

It's a little difficult to distinguish the variables. To fix this, we temporarily view the indeterminate as :

sage: with localvars(f.parent(), 'Z'): print f
Z^2 + (-y^2 - x)*Z - x^2*y + x*y^2

We could also compute f in terms of Z from the start:

sage: A.charpoly('Z')
Z^2 + (-y^2 - x)*Z - x^2*y + x*y^2

Here is an example over a number field:

sage: x = QQ['x'].gen()
sage: K.<a> = NumberField(x^2 - 2)
sage: m = matrix(K, [[a-1, 2], [a, a+1]])
sage: m.charpoly('Z')
Z^2 + (-2*a)*Z - 2*a + 1
sage: m.charpoly('a')(m) == 0
True

TESTS:

sage: P.<a,b,c> = PolynomialRing(Rationals())
sage: u = MatrixSpace(P,3)([[0,0,a],[1,0,b],[0,1,c]])
sage: Q.<x> = PolynomialRing(P)
sage: u.charpoly('x')
x^3 + (-c)*x^2 + (-b)*x - a

column_module( )

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

sage: t = matrix(QQ, 3, range(9)); t
[0 1 2]
[3 4 5]
[6 7 8]
sage: t.column_module()
Vector space of degree 3 and dimension 2 over Rational Field
Basis matrix:
[ 1  0 -1]
[ 0  1  2]

column_space( )

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.00000000000000 2.00000000000000 +
3.00000000000000*I]
[4.00000000000000 + 5.00000000000000*I                     
9.00000000000000]
sage: B.column_space()
Vector space of degree 2 and dimension 2 over Complex Field with 53 bits of
precision
Basis matrix:
[1.00000000000000                0]
[               0 1.00000000000000]

conjugate( )

Return the conjugate of self, i.e. the matrix whose entries are the conjugates of the entries of self.

The entries of self must be complex numbers.

sage: A = matrix(CDF, [[1+I,1],[0,2*I]])
sage: A.conjugate()
[1.0 - 1.0*I         1.0]
[          0      -2.0*I]

decomposition( )

Returns 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.

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 , 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)) = .

Input:

self

- a matrix

algorithm

- 'spin' (default): algorithm involves iterating the action of self on a vector. 'kernel': naively just compute ker f_i(A) for each factor f_i.

dual

- bool (default: False): If True, also returns the corresponding decomposition of V under the action of the transpose of A. The factors are guaranteed to correspond.

is_diagonalizable

- if the matrix is known to be diagonalizable, set this to True, which might speed up the algorithm in some cases.

NOTE: If the base ring is not a field, the kernel algorithm is used.

Output:

Sequence: - 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.

sage: A = matrix(ZZ, 4, [3,4,5,6,7,3,8,10,14,5,6,7,2,2,10,9])
sage: B = matrix(QQ, 6, range(36))
sage: B*11
[  0  11  22  33  44  55]
[ 66  77  88  99 110 121]
[132 143 154 165 176 187]
[198 209 220 231 242 253]
[264 275 286 297 308 319]
[330 341 352 363 374 385]
sage: A.decomposition()
[
(Ambient free module of rank 4 over the principal ideal domain Integer
Ring, True)
]           
sage: B.decomposition()
[
(Vector space of degree 6 and dimension 2 over Rational Field
Basis matrix:
[ 1  0 -1 -2 -3 -4]
[ 0  1  2  3  4  5], True),
(Vector space of degree 6 and dimension 4 over Rational Field
Basis matrix:
[ 1  0  0  0 -5  4]
[ 0  1  0  0 -4  3]
[ 0  0  1  0 -3  2]
[ 0  0  0  1 -2  1], False)
]

decomposition_of_subspace( )

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.

Additional inputs besides M are passed onto the decomposition command.

sage: t = matrix(QQ, 3, [3, 0, -2, 0, -2, 0, 0, 0, 0]); t
[ 3  0 -2]
[ 0 -2  0]
[ 0  0  0]
sage: t.fcp('X')   # factored charpoly
(X - 3) * X * (X + 2)
sage: v = kernel(t*(t+2)); v   # an invariant subspace
Vector space of degree 3 and dimension 2 over Rational Field
Basis matrix:
[0 1 0]
[0 0 1]
sage: D = t.decomposition_of_subspace(v); D
[
(Vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[0 0 1], True),
(Vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[0 1 0], True)
]
sage: t.restrict(D[0][0])
[0]
sage: t.restrict(D[1][0])
[-2]

We do a decomposition over ZZ:

sage: a = matrix(ZZ,6,[0, 0, -2, 0, 2, 0, 2, -4, -2, 0, 2, 0, 0, 0, -2, -2, 0, 0, 2, 0, -2, -4, 2, -2, 0, 2, 0, -2, -2, 0, 0, 2, 0, -2, 0, 0])
sage: a.decomposition_of_subspace(ZZ^6)
[
(Free module of degree 6 and rank 2 over Integer Ring
Echelon basis matrix:
[ 1  0  1 -1  1 -1]
[ 0  1  0 -1  2 -1], False),
(Free module of degree 6 and rank 4 over Integer Ring
Echelon basis matrix:
[ 1  0 -1  0  1  0]
[ 0  1  0  0  0  0]
[ 0  0  0  1  0  0]
[ 0  0  0  0  0  1], False)
]

denominator( )

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(QQ,2)(['1/2', '1/3', '1/5', '1/7'])
sage: A.denominator()
210

A trivial example:

sage: A = matrix(QQ, 0,2)
sage: A.denominator()
1

Denominators are not 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.<x> = Frac(ZZ['x'])
sage: A = MatrixSpace(K,2)([1/x, 2/(x+1), 1, 5/(x^3)])
sage: A.denominator()
x^4 + x^3

Here's an example involving a cyclotomic field:

sage: K.<z> = CyclotomicField(3)
sage: M = MatrixSpace(K,3,sparse=True)
sage: A = M([(1+z)/3,(2+z)/3,z/3,1,1+z,-2,1,5,-1+z])
sage: print A
[1/3*z + 1/3 1/3*z + 2/3       1/3*z]
[          1       z + 1          -2]
[          1           5       z - 1]
sage: print A.denominator()
3

density( )

Return the density of self.

By density we understand the ration of the number of nonzero positions and the self.nrows() * self.ncols(), i.e. the number of possible nonzero positions.

First, note that the density parameter does not ensure the density of a matrix, it is only an upper bound.

sage: A = random_matrix(GF(127),200,200,density=0.3)
sage: A.density()
5159/20000

sage: A = matrix(QQ,3,3,[0,1,2,3,0,0,6,7,8])
sage: A.density()
2/3

sage: a = matrix([[],[],[],[]])
sage: a.density()
0

det( )

Synonym for self.determinant(...).

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

determinant( )

Return the determinant of self.

ALGORITHM: For small matrices (n<4), this is computed using the naive formula For integral domains, the charpoly is computed (using hessenberg form) Otherwise this is computed using the very stupid expansion by minors stupid 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.)

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()
True
sage: A[0,0] = 10
sage: A.determinant()
7

We compute the determinant of the arbitrary 3x3 matrix:

sage: R = PolynomialRing(QQ,9,'x')
sage: A = matrix(R,3,R.gens())
sage: A
[x0 x1 x2]
[x3 x4 x5]
[x6 x7 x8]
sage: A.determinant()
-x2*x4*x6 + x1*x5*x6 + x2*x3*x7 - x0*x5*x7 - x1*x3*x8 + x0*x4*x8

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

sage: R.<x,y> = PolynomialRing(IntegerRing(),2)
sage: A = MatrixSpace(R,2)([x, y, x**2, y**2])
sage: A.determinant()
-x^2*y + x*y^2

TEST:

sage: A = matrix(5, 5, [next_prime(i^2) for i in range(25)])
sage: B = MatrixSpace(ZZ['x'], 5, 5)(A)
sage: A.det() - B.det()
0

echelon_form( )

Return the echelon form of self.

Input:

matrix: - an element A of a MatrixSpace

Output:

matrix: - The reduced row echelon form of A, as an immutable matrix. Note that self is *not* changed by this command. Use A.echelonize() to change A in place.

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

echelonize( )

Transform self into a matrix in echelon form over the same base ring as self.

Input:

algorithm: - string, which algorithm to use (default: 'default')
'default': - use a default algorithm, chosen by SAGE
'strassen': - use a Strassen divide and conquer algorithm (if available)
cutoff: - integer; only used if the Strassen algorithm is selected.

sage: a = matrix(QQ,3,range(9)); a
[0 1 2]
[3 4 5]
[6 7 8]
sage: a.echelonize()
sage: a
[ 1  0 -1]
[ 0  1  2]
[ 0  0  0]

An immutable matrix cannot be transformed into echelon form. Use self.echelon_form() instead:

sage: a = matrix(QQ,3,range(9)); a.set_immutable()
sage: a.echelonize()
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead (use
self.copy()).
sage: a.echelon_form()
[ 1  0 -1]
[ 0  1  2]
[ 0  0  0]

Echelon form over the integers is what is also classically often known as Hermite normal form:

sage: a = matrix(ZZ,3,range(9))
sage: a.echelonize(); a
[ 3  0 -3]
[ 0  1  2]
[ 0  0  0]

We compute an echelon form both over a domain and fraction field:

sage: R.<x,y> = QQ[]
sage: a = matrix(R, 2, [x,y,x,y])
sage: a.echelon_form()               # not very useful? -- why two copies of the same row?
[x y]
[x y]

sage: b = a.change_ring(R.fraction_field()) 
sage: b.echelon_form()               # potentially useful
[  1 y/x]
[  0   0]

Echelon form is not defined over arbitrary rings:

sage: a = matrix(Integers(9),3,range(9))
sage: a.echelon_form()
Traceback (most recent call last):
...
NotImplementedError: Echelon form not implemented over 'Ring of integers
modulo 9'.

Involving a sparse matrix:

sage: m = matrix(3,[1, 1, 1, 1, 0, 2, 1, 2, 0], sparse=True); m
[1 1 1]
[1 0 2]
[1 2 0]
sage: m.echelon_form()
[ 1  0  2]
[ 0  1 -1]
[ 0  0  0]            
sage: m.echelonize(); m
[ 1  0  2]
[ 0  1 -1]
[ 0  0  0]

eigenmatrix_left( )

Return matrices D and P, where D is a diagonal matrix of eigenvalues and P is the corresponding matrix where the rows are corresponding eigenvectors (or zero vectors) so that P*self = D*P.

sage: A = matrix(QQ,3,3,range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: D, P = A.eigenmatrix_left()
sage: D
[                  0                   0                   0]
[                  0 -1.348469228349535?                   0]
[                  0                   0 13.348469228349534?]
sage: P
[                   1                   -2                    1]
[                   1  0.3101020514433644? -0.3797958971132713?]
[                   1   1.289897948556636?  1.5797958971132712?]
sage: P*A == D*P
True

Because P is invertible, A is diagonalizable.

sage: A == (~P)*D*P
True

The matrix P may contain zero rows corresponding to eigenvalues for which the algebraic multiplicity is greater than the geometric multiplicity. In these cases, the matrix is not diagonalizable.

sage: A = jordan_block(2,3); A            
[2 1 0]
[0 2 1]
[0 0 2]
sage: A = jordan_block(2,3)
sage: D, P = A.eigenmatrix_left()
sage: D
[2 0 0]
[0 2 0]
[0 0 2]
sage: P
[0 0 1]
[0 0 0]
[0 0 0]
sage: P*A == D*P
True

eigenmatrix_right( )

Return matrices D and P, where D is a diagonal matrix of eigenvalues and P is the corresponding matrix where the columns are corresponding eigenvectors (or zero vectors) so that self*P = P*D.

sage: A = matrix(QQ,3,3,range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: D, P = A.eigenmatrix_right()
sage: D
[                  0                   0                   0]
[                  0 -1.348469228349535?                   0]
[                  0                   0 13.348469228349534?]
sage: P
[                   1                    1                    1]
[                  -2  0.1303061543300932?   3.069693845669907?]
[                   1 -0.7393876913398137?   5.139387691339814?]
sage: A*P == P*D
True

Because P is invertible, A is diagonalizable.

sage: A == P*D*(~P)
True

The matrix P may contain zero columns corresponding to eigenvalues for which the algebraic multiplicity is greater than the geometric multiplicity. In these cases, the matrix is not diagonalizable.

sage: A = jordan_block(2,3); A    
[2 1 0]
[0 2 1]
[0 0 2]
sage: A = jordan_block(2,3)
sage: D, P = A.eigenmatrix_right()
sage: D
[2 0 0]
[0 2 0]
[0 0 2]
sage: P
[1 0 0]
[0 0 0]
[0 0 0]
sage: A*P == P*D
True

eigenspaces( ): Deprecated: Instead of eigenspaces, use eigenspaces_left

eigenspaces_left( )

Compute left eigenspaces of a matrix.

If algebraic_multiplicity=False, return a list of pairs (e, V) where e runs through all eigenvalues (up to Galois conjugation) of this matrix, and V is the corresponding left eigenspace.

If algebraic_multiplicity=True, return a list of pairs (e, V, n) where e and V are as above and n is the algebraic multiplicity of the eigenvalue. If the eigenvalues are given symbolically, as roots of an irreducible factor of the characteristic polynomial, then the algebraic multiplicity returned is the multiplicity of each conjugate eigenvalue.

The eigenspaces are returned sorted by the corresponding characteristic polynomials, where polynomials are sorted in dictionary order starting with constant terms.

Input:

var: - variable name used to represent elements of the root field of each irreducible factor of the characteristic polynomial I.e., if var='a', then the root fields will be in terms of a0, a1, a2, ..., ak.

WARNING: Uses a somewhat naive algorithm (simply factors the characteristic polynomial and computes kernels directly over the extension field). TODO: Maybe implement the better algorithm that is in dual_eigenvector in sage/modular/hecke/module.py.

We compute the left eigenspaces of a $3\times 3$ rational matrix.

sage: A = matrix(QQ,3,3,range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: es = A.eigenspaces_left(); es
[
(0, Vector space of degree 3 and dimension 1 over Rational Field
User basis matrix:
[ 1 -2  1]),
(a1, Vector space of degree 3 and dimension 1 over Number Field in a1 with
defining polynomial x^2 - 12*x - 18
User basis matrix:
[            1 1/15*a1 + 2/5 2/15*a1 - 1/5])
]
sage: es = A.eigenspaces_left(algebraic_multiplicity=True); es
[
(0, Vector space of degree 3 and dimension 1 over Rational Field
User basis matrix:
[ 1 -2  1], 1),
(a1, Vector space of degree 3 and dimension 1 over Number Field in a1 with
defining polynomial x^2 - 12*x - 18
User basis matrix:
[            1 1/15*a1 + 2/5 2/15*a1 - 1/5], 1)
]
sage: e, v, n = es[0]; v = v.basis()[0]
sage: delta = e*v - v*A
sage: abs(abs(delta)) < 1e-10
True

The same computation, but with implicit base change to a field:

sage: A = matrix(ZZ,3,range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: A.eigenspaces_left()
[
(0, Vector space of degree 3 and dimension 1 over Rational Field
User basis matrix:
[ 1 -2  1]),
(a1, Vector space of degree 3 and dimension 1 over Number Field in a1 with
defining polynomial x^2 - 12*x - 18
User basis matrix:
[            1 1/15*a1 + 2/5 2/15*a1 - 1/5])
]

We compute the left eigenspaces of the matrix of the Hecke operator on level 43 modular symbols.

sage: A = ModularSymbols(43).T(2).matrix(); A
[ 3  0  0  0  0  0 -1]
[ 0 -2  1  0  0  0  0]
[ 0 -1  1  1  0 -1  0]
[ 0 -1  0 -1  2 -1  1]
[ 0 -1  0  1  1 -1  1]
[ 0  0 -2  0  2 -2  1]
[ 0  0 -1  0  1  0 -1]
sage: A.base_ring()
Rational Field
sage: f = A.charpoly(); f
x^7 + x^6 - 12*x^5 - 16*x^4 + 36*x^3 + 52*x^2 - 32*x - 48
sage: factor(f)
(x - 3) * (x + 2)^2 * (x^2 - 2)^2
sage: A.eigenspaces_left(algebraic_multiplicity=True)
[
(3, Vector space of degree 7 and dimension 1 over Rational Field
User basis matrix:
[   1    0  1/7    0 -1/7    0 -2/7], 1),
(-2, Vector space of degree 7 and dimension 2 over Rational Field
User basis matrix:
[ 0  1  0  1 -1  1 -1]
[ 0  0  1  0 -1  2 -1], 2),
(a2, Vector space of degree 7 and dimension 2 over Number Field in a2 with
defining polynomial x^2 - 2
User basis matrix:
[      0       1       0      -1 -a2 - 1       1      -1]
[      0       0       1       0      -1       0 -a2 + 1], 2)
]

Next we compute the left eigenspaces over the finite field of order 11:

sage: A = ModularSymbols(43, base_ring=GF(11), sign=1).T(2).matrix(); A
[ 3  9  0  0]
[ 0  9  0  1]
[ 0 10  9  2]
[ 0  9  0  2]
sage: A.base_ring()
Finite Field of size 11
sage: A.charpoly()
x^4 + 10*x^3 + 3*x^2 + 2*x + 1
sage: A.eigenspaces_left(var = 'beta')
[
(9, Vector space of degree 4 and dimension 1 over Finite Field of size 11
User basis matrix:
[0 0 1 5]),
(3, Vector space of degree 4 and dimension 1 over Finite Field of size 11
User basis matrix:
[1 6 0 6]),
(beta2, Vector space of degree 4 and dimension 1 over Univariate Quotient
Polynomial Ring in beta2 over Finite Field of size 11 with modulus x^2 + 9
User basis matrix:
[           0            1            0 5*beta2 + 10])
]

TESTS: Warnings are issued if the generic algorithm is used over inexact fields. Garbage may result in these cases because of numerical precision issues.

sage: R=RealField(30)
sage: M=matrix(R,2,[2,1,1,1])
sage: M.eigenspaces_left() # random output from numerical issues
[
(2.6180340, Vector space of degree 2 and dimension 0 over Real Field with
30 bits of precision
User basis matrix:
[]),
(0.38196601, Vector space of degree 2 and dimension 0 over Real Field with
30 bits of precision
User basis matrix:
[])
]
sage: R=ComplexField(30)
sage: N=matrix(R,2,[2,1,1,1])
sage: N.eigenspaces_left() # random output from numerical issues
[
(2.6180340, Vector space of degree 2 and dimension 0 over Complex Field
with 30 bits of precision
User basis matrix:
[]),
(0.38196601, Vector space of degree 2 and dimension 0 over Complex Field
with 30 bits of precision
User basis matrix:
[])
]

eigenspaces_right( )

Compute right eigenspaces of a matrix.

If algebraic_multiplicity=False, return a list of pairs (e, V) where e runs through all eigenvalues (up to Galois conjugation) of this matrix, and V is the corresponding right eigenspace.

The eigenspaces are returned sorted by the corresponding characteristic polynomials, where polynomials are sorted in dictionary order starting with constant terms.

Input:

var: - variable name used to represent elements of the root field of each irreducible factor of the characteristic polynomial I.e., if var='a', then the root fields will be in terms of a0, a1, a2, ..., ak.

We compute the right eigenspaces of a $3\times 3$ rational matrix.

sage: A = matrix(QQ,3,3,range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: es = A.eigenspaces_right(); es
[
(0, Vector space of degree 3 and dimension 1 over Rational Field
User basis matrix:
[ 1 -2  1]),
(a1, Vector space of degree 3 and dimension 1 over Number Field in a1 with
defining polynomial x^2 - 12*x - 18
User basis matrix:
[           1 1/5*a1 + 2/5 2/5*a1 - 1/5])
]
sage: es = A.eigenspaces_right(algebraic_multiplicity=True); es 
[
(0, Vector space of degree 3 and dimension 1 over Rational Field
User basis matrix:
[ 1 -2  1], 1),
(a1, Vector space of degree 3 and dimension 1 over Number Field in a1 with
defining polynomial x^2 - 12*x - 18
User basis matrix:
[           1 1/5*a1 + 2/5 2/5*a1 - 1/5], 1)
]
sage: e, v, n = es[0]; v = v.basis()[0]
sage: delta = v*e - A*v
sage: abs(abs(delta)) < 1e-10
True

The same computation, but with implicit base change to a field:

sage: A = matrix(ZZ,3,range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: A.eigenspaces_right()
[
(0, Vector space of degree 3 and dimension 1 over Rational Field
User basis matrix:
[ 1 -2  1]),
(a1, Vector space of degree 3 and dimension 1 over Number Field in a1 with
defining polynomial x^2 - 12*x - 18
User basis matrix:
[           1 1/5*a1 + 2/5 2/5*a1 - 1/5])
]

TESTS: Warnings are issued if the generic algorithm is used over inexact fields. Garbage may result in these cases because of numerical precision issues.

sage: R=RealField(30) 
sage: M=matrix(R,2,[2,1,1,1])
sage: M.eigenspaces_right() # random output from numerical issues
[(2.6180340,
Vector space of degree 2 and dimension 0 over Real Field with 30 bits of
precision
User basis matrix:
[]),
(0.38196601,
Vector space of degree 2 and dimension 0 over Real Field with 30 bits of
precision
User basis matrix:
[])]
sage: R=ComplexField(30)
sage: N=matrix(R,2,[2,1,1,1])
sage: N.eigenspaces_right() # random output from numerical issues
[(2.6180340,
Vector space of degree 2 and dimension 0 over Complex Field with 30 bits of
precision
User basis matrix:
[]),
(0.38196601,
Vector space of degree 2 and dimension 0 over Complex Field with 30 bits of
precision
User basis matrix:
[])]

eigenvalues( )

Return a sequence of the eigenvalues of a matrix, with multiplicity. If the eigenvalues are roots of polynomials in QQ, then QQbar elements are returned that represent each separate root.

sage: a = matrix(QQ, 4, range(16)); a
[ 0  1  2  3]
[ 4  5  6  7]
[ 8  9 10 11]
[12 13 14 15]
sage: sorted(a.eigenvalues(), reverse=True)
[32.46424919657298?, 0, 0, -2.464249196572981?]

sage: a=matrix([(1, 9, -1, -1), (-2, 0, -10, 2), (-1, 0, 15, -2), (0, 1, 0, -1)])
sage: a.eigenvalues()
[-0.9386318578049146?, 15.50655435353258?, 0.2160387521361705? +
4.713151979747493?*I, 0.2160387521361705? - 4.713151979747493?*I]

A symmetric matrix a+a.transpose() should have real eigenvalues

sage: b=a+a.transpose()
sage: ev = b.eigenvalues(); ev
[-8.35066086057957?, -1.107247901349379?, 5.718651326708515?,
33.73925743522043?]

The eigenvalues are elements of QQbar, so they really represent exact roots of polynomials, not just approximations.

sage: e = ev[0]; e
-8.35066086057957?
sage: p = e.minpoly(); p
x^4 - 30*x^3 - 171*x^2 + 1460*x + 1784
sage: p(e) == 0
True

To perform computations on the eigenvalue as an element of a number field, you can always convert back to a number field element.

sage: e.as_number_field_element()
(Number Field in a with defining polynomial y^4 - 2*y^3 - 507*y^2 + 4988*y
- 8744,
-a + 8,
Ring morphism:
From: Number Field in a with defining polynomial y^4 - 2*y^3 - 507*y^2 +
4988*y - 8744
To:   Algebraic Real Field
Defn: a |--> 16.35066086057957?)

eigenvectors_left( )

Compute the left eigenvectors of a matrix.

For each distinct eigenvalue, returns a list of the form (e,V,n) where e is the eigenvalue, V is a list of eigenvectors forming a basis for the corresponding left eigenspace, and n is the algebraic multiplicity of the eigenvalue.

We compute the left eigenvectors of a $3\times 3$ rational matrix.

sage: A = matrix(QQ,3,3,range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: es = A.eigenvectors_left(); es
[(0, [
(1, -2, 1)
], 1),
(-1.348469228349535?, [(1, 0.3101020514433644?, -0.3797958971132713?)], 1),
(13.348469228349534?, [(1, 1.289897948556636?, 1.5797958971132712?)], 1)]
sage: eval, [evec], mult = es[0]
sage: delta = eval*evec - evec*A
sage: abs(abs(delta)) < 1e-10
True

eigenvectors_right( )

Compute the right eigenvectors of a matrix.

For each distinct eigenvalue, returns a list of the form (e,V,n) where e is the eigenvalue, V is a list of eigenvectors forming a basis for the corresponding right eigenspace, and n is the algebraic multiplicity of the eigenvalue.

We compute the right eigenvectors of a $3\times 3$ rational matrix.

sage: A = matrix(QQ,3,3,range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: es = A.eigenvectors_right(); es
[(0, [
(1, -2, 1)
], 1),
(-1.348469228349535?, [(1, 0.1303061543300932?, -0.7393876913398137?)], 1),
(13.348469228349534?, [(1, 3.069693845669907?, 5.139387691339814?)], 1)]
sage: eval, [evec], mult = es[0]
sage: delta = eval*evec - A*evec
sage: abs(abs(delta)) < 1e-10
True

fcp( )

Return the factorization of the characteristic polynomial of self.

Input:

var: - (default: 'x') name of variable of charpoly

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('T')
(T - 3) * T * (T + 2)

find( )

Find elements in this matrix satisfying the constraints in the function . The function is evaluated on each element of the matrix .

Input:

f: - a function that is evaluated on each element of this matrix.
indices: - whether or not to return the indices and elements of this matrix that satisfy the function.

Output: If indices is not specified, return a matrix with 1 where

is satisfied and 0 where it is not. If indices is specified, return a dictionary with containing the elements of this matrix satisfying

sage: M = matrix(4,3,[1, -1/2, -1, 1, -1, -1/2, -1, 0, 0, 2, 0, 1])
sage: M.find(lambda entry:entry==0)
[0 0 0]
[0 0 0]
[0 1 1]
[0 1 0]

sage: M.find(lambda u:u<0)
[0 1 1]
[0 1 1]
[1 0 0]
[0 0 0]

sage: M = matrix(4,3,[1, -1/2, -1, 1, -1, -1/2, -1, 0, 0, 2, 0, 1])
sage: len(M.find(lambda u:u<1 and u>-1,indices=True))
5

sage: M.find(lambda u:u!=1/2)
[1 1 1]
[1 1 1]
[1 1 1]
[1 1 1]

sage: M.find(lambda u:u>1.2)
[0 0 0]
[0 0 0]
[0 0 0]
[1 0 0]

sage: sorted(M.find(lambda u:u!=0,indices=True).keys()) == M.nonzero_positions()
True

get_subdivisions( )

Returns the current subdivision of self.

sage: M = matrix(5, 5, range(25))
sage: M.get_subdivisions()
([], [])
sage: M.subdivide(2,3)
sage: M.get_subdivisions()
([2], [3])
sage: N = M.parent()(1)
sage: N.subdivide(M.get_subdivisions()); N
[1 0 0|0 0]
[0 1 0|0 0]
[-----+---]
[0 0 1|0 0]
[0 0 0|1 0]
[0 0 0|0 1]

gram_schmidt( )

Return the matrix G whose rows are obtained from the rows of self (=A) by applying the Gram-Schmidt orthogonalization process. Also return the coefficients mu ij, i.e., a matrix mu such that (mu + 1)*G == A.

Output:

G: - a matrix whose rows are orthogonal
mu: - a matrix that gives the transformation, via the relation (mu + 1)*G == self

sage: A = matrix(ZZ, 3, [-1, 2, 5, -11, 1, 1, 1, -1, -3]); A
[ -1   2   5]
[-11   1   1]
[  1  -1  -3]
sage: G, mu = A.gram_schmidt()
sage: G
[     -1       2       5]
[  -52/5    -1/5      -2]
[  2/187  36/187 -14/187]
sage: mu
[     0      0      0]
[   3/5      0      0]
[  -3/5 -7/187      0]
sage: G.row(0) * G.row(1)
0
sage: G.row(0) * G.row(2)
0
sage: G.row(1) * G.row(2)
0

The relation between mu and A is as follows:

sage: (mu + 1)*G == A
True

hadamard_bound( )

Return an int n such that the absolute value of the determinant of this matrix is at most .

This is got using both the row norms and the column norms.

This function only makes sense when the base field can be coerced to the real double field RDF or the MPFR Real Field with 53-bits precision.

sage: a = matrix(ZZ, 3, [1,2,5,7,-3,4,2,1,123])
sage: a.hadamard_bound()
4
sage: a.det()
-2014
sage: 10^4
10000

In this example the Hadamard bound has to be computed (automatically) using mpfr instead of doubles, since doubles overflow:

sage: a = matrix(ZZ, 2, [2^10000,3^10000,2^50,3^19292])
sage: a.hadamard_bound()
12215
sage: len(str(a.det()))
12215

hessenberg_form( )

Return Hessenberg form of self.

If the base ring is merely an integral domain (and not a field), the Hessenberg form will (in general) only be defined over the fraction field of the base ring.

sage: A = matrix(ZZ,4,[2, 1, 1, -2, 2, 2, -1, -1, -1,1,2,3,4,5,6,7])
sage: h = A.hessenberg_form(); h
[    2  -7/2 -19/5    -2]
[    2   1/2 -17/5    -1]
[    0  25/4  15/2   5/2]
[    0     0  58/5     3]
sage: parent(h)
Full MatrixSpace of 4 by 4 dense matrices over Rational Field
sage: A.hessenbergize()
Traceback (most recent call last):
...
TypeError: Hessenbergize only possible for matrices over a field

hessenbergize( )

Transform self to Hessenberg form.

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

ALGORITHM: See Henri Cohen's first book.

sage: A = matrix(QQ,3, [2, 1, 1, -2, 2, 2, -1, -1, -1])
sage: A.hessenbergize(); A
[  2 3/2   1]
[ -2   3   2]
[  0  -3  -2]

sage: A = matrix(QQ,4, [2, 1, 1, -2, 2, 2, -1, -1, -1,1,2,3,4,5,6,7])
sage: A.hessenbergize(); A
[    2  -7/2 -19/5    -2]
[    2   1/2 -17/5    -1]
[    0  25/4  15/2   5/2]
[    0     0  58/5     3]

You can't Hessenbergize an immutable matrix:

sage: A = matrix(QQ, 3, [1..9])
sage: A.set_immutable()
sage: A.hessenbergize()
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead (use
self.copy()).

image( )

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

sage: MS1 = MatrixSpace(ZZ,4)
sage: MS2 = MatrixSpace(QQ,6)
sage: A = MS1.matrix([3,4,5,6,7,3,8,10,14,5,6,7,2,2,10,9])
sage: B = MS2.random_element()

sage: image(A)
Free module of degree 4 and rank 4 over Integer Ring
Echelon basis matrix:
[  1   0   0 426]
[  0   1   0 518]
[  0   0   1 293]
[  0   0   0 687]

sage: image(B) == B.row_module()
True

integer_kernel( )

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]

inverse( )

Returns the inverse of self, without changing self.

Note that one can use the Python inverse operator to obtain the inverse as well.

sage: m = matrix([[1,2],[3,4]])
sage: m^(-1)
[  -2    1]
[ 3/2 -1/2]
sage: m.inverse()
[  -2    1]
[ 3/2 -1/2]
sage: ~m
[  -2    1]
[ 3/2 -1/2]

sage: m = matrix([[1,2],[3,4]], sparse=True)
sage: m^(-1)
[  -2    1]
[ 3/2 -1/2]
sage: m.inverse()
[  -2    1]
[ 3/2 -1/2]
sage: ~m
[  -2    1]
[ 3/2 -1/2]

is_one( )

Return True if this matrix is the identity matrix.

sage: m = matrix(QQ,2,range(4))
sage: m.is_one()
False
sage: m = matrix(QQ,2,[5,0,0,5])
sage: m.is_one()
False
sage: m = matrix(QQ,2,[1,0,0,1])
sage: m.is_one()
True
sage: m = matrix(QQ,2,[1,1,1,1])
sage: m.is_one()
False

is_scalar( )

Return True if this matrix is a scalar matrix.

INPUT - base_ring element a, which is chosen as self[0][0] if a = None

OUTPUT - whether self is a scalar matrix (in fact the scalar matrix aI if a is input)

sage: m = matrix(QQ,2,range(4))
sage: m.is_scalar(5)
False
sage: m = matrix(QQ,2,[5,0,0,5])
sage: m.is_scalar(5)
True
sage: m = matrix(QQ,2,[1,0,0,1])
sage: m.is_scalar(1)
True
sage: m = matrix(QQ,2,[1,1,1,1])
sage: m.is_scalar(1)
False

jordan_form( )

Compute the Jordan canonical form of the matrix, if it exists.

This computation is performed in a naive way using the ranks of powers of A-xI, where x is an eigenvalue of the matrix A.

Input:

base_ring: - ring in which to compute the Jordan form.
sparse: - (default False) If sparse=True, return a sparse matrix.
subdivide: - (default True) If subdivide=True, the subdivisions for the Jordan blocks in the matrix are shown.

sage: a = matrix(ZZ,4,[1, 0, 0, 0, 0, 1, 0, 0, 1, \
-1, 1, 0, 1, -1, 1, 2]); a
[ 1  0  0  0]
[ 0  1  0  0]
[ 1 -1  1  0]
[ 1 -1  1  2]
sage: a.jordan_form()
[2|0 0|0]
[-+---+-]
[0|1 1|0]
[0|0 1|0]
[-+---+-]
[0|0 0|1]
sage: a.jordan_form(subdivide=False)
[2 0 0 0]
[0 1 1 0]
[0 0 1 0] 
[0 0 0 1]
sage: b = matrix(ZZ,3,range(9)); b
[0 1 2]
[3 4 5]
[6 7 8]
sage: b.jordan_form()             
Traceback (most recent call last):
...
RuntimeError: Some eigenvalue does not exist in Integer Ring.
sage: b.jordan_form(RealField(15))
[-1.348|0.0000|0.0000]
[------+------+------]
[0.0000|0.0000|0.0000]
[------+------+------]
[0.0000|0.0000| 13.35]

If you need the transformation matrix as well as the Jordan form of self, then pass the option transformation=True.

sage: m = matrix([[5,4,2,1],[0,1,-1,-1],[-1,-1,3,0],[1,1,-1,2]]); m
[ 5  4  2  1]
[ 0  1 -1 -1]
[-1 -1  3  0]
[ 1  1 -1  2]
sage: jf, p = m.jordan_form(transformation=True)
sage: jf
[2|0|0 0]
[-+-+---]
[0|1|0 0]
[-+-+---]
[0|0|4 1]
[0|0|0 4]
sage: ~p * m * p
[2 0 0 0]
[0 1 0 0]
[0 0 4 1]
[0 0 0 4]

Note that for matrices over inexact rings, there can be problems computing the transformation matrix due to numerical stability issues in computing a basis for a kernel.

sage: b = matrix(ZZ,3,3,range(9))
sage: jf, p = b.jordan_form(RealField(15), transformation=True)
Traceback (most recent call last):
...
ValueError: cannot compute the transformation matrix due to lack of
precision

TESTS:

sage: c = matrix(ZZ, 3, [1]*9); c
[1 1 1]
[1 1 1]
[1 1 1]
sage: c.jordan_form(subdivide=False)
[3 0 0]
[0 0 0]
[0 0 0]

sage: evals = [(i,i) for i in range(1,6)]
sage: n = sum(range(1,6))
sage: jf = block_diagonal_matrix([jordan_block(ev,size) for ev,size in evals])
sage: p = random_matrix(ZZ,n,n)
sage: while p.rank() != n: p = random_matrix(ZZ,n,n)
sage: m = p * jf * ~p
sage: mjf, mp = m.jordan_form(transformation=True)
sage: mjf == jf
True

kernel( )

Return the (left) kernel of this matrix, as a vector space. This is the space of vectors x such that x*self=0. Use self.right_kernel() for the right kernel.

Input:

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

By convention if self has 0 rows, the kernel is of dimension 0, whereas the kernel is whole domain if self has 0 columns.

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}$ :

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(PolynomialRing(QQ, 2, 'x'))
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
Multivariate Polynomial Ring in x0, x1 over Rational Field
Basis matrix:
[ 1 -1]

kernel_on( )

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: True; whether to check that V is invariant under the action of self.
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 if check is False. With check False this function is much faster.

sage: t = matrix(QQ, 4, [39, -10, 0, -12, 0, 2, 0, -1, 0, 1, -2, 0, 0, 2, 0, -2]); t
[ 39 -10   0 -12]
[  0   2   0  -1]
[  0   1  -2   0]
[  0   2   0  -2]
sage: t.fcp()
(x - 39) * (x + 2) * (x^2 - 2)
sage: s = (t-39)*(t^2-2)
sage: V = s.kernel(); V
Vector space of degree 4 and dimension 3 over Rational Field
Basis matrix:
[1 0 0 0]
[0 1 0 0]
[0 0 0 1]
sage: s.restrict(V)
[0 0 0]
[0 0 0]
[0 0 0]
sage: s.kernel_on(V)
Vector space of degree 4 and dimension 3 over Rational Field
Basis matrix:
[1 0 0 0]
[0 1 0 0]
[0 0 0 1]
sage: k = t-39
sage: k.restrict(V)
[  0 -10 -12]
[  0 -37  -1]
[  0   2 -41]
sage: ker = k.kernel_on(V); ker
Vector space of degree 4 and dimension 1 over Rational Field
Basis matrix:
[   1 -2/7    0 -2/7]
sage: ker.0 * k
(0, 0, 0, 0)

left_eigenmatrix( )

Return matrices D and P, where D is a diagonal matrix of eigenvalues and P is the corresponding matrix where the rows are corresponding eigenvectors (or zero vectors) so that P*self = D*P.

sage: A = matrix(QQ,3,3,range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: D, P = A.eigenmatrix_left()
sage: D
[                  0                   0                   0]
[                  0 -1.348469228349535?                   0]
[                  0                   0 13.348469228349534?]
sage: P
[                   1                   -2                    1]
[                   1  0.3101020514433644? -0.3797958971132713?]
[                   1   1.289897948556636?  1.5797958971132712?]
sage: P*A == D*P
True

Because P is invertible, A is diagonalizable.

sage: A == (~P)*D*P
True

The matrix P may contain zero rows corresponding to eigenvalues for which the algebraic multiplicity is greater than the geometric multiplicity. In these cases, the matrix is not diagonalizable.

sage: A = jordan_block(2,3); A            
[2 1 0]
[0 2 1]
[0 0 2]
sage: A = jordan_block(2,3)
sage: D, P = A.eigenmatrix_left()
sage: D
[2 0 0]
[0 2 0]
[0 0 2]
sage: P
[0 0 1]
[0 0 0]
[0 0 0]
sage: P*A == D*P
True

left_eigenvectors( )

Compute the left eigenvectors of a matrix.

We compute the left eigenvectors of a $3\times 3$ rational matrix.

sage: A = matrix(QQ,3,3,range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: es = A.eigenvectors_left(); es
[(0, [
(1, -2, 1)
], 1),
(-1.348469228349535?, [(1, 0.3101020514433644?, -0.3797958971132713?)], 1),
(13.348469228349534?, [(1, 1.289897948556636?, 1.5797958971132712?)], 1)]
sage: eval, [evec], mult = es[0]
sage: delta = eval*evec - evec*A
sage: abs(abs(delta)) < 1e-10
True

left_kernel( )

Return the (left) kernel of this matrix, as a vector space. This is the space of vectors x such that x*self=0. Use self.right_kernel() for the right kernel.

Input:

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

By convention if self has 0 rows, the kernel is of dimension 0, whereas the kernel is whole domain if self has 0 columns.

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

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(PolynomialRing(QQ, 2, 'x'))
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
Multivariate Polynomial Ring in x0, x1 over Rational Field
Basis matrix:
[ 1 -1]

left_nullity( )

Return the (left) nullity of this matrix, which is the dimension of the (left) kernel of this matrix acting from the right on row vectors.

sage: M = Matrix(QQ,[[1,0,0,1],[0,1,1,0],[1,1,1,0]])
sage: M.nullity()
0
sage: M.left_nullity()
0

sage: A = M.transpose()
sage: A.nullity()
1
sage: A.left_nullity()
1

sage: M = M.change_ring(ZZ)
sage: M.nullity()
0
sage: A = M.transpose()
sage: A.nullity()
1

matrix_window( )

Return the requested matrix window.

sage: A = matrix(QQ, 3, range(9))
sage: A.matrix_window(1,1, 2, 1)
Matrix window of size 2 x 1 at (1,1):
[0 1 2]
[3 4 5]
[6 7 8]

maxspin( )

Computes the largest integer n such that the list of vectors 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.

sage: t = matrix(QQ, 3, range(9)); t
[0 1 2]
[3 4 5]
[6 7 8]
sage: v = (QQ^3).0
sage: t.maxspin(v)
[(1, 0, 0), (0, 1, 2), (15, 18, 21)]
sage: k = t.kernel(); k
Vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[ 1 -2  1]
sage: t.maxspin(k.0)
[(1, -2, 1)]

minimal_polynomial( )

This is a synonym for self.minpoly

sage: a = matrix(QQ, 4, range(16))
sage: a.minimal_polynomial('z')
z^3 - 30*z^2 - 80*z
sage: a.minpoly()
x^3 - 30*x^2 - 80*x

minors( )

Return the list of all k-minors of self.

Let A be an m x n matrix and k an integer with 0 < k, k <= m, and k <= n. A k x k minor of A is the determinant of a k x k matrix obtained from A by deleting m - k rows and n - k columns.

The returned list is sorted in lexicographical row major ordering, e.g., if A is a 3 x 3 matrix then the minors returned are with for these rows/columns: [ [0, 1]x[0, 1], [0, 1]x[0, 2], [0, 1]x[1, 2], [0, 2]x[0, 1], [0, 2]x[0, 2], [0, 2]x[1, 2], [1, 2]x[0, 1], [1, 2]x[0, 2], [1, 2]x[1, 2] ].

Input:

k: - integer

sage: A = Matrix(ZZ,2,3,[1,2,3,4,5,6]); A
[1 2 3]
[4 5 6]
sage: A.minors(2)
[-3, -6, -3]

sage: k = GF(37)
sage: P.<x0,x1,x2> = PolynomialRing(k)
sage: A = Matrix(P,2,3,[x0*x1, x0, x1, x2, x2 + 16, x2 + 5*x1 ])
sage: A.minors(2)
[x0*x1*x2 + 16*x0*x1 - x0*x2, 5*x0*x1^2 + x0*x1*x2 - x1*x2, 5*x0*x1 + x0*x2
- x1*x2 - 16*x1]

minpoly( )

Return the minimal polynomial of self.

This uses a simplistic - and potentially very very slow - algorithm that involves computing kernels to determine the powers of the factors of the charpoly that divide the minpoly.

sage: A = matrix(GF(9,'c'), 4, [1, 1, 0,0, 0,1,0,0, 0,0,5,0, 0,0,0,5])
sage: factor(A.minpoly())
(x + 1) * (x + 2)^2
sage: A.minpoly()(A) == 0
True
sage: factor(A.charpoly())
(x + 1)^2 * (x + 2)^2

The default variable name is , but you can specify another name:

sage: factor(A.minpoly('y'))
(y + 1) * (y + 2)^2

norm( )

Return the p-norm of this matrix, where can be 1, 2, $\inf$ , or the Frobenius norm.

Input:

self: - a matrix whose entries are coercible into CDF
p: - one of the following options:
1: - the largest column-sum norm
2 (default): - the Euclidean norm
Infinity: - the largest row-sum norm
'frob': - the Frobenius (sum of squares) norm

Output: RDF number

sage: A = matrix(ZZ, [[1,2,4,3],[-1,0,3,-10]]) 
sage: A.norm(1) 
13.0 
sage: A.norm(Infinity) 
14.0
sage: B = random_matrix(QQ, 20, 21) 
sage: B.norm(Infinity) == (B.transpose()).norm(1) 
True

sage: Id = identity_matrix(12) 
sage: Id.norm(2) 
1.0 
sage: A = matrix(RR, 2, 2, [13,-4,-4,7]) 
sage: A.norm() 
15.0

sage: A = matrix(CDF, 2, 3, [3*I,4,1-I,1,2,0]) 
sage: A.norm('frob') 
5.65685424949
sage: A.norm(2)
5.47068444321
sage: A.norm(1)
6.0
sage: A.norm(Infinity)
8.41421356237
sage: a = matrix([[],[],[],[]])
sage: a.norm()
0.0
sage: a.norm(Infinity) == a.norm(1)
True

nullity( )

Return the (left) nullity of this matrix, which is the dimension of the (left) kernel of this matrix acting from the right on row vectors.

sage: M = Matrix(QQ,[[1,0,0,1],[0,1,1,0],[1,1,1,0]])
sage: M.nullity()
0
sage: M.left_nullity()
0

sage: A = M.transpose()
sage: A.nullity()
1
sage: A.left_nullity()
1

sage: M = M.change_ring(ZZ)
sage: M.nullity()
0
sage: A = M.transpose()
sage: A.nullity()
1

numerical_approx( )

Return a numerical approximation of self as either a real or complex number with at least the requested number of bits or digits of precision.

Input:

prec: - an integer: the number of bits of precision
digits: - an integer: digits of precision

Output: A matrix coerced to a real or complex field with prec bits of precision.

sage: d = matrix([[3, 0],[0,sqrt(2)]]) ;
sage: b = matrix([[1, -1], [2, 2]]) ; e = b * d * b.inverse();e
[    1/sqrt(2) + 3/2 3/4 - 1/(2*sqrt(2))]
[        3 - sqrt(2)     1/sqrt(2) + 3/2]

sage: e.numerical_approx(53)
[ 2.20710678118655 0.396446609406726]
[ 1.58578643762690  2.20710678118655]

sage: e.numerical_approx(20)
[ 2.2071 0.39645]
[ 1.5858  2.2071]

sage: (e-I).numerical_approx(20)
[2.2071 - 1.0000*I           0.39645]
[           1.5858 2.2071 - 1.0000*I]

sage: M=matrix(QQ,4,[i/(i+1) for i in range(12)]);M
[    0   1/2   2/3]
[  3/4   4/5   5/6]
[  6/7   7/8   8/9]
[ 9/10 10/11 11/12]

sage: M.numerical_approx()
[0.000000000000000 0.500000000000000 0.666666666666667]
[0.750000000000000 0.800000000000000 0.833333333333333]
[0.857142857142857 0.875000000000000 0.888888888888889]
[0.900000000000000 0.909090909090909 0.916666666666667]

sage: matrix(SR, 2, 2, range(4)).n()
[0.000000000000000  1.00000000000000]
[ 2.00000000000000  3.00000000000000]

permanent( )

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 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 is the sum of all the diagonal products of .

Modification of theorem 7.1.1. from Brualdi and Ryser: Combinatorial Matrix Theory. Instead of deleting columns from , we choose columns from 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.0000000000000

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 and n+3 boys:
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.<a> = PolynomialRing(ZZ)
sage: A = MatrixSpace(R,2)([[a,1], [a,a+1]])
sage: A.permanent()
a^2 + 2*a

sage: R.<x,y> = PolynomialRing(ZZ,2)
sage: A = MatrixSpace(R,2)([x, y, x^2, y^2])
sage: A.permanent()
x^2*y + x*y^2

Author Log:

Jaap Spies (2006-02-16) Copyright (C) 2006 Jaap Spies (j.spies@hccnet.nl) Copyright (C) 2006 William Stein (wstein@gmail.com)
Jaap Spies (2006-02-21): added definition of permanent

permanental_minor( )

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

This is the sum of the permanents of all possible by submatrices of .

See Brualdi and Ryser: Combinatorial Matrix Theory, p. 203. Note the typo in that reference! For applications see Theorem 7.2.1 and Theorem 7.2.4.

Note that the permanental -minor equals .

For a (0,1)-matrix the permanental -minor counts the number of different selections of 1's of 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)

pivot_rows( )

Return the pivot row positions for this matrix, which are a topmost subset of the rows that span the row space and are linearly independent.

Output:

list: - a list of integers

sage: A = matrix(QQ,3,3, [0,0,0,1,2,3,2,4,6]); A
[0 0 0]
[1 2 3]
[2 4 6]
sage: A.pivot_rows()
[1]

plot( )

A plot of this matrix.

Each (ith, jth) matrix element is given a different color value depending on its relative size compared to the other elements in the matrix.

The tick marks drawn on the frame axes denote the (ith, jth) element of the matrix.

This method just calls matrix_plot. *args and **kwds are passed to matrix_plot.

A matrix over ZZ colored with different grey levels:

sage: A = matrix([[1,3,5,1],[2,4,5,6],[1,3,5,7]])
sage: A.plot()

Here we make a random matrix over RR and use cmap='hsv' to color the matrix elements different RGB colors:

sage: A = random_matrix(RDF, 50)
sage: plot(A, cmap='hsv')

Another random plot, but over GF(389):

sage: A = random_matrix(GF(389), 10)
sage: A.plot(cmap='Oranges')

prod_of_row_sums( )

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

sage: a = matrix(QQ, 2,2, [1,2,3,2]); a
[1 2]
[3 2]
sage: a.prod_of_row_sums([0,1])
15

Another example:

sage: a = matrix(QQ, 2,3, [1,2,3,2,5,6]); a
[1 2 3]
[2 5 6]
sage: a.prod_of_row_sums([1,2])
55

Author: Jaap Spies (2006-02-18)

randomize( )

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

NOTE: We actually choose at random density proportion of entries of the matrix and set them to random elements. It's possible that the same position can be chosen multiple times, especially for a very small matrix.

Input:

density: - integer (default: 1) rough measure of the proportion of nonzero entries in the random matrix
*args, **kwds: - rest of parameters may be passed to the random_element function of the base ring.

We construct the zero matrix over a polynomial ring.

sage: a = matrix(QQ['x'], 3); a
[0 0 0]
[0 0 0]
[0 0 0]

We then randomize roughly half the entries:

sage: a.randomize(0.5)
sage: a
[      1/2*x^2 - x - 12 1/2*x^2 - 1/95*x - 1/2                      0]
[-5/2*x^2 + 2/3*x - 1/4                      0                      0]
[          -x^2 + 2/3*x                      0                      0]

Now we randomize all the entries of the resulting matrix:

sage: a.randomize()
sage: a
[     1/3*x^2 - x + 1             -x^2 + 1              x^2 - x]
[ -1/14*x^2 - x - 1/4           -4*x - 1/5 -1/4*x^2 - 1/2*x + 4]
[ 1/9*x^2 + 5/2*x - 3     -x^2 + 3/2*x + 1   -2/7*x^2 - x - 1/2]

We create the zero matrix over the integers:

sage: a = matrix(ZZ, 2); a
[0 0]
[0 0]

Then we randomize it; the x and y parameters, which determine the size of the random elements, are passed onto the ZZ random_element method.

sage: a.randomize(x=-2^64, y=2^64)
sage: a
[-12401200298100116246   1709403521783430739]
[ -4417091203680573707  17094769731745295000]

restrict( )

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.

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_codomain( )

Suppose that self defines a linear map from some domain to a codomain that contains and that the image of self is contained in . This function returns a new matrix that represents this linear map but as a map to , in the sense that if is in the domain, then is the linear combination of the elements of the basis of that equals v*self.

Input:

V: - vector space (space of degree self.ncols()) that contains the image of self.

SEE ALSO: restrict(), restrict_domain()

sage: A = matrix(QQ,3,[1..9])
sage: V = (QQ^3).span([[1,2,3], [7,8,9]]); V
Vector space of degree 3 and dimension 2 over Rational Field
Basis matrix:
[ 1  0 -1]
[ 0  1  2]
sage: z = vector(QQ,[1,2,5])
sage: B = A.restrict_codomain(V); B
[1 2]
[4 5]
[7 8]
sage: z*B
(44, 52)
sage: z*A
(44, 52, 60)
sage: 44*V.0 + 52*V.1
(44, 52, 60)

restrict_domain( )

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)