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
) |
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.
) |
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
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
) |
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
) |
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:
First a matrix over
:
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
:
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
:
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
:
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
) |
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]
) |
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]
) |
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]
) |
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:
NOTE: If the base ring is not a field, the kernel algorithm is used.
(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) ]
) |
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) ]
) |
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
.
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
) |
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
) |
Synonym for self.determinant(...).
sage: A = MatrixSpace(Integers(8),3)([1,7,3, 1,1,1, 3,4,5]) sage: A.det() 6
) |
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
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
) |
Return the echelon form of self.
Input:
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]
) |
Transform self into a matrix in echelon form over the same base ring as self.
Input:
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]
) |
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:
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
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
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: []) ]
) |
Return the factorization of the characteristic polynomial of self.
Input:
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 elements in this matrix satisfying the constraints
in the function
. The function is evaluated on each element of
the matrix .
Input:
indices
is not specified, return a matrix with 1 where 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
) |
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]
) |
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:
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
) |
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
) |
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
) |
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()).
) |
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
) |
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]
) |
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]
) |
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
) |
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
) |
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:
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
) |
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:
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
:
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]
) |
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:
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)
) |
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:
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
:
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]
) |
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
) |
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]
) |
Computes the largest integer n such that the list of vectors
are linearly independent, and returns
that list.
Input:
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)]
) |
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
) |
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:
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]
) |
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
) |
Return the p-norm of this matrix, where
can be 1, 2,
, or
the Frobenius norm.
Input:
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
) |
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
) |
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:
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]
) |
Calculate and return the permanent of this
matrix using
Ryser's algorithm.
Let
be an
matrix over any
commutative ring, with
. The permanent of
is
where the summation extends over all one-to-one functions
The product
is called
diagonal product. So the permanent of an
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:
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:
) |
Calculates the permanental
-minor of a
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:
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)
) |
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:
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]
) |
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 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:
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]
) |
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:
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
) |
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:
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)
) |
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:
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]
) |
Return the right kernel of this matrix, as a vector space. This is the space of vectors x such that self*x=0.
Input:
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
:
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)]
) |
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
) |
Returns rook vector of this matrix.
Let
be a general
by
(0,1)-matrix with
.
We identify
with a chessboard where rooks can be placed on
the fields corresponding with
. The number
(the permanental
-minor) counts the number of ways
to place
rooks on this board so that no two rooks can
attack another.
The rook vector is the list consisting of
.
The rook polynomial is defined by
.
Input:
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)
) |
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]
) |
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]
) |
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]
) |
If self is a matrix
, then this function returns a vector
or matrix
such that
. If
is a vector then
is a vector and if
is a matrix, then
is a matrix.
Input:
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
) |
If self is a matrix
, then this function returns a vector
or matrix
such that
. If
is a vector then
is a vector and if
is a matrix, then
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:
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
:
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
) |
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:
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)
) |
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) []
) |
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
) |
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]
) |
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
. Alternating means that the
diagonal of
is identically zero.
A symplectic basis is a basis of the form
such that
*
= 0 for all vectors
;
*
for all
;
*
for all
;
*
for all
;
*
for all
not equal
.
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
) |
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]
) |
Return the trace of self, which is the sum of the diagonal entries of self.
Input:
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
) |
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:
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.
) |
Application of Wiedemann's algorithm to the i-th standard basis vector.
Input:
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
) |
Synonym for self.determinant(...).
sage: a = matrix(QQ, 2,2, [1,2,3,4]); a [1 2] [3 4] sage: abs(a) -2
) |
Used to compute
, 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
) |
Transforms self in place to its Hessenberg form then computes and returns the coefficients of the characteristic polynomial of this matrix.
Input:
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
) |
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
) |
) |
Compute the decomposition of this matrix using the spin algorithm.
Input:
Author: William Stein
) |
) |
Return the echelon form of self.
) |
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]
) |
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 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 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:
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]
) |
) |
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:
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]
) |
If self is a matrix
of full rank, then this function
returns a matrix
such that
.
SEE ALSO: self.solve_right
and self.solve_left
Input:
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.