32.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,$ \,$ eigenspaces,$ \,$ 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_kernel,$ \,$ left_nullity,$ \,$ matrix_window,$ \,$ maxspin,$ \,$ minimal_polynomial,$ \,$ minors,$ \,$ minpoly,$ \,$ norm,$ \,$ nullity,$ \,$ numerical_approx,$ \,$ permanent,$ \,$ permanental_minor,$ \,$ pivot_rows,$ \,$ prod_of_row_sums,$ \,$ randomize,$ \,$ restrict,$ \,$ restrict_codomain,$ \,$ restrict_domain,$ \,$ 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 $ Z$ :

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 $ 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)$ .

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]

eigenspaces( )

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

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

NOTE: Calling this method of a matrix over an inexact base ring will raise a NotImplementedError. If you want to force this anyway, pass the option even_if_inexact=True.

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 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(); 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: e, v = 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()
[
(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 eigenspaces of the matrix of the Hecke operator $ T_2$ 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()
[
(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]),
(-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]),
(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])
]

Next we compute the 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(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:

sage: R=RealField(30)
sage: M=matrix(R,2,[2,1,1,1])
sage: M.eigenspaces()
Traceback (most recent call last):
...
NotImplementedError: won't use generic algorithm for inexact base rings,
pass the option even_if_inexact=True if you really want this.

sage: R=ComplexField(30)
sage: N=matrix(R,2,[2,1,1,1])
sage: N.eigenspaces()
Traceback (most recent call last):
...
NotImplementedError: won't use generic algorithm for inexact base rings,
pass the option even_if_inexact=True if you really want this.

But you can ask for (and receive!) garbage:

sage: M.eigenspaces(even_if_inexact=True) #random
[
(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: N.eigenspaces(even_if_inexact=True) #random
[
(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:
[])
]

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 $ f$ . 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 $ f$ is satisfied and 0 where it is not. If indices is specified, return a dictionary with containing the elements of this matrix satisfying $ f$ .

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 $ 10^n$ .

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 $ 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 = 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_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]

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 $ S=[v, v*A, ..., v * A^n]$ 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 $ x$ , 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 $ p$ 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 $ 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.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:

permanental_minor( )

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

This is the sum of the permanents of all possible $ k$ by $ k$ submatrices 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)

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]

prod_of_row_sums( )

Calculate the product of all row sums of a submatrix of $ A$ 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 $ V$ and that the image of self is contained in $ V$ . This function returns a new matrix $ A$ that represents this linear map but as a map to $ V$ , in the sense that if $ x$ is in the domain, then $ xA$ is the linear combination of the elements of the basis of $ V$ 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)

SEE ALSO: restrict()

sage: V = QQ^3
sage: A = matrix(QQ,3,[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]

right_kernel( )

Return the right kernel of this matrix, as a vector space. This is the space of vectors x such that self*x=0.

Input:

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

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

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

sage: A = MatrixSpace(QQ, 3)(range(9))
sage: A.right_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.right_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.right_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,2,3)(range(6))
sage: A.right_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,2,4)([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.right_kernel()
Vector space of degree 4 and dimension 2 over Cyclotomic Field of order 12
and degree 4
Basis matrix:
[      1  4/13*zeta12^2 - 1/13      0 -2/13*zeta12^2 + 7/13]
[      0                     0      1                     0]

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.right_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 x1/(-x0)]

right_nullity( )

Return the right nullity of this matrix, which is the dimension of the right kernel.

sage: A = MatrixSpace(QQ,3,2)(range(6))
sage: A.right_nullity()
0

sage: A = matrix(ZZ,3,range(9))
sage: A.right_nullity()
1

rook_vector( )

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: R.<x> = PolynomialRing(ZZ)
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_module( )

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]

row_space( )

Return the row space of this matrix. (Synonym for self.row_module().)

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

sage: m = Matrix(Integers(5),2,2,[2,2,2,2]);
sage: m.row_space()
Vector space of degree 2 and dimension 1 over Ring of integers modulo 5
Basis matrix:
[1 1]

set_block( )

Sets the sub-matrix of self, with upper left corner given by row, col to block.

sage: A = matrix(QQ, 3, 3, range(9))/2
sage: B = matrix(ZZ, 2, 1, [100,200])
sage: A.set_block(0, 1, B)
sage: A
[  0 100   1]
[3/2 200 5/2]
[  3 7/2   4]

solve_left( )

If self is a matrix $ A$ , then this function returns a vector or matrix $ X$ such that $ X A = B$ . If $ B$ is a vector then $ X$ is a vector and if $ B$ is a matrix, then $ X$ is a matrix.

Input:

B
- a matrix
check
- bool (default: True) - if False and self is nonsquare, may not raise an error message even if there is no solution. This is faster but more dangerous.

sage: A = matrix(QQ,4,2, [0, -1, 1, 0, -2, 2, 1, 0])
sage: B = matrix(QQ,2,2, [1, 0, 1, -1])
sage: X = A.solve_left(B)
sage: X*A == B
True

solve_right( )

If self is a matrix $ A$ , then this function returns a vector or matrix $ X$ such that $ A X = B$ . If $ B$ is a vector then $ X$ is a vector and if $ B$ is a matrix, then $ X$ is a matrix.

NOTE: In SAGE one can also write A B for A.solve_right(B), i.e., SAGE implements the ``the MATLAB/Octave backslash operator''.

Input:

B
- a matrix or vector
check
- bool (default: True) - if False and self is nonsquare, may not raise an error message even if there is no solution. This is faster but more dangerous.

Output: a matrix or vector

SEE ALSO: solve_left

sage: A = matrix(QQ, 3, [1,2,3,-1,2,5,2,3,1])
sage: b = vector(QQ,[1,2,3])
sage: x = A \ b; x
(-13/12, 23/12, -7/12)
sage: A * x
(1, 2, 3)

We solve with A nonsquare:

sage: A = matrix(QQ,2,4, [0, -1, 1, 0, -2, 2, 1, 0]); B = matrix(QQ,2,2, [1, 0, 1, -1])
sage: X = A.solve_right(B); X
[-3/2  1/2]
[  -1    0]
[   0    0]
[   0    0]
sage: A*X == B
True

Another nonsingular example:

sage: A = matrix(QQ,2,3, [1,2,3,2,4,6]); v = vector([-1/2,-1])
sage: x = A \ v; x
(-1/2, 0, 0)
sage: A*x == v
True

Same example but over $ \mathbf{Z}$ :

sage: A = matrix(ZZ,2,3, [1,2,3,2,4,6]); v = vector([-1,-2])
sage: A \ v
(-1, 0, 0)

An example in which there is no solution:

sage: A = matrix(QQ,2,3, [1,2,3,2,4,6]); v = vector([1,1])
sage: A \ v
Traceback (most recent call last):
...
ValueError: matrix equation has no solutions

A ValueError is raised if the input is invalid:

sage: A = matrix(QQ,4,2, [0, -1, 1, 0, -2, 2, 1, 0])
sage: B = matrix(QQ,2,2, [1, 0, 1, -1])
sage: X = A.solve_right(B)
Traceback (most recent call last):
...
ValueError: number of rows of self must equal number of rows of B

We solve with A singular:

sage: A = matrix(QQ,2,3, [1,2,3,2,4,6]); B = matrix(QQ,2,2, [6, -6, 12, -12])
sage: X = A.solve_right(B); X
[ 6 -6]
[ 0  0]
[ 0  0]
sage: A*X == B
True

We illustrate left associativity, etc., of the backslash operator.

sage: A = matrix(QQ, 2, [1,2,3,4])
sage: A \ A
[1 0]
[0 1]
sage: A \ A \ A
[1 2]
[3 4]
sage: A.parent()(1) \ A
[1 2]
[3 4]
sage: A \ (A \ A)
[  -2    1]
[ 3/2 -1/2]
sage: X = A \ (A - 2); X
[ 5 -2]
[-3  2]
sage: A * X
[-1  2]
[ 3  2]

Solving over a polynomial ring:

sage: x = polygen(QQ, 'x')
sage: A = matrix(2, [x,2*x,-5*x^2+1,3])
sage: v = vector([3,4*x - 2])
sage: X = A \ v
sage: X
((-8*x^2 + 4*x + 9)/(10*x^3 + x), (19*x^2 - 2*x - 3)/(10*x^3 + x))
sage: A * X == v
True

Solving a system over the p-adics:

sage: k = Qp(5,4)
sage: a = matrix(k, 3, [1,7,3,2,5,4,1,1,2]); a
[    1 + O(5^4) 2 + 5 + O(5^4)     3 + O(5^4)]
[    2 + O(5^4)     5 + O(5^5)     4 + O(5^4)]
[    1 + O(5^4)     1 + O(5^4)     2 + O(5^4)]
sage: v = vector(k, 3, [1,2,3])
sage: x = a \ v; x
(4 + 5 + 5^2 + 3*5^3 + O(5^4), 2 + 5 + 3*5^2 + 5^3 + O(5^4), 1 + 5 +
O(5^4))
sage: a * x == v
True

subdivide( )

Divides self into logical submatrices which can then be queried and extracted. If a subdivision already exists, this method forgets the previous subdivision and flushes the cache.

Input:

row_lines
- None, an integer, or a list of integers
col_lines
- None, an integer, or a list of integers

Output: changes self

NOTE: One may also pass a tuple into the first argument which will be interpreted as (row_lines, col_lines)

sage: M = matrix(5, 5, prime_range(100))
sage: M.subdivide(2,3); M
[ 2  3  5| 7 11]
[13 17 19|23 29]
[--------+-----]
[31 37 41|43 47]
[53 59 61|67 71]
[73 79 83|89 97]
sage: M.subdivision(0,0)
[ 2  3  5]
[13 17 19]
sage: M.subdivision(1,0)
[31 37 41]
[53 59 61]
[73 79 83]
sage: M.subdivision_entry(1,0,0,0)
31
sage: M.get_subdivisions()
([2], [3])
sage: M.subdivide(None, [1,3]); M
[ 2| 3  5| 7 11]
[13|17 19|23 29]
[31|37 41|43 47]
[53|59 61|67 71]
[73|79 83|89 97]

Degenerate cases work too.

sage: M.subdivide([2,5], [0,1,3]); M
[| 2| 3  5| 7 11]
[|13|17 19|23 29]
[+--+-----+-----]
[|31|37 41|43 47]
[|53|59 61|67 71]
[|73|79 83|89 97]
[+--+-----+-----]
sage: M.subdivision(0,0)
[]
sage: M.subdivision(0,1)
[ 2]
[13]
sage: M.subdivide([2,2,3], [0,0,1,1]); M
[|| 2|| 3  5  7 11]
[||13||17 19 23 29]
[++--++-----------]
[++--++-----------]
[||31||37 41 43 47]
[++--++-----------]
[||53||59 61 67 71]
[||73||79 83 89 97]
sage: M.subdivision(0,0)
[]
sage: M.subdivision(2,4)
[37 41 43 47]

Author: Robert Bradshaw (2007-06-14)

subdivision( )

Returns in immutable copy of the (i,j)th submatrix of self, according to a previously set subdivision.

Before a subdivision is set, the only valid arguments are (0,0) which returns self.

sage: M = matrix(3, 4, range(12))
sage: M.subdivide(1,2); M
[ 0  1| 2  3]
[-----+-----]
[ 4  5| 6  7]
[ 8  9|10 11]
sage: M.subdivision(0,0)
[0 1]
sage: M.subdivision(0,1)
[2 3]
sage: M.subdivision(1,0)
[4 5]
[8 9]

It handles size-zero subdivisions as well.

sage: M = matrix(3, 4, range(12))
sage: M.subdivide([0],[0,2,2,4]); M
[+-----++-----+]
[| 0  1|| 2  3|]
[| 4  5|| 6  7|]
[| 8  9||10 11|]
sage: M.subdivision(0,0)
[]
sage: M.subdivision(1,1)
[0 1]
[4 5]
[8 9]
sage: M.subdivision(1,2)
[]
sage: M.subdivision(1,0)
[]
sage: M.subdivision(0,1)
[]

subdivision_entry( )

Returns the x,y entry of the i,j submatrix of self.

sage: M = matrix(5, 5, range(25))
sage: M.subdivide(3,3); M
[ 0  1  2| 3  4]
[ 5  6  7| 8  9]
[10 11 12|13 14]
[--------+-----]
[15 16 17|18 19]
[20 21 22|23 24]
sage: M.subdivision_entry(0,0,1,2)
7
sage: M.subdivision(0,0)[1,2]
7
sage: M.subdivision_entry(0,1,0,0)
3
sage: M.subdivision_entry(1,0,0,0)
15
sage: M.subdivision_entry(1,1,1,1)
24

Even though this entry exists in the matrix, the index is invalid for the submatrix.

sage: M.subdivision_entry(0,0,4,0)
Traceback (most recent call last):
...
IndexError: Submatrix 0,0 has no entry 4,0

subs( )

sage: var('a,b,d,e')
(a, b, d, e)
sage: m = matrix([[a,b], [d,e]])
sage: m.substitute(a=1)
[1 b]
[d e]
sage: m.subs(a=b, b=d)
[b d]
[d e]

symplectic_form( )

Find a symplectic form for self if self is an anti-symmetric, alternating matrix defined over a field.

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

Raises a ValueError if not over a field, or self is not anti-symmetric, or self is not alternating.

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

A symplectic basis is a basis of the form $ z_1, \ldots, z_i, e_1,
\ldots, e_j, f_1, \ldots f_j$ such that * $ z_i M v^t$ = 0 for all vectors $ v$ ; * $ e_i M {e_j}^t = 0$ for all $ i,j$ ; * $ f_i M {f_j}^t = 0$ for all $ i,j$ ; * $ e_i M {f_i}^t = 1$ for all $ i$ ; * $ e_i M {f_j}^t = 0$ for all $ i$ not equal $ j$ .

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

sage: E = matrix(QQ, 8, 8, [0, -1/2, -2, 1/2, 2, 0, -2, 1, 1/2, 0, -1, -3, 0, 2, 5/2, -3, 2, 1, 0, 3/2, -1, 0, -1, -2, -1/2, 3, -3/2, 0, 1, 3/2, -1/2, -1/2, -2, 0, 1, -1, 0, 0, 1, -1, 0, -2, 0, -3/2, 0, 0, 1/2, -2, 2, -5/2, 1, 1/2, -1, -1/2, 0, -1, -1, 3, 2, 1/2, 1, 2, 1, 0]); E
[   0 -1/2   -2  1/2    2    0   -2    1]
[ 1/2    0   -1   -3    0    2  5/2   -3]
[   2    1    0  3/2   -1    0   -1   -2]
[-1/2    3 -3/2    0    1  3/2 -1/2 -1/2]
[  -2    0    1   -1    0    0    1   -1]
[   0   -2    0 -3/2    0    0  1/2   -2]
[   2 -5/2    1  1/2   -1 -1/2    0   -1]
[  -1    3    2  1/2    1    2    1    0]
sage: F, C = E.symplectic_form(); F
[ 0  0  0  0  1  0  0  0]
[ 0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  1  0]
[ 0  0  0  0  0  0  0  1]
[-1  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0  0  0]
[ 0  0 -1  0  0  0  0  0]
[ 0  0  0 -1  0  0  0  0]        
sage: F == C * E * C.transpose()
True

tensor_product( )

Returns the tensor product of two matrices.

sage: M1=Matrix(QQ,[[-1,0],[-1/2,-1]])
sage: M2=Matrix(ZZ,[[1,-1,2],[-2,4,8]])
sage: M1.tensor_product(M2)
[  -1    1   -2|   0    0    0]
[   2   -4   -8|   0    0    0]
[--------------+--------------]
[-1/2  1/2   -1|  -1    1   -2]
[   1   -2   -4|   2   -4   -8]
sage: M2.tensor_product(M1)
[  -1    0|   1    0|  -2    0]
[-1/2   -1| 1/2    1|  -1   -2]
[---------+---------+---------]
[   2    0|  -4    0|  -8    0]
[   1    2|  -2   -4|  -4   -8]

trace( )

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

sage: a = matrix(3,range(9)); a
[0 1 2]
[3 4 5]
[6 7 8]            
sage: a.trace()
12
sage: a = matrix({(1,1):10, (2,1):-3, (2,2):4/3}); a
[  0   0   0]
[  0  10   0]
[  0  -3 4/3]
sage: a.trace()
34/3

visualize_structure( )

Write a PNG image to 'filename' which visualizes self by putting black pixels in those positions which have nonzero entries.

White pixels are put at positions with zero entries. If 'maxsize' is given, then the maximal dimension in either x or y direction is set to 'maxsize' depending on which is bigger. If the image is scaled, the darkness of the pixel reflects how many of the represented entries are nonzero. So if e.g. one image pixel actually represents a 2x2 submatrix, the dot is darker the more of the four values are nonzero.

Input:

filename
- either a path or None in which case a filename in the current directory is chosen automatically (default:None)

maxsize - maximal dimension in either x or y direction of the resulting image. If None or a maxsize larger than max(self.nrows(),self.ncols()) is given the image will have the same pixelsize as the matrix dimensions (default: 512)

sage: M = random_matrix(CC, 4)
sage: M.visualize_structure()           # not tested

WARNING - the above *may* fail on some OSX systems due to some libpng.dylib issues.

wiedemann( )

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

Input:

i
- an integer
t
- an integer (default: 0) if t is nonzero, use only the first t linear recurrence relations.

IMPLEMENTATION: This is a toy implementation.

sage: t = matrix(QQ, 3, range(9)); t
[0 1 2]
[3 4 5]
[6 7 8]
sage: t.wiedemann(0)
x^2 - 12*x - 18
sage: t.charpoly()
x^3 - 12*x^2 - 18*x

Special Functions: __abs__,$ \,$ _backslash_,$ \,$ _charpoly_hessenberg,$ \,$ _charpoly_over_number_field,$ \,$ _column_ambient_module,$ \,$ _decomposition_spin_generic,$ \,$ _decomposition_using_kernels,$ \,$ _echelon_classical,$ \,$ _echelon_in_place_classical,$ \,$ _echelon_strassen,$ \,$ _echelonize_ring,$ \,$ _multiply_strassen,$ \,$ _row_ambient_module,$ \,$ _solve_right_general,$ \,$ _solve_right_nonsingular_square

__abs__( )

Synonym for self.determinant(...).

sage: a = matrix(QQ, 2,2, [1,2,3,4]); a
[1 2]
[3 4]
sage: abs(a)
-2

_backslash_( )

Used to compute $ A \ B$ , i.e., the backslash solver operator.

sage: A = matrix(QQ, 3, [1,2,4,2,3,1,0,1,2])
sage: B = matrix(QQ, 3, 2, [1,7,5, 2,1,3])
sage: C = A._backslash_(B); C
[  -1    1]
[13/5 -3/5]
[-4/5  9/5]
sage: A*C == B
True
sage: A._backslash_(B) == A \ B
True
sage: A._backslash_(B) == A.solve_right(B)
True

_charpoly_hessenberg( )

Transforms self in place to its Hessenberg form then computes and returns the coefficients of the characteristic polynomial of this matrix.

Input:

var
- name of the indeterminate of the charpoly.

The characteristic polynomial is represented as a vector of ints, where the constant term of the characteristic polynomial is the 0th coefficient of the vector.

sage: matrix(QQ,3,range(9))._charpoly_hessenberg('Z')
Z^3 - 12*Z^2 - 18*Z
sage: matrix(ZZ,3,range(9))._charpoly_hessenberg('Z')
Z^3 - 12*Z^2 - 18*Z
sage: matrix(GF(7),3,range(9))._charpoly_hessenberg('Z')
Z^3 + 2*Z^2 + 3*Z
sage: matrix(QQ['x'],3,range(9))._charpoly_hessenberg('Z')
Z^3 + (-12)*Z^2 + (-18)*Z
sage: matrix(ZZ['ZZ'],3,range(9))._charpoly_hessenberg('Z')
Z^3 + (-12)*Z^2 + (-18)*Z

_charpoly_over_number_field( )

Use PARI to compute the characteristic polynomial of self as a polynomial over the base ring.

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_over_number_field('Z')
Z^2 + (-2*a)*Z - 2*a + 1
sage: m._charpoly_over_number_field('a')(m) == 0
True
sage: m = matrix(K, [[0, a, 0], [-a, 0, 0], [0, 0, 0]])
sage: m._charpoly_over_number_field('Z')
Z^3 + 2*Z

The remaining tests are indirect:

sage: L.<b> = K.extension(x^3 - a)
sage: m = matrix(L, [[b+a, 1], [a, b^2-2]])
sage: m.charpoly('Z')
Z^2 + ((-1)*b^2 + (-1)*b - a + 2)*Z + a*b^2 + (-2)*b - 2*a
sage: m.charpoly('a')
a^2 + ((-1)*b^2 + (-1)*b - a + 2)*a + a*b^2 + (-2)*b - 2*a
sage: m.charpoly('a')(m) == 0
True

sage: M.<c> = L.extension(x^2 - a*x + b)
sage: m = matrix(M, [[a+b+c, 0, b], [0, c, 1], [a-1, b^2+1, 2]])
sage: f = m.charpoly('Z'); f
Z^3 + ((-2)*c + (-1)*b - a - 2)*Z^2 + ((b + 2*a + 4)*c + (-1)*b^2 + (-a +
2)*b + 2*a - 1)*Z + (b^2 + (a - 3)*b - 4*a + 1)*c + a*b^2 + 3*b + 2*a
sage: f(m) == 0
True
sage: f.base_ring() is M
True

_column_ambient_module( )

_decomposition_spin_generic( )

Compute the decomposition of this matrix using the spin algorithm.

Input:

self
- a matrix with field entries

Output: a list of reduced row echelon form basis

Author: William Stein

_decomposition_using_kernels( )

_echelon_classical( )

Return the echelon form of self.

_echelon_in_place_classical( )

Return the echelon form of self and set the pivots of self.

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

_echelon_strassen( )

In place Strassen echelon of self, and sets the pivots.

ALGORITHM: Custom algorithm for arbitrary size matrices designed by David Harvey and Robert Bradshaw, based on Strassen's algorithm.

sage: A = matrix(QQ, 4, range(16))
sage: A._echelon_strassen(2)
sage: A
[ 1  0 -1 -2]
[ 0  1  2  3]
[ 0  0  0  0]
[ 0  0  0  0]

_echelonize_ring( )

Echelonize self in place, where the base ring of self is assumed to be a ring (not a field).

Right now this *only* works over ZZ; otherwise a NotImplementedError is raised. In the special case of sparse matrices over ZZ it makes them dense, gets the echelon form of the dense matrix, then sets self equal to the result.

sage: a = matrix(ZZ, 3, 4, [1..12], sparse=True); a
[ 1  2  3  4]
[ 5  6  7  8]
[ 9 10 11 12]
sage: a._echelonize_ring()
sage: a
[ 1  2  3  4]
[ 0  4  8 12]
[ 0  0  0  0]

_multiply_strassen( )

Multiply self by the matrix right using a Strassen-based asymptotically fast arithmetic algorithm.

ALGORITHM: Custom algorithm for arbitrary size matrices designed by David Harvey and Robert Bradshaw, based on Strassen's algorithm.

Input:

cutoff
- integer (default: 0 - let class decide).

sage: a = matrix(ZZ,4,range(16))
sage: a._multiply_strassen(a,2)
[ 56  62  68  74]
[152 174 196 218]
[248 286 324 362]
[344 398 452 506]

_row_ambient_module( )

_solve_right_general( )

This is used internally by the solve_right command to solve for self*X = B when self is not square or not of full rank. It does some linear algebra, then solves a full-rank square system.

Input:

B
- a matrix
check
- bool (default: True); if False, if there is no solution this function will not detect that fact.

Output: matrix

sage: A = matrix(QQ,2,3, [1,2,3,2,4,6]); B = matrix(QQ,2,2, [6, -6, 12, -12])
sage: A._solve_right_general(B)
[ 6 -6]
[ 0  0]
[ 0  0]

_solve_right_nonsingular_square( )

If self is a matrix $ A$ of full rank, then this function returns a matrix $ X$ such that $ A X = B$ .

SEE ALSO: self.solve_right and self.solve_left

Input:

B
- a matrix
check_rank
- bool (default: True)

Output: matrix

sage: A = matrix(QQ,3,[1,2,4,5,3,1,1,2,-1])
sage: B = matrix(QQ,3,2,[1,5,1,2,1,5])
sage: A._solve_right_nonsingular_square(B)
[ -1/7 -11/7]
[  4/7  23/7]
[    0     0]
sage: A._solve_right_nonsingular_square(B, check_rank=False)
[ -1/7 -11/7]
[  4/7  23/7]
[    0     0]
sage: X = A._solve_right_nonsingular_square(B, check_rank=False)
sage: A*X == B
True

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