# Introducing the domainmatrix of the poly module#

This page introduces the idea behind domainmatrix which is used in SymPy’s sympy.polys module. This is a relatively advanced topic so for a better understanding it is recommended to read about Domain and DDM along with sympy.matrices module.

## What is domainmatrix?#

It is way of associating Matrix with Domain.

A domainmatrix represents a matrix with elements that are in a particular Domain. Each domainmatrix internally wraps a DDM which is used for the lower-level operations. The idea is that the domainmatrix class provides the convenience routines for converting between Expr and the poly domains as well as unifying matrices with different domains.

In general, we represent a matrix without concerning about the Domain as:
>>> from sympy import Matrix
>>> from sympy.polys.matrices import DomainMatrix
>>> A = Matrix([
... [1, 2],
... [3, 4]])
>>> A
Matrix([
[1, 2],
[3, 4]])


Module for the DomainMatrix class.

A DomainMatrix represents a matrix with elements that are in a particular Domain. Each DomainMatrix internally wraps a DDM which is used for the lower-level operations. The idea is that the DomainMatrix class provides the convenience routines for converting between Expr and the poly domains as well as unifying matrices with different domains.

sympy.polys.matrices.domainmatrix.DM(rows, domain)[source]#

Convenient alias for DomainMatrix.from_list

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DM
>>> DM([[1, 2], [3, 4]], ZZ)
DomainMatrix([[1, 2], [3, 4]], (2, 2), ZZ)

class sympy.polys.matrices.domainmatrix.DomainMatrix(rows, shape, domain, *, fmt=None)[source]#

Associate Matrix with Domain

Explanation

DomainMatrix uses Domain for its internal representation which makes it faster than the SymPy Matrix class (currently) for many common operations, but this advantage makes it not entirely compatible with Matrix. DomainMatrix are analogous to numpy arrays with “dtype”. In the DomainMatrix, each element has a domain such as ZZ or QQ<a>.

Examples

Creating a DomainMatrix from the existing Matrix class:

>>> from sympy import Matrix
>>> from sympy.polys.matrices import DomainMatrix
>>> Matrix1 = Matrix([
...    [1, 2],
...    [3, 4]])
>>> A = DomainMatrix.from_Matrix(Matrix1)
>>> A
DomainMatrix({0: {0: 1, 1: 2}, 1: {0: 3, 1: 4}}, (2, 2), ZZ)


Directly forming a DomainMatrix:

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> A
DomainMatrix([[1, 2], [3, 4]], (2, 2), ZZ)


Adds two DomainMatrix matrices of the same Domain

Parameters:

A, B: DomainMatrix

Returns:

DomainMatrix

Raises:

DMShapeError

If the dimensions of the two DomainMatrix are not equal

ValueError

If the domain of the two DomainMatrix are not same

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> B = DomainMatrix([
...    [ZZ(4), ZZ(3)],
...    [ZZ(2), ZZ(1)]], (2, 2), ZZ)

>>> A.add(B)
DomainMatrix([[5, 5], [5, 5]], (2, 2), ZZ)


Adjugate and determinant of a square DomainMatrix.

Returns:

The adjugate matrix and determinant of this matrix.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DM
>>> A = DM([
...     [ZZ(1), ZZ(2)],
...     [ZZ(3), ZZ(4)]], ZZ)
DomainMatrix([[4, -2], [-3, 1]], (2, 2), ZZ)
>>> detA
-2


adjugate

det

Returns only the determinant.

inv_den

Returns a matrix/denominator pair representing the inverse matrix but perhaps differing from the adjugate and determinant by a common factor.

Return the polynomial $$p$$ such that $$p(A) = adj(A)$$ and also the determinant of $$A$$.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices import DM
>>> A = DM([[QQ(1), QQ(2)], [QQ(3), QQ(4)]], QQ)
>>> p
[-1, 5]
>>> p_A = A.eval_poly(p)
>>> p_A
DomainMatrix([[4, -2], [-3, 1]], (2, 2), QQ)
>>> p*A**1 + p*A**0 == p_A
True
True
>>> A * A.adjugate() == detA * A.eye(A.shape, A.domain).to_dense()
True


Adjugate of a square DomainMatrix.

The adjugate matrix is the transpose of the cofactor matrix and is related to the inverse by:

adj(A) = det(A) * A.inv()


Unlike the inverse matrix the adjugate matrix can be computed and expressed without division or fractions in the ground domain.

Returns:

DomainMatrix

The adjugate matrix of this matrix with the same domain.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DM
>>> A = DM([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], ZZ)
DomainMatrix([[4, -2], [-3, 1]], (2, 2), ZZ)

cancel_denom(denom)[source]#

Cancel factors between a matrix and a denominator.

Returns a matrix and denominator on lowest terms.

Requires gcd in the ground domain.

Methods like solve_den(), inv_den() and rref_den() return a matrix and denominator but not necessarily on lowest terms. Reduction to lowest terms without fractions can be performed with cancel_denom().

Examples

>>> from sympy.polys.matrices import DM
>>> from sympy import ZZ
>>> M = DM([[2, 2, 0],
...         [0, 2, 2],
...         [0, 0, 2]], ZZ)
>>> Minv, den = M.inv_den()
>>> Minv.to_Matrix()
Matrix([
[1, -1,  1],
[0,  1, -1],
[0,  0,  1]])
>>> den
2
>>> Minv_reduced, den_reduced = Minv.cancel_denom(den)
>>> Minv_reduced.to_Matrix()
Matrix([
[1, -1,  1],
[0,  1, -1],
[0,  0,  1]])
>>> den_reduced
2
>>> Minv_reduced.to_field() / den_reduced == Minv.to_field() / den
True


The denominator is made canonical with respect to units (e.g. a negative denominator is made positive):

>>> M = DM([[2, 2, 0]], ZZ)
>>> den = ZZ(-4)
>>> M.cancel_denom(den)
(DomainMatrix([[-1, -1, 0]], (1, 3), ZZ), 2)


Any factor common to _all_ elements will be cancelled but there can still be factors in common between _some_ elements of the matrix and the denominator. To cancel factors between each element and the denominator, use cancel_denom_elementwise() or otherwise convert to a field and use division:

>>> M = DM([[4, 6]], ZZ)
>>> den = ZZ(12)
>>> M.cancel_denom(den)
(DomainMatrix([[2, 3]], (1, 2), ZZ), 6)
>>> numers, denoms = M.cancel_denom_elementwise(den)
>>> numers
DomainMatrix([[1, 1]], (1, 2), ZZ)
>>> denoms
DomainMatrix([[3, 2]], (1, 2), ZZ)
>>> M.to_field() / den
DomainMatrix([[1/3, 1/2]], (1, 2), QQ)

cancel_denom_elementwise(denom)[source]#

Cancel factors between the elements of a matrix and a denominator.

Returns a matrix of numerators and matrix of denominators.

Requires gcd in the ground domain.

Examples

>>> from sympy.polys.matrices import DM
>>> from sympy import ZZ
>>> M = DM([[2, 3], [4, 12]], ZZ)
>>> denom = ZZ(6)
>>> numers, denoms = M.cancel_denom_elementwise(denom)
>>> numers.to_Matrix()
Matrix([
[1, 1],
[2, 2]])
>>> denoms.to_Matrix()
Matrix([
[3, 2],
[3, 1]])
>>> M_frac = (M.to_field() / denom).to_Matrix()
>>> M_frac
Matrix([
[1/3, 1/2],
[2/3,   2]])
>>> denoms_inverted = denoms.to_Matrix().applyfunc(lambda e: 1/e)
>>> numers.to_Matrix().multiply_elementwise(denoms_inverted) == M_frac
True


Use cancel_denom() to cancel factors between the matrix and the denominator while preserving the form of a matrix with a scalar denominator.

charpoly()[source]#

Characteristic polynomial of a square matrix.

Computes the characteristic polynomial in a fully expanded form using division free arithmetic. If a factorization of the characteristic polynomial is needed then it is more efficient to call charpoly_factor_list() than calling charpoly() and then factorizing the result.

Returns:

list: list of DomainElement

coefficients of the characteristic polynomial

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)

>>> A.charpoly()
[1, -5, -2]


charpoly_factor_list

Compute the factorisation of the characteristic polynomial.

charpoly_factor_blocks

A partial factorisation of the characteristic polynomial that can be computed more efficiently than either the full factorisation or the fully expanded polynomial.

charpoly_base()[source]#

Base case for charpoly_factor_blocks() after block decomposition.

This method is used internally by charpoly_factor_blocks() as the base case for computing the characteristic polynomial of a block. It is more efficient to call charpoly_factor_blocks(), charpoly() or charpoly_factor_list() rather than call this method directly.

This will use either the dense or the sparse implementation depending on the sparsity of the matrix and will clear denominators if possible before calling charpoly_berk() to compute the characteristic polynomial using the Berkowitz algorithm.

charpoly_berk()[source]#

Compute the characteristic polynomial using the Berkowitz algorithm.

This method directly calls the underlying implementation of the Berkowitz algorithm (sympy.polys.matrices.dense.ddm_berk() or sympy.polys.matrices.sdm.sdm_berk()).

This is used by charpoly() and other methods as the base case for for computing the characteristic polynomial. However those methods will apply other optimizations such as block decomposition, clearing denominators and converting between dense and sparse representations before calling this method. It is more efficient to call those methods instead of this one but this method is provided for direct access to the Berkowitz algorithm.

Examples

>>> from sympy.polys.matrices import DM
>>> from sympy import QQ
>>> M = DM([[6, -1, 0, 0],
...         [9, 12, 0, 0],
...         [0,  0, 1, 2],
...         [0,  0, 5, 6]], QQ)
>>> M.charpoly_berk()
[1, -25, 203, -495, -324]

charpoly_factor_blocks()[source]#

Partial factorisation of the characteristic polynomial.

This factorisation arises from a block structure of the matrix (if any) and so the factors are not guaranteed to be irreducible. The charpoly_factor_blocks() method is the most efficient way to get a representation of the characteristic polynomial but the result is neither fully expanded nor fully factored.

Returns:

list: list of pairs (factor, multiplicity)

A partial factorization of the characteristic polynomial.

Examples

>>> from sympy.polys.matrices import DM
>>> from sympy import ZZ
>>> M = DM([[6, -1, 0, 0],
...         [9, 12, 0, 0],
...         [0,  0, 1, 2],
...         [0,  0, 5, 6]], ZZ)


This computes a partial factorization using only the block structure of the matrix to reveal factors:

>>> M.charpoly_factor_blocks()
[([1, -18, 81], 1), ([1, -7, -4], 1)]


These factors correspond to the two diagonal blocks in the matrix:

>>> DM([[6, -1], [9, 12]], ZZ).charpoly()
[1, -18, 81]
>>> DM([[1, 2], [5, 6]], ZZ).charpoly()
[1, -7, -4]


Use charpoly_factor_list() to get a complete factorization into irreducibles:

>>> M.charpoly_factor_list()
[([1, -9], 2), ([1, -7, -4], 1)]


Use charpoly() to get the expanded characteristic polynomial:

>>> M.charpoly()
[1, -25, 203, -495, -324]


charpoly

Compute the fully expanded characteristic polynomial.

charpoly_factor_list

Compute a full factorization of the characteristic polynomial.

charpoly_factor_list()[source]#

Full factorization of the characteristic polynomial.

Returns:

list: list of pairs (factor, multiplicity)

A full factorization of the characteristic polynomial.

Examples

>>> from sympy.polys.matrices import DM
>>> from sympy import ZZ
>>> M = DM([[6, -1, 0, 0],
...         [9, 12, 0, 0],
...         [0,  0, 1, 2],
...         [0,  0, 5, 6]], ZZ)


Compute the factorization of the characteristic polynomial:

>>> M.charpoly_factor_list()
[([1, -9], 2), ([1, -7, -4], 1)]


Use charpoly() to get the unfactorized characteristic polynomial:

>>> M.charpoly()
[1, -25, 203, -495, -324]


The same calculations with Matrix:

>>> M.to_Matrix().charpoly().as_expr()
lambda**4 - 25*lambda**3 + 203*lambda**2 - 495*lambda - 324
>>> M.to_Matrix().charpoly().as_expr().factor()
(lambda - 9)**2*(lambda**2 - 7*lambda - 4)


charpoly

Expanded form of the characteristic polynomial.

charpoly_factor_blocks

A partial factorisation of the characteristic polynomial that can be computed more efficiently.

choose_domain(**opts)[source]#

Convert to a domain found by construct_domain().

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DM
>>> M = DM([[1, 2], [3, 4]], ZZ)
>>> M
DomainMatrix([[1, 2], [3, 4]], (2, 2), ZZ)
>>> M.choose_domain(field=True)
DomainMatrix([[1, 2], [3, 4]], (2, 2), QQ)

>>> from sympy.abc import x
>>> M = DM([[1, x], [x**2, x**3]], ZZ[x])
>>> M.choose_domain(field=True).domain
ZZ(x)


Keyword arguments are passed to construct_domain().

clear_denoms(convert=False)[source]#

Clear denominators, but keep the domain unchanged.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices import DM
>>> A = DM([[(1,2), (1,3)], [(1,4), (1,5)]], QQ)
>>> den, Anum = A.clear_denoms()
>>> den.to_sympy()
60
>>> Anum.to_Matrix()
Matrix([
[30, 20],
[15, 12]])
>>> den * A == Anum
True


The numerator matrix will be in the same domain as the original matrix unless convert is set to True:

>>> A.clear_denoms().domain
QQ
>>> A.clear_denoms(convert=True).domain
ZZ


The denominator is always in the associated ring:

>>> A.clear_denoms().domain
ZZ
>>> A.domain.get_ring()
ZZ

columnspace()[source]#

Returns the columnspace for the DomainMatrix

Returns:

DomainMatrix

The columns of this matrix form a basis for the columnspace.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [QQ(1), QQ(-1)],
...    [QQ(2), QQ(-2)]], (2, 2), QQ)
>>> A.columnspace()
DomainMatrix([, ], (2, 1), QQ)

content()[source]#

Return the gcd of the elements of the matrix.

Requires gcd in the ground domain.

Examples

>>> from sympy.polys.matrices import DM
>>> from sympy import ZZ
>>> M = DM([[2, 4], [4, 12]], ZZ)
>>> M.content()
2

convert_to(K)[source]#

Change the domain of DomainMatrix to desired domain or field

Parameters:

K : Represents the desired domain or field.

Alternatively, None may be passed, in which case this method just returns a copy of this DomainMatrix.

Returns:

DomainMatrix

DomainMatrix with the desired domain or field

Examples

>>> from sympy import ZZ, ZZ_I
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)

>>> A.convert_to(ZZ_I)
DomainMatrix([[1, 2], [3, 4]], (2, 2), ZZ_I)

det()[source]#

Returns the determinant of a square DomainMatrix.

Returns:

determinant: DomainElement

Determinant of the matrix.

Raises:

ValueError

If the domain of DomainMatrix is not a Field

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)

>>> A.det()
-2

classmethod diag(diagonal, domain, shape=None)[source]#

Return diagonal matrix with entries from diagonal.

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy import ZZ
>>> DomainMatrix.diag([ZZ(5), ZZ(6)], ZZ)
DomainMatrix({0: {0: 5}, 1: {1: 6}}, (2, 2), ZZ)

diagonal()[source]#

Get the diagonal entries of the matrix as a list.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DM
>>> M = DM([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], ZZ)
>>> M.diagonal()
[1, 4]


eval_poly(p)[source]#

Evaluate polynomial function of a matrix $$p(A)$$.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices import DM
>>> A = DM([[QQ(1), QQ(2)], [QQ(3), QQ(4)]], QQ)
>>> p = [QQ(1), QQ(2), QQ(3)]
>>> p_A = A.eval_poly(p)
>>> p_A
DomainMatrix([[12, 14], [21, 33]], (2, 2), QQ)
>>> p_A == p*A**2 + p*A + p*A**0
True

eval_poly_mul(p, B)[source]#

Evaluate polynomial matrix product $$p(A) \times B$$.

Evaluate the polynomial matrix product $$p(A) \times B$$ using Horner’s method without creating the matrix $$p(A)$$ explicitly. If $$B$$ is a column matrix then this method will only use matrix-vector multiplies and no matrix-matrix multiplies are needed.

If $$B$$ is square or wide or if $$A$$ can be represented in a simpler domain than $$B$$ then it might be faster to evaluate $$p(A)$$ explicitly (see eval_poly()) and then multiply with $$B$$.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices import DM
>>> A = DM([[QQ(1), QQ(2)], [QQ(3), QQ(4)]], QQ)
>>> b = DM([[QQ(5)], [QQ(6)]], QQ)
>>> p = [QQ(1), QQ(2), QQ(3)]
>>> p_A_b = A.eval_poly_mul(p, b)
>>> p_A_b
DomainMatrix([, ], (2, 1), QQ)
>>> p_A_b == p*A**2*b + p*A*b + p*b
True
>>> A.eval_poly_mul(p, b) == A.eval_poly(p)*b
True

classmethod eye(shape, domain)[source]#

Return identity matrix of size n or shape (m, n).

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy import QQ
>>> DomainMatrix.eye(3, QQ)
DomainMatrix({0: {0: 1}, 1: {1: 1}, 2: {2: 1}}, (3, 3), QQ)

classmethod from_Matrix(M, fmt='sparse', **kwargs)[source]#

Convert Matrix to DomainMatrix

Parameters:

M: Matrix

Returns:

Returns DomainMatrix with identical elements as M

Examples

>>> from sympy import Matrix
>>> from sympy.polys.matrices import DomainMatrix
>>> M = Matrix([
...    [1.0, 3.4],
...    [2.4, 1]])
>>> A = DomainMatrix.from_Matrix(M)
>>> A
DomainMatrix({0: {0: 1.0, 1: 3.4}, 1: {0: 2.4, 1: 1.0}}, (2, 2), RR)


We can keep internal representation as ddm using fmt=’dense’ >>> from sympy import Matrix, QQ >>> from sympy.polys.matrices import DomainMatrix >>> A = DomainMatrix.from_Matrix(Matrix([[QQ(1, 2), QQ(3, 4)], [QQ(0, 1), QQ(0, 1)]]), fmt=’dense’) >>> A.rep [[1/2, 3/4], [0, 0]]

classmethod from_dict_sympy(nrows, ncols, elemsdict, **kwargs)[source]#
Parameters:

nrows: number of rows

ncols: number of cols

elemsdict: dict of dicts containing non-zero elements of the DomainMatrix

Returns:

DomainMatrix containing elements of elemsdict

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy.abc import x,y,z
>>> elemsdict = {0: {0:x}, 1:{1: y}, 2: {2: z}}
>>> A = DomainMatrix.from_dict_sympy(3, 3, elemsdict)
>>> A
DomainMatrix({0: {0: x}, 1: {1: y}, 2: {2: z}}, (3, 3), ZZ[x,y,z])

classmethod from_dok(dok, shape, domain)[source]#

Create DomainMatrix from dictionary of keys (dok) format.

See to_dok() for explanation.

from_flat_nz(elements, data, domain)[source]#

Reconstruct DomainMatrix after calling to_flat_nz().

See to_flat_nz() for explanation.

classmethod from_list(rows, domain)[source]#

Convert a list of lists into a DomainMatrix

Parameters:

rows: list of lists

Each element of the inner lists should be either the single arg, or tuple of args, that would be passed to the domain constructor in order to form an element of the domain. See examples.

Returns:

DomainMatrix containing elements defined in rows

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy import FF, QQ, ZZ
>>> A = DomainMatrix.from_list([[1, 0, 1], [0, 0, 1]], ZZ)
>>> A
DomainMatrix([[1, 0, 1], [0, 0, 1]], (2, 3), ZZ)
>>> B = DomainMatrix.from_list([[1, 0, 1], [0, 0, 1]], FF(7))
>>> B
DomainMatrix([[1 mod 7, 0 mod 7, 1 mod 7], [0 mod 7, 0 mod 7, 1 mod 7]], (2, 3), GF(7))
>>> C = DomainMatrix.from_list([[(1, 2), (3, 1)], [(1, 4), (5, 1)]], QQ)
>>> C
DomainMatrix([[1/2, 3], [1/4, 5]], (2, 2), QQ)

classmethod from_list_flat(elements, shape, domain)[source]#

Create DomainMatrix from flat list.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> element_list = [ZZ(1), ZZ(2), ZZ(3), ZZ(4)]
>>> A = DomainMatrix.from_list_flat(element_list, (2, 2), ZZ)
>>> A
DomainMatrix([[1, 2], [3, 4]], (2, 2), ZZ)
>>> A == A.from_list_flat(A.to_list_flat(), A.shape, A.domain)
True

classmethod from_list_sympy(nrows, ncols, rows, **kwargs)[source]#

Convert a list of lists of Expr into a DomainMatrix using construct_domain

Parameters:

nrows: number of rows

ncols: number of columns

rows: list of lists

Returns:

DomainMatrix containing elements of rows

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy.abc import x, y, z
>>> A = DomainMatrix.from_list_sympy(1, 3, [[x, y, z]])
>>> A
DomainMatrix([[x, y, z]], (1, 3), ZZ[x,y,z])

classmethod from_rep(rep)[source]#

Create a new DomainMatrix efficiently from DDM/SDM.

Parameters:

rep: SDM or DDM

The internal sparse or dense representation of the matrix.

Returns:

DomainMatrix

Examples

Create a DomainMatrix with an dense internal representation as DDM:

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy.polys.matrices.ddm import DDM
>>> drep = DDM([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> dM = DomainMatrix.from_rep(drep)
>>> dM
DomainMatrix([[1, 2], [3, 4]], (2, 2), ZZ)


Create a DomainMatrix with a sparse internal representation as SDM:

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import ZZ
>>> drep = SDM({0:{1:ZZ(1)},1:{0:ZZ(2)}}, (2, 2), ZZ)
>>> dM = DomainMatrix.from_rep(drep)
>>> dM
DomainMatrix({0: {1: 1}, 1: {0: 2}}, (2, 2), ZZ)


Notes

This takes ownership of rep as its internal representation. If rep is being mutated elsewhere then a copy should be provided to from_rep. Only minimal verification or checking is done on rep as this is supposed to be an efficient internal routine.

hstack(*B)[source]#

Horizontally stack the given matrices.

Parameters:

B: DomainMatrix

Matrices to stack horizontally.

Returns:

DomainMatrix

DomainMatrix by stacking horizontally.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix

>>> A = DomainMatrix([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> B = DomainMatrix([[ZZ(5), ZZ(6)], [ZZ(7), ZZ(8)]], (2, 2), ZZ)
>>> A.hstack(B)
DomainMatrix([[1, 2, 5, 6], [3, 4, 7, 8]], (2, 4), ZZ)

>>> C = DomainMatrix([[ZZ(9), ZZ(10)], [ZZ(11), ZZ(12)]], (2, 2), ZZ)
>>> A.hstack(B, C)
DomainMatrix([[1, 2, 5, 6, 9, 10], [3, 4, 7, 8, 11, 12]], (2, 6), ZZ)

inv()[source]#

Finds the inverse of the DomainMatrix if exists

Returns:

DomainMatrix

DomainMatrix after inverse

Raises:

ValueError

If the domain of DomainMatrix not a Field

DMNonSquareMatrixError

If the DomainMatrix is not a not Square DomainMatrix

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...     [QQ(2), QQ(-1), QQ(0)],
...     [QQ(-1), QQ(2), QQ(-1)],
...     [QQ(0), QQ(0), QQ(2)]], (3, 3), QQ)
>>> A.inv()
DomainMatrix([[2/3, 1/3, 1/6], [1/3, 2/3, 1/3], [0, 0, 1/2]], (3, 3), QQ)

inv_den(method=None)[source]#

Return the inverse as a DomainMatrix with denominator.

Parameters:

method : str, optional

The method to use to compute the inverse. Can be one of None, 'rref' or 'charpoly'. If None then the method is chosen automatically (see solve_den() for details).

Returns:

(inv, den) : (DomainMatrix, DomainElement)

The inverse matrix and its denominator.

This is more or less equivalent to adj_det() except that inv

and den are not guaranteed to be the adjugate and inverse. The

ratio inv/den is equivalent to adj/det but some factors

might be cancelled between inv and den. In simple cases this

might just be a minus sign so that (inv, den) == (-adj, -det) but

factors more complicated than -1 can also be cancelled.

Cancellation is not guaranteed to be complete so inv and den

may not be on lowest terms. The denominator den will be zero if and

only if the determinant is zero.

If the actual adjugate and determinant are needed, use adj_det()

instead. If the intention is to compute the inverse matrix or solve a

system of equations then inv_den() is more efficient.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...     [ZZ(2), ZZ(-1), ZZ(0)],
...     [ZZ(-1), ZZ(2), ZZ(-1)],
...     [ZZ(0), ZZ(0), ZZ(2)]], (3, 3), ZZ)
>>> Ainv, den = A.inv_den()
>>> den
6
>>> Ainv
DomainMatrix([[4, 2, 1], [2, 4, 2], [0, 0, 3]], (3, 3), ZZ)
>>> A * Ainv == den * A.eye(A.shape, A.domain).to_dense()
True

property is_diagonal#

True if the matrix is diagonal.

Can return true for non-square matrices. A matrix is diagonal if M[i,j] == 0 whenever i != j.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DM
>>> M = DM([[ZZ(1), ZZ(0)], [ZZ(0), ZZ(1)]], ZZ)
>>> M.is_diagonal
True

property is_lower#

Says whether this matrix is lower-triangular. True can be returned even if the matrix is not square.

property is_square#

True if the matrix is square.

property is_upper#

Says whether this matrix is upper-triangular. True can be returned even if the matrix is not square.

lll(delta=MPQ(3, 4))[source]#

Performs the Lenstra–Lenstra–Lovász (LLL) basis reduction algorithm. See [R735] and [R736].

Parameters:

delta : QQ, optional

The Lovász parameter. Must be in the interval (0.25, 1), with larger values producing a more reduced basis. The default is 0.75 for historical reasons.

Returns:

The reduced basis as a DomainMatrix over ZZ.

Throws

DMValueError: if delta is not in the range (0.25, 1) DMShapeError: if the matrix is not of shape (m, n) with m <= n DMDomainError: if the matrix domain is not ZZ DMRankError: if the matrix contains linearly dependent rows

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.matrices import DM
>>> x = DM([[1, 0, 0, 0, -20160],
...         [0, 1, 0, 0, 33768],
...         [0, 0, 1, 0, 39578],
...         [0, 0, 0, 1, 47757]], ZZ)
>>> y = DM([[10, -3, -2, 8, -4],
...         [3, -9, 8, 1, -11],
...         [-3, 13, -9, -3, -9],
...         [-12, -7, -11, 9, -1]], ZZ)
>>> assert x.lll(delta=QQ(5, 6)) == y


Notes

The implementation is derived from the Maple code given in Figures 4.3 and 4.4 of [R737] (pp.68-69). It uses the efficient method of only calculating state updates as they are required.

References

[R737] (1,2)

Murray R. Bremner, “Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications”

lll_transform(delta=MPQ(3, 4))[source]#

Performs the Lenstra–Lenstra–Lovász (LLL) basis reduction algorithm and returns the reduced basis and transformation matrix.

Explanation

Parameters, algorithm and basis are the same as for lll() except that the return value is a tuple $$(B, T)$$ with $$B$$ the reduced basis and $$T$$ a transformation matrix. The original basis $$A$$ is transformed to $$B$$ with $$T*A == B$$. If only $$B$$ is needed then lll() should be used as it is a little faster.

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.matrices import DM
>>> X = DM([[1, 0, 0, 0, -20160],
...         [0, 1, 0, 0, 33768],
...         [0, 0, 1, 0, 39578],
...         [0, 0, 0, 1, 47757]], ZZ)
>>> B, T = X.lll_transform(delta=QQ(5, 6))
>>> T * X == B
True

lu()[source]#

Returns Lower and Upper decomposition of the DomainMatrix

Returns:

(L, U, exchange)

L, U are Lower and Upper decomposition of the DomainMatrix, exchange is the list of indices of rows exchanged in the decomposition.

Raises:

ValueError

If the domain of DomainMatrix not a Field

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [QQ(1), QQ(-1)],
...    [QQ(2), QQ(-2)]], (2, 2), QQ)
>>> L, U, exchange = A.lu()
>>> L
DomainMatrix([[1, 0], [2, 1]], (2, 2), QQ)
>>> U
DomainMatrix([[1, -1], [0, 0]], (2, 2), QQ)
>>> exchange
[]

lu_solve(rhs)[source]#

Solver for DomainMatrix x in the A*x = B

Parameters:

rhs : DomainMatrix B

Returns:

DomainMatrix

x in A*x = B

Raises:

DMShapeError

If the DomainMatrix A and rhs have different number of rows

ValueError

If the domain of DomainMatrix A not a Field

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [QQ(1), QQ(2)],
...    [QQ(3), QQ(4)]], (2, 2), QQ)
>>> B = DomainMatrix([
...    [QQ(1), QQ(1)],
...    [QQ(0), QQ(1)]], (2, 2), QQ)

>>> A.lu_solve(B)
DomainMatrix([[-2, -1], [3/2, 1]], (2, 2), QQ)


lu

matmul(B)[source]#

Performs matrix multiplication of two DomainMatrix matrices

Parameters:

A, B: DomainMatrix

to multiply

Returns:

DomainMatrix

DomainMatrix after multiplication

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> B = DomainMatrix([
...    [ZZ(1), ZZ(1)],
...    [ZZ(0), ZZ(1)]], (2, 2), ZZ)

>>> A.matmul(B)
DomainMatrix([[1, 3], [3, 7]], (2, 2), ZZ)


mul(b)[source]#

Performs term by term multiplication for the second DomainMatrix w.r.t first DomainMatrix. Returns a DomainMatrix whose rows are list of DomainMatrix matrices created after term by term multiplication.

Parameters:

A, B: DomainMatrix

matrices to multiply term-wise

Returns:

DomainMatrix

DomainMatrix after term by term multiplication

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> b = ZZ(2)

>>> A.mul(b)
DomainMatrix([[2, 4], [6, 8]], (2, 2), ZZ)

neg()[source]#

Returns the negative of DomainMatrix

Parameters:

A : Represents a DomainMatrix

Returns:

DomainMatrix

DomainMatrix after Negation

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)

>>> A.neg()
DomainMatrix([[-1, -2], [-3, -4]], (2, 2), ZZ)

nnz()[source]#

Number of nonzero elements in the matrix.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DM
>>> A = DM([[1, 0], [0, 4]], ZZ)
>>> A.nnz()
2

nullspace(divide_last=False)[source]#

Returns the nullspace for the DomainMatrix

Parameters:

divide_last : bool, optional

If False (the default), the vectors are not normalized and the RREF is computed using rref_den() and the denominator is discarded. If True, then each row is divided by its final element; the domain must be a field in this case.

Returns:

DomainMatrix

The rows of this matrix form a basis for the nullspace.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices import DM
>>> A = DM([
...    [QQ(2), QQ(-2)],
...    [QQ(4), QQ(-4)]], QQ)
>>> A.nullspace()
DomainMatrix([[1, 1]], (1, 2), QQ)


The returned matrix is a basis for the nullspace:

>>> A_null = A.nullspace().transpose()
>>> A * A_null
DomainMatrix([, ], (2, 1), QQ)
>>> rows, cols = A.shape
>>> nullity = rows - A.rank()
>>> A_null.shape == (cols, nullity)
True


Nullspace can also be computed for non-field rings. If the ring is not a field then division is not used. Setting divide_last to True will raise an error in this case:

>>> from sympy import ZZ
>>> B = DM([[6, -3],
...         [4, -2]], ZZ)
>>> B.nullspace()
DomainMatrix([[3, 6]], (1, 2), ZZ)
>>> B.nullspace(divide_last=True)
Traceback (most recent call last):
...
DMNotAField: Cannot normalize vectors over a non-field


Over a ring with gcd defined the nullspace can potentially be reduced with primitive():

>>> B.nullspace().primitive()
(3, DomainMatrix([[1, 2]], (1, 2), ZZ))


A matrix over a ring can often be normalized by converting it to a field but it is often a bad idea to do so:

>>> from sympy.abc import a, b, c
>>> from sympy import Matrix
>>> M = Matrix([[        a*b,       b + c,        c],
...             [      a - b,         b*c,     c**2],
...             [a*b + a - b, b*c + b + c, c**2 + c]])
>>> M.to_DM().domain
ZZ[a,b,c]
>>> M.to_DM().nullspace().to_Matrix().transpose()
Matrix([
[                             c**3],
[            -a*b*c**2 + a*c - b*c],
[a*b**2*c - a*b - a*c + b**2 + b*c]])


The unnormalized form here is nicer than the normalized form that spreads a large denominator throughout the matrix:

>>> M.to_DM().to_field().nullspace(divide_last=True).to_Matrix().transpose()
Matrix([
[                   c**3/(a*b**2*c - a*b - a*c + b**2 + b*c)],
[(-a*b*c**2 + a*c - b*c)/(a*b**2*c - a*b - a*c + b**2 + b*c)],
[                                                          1]])

nullspace_from_rref(pivots=None)[source]#

Compute nullspace from rref and pivots.

The domain of the matrix can be any domain.

The matrix must be in reduced row echelon form already. Otherwise the result will be incorrect. Use rref() or rref_den() first to get the reduced row echelon form or use nullspace() instead.

classmethod ones(shape, domain)[source]#

Returns a DomainMatrix of 1s, of size shape, belonging to the specified domain

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy import QQ
>>> DomainMatrix.ones((2,3), QQ)
DomainMatrix([[1, 1, 1], [1, 1, 1]], (2, 3), QQ)

pow(n)[source]#

Computes A**n

Parameters:

A : DomainMatrix

n : exponent for A

Returns:

DomainMatrix

DomainMatrix on computing A**n

Raises:

NotImplementedError

if n is negative.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(1)],
...    [ZZ(0), ZZ(1)]], (2, 2), ZZ)

>>> A.pow(2)
DomainMatrix([[1, 2], [0, 1]], (2, 2), ZZ)

primitive()[source]#

Factor out gcd of the elements of a matrix.

Requires gcd in the ground domain.

Examples

>>> from sympy.polys.matrices import DM
>>> from sympy import ZZ
>>> M = DM([[2, 4], [4, 12]], ZZ)
>>> content, M_primitive = M.primitive()
>>> content
2
>>> M_primitive
DomainMatrix([[1, 2], [2, 6]], (2, 2), ZZ)
>>> content * M_primitive == M
True
>>> M_primitive.content() == ZZ(1)
True


rowspace()[source]#

Returns the rowspace for the DomainMatrix

Returns:

DomainMatrix

The rows of this matrix form a basis for the rowspace.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [QQ(1), QQ(-1)],
...    [QQ(2), QQ(-2)]], (2, 2), QQ)
>>> A.rowspace()
DomainMatrix([[1, -1]], (1, 2), QQ)

rref(*, method='auto')[source]#

Returns reduced-row echelon form (RREF) and list of pivots.

If the domain is not a field then it will be converted to a field. See rref_den() for the fraction-free version of this routine that returns RREF with denominator instead.

The domain must either be a field or have an associated fraction field (see to_field()).

Parameters:

method : str, optional (default: ‘auto’)

The method to use to compute the RREF. The default is 'auto', which will attempt to choose the fastest method. The other options are:

• A.rref(method='GJ') uses Gauss-Jordan elimination with division. If the domain is not a field then it will be converted to a field with to_field() first and RREF will be computed by inverting the pivot elements in each row. This is most efficient for very sparse matrices or for matrices whose elements have complex denominators.

• A.rref(method='FF') uses fraction-free Gauss-Jordan elimination. Elimination is performed using exact division (exquo) to control the growth of the coefficients. In this case the current domain is always used for elimination but if the domain is not a field then it will be converted to a field at the end and divided by the denominator. This is most efficient for dense matrices or for matrices with simple denominators.

• A.rref(method='CD') clears the denominators before using fraction-free Gauss-Jordan elimination in the assoicated ring. This is most efficient for dense matrices with very simple denominators.

• A.rref(method='GJ_dense'), A.rref(method='FF_dense'), and A.rref(method='CD_dense') are the same as the above methods except that the dense implementations of the algorithms are used. By default A.rref(method='auto') will usually choose the sparse implementations for RREF.

Regardless of which algorithm is used the returned matrix will always have the same format (sparse or dense) as the input and its domain will always be the field of fractions of the input domain.

Returns:

(DomainMatrix, list)

reduced-row echelon form and list of pivots for the DomainMatrix

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...     [QQ(2), QQ(-1), QQ(0)],
...     [QQ(-1), QQ(2), QQ(-1)],
...     [QQ(0), QQ(0), QQ(2)]], (3, 3), QQ)

>>> rref_matrix, rref_pivots = A.rref()
>>> rref_matrix
DomainMatrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]], (3, 3), QQ)
>>> rref_pivots
(0, 1, 2)


rref_den

RREF with denominator

sympy.polys.matrices.sdm.sdm_irref

Sparse implementation of method='GJ'.

sympy.polys.matrices.sdm.sdm_rref_den

Sparse implementation of method='FF' and method='CD'.

sympy.polys.matrices.dense.ddm_irref

Dense implementation of method='GJ'.

sympy.polys.matrices.dense.ddm_irref_den

Dense implementation of method='FF' and method='CD'.

clear_denoms

Clear denominators from a matrix, used by method='CD' and by method='GJ' when the original domain is not a field.

rref_den(*, method='auto', keep_domain=True)[source]#

Returns reduced-row echelon form with denominator and list of pivots.

Requires exact division in the ground domain (exquo).

Parameters:

method : str, optional (default: ‘auto’)

The method to use to compute the RREF. The default is 'auto', which will attempt to choose the fastest method. The other options are:

• A.rref(method='FF') uses fraction-free Gauss-Jordan elimination. Elimination is performed using exact division (exquo) to control the growth of the coefficients. In this case the current domain is always used for elimination and the result is always returned as a matrix over the current domain. This is most efficient for dense matrices or for matrices with simple denominators.

• A.rref(method='CD') clears denominators before using fraction-free Gauss-Jordan elimination in the assoicated ring. The result will be converted back to the original domain unless keep_domain=False is passed in which case the result will be over the ring used for elimination. This is most efficient for dense matrices with very simple denominators.

• A.rref(method='GJ') uses Gauss-Jordan elimination with division. If the domain is not a field then it will be converted to a field with to_field() first and RREF will be computed by inverting the pivot elements in each row. The result is converted back to the original domain by clearing denominators unless keep_domain=False is passed in which case the result will be over the field used for elimination. This is most efficient for very sparse matrices or for matrices whose elements have complex denominators.

• A.rref(method='GJ_dense'), A.rref(method='FF_dense'), and A.rref(method='CD_dense') are the same as the above methods except that the dense implementations of the algorithms are used. By default A.rref(method='auto') will usually choose the sparse implementations for RREF.

Regardless of which algorithm is used the returned matrix will always have the same format (sparse or dense) as the input and if keep_domain=True its domain will always be the same as the input.

keep_domain : bool, optional

If True (the default), the domain of the returned matrix and denominator are the same as the domain of the input matrix. If False, the domain of the returned matrix might be changed to an associated ring or field if the algorithm used a different domain. This is useful for efficiency if the caller does not need the result to be in the original domain e.g. it avoids clearing denominators in the case of A.rref(method='GJ').

Returns:

(DomainMatrix, scalar, list)

Reduced-row echelon form, denominator and list of pivot indices.

Examples

>>> from sympy import ZZ, QQ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...     [ZZ(2), ZZ(-1), ZZ(0)],
...     [ZZ(-1), ZZ(2), ZZ(-1)],
...     [ZZ(0), ZZ(0), ZZ(2)]], (3, 3), ZZ)

>>> A_rref, denom, pivots = A.rref_den()
>>> A_rref
DomainMatrix([[6, 0, 0], [0, 6, 0], [0, 0, 6]], (3, 3), ZZ)
>>> denom
6
>>> pivots
(0, 1, 2)
>>> A_rref.to_field() / denom
DomainMatrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]], (3, 3), QQ)
>>> A_rref.to_field() / denom == A.convert_to(QQ).rref()
True


rref

RREF without denominator for field domains.

sympy.polys.matrices.sdm.sdm_irref

Sparse implementation of method='GJ'.

sympy.polys.matrices.sdm.sdm_rref_den

Sparse implementation of method='FF' and method='CD'.

sympy.polys.matrices.dense.ddm_irref

Dense implementation of method='GJ'.

sympy.polys.matrices.dense.ddm_irref_den

Dense implementation of method='FF' and method='CD'.

clear_denoms

Clear denominators from a matrix, used by method='CD'.

scc()[source]#

Compute the strongly connected components of a DomainMatrix

Returns:

List of lists of integers

Each list represents a strongly connected component.

Explanation

A square matrix can be considered as the adjacency matrix for a directed graph where the row and column indices are the vertices. In this graph if there is an edge from vertex i to vertex j if M[i, j] is nonzero. This routine computes the strongly connected components of that graph which are subsets of the rows and columns that are connected by some nonzero element of the matrix. The strongly connected components are useful because many operations such as the determinant can be computed by working with the submatrices corresponding to each component.

Examples

Find the strongly connected components of a matrix:

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> M = DomainMatrix([[ZZ(1), ZZ(0), ZZ(2)],
...                   [ZZ(0), ZZ(3), ZZ(0)],
...                   [ZZ(4), ZZ(6), ZZ(5)]], (3, 3), ZZ)
>>> M.scc()
[, [0, 2]]


Compute the determinant from the components:

>>> MM = M.to_Matrix()
>>> MM
Matrix([
[1, 0, 2],
[0, 3, 0],
[4, 6, 5]])
>>> MM[, ]
Matrix([])
>>> MM[[0, 2], [0, 2]]
Matrix([
[1, 2],
[4, 5]])
>>> MM.det()
-9
>>> MM[, ].det() * MM[[0, 2], [0, 2]].det()
-9


The components are given in reverse topological order and represent a permutation of the rows and columns that will bring the matrix into block lower-triangular form:

>>> MM[[1, 0, 2], [1, 0, 2]]
Matrix([
[3, 0, 0],
[0, 1, 2],
[6, 4, 5]])

solve_den(b, method=None)[source]#

Solve matrix equation $$Ax = b$$ without fractions in the ground domain.

Parameters:

The m x n matrix $$A$$ in the equation $$Ax = b$$. Underdetermined systems are not supported so m >= n: $$A$$ should be square or have more rows than columns.

The n x m matrix $$b$$ for the rhs.

cp : list of DomainElement, optional

The characteristic polynomial of the matrix $$A$$. If not given, it will be computed using charpoly().

method: str, optional

The method to use for solving the system. Can be one of None, 'charpoly' or 'rref'. If None (the default) then the method will be chosen automatically.

The charpoly method uses solve_den_charpoly() and can only be used if the matrix is square. This method is division free and can be used with any domain.

The rref method is fraction free but requires exact division in the ground domain (exquo). This is also suitable for most domains. This method can be used with overdetermined systems (more equations than unknowns) but not underdetermined systems as a unique solution is sought.

Returns:

(xnum, xden) : (DomainMatrix, DomainElement)

The solution of the equation $$Ax = b$$ as a pair consisting of an n x m matrix numerator xnum and a scalar denominator xden.

The solution $$x$$ is given by x = xnum / xden. The division free

invariant is A * xnum == xden * b. If $$A$$ is square then the

denominator xden will be a divisor of the determinant $$det(A)$$.

Raises:

DMNonInvertibleMatrixError

If the system $$Ax = b$$ does not have a unique solution.

Examples

Solve a matrix equation over the integers:

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DM
>>> A = DM([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], ZZ)
>>> b = DM([[ZZ(5)], [ZZ(6)]], ZZ)
>>> xnum, xden = A.solve_den(b)
>>> xden
-2
>>> xnum
DomainMatrix([, [-9]], (2, 1), ZZ)
>>> A * xnum == xden * b
True


Solve a matrix equation over a polynomial ring:

>>> from sympy import ZZ
>>> from sympy.abc import x, y, z, a, b
>>> R = ZZ[x, y, z, a, b]
>>> M = DM([[x*y, x*z], [y*z, x*z]], R)
>>> b = DM([[a], [b]], R)
>>> M.to_Matrix()
Matrix([
[x*y, x*z],
[y*z, x*z]])
>>> b.to_Matrix()
Matrix([
[a],
[b]])
>>> xnum, xden = M.solve_den(b)
>>> xden
x**2*y*z - x*y*z**2
>>> xnum.to_Matrix()
Matrix([
[ a*x*z - b*x*z],
[-a*y*z + b*x*y]])
>>> M * xnum == xden * b
True


The solution can be expressed over a fraction field which will cancel gcds between the denominator and the elements of the numerator:

>>> xsol = xnum.to_field() / xden
>>> xsol.to_Matrix()
Matrix([
[           (a - b)/(x*y - y*z)],
[(-a*z + b*x)/(x**2*z - x*z**2)]])
>>> (M * xsol).to_Matrix() == b.to_Matrix()
True


When solving a large system of equations this cancellation step might be a lot slower than solve_den() itself. The solution can also be expressed as a Matrix without attempting any polynomial cancellation between the numerator and denominator giving a less simplified result more quickly:

>>> xsol_uncancelled = xnum.to_Matrix() / xnum.domain.to_sympy(xden)
>>> xsol_uncancelled
Matrix([
[ (a*x*z - b*x*z)/(x**2*y*z - x*y*z**2)],
[(-a*y*z + b*x*y)/(x**2*y*z - x*y*z**2)]])
>>> from sympy import cancel
>>> cancel(xsol_uncancelled) == xsol.to_Matrix()
True

solve_den_charpoly(b, cp=None, check=True)[source]#

Solve matrix equation $$Ax = b$$ using the characteristic polynomial.

This method solves the square matrix equation $$Ax = b$$ for $$x$$ using the characteristic polynomial without any division or fractions in the ground domain.

Parameters:

self : DomainMatrix

The n x n matrix $$A$$ in the equation $$Ax = b$$. Must be square and invertible.

b : DomainMatrix

The n x m matrix $$b$$ for the rhs.

cp : list, optional

The characteristic polynomial of the matrix $$A$$ if known. If not given, it will be computed using charpoly().

check : bool, optional

If True (the default) check that the determinant is not zero and raise an error if it is. If False then if the determinant is zero the return value will be equal to (A.adjugate()*b, 0).

Returns:

(xnum, detA) : (DomainMatrix, DomainElement)

The solution of the equation $$Ax = b$$ as a matrix numerator and scalar denominator pair. The denominator is equal to the determinant of $$A$$ and the numerator is adj(A)*b.

The solution $$x$$ is given by x = xnum / detA. The division free

invariant is A * xnum == detA * b.

If b is the identity matrix, then xnum is the adjugate matrix

and we have A * adj(A) == detA * I.

Examples

Solve a matrix equation over the integers:

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DM
>>> A = DM([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], ZZ)
>>> b = DM([[ZZ(5)], [ZZ(6)]], ZZ)
>>> xnum, detA = A.solve_den_charpoly(b)
>>> detA
-2
>>> xnum
DomainMatrix([, [-9]], (2, 1), ZZ)
>>> A * xnum == detA * b
True


solve_den

Main frontend for solving matrix equations with denominator.

solve_den_rref

Solve matrix equations using fraction-free RREF.

inv_den

Invert a matrix using the characteristic polynomial.

solve_den_rref(b)[source]#

Solve matrix equation $$Ax = b$$ using fraction-free RREF

Solves the matrix equation $$Ax = b$$ for $$x$$ and returns the solution as a numerator/denominator pair.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DM
>>> A = DM([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], ZZ)
>>> b = DM([[ZZ(5)], [ZZ(6)]], ZZ)
>>> xnum, xden = A.solve_den_rref(b)
>>> xden
-2
>>> xnum
DomainMatrix([, [-9]], (2, 1), ZZ)
>>> A * xnum == xden * b
True

sub(B)[source]#

Subtracts two DomainMatrix matrices of the same Domain

Parameters:

A, B: DomainMatrix

matrices to subtract

Returns:

DomainMatrix

DomainMatrix after Subtraction

Raises:

DMShapeError

If the dimensions of the two DomainMatrix are not equal

ValueError

If the domain of the two DomainMatrix are not same

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> B = DomainMatrix([
...    [ZZ(4), ZZ(3)],
...    [ZZ(2), ZZ(1)]], (2, 2), ZZ)

>>> A.sub(B)
DomainMatrix([[-3, -1], [1, 3]], (2, 2), ZZ)


to_Matrix()[source]#

Convert DomainMatrix to Matrix

Returns:

Matrix

MutableDenseMatrix for the DomainMatrix

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)

>>> A.to_Matrix()
Matrix([
[1, 2],
[3, 4]])

to_ddm()[source]#

Return a DDM representation of self.

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy import QQ
>>> A = DomainMatrix({0: {0: 1}, 1: {1: 2}}, (2, 2), QQ)
>>> ddm = A.to_ddm()
>>> ddm
[[1, 0], [0, 2]]
>>> type(ddm)
<class 'sympy.polys.matrices.ddm.DDM'>

to_dense()[source]#

Return a dense DomainMatrix representation of self.

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy import QQ
>>> A = DomainMatrix({0: {0: 1}, 1: {1: 2}}, (2, 2), QQ)
>>> A.rep
{0: {0: 1}, 1: {1: 2}}
>>> B = A.to_dense()
>>> B.rep
[[1, 0], [0, 2]]

to_dfm()[source]#

Return a DFM representation of self.

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy import QQ
>>> A = DomainMatrix([[1, 0],[0, 2]], (2, 2), QQ)
>>> dfm = A.to_dfm()
>>> dfm
[[1, 0], [0, 2]]
>>> type(dfm)
<class 'sympy.polys.matrices._dfm.DFM'>


to_dfm_or_ddm()[source]#

Return a DFM or DDM representation of self.

Explanation

The DFM representation can only be used if the ground types are flint and the ground domain is supported by python-flint. This method will return a DFM representation if possible, but will return a DDM representation otherwise.

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy import QQ
>>> A = DomainMatrix([[1, 0],[0, 2]], (2, 2), QQ)
>>> dfm = A.to_dfm_or_ddm()
>>> dfm
[[1, 0], [0, 2]]
>>> type(dfm)  # Depends on the ground domain and ground types
<class 'sympy.polys.matrices._dfm.DFM'>


to_ddm

Always return a DDM representation.

to_dfm

Returns a DFM representation or raise an error.

to_dense

Convert internally to a DFM or DDM

DFM

The DFM dense FLINT matrix representation.

DDM

The Python DDM dense domain matrix representation.

to_dok()[source]#

Convert DomainMatrix to dictionary of keys (dok) format.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(0)],
...    [ZZ(0), ZZ(4)]], (2, 2), ZZ)
>>> A.to_dok()
{(0, 0): 1, (1, 1): 4}


The matrix can be reconstructed by calling from_dok() although the reconstructed matrix will always be in sparse format:

>>> A.to_sparse() == A.from_dok(A.to_dok(), A.shape, A.domain)
True

to_field()[source]#

Returns a DomainMatrix with the appropriate field

Returns:

DomainMatrix

DomainMatrix with the appropriate field

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)

>>> A.to_field()
DomainMatrix([[1, 2], [3, 4]], (2, 2), QQ)

to_flat_nz()[source]#

Convert DomainMatrix to list of nonzero elements and data.

Explanation

Returns a tuple (elements, data) where elements is a list of elements of the matrix with zeros possibly excluded. The matrix can be reconstructed by passing these to from_flat_nz(). The idea is to be able to modify a flat list of the elements and then create a new matrix of the same shape with the modified elements in the same positions.

The format of data differs depending on whether the underlying representation is dense or sparse but either way it represents the positions of the elements in the list in a way that from_flat_nz() can use to reconstruct the matrix. The from_flat_nz() method should be called on the same DomainMatrix that was used to call to_flat_nz().

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([
...    [ZZ(1), ZZ(2)],
...    [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> elements, data = A.to_flat_nz()
>>> elements
[1, 2, 3, 4]
>>> A == A.from_flat_nz(elements, data, A.domain)
True


Create a matrix with the elements doubled:

>>> elements_doubled = [2*x for x in elements]
>>> A2 = A.from_flat_nz(elements_doubled, data, A.domain)
>>> A2 == 2*A
True

to_list()[source]#

Convert DomainMatrix to list of lists.

to_list_flat()[source]#

Convert DomainMatrix to flat list.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> A.to_list_flat()
[1, 2, 3, 4]

to_sdm()[source]#

Return a SDM representation of self.

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy import QQ
>>> A = DomainMatrix([[1, 0],[0, 2]], (2, 2), QQ)
>>> sdm = A.to_sdm()
>>> sdm
{0: {0: 1}, 1: {1: 2}}
>>> type(sdm)
<class 'sympy.polys.matrices.sdm.SDM'>

to_sparse()[source]#

Return a sparse DomainMatrix representation of self.

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy import QQ
>>> A = DomainMatrix([[1, 0],[0, 2]], (2, 2), QQ)
>>> A.rep
[[1, 0], [0, 2]]
>>> B = A.to_sparse()
>>> B.rep
{0: {0: 1}, 1: {1: 2}}

transpose()[source]#

Matrix transpose of self

unify(*others, fmt=None)[source]#

Unifies the domains and the format of self and other matrices.

Parameters:

others : DomainMatrix

fmt: string ‘dense’, ‘sparse’ or None (default)

The preferred format to convert to if self and other are not already in the same format. If $$None$$ or not specified then no conversion if performed.

Returns:

Tuple[DomainMatrix]

Matrices with unified domain and format

Examples

Unify the domain of DomainMatrix that have different domains:

>>> from sympy import ZZ, QQ
>>> from sympy.polys.matrices import DomainMatrix
>>> A = DomainMatrix([[ZZ(1), ZZ(2)]], (1, 2), ZZ)
>>> B = DomainMatrix([[QQ(1, 2), QQ(2)]], (1, 2), QQ)
>>> Aq, Bq = A.unify(B)
>>> Aq
DomainMatrix([[1, 2]], (1, 2), QQ)
>>> Bq
DomainMatrix([[1/2, 2]], (1, 2), QQ)


Unify the format (dense or sparse):

>>> A = DomainMatrix([[ZZ(1), ZZ(2)]], (1, 2), ZZ)
>>> B = DomainMatrix({0:{0: ZZ(1)}}, (2, 2), ZZ)
>>> B.rep
{0: {0: 1}}

>>> A2, B2 = A.unify(B, fmt='dense')
>>> B2.rep
[[1, 0], [0, 0]]

vstack(*B)[source]#

Vertically stack the given matrices.

Parameters:

B: DomainMatrix

Matrices to stack vertically.

Returns:

DomainMatrix

DomainMatrix by stacking vertically.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix

>>> A = DomainMatrix([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> B = DomainMatrix([[ZZ(5), ZZ(6)], [ZZ(7), ZZ(8)]], (2, 2), ZZ)
>>> A.vstack(B)
DomainMatrix([[1, 2], [3, 4], [5, 6], [7, 8]], (4, 2), ZZ)

>>> C = DomainMatrix([[ZZ(9), ZZ(10)], [ZZ(11), ZZ(12)]], (2, 2), ZZ)
>>> A.vstack(B, C)
DomainMatrix([[1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12]], (6, 2), ZZ)

classmethod zeros(shape, domain, *, fmt='sparse')[source]#

Returns a zero DomainMatrix of size shape, belonging to the specified domain

Examples

>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy import QQ
>>> DomainMatrix.zeros((2, 3), QQ)
DomainMatrix({}, (2, 3), QQ)


Module for the DDM class.

The DDM class is an internal representation used by DomainMatrix. The letters DDM stand for Dense Domain Matrix. A DDM instance represents a matrix using elements from a polynomial Domain (e.g. ZZ, QQ, …) in a dense-matrix representation.

Basic usage:

>>> from sympy import ZZ, QQ
>>> from sympy.polys.matrices.ddm import DDM
>>> A = DDM([[ZZ(0), ZZ(1)], [ZZ(-1), ZZ(0)]], (2, 2), ZZ)
>>> A.shape
(2, 2)
>>> A
[[0, 1], [-1, 0]]
>>> type(A)
<class 'sympy.polys.matrices.ddm.DDM'>
>>> A @ A
[[-1, 0], [0, -1]]


The ddm_* functions are designed to operate on DDM as well as on an ordinary list of lists:

>>> from sympy.polys.matrices.dense import ddm_idet
>>> ddm_idet(A, QQ)
1
>>> ddm_idet([[0, 1], [-1, 0]], QQ)
1
>>> A
[[-1, 0], [0, -1]]


Note that ddm_idet modifies the input matrix in-place. It is recommended to use the DDM.det method as a friendlier interface to this instead which takes care of copying the matrix:

>>> B = DDM([[ZZ(0), ZZ(1)], [ZZ(-1), ZZ(0)]], (2, 2), ZZ)
>>> B.det()
1


Normally DDM would not be used directly and is just part of the internal representation of DomainMatrix which adds further functionality including e.g. unifying domains.

The dense format used by DDM is a list of lists of elements e.g. the 2x2 identity matrix is like [[1, 0], [0, 1]]. The DDM class itself is a subclass of list and its list items are plain lists. Elements are accessed as e.g. ddm[i][j] where ddm[i] gives the ith row and ddm[i][j] gets the element in the jth column of that row. Subclassing list makes e.g. iteration and indexing very efficient. We do not override __getitem__ because it would lose that benefit.

The core routines are implemented by the ddm_* functions defined in dense.py. Those functions are intended to be able to operate on a raw list-of-lists representation of matrices with most functions operating in-place. The DDM class takes care of copying etc and also stores a Domain object associated with its elements. This makes it possible to implement things like A + B with domain checking and also shape checking so that the list of lists representation is friendlier.

class sympy.polys.matrices.ddm.DDM(rowslist, shape, domain)[source]#

Dense matrix based on polys domain elements

This is a list subclass and is a wrapper for a list of lists that supports basic matrix arithmetic +, -, , *.

a + b

charpoly()[source]#

Coefficients of characteristic polynomial of a

det()[source]#

Determinant of a

classmethod diag(values, domain)[source]#

Returns a square diagonal matrix with values on the diagonal.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import DDM
>>> DDM.diag([ZZ(1), ZZ(2), ZZ(3)], ZZ)
[[1, 0, 0], [0, 2, 0], [0, 0, 3]]

diagonal()[source]#

Returns a list of the elements from the diagonal of the matrix.

classmethod from_dok(dok, shape, domain)[source]#

Create a DDM from a dictionary of keys (dok) format.

Examples

>>> from sympy.polys.matrices.ddm import DDM
>>> from sympy import QQ
>>> dok = {(0, 0): 1, (0, 1): 2, (1, 0): 3, (1, 1): 4}
>>> A = DDM.from_dok(dok, (2, 2), QQ)
>>> A
[[1, 2], [3, 4]]

classmethod from_flat_nz(elements, data, domain)[source]#

Reconstruct a DDM after calling to_flat_nz().

Examples

>>> from sympy.polys.matrices.ddm import DDM
>>> from sympy import QQ
>>> A = DDM([[1, 2], [3, 4]], (2, 2), QQ)
>>> elements, data = A.to_flat_nz()
>>> elements
[1, 2, 3, 4]
>>> A == DDM.from_flat_nz(elements, data, A.domain)
True

classmethod from_list(rowslist, shape, domain)[source]#

Create a DDM from a list of lists.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.ddm import DDM
>>> A = DDM.from_list([[ZZ(0), ZZ(1)], [ZZ(-1), ZZ(0)]], (2, 2), ZZ)
>>> A
[[0, 1], [-1, 0]]
>>> A == DDM([[ZZ(0), ZZ(1)], [ZZ(-1), ZZ(0)]], (2, 2), ZZ)
True

classmethod from_list_flat(flat, shape, domain)[source]#

Create a DDM from a flat list of elements.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices.ddm import DDM
>>> A = DDM.from_list_flat([1, 2, 3, 4], (2, 2), QQ)
>>> A
[[1, 2], [3, 4]]
>>> A == DDM.from_list_flat(A.to_list_flat(), A.shape, A.domain)
True

hstack(*B)[source]#

Horizontally stacks DDM matrices.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import DDM

>>> A = DDM([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> B = DDM([[ZZ(5), ZZ(6)], [ZZ(7), ZZ(8)]], (2, 2), ZZ)
>>> A.hstack(B)
[[1, 2, 5, 6], [3, 4, 7, 8]]

>>> C = DDM([[ZZ(9), ZZ(10)], [ZZ(11), ZZ(12)]], (2, 2), ZZ)
>>> A.hstack(B, C)
[[1, 2, 5, 6, 9, 10], [3, 4, 7, 8, 11, 12]]

inv()[source]#

Inverse of a

is_diagonal()[source]#

Says whether this matrix is diagonal. True can be returned even if the matrix is not square.

is_lower()[source]#

Says whether this matrix is lower-triangular. True can be returned even if the matrix is not square.

is_upper()[source]#

Says whether this matrix is upper-triangular. True can be returned even if the matrix is not square.

is_zero_matrix()[source]#

Says whether this matrix has all zero entries.

lu()[source]#

L, U decomposition of a

lu_solve(b)[source]#

x where a*x = b

matmul(b)[source]#

a @ b (matrix product)

neg()[source]#

-a

nnz()[source]#

Number of non-zero entries in DDM matrix.

nullspace()[source]#

Returns a basis for the nullspace of a.

The domain of the matrix must be a field.

nullspace_from_rref(pivots=None)[source]#

Compute the nullspace of a matrix from its rref.

The domain of the matrix can be any domain.

Returns a tuple (basis, nonpivots).

sympy.polys.matrices.domainmatrix.DomainMatrix.nullspace

The higher level interface to this function.

rref()[source]#

Reduced-row echelon form of a and list of pivots.

sympy.polys.matrices.domainmatrix.DomainMatrix.rref

Higher level interface to this function.

sympy.polys.matrices.dense.ddm_irref

The underlying algorithm.

rref_den()[source]#

Reduced-row echelon form of a with denominator and list of pivots

scc()[source]#

Strongly connected components of a square matrix a.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import DDM
>>> A = DDM([[ZZ(1), ZZ(0)], [ZZ(0), ZZ(1)]], (2, 2), ZZ)
>>> A.scc()
[, ]

sub(b)[source]#

a - b

to_ddm()[source]#

Convert to a DDM.

This just returns self but exists to parallel the corresponding method in other matrix types like SDM.

to_dfm()[source]#

Convert to DDM to DFM.

Examples

>>> from sympy.polys.matrices.ddm import DDM
>>> from sympy import QQ
>>> A = DDM([[1, 2], [3, 4]], (2, 2), QQ)
>>> A.to_dfm()
[[1, 2], [3, 4]]
>>> type(A.to_dfm())
<class 'sympy.polys.matrices._dfm.DFM'>

to_dfm_or_ddm()[source]#

Convert to DFM if possible or otherwise return self.

Examples

>>> from sympy.polys.matrices.ddm import DDM
>>> from sympy import QQ
>>> A = DDM([[1, 2], [3, 4]], (2, 2), QQ)
>>> A.to_dfm_or_ddm()
[[1, 2], [3, 4]]
>>> type(A.to_dfm_or_ddm())
<class 'sympy.polys.matrices._dfm.DFM'>

to_dok()[source]#

Convert DDM to dictionary of keys (dok) format.

Examples

>>> from sympy.polys.matrices.ddm import DDM
>>> from sympy import QQ
>>> A = DDM([[1, 2], [3, 4]], (2, 2), QQ)
>>> A.to_dok()
{(0, 0): 1, (0, 1): 2, (1, 0): 3, (1, 1): 4}

to_flat_nz()[source]#

Convert to a flat list of nonzero elements and data.

Explanation

This is used to operate on a list of the elements of a matrix and then reconstruct a matrix using from_flat_nz(). Zero elements are included in the list but that may change in the future.

Examples

>>> from sympy.polys.matrices.ddm import DDM
>>> from sympy import QQ
>>> A = DDM([[1, 2], [3, 4]], (2, 2), QQ)
>>> elements, data = A.to_flat_nz()
>>> elements
[1, 2, 3, 4]
>>> A == DDM.from_flat_nz(elements, data, A.domain)
True

to_list()[source]#

Convert to a list of lists.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices.ddm import DDM
>>> A = DDM([[1, 2], [3, 4]], (2, 2), QQ)
>>> A.to_list()
[[1, 2], [3, 4]]

to_list_flat()[source]#

Convert to a flat list of elements.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices.ddm import DDM
>>> A = DDM([[1, 2], [3, 4]], (2, 2), QQ)
>>> A.to_list_flat()
[1, 2, 3, 4]
>>> A == DDM.from_list_flat(A.to_list_flat(), A.shape, A.domain)
True

to_sdm()[source]#

Convert to a SDM.

Examples

>>> from sympy.polys.matrices.ddm import DDM
>>> from sympy import QQ
>>> A = DDM([[1, 2], [3, 4]], (2, 2), QQ)
>>> A.to_sdm()
{0: {0: 1, 1: 2}, 1: {0: 3, 1: 4}}
>>> type(A.to_sdm())
<class 'sympy.polys.matrices.sdm.SDM'>

vstack(*B)[source]#

Vertically stacks DDM matrices.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import DDM

>>> A = DDM([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> B = DDM([[ZZ(5), ZZ(6)], [ZZ(7), ZZ(8)]], (2, 2), ZZ)
>>> A.vstack(B)
[[1, 2], [3, 4], [5, 6], [7, 8]]

>>> C = DDM([[ZZ(9), ZZ(10)], [ZZ(11), ZZ(12)]], (2, 2), ZZ)
>>> A.vstack(B, C)
[[1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12]]


Module for the ddm_* routines for operating on a matrix in list of lists matrix representation.

These routines are used internally by the DDM class which also provides a friendlier interface for them. The idea here is to implement core matrix routines in a way that can be applied to any simple list representation without the need to use any particular matrix class. For example we can compute the RREF of a matrix like:

>>> from sympy.polys.matrices.dense import ddm_irref
>>> M = [[1, 2, 3], [4, 5, 6]]
>>> pivots = ddm_irref(M)
>>> M
[[1.0, 0.0, -1.0], [0, 1.0, 2.0]]


These are lower-level routines that work mostly in place.The routines at this level should not need to know what the domain of the elements is but should ideally document what operations they will use and what functions they need to be provided with.

The next-level up is the DDM class which uses these routines but wraps them up with an interface that handles copying etc and keeps track of the Domain of the elements of the matrix:

>>> from sympy.polys.domains import QQ
>>> from sympy.polys.matrices.ddm import DDM
>>> M = DDM([[QQ(1), QQ(2), QQ(3)], [QQ(4), QQ(5), QQ(6)]], (2, 3), QQ)
>>> M
[[1, 2, 3], [4, 5, 6]]
>>> Mrref, pivots = M.rref()
>>> Mrref
[[1, 0, -1], [0, 1, 2]]

class sympy.polys.matrices.dense.R#

Type variable for the elements of the matrix that are in a ring

alias of TypeVar(‘R’, bound=RingElement)

class sympy.polys.matrices.dense.T#

Type variable for the elements of the matrix

alias of TypeVar(‘T’)

sympy.polys.matrices.dense.ddm_berk(M, K)[source]#

Berkowitz algorithm for computing the characteristic polynomial.

Explanation

The Berkowitz algorithm is a division-free algorithm for computing the characteristic polynomial of a matrix over any commutative ring using only arithmetic in the coefficient ring.

Examples

>>> from sympy import Matrix
>>> from sympy.polys.matrices.dense import ddm_berk
>>> from sympy.polys.domains import ZZ
>>> M = [[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]]
>>> ddm_berk(M, ZZ)
[, [-5], [-2]]
>>> Matrix(M).charpoly()
PurePoly(lambda**2 - 5*lambda - 2, lambda, domain='ZZ')


sympy.polys.matrices.domainmatrix.DomainMatrix.charpoly

The high-level interface to this function.

References

a += b

sympy.polys.matrices.dense.ddm_idet(a, K)[source]#

a <– echelon(a); return det

Explanation

Compute the determinant of $$a$$ using the Bareiss fraction-free algorithm. The matrix $$a$$ is modified in place. Its diagonal elements are the determinants of the leading principal minors. The determinant of $$a$$ is returned.

The domain $$K$$ must support exact division (K.exquo). This method is suitable for most exact rings and fields like ZZ, QQ and QQ<a> but not for inexact domains like RR and CC.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.ddm import ddm_idet
>>> a = [[ZZ(1), ZZ(2), ZZ(3)], [ZZ(4), ZZ(5), ZZ(6)], [ZZ(7), ZZ(8), ZZ(9)]]
>>> a
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> ddm_idet(a, ZZ)
0
>>> a
[[1, 2, 3], [4, -3, -6], [7, -6, 0]]
>>> [a[i][i] for i in range(len(a))]
[1, -3, 0]


References

sympy.polys.matrices.dense.ddm_iinv(ainv, a, K)[source]#

ainv <– inv(a)

Compute the inverse of a matrix $$a$$ over a field $$K$$ using Gauss-Jordan elimination. The result is stored in $$ainv$$.

Uses division in the ground domain which should be an exact field.

Examples

>>> from sympy.polys.matrices.ddm import ddm_iinv, ddm_imatmul
>>> from sympy import QQ
>>> a = [[QQ(1), QQ(2)], [QQ(3), QQ(4)]]
>>> ainv = [[None, None], [None, None]]
>>> ddm_iinv(ainv, a, QQ)
>>> ainv
[[-2, 1], [3/2, -1/2]]
>>> result = [[QQ(0), QQ(0)], [QQ(0), QQ(0)]]
>>> ddm_imatmul(result, a, ainv)
>>> result
[[1, 0], [0, 1]]


ddm_irref

the underlying routine.

sympy.polys.matrices.dense.ddm_ilu(a)[source]#

a <– LU(a)

Computes the LU decomposition of a matrix in place. Returns a list of row swaps that were performed.

Uses division in the ground domain which should be an exact field.

This is only suitable for domains like GF(p), QQ, QQ_I and QQ<a>. With a rational function field like K(x) it is better to clear denominators and use division-free algorithms. Pivoting is used to avoid exact zeros but not for floating point accuracy so RR and CC are not suitable (use ddm_irref() instead).

Examples

>>> from sympy.polys.matrices.dense import ddm_ilu
>>> from sympy import QQ
>>> a = [[QQ(1, 2), QQ(1, 3)], [QQ(1, 4), QQ(1, 5)]]
>>> swaps = ddm_ilu(a)
>>> swaps
[]
>>> a
[[1/2, 1/3], [1/2, 1/30]]


The same example using Matrix:

>>> from sympy import Matrix, S
>>> M = Matrix([[S(1)/2, S(1)/3], [S(1)/4, S(1)/5]])
>>> L, U, swaps = M.LUdecomposition()
>>> L
Matrix([
[  1, 0],
[1/2, 1]])
>>> U
Matrix([
[1/2,  1/3],
[  0, 1/30]])
>>> swaps
[]

sympy.polys.matrices.dense.ddm_ilu_solve(x, L, U, swaps, b)[source]#

x <– solve(L*U*x = swaps(b))

Solve a linear system, $$A*x = b$$, given an LU factorization of $$A$$.

Uses division in the ground domain which must be a field.

Modifies $$x$$ in place.

Examples

Compute the LU decomposition of $$A$$ (in place):

>>> from sympy import QQ
>>> from sympy.polys.matrices.dense import ddm_ilu, ddm_ilu_solve
>>> A = [[QQ(1), QQ(2)], [QQ(3), QQ(4)]]
>>> swaps = ddm_ilu(A)
>>> A
[[1, 2], [3, -2]]
>>> L = U = A


Solve the linear system:

>>> b = [[QQ(5)], [QQ(6)]]
>>> x = [[None], [None]]
>>> ddm_ilu_solve(x, L, U, swaps, b)
>>> x
[[-4], [9/2]]


ddm_ilu

Compute the LU decomposition of a matrix in place.

ddm_ilu_split

Compute the LU decomposition of a matrix and separate $$L$$ and $$U$$.

sympy.polys.matrices.domainmatrix.DomainMatrix.lu_solve

Higher level interface to this function.

sympy.polys.matrices.dense.ddm_ilu_split(L, U, K)[source]#

L, U <– LU(U)

Compute the LU decomposition of a matrix $$L$$ in place and store the lower and upper triangular matrices in $$L$$ and $$U$$, respectively. Returns a list of row swaps that were performed.

Uses division in the ground domain which should be an exact field.

Examples

>>> from sympy.polys.matrices.ddm import ddm_ilu_split
>>> from sympy import QQ
>>> L = [[QQ(0), QQ(0)], [QQ(0), QQ(0)]]
>>> U = [[QQ(1), QQ(2)], [QQ(3), QQ(4)]]
>>> swaps = ddm_ilu_split(L, U, QQ)
>>> swaps
[]
>>> L
[[0, 0], [3, 0]]
>>> U
[[1, 2], [0, -2]]


sympy.polys.matrices.dense.ddm_imatmul(a: list[list[R]], b: Sequence[Sequence[R]], c: Sequence[Sequence[R]]) None[source]#

a += b @ c

sympy.polys.matrices.dense.ddm_imul(a: list[list[R]], b: R) None[source]#

a <– a*b

sympy.polys.matrices.dense.ddm_ineg(a: list[list[R]]) None[source]#

a <– -a

sympy.polys.matrices.dense.ddm_irmul(a: list[list[R]], b: R) None[source]#

a <– b*a

sympy.polys.matrices.dense.ddm_irref(a, _partial_pivot=False)[source]#

In-place reduced row echelon form of a matrix.

Compute the reduced row echelon form of $$a$$. Modifies $$a$$ in place and returns a list of the pivot columns.

Uses naive Gauss-Jordan elimination in the ground domain which must be a field.

This routine is only really suitable for use with simple field domains like GF(p), QQ and QQ<a> although even for QQ with larger matrices it is possibly more efficient to use fraction free approaches.

This method is not suitable for use with rational function fields (K(x)) because the elements will blowup leading to costly gcd operations. In this case clearing denominators and using fraction free approaches is likely to be more efficient.

For inexact numeric domains like RR and CC pass _partial_pivot=True to use partial pivoting to control rounding errors.

Examples

>>> from sympy.polys.matrices.dense import ddm_irref
>>> from sympy import QQ
>>> M = [[QQ(1), QQ(2), QQ(3)], [QQ(4), QQ(5), QQ(6)]]
>>> pivots = ddm_irref(M)
>>> M
[[1, 0, -1], [0, 1, 2]]
>>> pivots
[0, 1]


sympy.polys.matrices.domainmatrix.DomainMatrix.rref

Higher level interface to this routine.

ddm_irref_den

The fraction free version of this routine.

sdm_irref

A sparse version of this routine.

References

sympy.polys.matrices.dense.ddm_irref_den(a, K)[source]#

a <– rref(a); return (den, pivots)

Compute the fraction-free reduced row echelon form (RREF) of $$a$$. Modifies $$a$$ in place and returns a tuple containing the denominator of the RREF and a list of the pivot columns.

Explanation

The algorithm used is the fraction-free version of Gauss-Jordan elimination described as FFGJ in [R742]. Here it is modified to handle zero or missing pivots and to avoid redundant arithmetic.

The domain $$K$$ must support exact division (K.exquo) but does not need to be a field. This method is suitable for most exact rings and fields like ZZ, QQ and QQ<a>. In the case of QQ or K(x) it might be more efficient to clear denominators and use ZZ or K[x] instead.

For inexact domains like RR and CC use ddm_irref instead.

Examples

>>> from sympy.polys.matrices.dense import ddm_irref_den
>>> from sympy import ZZ, Matrix
>>> M = [[ZZ(1), ZZ(2), ZZ(3)], [ZZ(4), ZZ(5), ZZ(6)]]
>>> den, pivots = ddm_irref_den(M, ZZ)
>>> M
[[-3, 0, 3], [0, -3, -6]]
>>> den
-3
>>> pivots
[0, 1]
>>> Matrix(M).rref()
Matrix([
[1, 0, -1],
[0, 1,  2]])


ddm_irref

A version of this routine that uses field division.

sdm_irref

A sparse version of ddm_irref().

sdm_rref_den

A sparse version of ddm_irref_den().

sympy.polys.matrices.domainmatrix.DomainMatrix.rref_den

Higher level interface.

References

[R742] (1,2)

Fraction-free algorithms for linear and polynomial equations. George C. Nakos , Peter R. Turner , Robert M. Williams. https://dl.acm.org/doi/10.1145/271130.271133

sympy.polys.matrices.dense.ddm_isub(a: list[list[R]], b: Sequence[Sequence[R]]) None[source]#

a -= b

sympy.polys.matrices.dense.ddm_transpose(matrix: Sequence[Sequence[T]]) list[list[T]][source]#

matrix transpose

class sympy.polys.matrices._typing.RingElement(*args, **kwargs)[source]#

A ring element.

Must support +, -, *, ** and -.

Module for the SDM class.

class sympy.polys.matrices.sdm.SDM(elemsdict, shape, domain)[source]#

Sparse matrix based on polys domain elements

This is a dict subclass and is a wrapper for a dict of dicts that supports basic matrix arithmetic +, -, , *.

In order to create a new SDM, a dict of dicts mapping non-zero elements to their corresponding row and column in the matrix is needed.

We also need to specify the shape and Domain of our SDM object.

We declare a 2x2 SDM matrix belonging to QQ domain as shown below. The 2x2 Matrix in the example is

$\begin{split}A = \left[\begin{array}{ccc} 0 & \frac{1}{2} \\ 0 & 0 \end{array} \right]\end{split}$
>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> elemsdict = {0:{1:QQ(1, 2)}}
>>> A = SDM(elemsdict, (2, 2), QQ)
>>> A
{0: {1: 1/2}}


We can manipulate SDM the same way as a Matrix class

>>> from sympy import ZZ
>>> A = SDM({0:{1: ZZ(2)}, 1:{0:ZZ(1)}}, (2, 2), ZZ)
>>> B  = SDM({0:{0: ZZ(3)}, 1:{1:ZZ(4)}}, (2, 2), ZZ)
>>> A + B
{0: {0: 3, 1: 2}, 1: {0: 1, 1: 4}}


Multiplication

>>> A*B
{0: {1: 8}, 1: {0: 3}}
>>> A*ZZ(2)
{0: {1: 4}, 1: {0: 2}}


Adds two SDM matrices

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{1: ZZ(2)}, 1:{0:ZZ(1)}}, (2, 2), ZZ)
>>> B = SDM({0:{0: ZZ(3)}, 1:{1:ZZ(4)}}, (2, 2), ZZ)
{0: {0: 3, 1: 2}, 1: {0: 1, 1: 4}}

charpoly()[source]#

Returns the coefficients of the characteristic polynomial of the SDM matrix. These elements will be domain elements. The domain of the elements will be same as domain of the SDM.

Examples

>>> from sympy import QQ, Symbol
>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy.polys import Poly
>>> A = SDM({0:{0:QQ(1), 1:QQ(2)}, 1:{0:QQ(3), 1:QQ(4)}}, (2, 2), QQ)
>>> A.charpoly()
[1, -5, -2]


We can create a polynomial using the coefficients using Poly

>>> x = Symbol('x')
>>> p = Poly(A.charpoly(), x, domain=A.domain)
>>> p
Poly(x**2 - 5*x - 2, x, domain='QQ')

convert_to(K)[source]#

Converts the Domain of a SDM matrix to K

Examples

>>> from sympy import ZZ, QQ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{1: ZZ(2)}, 1:{0:ZZ(1)}}, (2, 2), ZZ)
>>> A.convert_to(QQ)
{0: {1: 2}, 1: {0: 1}}

copy()[source]#

Returns the copy of a SDM object

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> elemsdict = {0:{1:QQ(2)}, 1:{}}
>>> A = SDM(elemsdict, (2, 2), QQ)
>>> B = A.copy()
>>> B
{0: {1: 2}, 1: {}}

det()[source]#

Returns determinant of A

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{0:QQ(1), 1:QQ(2)}, 1:{0:QQ(3), 1:QQ(4)}}, (2, 2), QQ)
>>> A.det()
-2

diagonal()[source]#

Returns the diagonal of the matrix as a list.

classmethod eye(shape, domain)[source]#

Returns a identity SDM matrix of dimensions size x size, belonging to the specified domain

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> I = SDM.eye((2, 2), QQ)
>>> I
{0: {0: 1}, 1: {1: 1}}

classmethod from_ddm(ddm)[source]#

Create SDM from a DDM.

Examples

>>> from sympy.polys.matrices.ddm import DDM
>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> ddm = DDM( [[QQ(1, 2), 0], [0, QQ(3, 4)]], (2, 2), QQ)
>>> A = SDM.from_ddm(ddm)
>>> A
{0: {0: 1/2}, 1: {1: 3/4}}
>>> SDM.from_ddm(ddm).to_ddm() == ddm
True

classmethod from_dok(dok, shape, domain)[source]#

Create SDM from dictionary of keys (dok) format.

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> dok = {(0, 1): QQ(2), (1, 0): QQ(3)}
>>> A = SDM.from_dok(dok, (2, 2), QQ)
>>> A
{0: {1: 2}, 1: {0: 3}}
>>> A == SDM.from_dok(A.to_dok(), A.shape, A.domain)
True

classmethod from_flat_nz(elements, data, domain)[source]#

Reconstruct a SDM after calling to_flat_nz().

See to_flat_nz() for explanation.

classmethod from_list(ddm, shape, domain)[source]#

Create SDM object from a list of lists.

Parameters:

ddm:

list of lists containing domain elements

shape:

Dimensions of SDM matrix

domain:

Returns:

SDM containing elements of ddm

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> ddm = [[QQ(1, 2), QQ(0)], [QQ(0), QQ(3, 4)]]
>>> A = SDM.from_list(ddm, (2, 2), QQ)
>>> A
{0: {0: 1/2}, 1: {1: 3/4}}

classmethod from_list_flat(elements, shape, domain)[source]#

Create SDM from a flat list of elements.

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> A = SDM.from_list_flat([QQ(0), QQ(2), QQ(0), QQ(0)], (2, 2), QQ)
>>> A
{0: {1: 2}}
>>> A == A.from_list_flat(A.to_list_flat(), A.shape, A.domain)
True

hstack(*B)[source]#

Horizontally stacks SDM matrices.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import SDM

>>> A = SDM({0: {0: ZZ(1), 1: ZZ(2)}, 1: {0: ZZ(3), 1: ZZ(4)}}, (2, 2), ZZ)
>>> B = SDM({0: {0: ZZ(5), 1: ZZ(6)}, 1: {0: ZZ(7), 1: ZZ(8)}}, (2, 2), ZZ)
>>> A.hstack(B)
{0: {0: 1, 1: 2, 2: 5, 3: 6}, 1: {0: 3, 1: 4, 2: 7, 3: 8}}

>>> C = SDM({0: {0: ZZ(9), 1: ZZ(10)}, 1: {0: ZZ(11), 1: ZZ(12)}}, (2, 2), ZZ)
>>> A.hstack(B, C)
{0: {0: 1, 1: 2, 2: 5, 3: 6, 4: 9, 5: 10}, 1: {0: 3, 1: 4, 2: 7, 3: 8, 4: 11, 5: 12}}

inv()[source]#

Returns inverse of a matrix A

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{0:QQ(1), 1:QQ(2)}, 1:{0:QQ(3), 1:QQ(4)}}, (2, 2), QQ)
>>> A.inv()
{0: {0: -2, 1: 1}, 1: {0: 3/2, 1: -1/2}}

is_diagonal()[source]#

Says whether this matrix is diagonal. True can be returned even if the matrix is not square.

is_lower()[source]#

Says whether this matrix is lower-triangular. True can be returned even if the matrix is not square.

is_upper()[source]#

Says whether this matrix is upper-triangular. True can be returned even if the matrix is not square.

is_zero_matrix()[source]#

Says whether this matrix has all zero entries.

lll(delta=MPQ(3, 4))[source]#

Returns the LLL-reduced basis for the SDM matrix.

lll_transform(delta=MPQ(3, 4))[source]#

Returns the LLL-reduced basis and transformation matrix.

lu()[source]#

Returns LU decomposition for a matrix A

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{0:QQ(1), 1:QQ(2)}, 1:{0:QQ(3), 1:QQ(4)}}, (2, 2), QQ)
>>> A.lu()
({0: {0: 1}, 1: {0: 3, 1: 1}}, {0: {0: 1, 1: 2}, 1: {1: -2}}, [])

lu_solve(b)[source]#

Uses LU decomposition to solve Ax = b,

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{0:QQ(1), 1:QQ(2)}, 1:{0:QQ(3), 1:QQ(4)}}, (2, 2), QQ)
>>> b = SDM({0:{0:QQ(1)}, 1:{0:QQ(2)}}, (2, 1), QQ)
>>> A.lu_solve(b)
{1: {0: 1/2}}

matmul(B)[source]#

Performs matrix multiplication of two SDM matrices

Parameters:

A, B: SDM to multiply

Returns:

SDM

SDM after multiplication

Raises:

DomainError

If domain of A does not match with that of B

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{1: ZZ(2)}, 1:{0:ZZ(1)}}, (2, 2), ZZ)
>>> B = SDM({0:{0:ZZ(2), 1:ZZ(3)}, 1:{0:ZZ(4)}}, (2, 2), ZZ)
>>> A.matmul(B)
{0: {0: 8}, 1: {0: 2, 1: 3}}

mul(b)[source]#

Multiplies each element of A with a scalar b

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{1: ZZ(2)}, 1:{0:ZZ(1)}}, (2, 2), ZZ)
>>> A.mul(ZZ(3))
{0: {1: 6}, 1: {0: 3}}

neg()[source]#

Returns the negative of a SDM matrix

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{1: ZZ(2)}, 1:{0:ZZ(1)}}, (2, 2), ZZ)
>>> A.neg()
{0: {1: -2}, 1: {0: -1}}

classmethod new(sdm, shape, domain)[source]#
Parameters:

sdm: A dict of dicts for non-zero elements in SDM

shape: tuple representing dimension of SDM

domain: Represents :py:class:~.Domain of SDM

Returns:

An SDM object

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> elemsdict = {0:{1: QQ(2)}}
>>> A = SDM.new(elemsdict, (2, 2), QQ)
>>> A
{0: {1: 2}}

nnz()[source]#

Number of non-zero elements in the SDM matrix.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{1: ZZ(2)}, 1:{0:ZZ(1)}}, (2, 2), ZZ)
>>> A.nnz()
2

nullspace()[source]#

Nullspace of a SDM matrix A.

The domain of the matrix must be a field.

It is better to use the nullspace() method rather than this method which is otherwise no longer used.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{0:QQ(1), 1:QQ(2)}, 1:{0: QQ(2), 1: QQ(4)}}, (2, 2), QQ)
>>> A.nullspace()
({0: {0: -2, 1: 1}}, )


sympy.polys.matrices.domainmatrix.DomainMatrix.nullspace

The preferred way to get the nullspace of a matrix.

nullspace_from_rref(pivots=None)[source]#

Returns nullspace for a SDM matrix A in RREF.

The domain of the matrix can be any domain.

The matrix must already be in reduced row echelon form (RREF).

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{0:QQ(1), 1:QQ(2)}, 1:{0: QQ(2), 1: QQ(4)}}, (2, 2), QQ)
>>> A_rref, pivots = A.rref()
>>> A_null, nonpivots = A_rref.nullspace_from_rref(pivots)
>>> A_null
{0: {0: -2, 1: 1}}
>>> pivots

>>> nonpivots



sympy.polys.matrices.domainmatrix.DomainMatrix.nullspace

The higher-level function that would usually be called instead of calling this one directly.

sympy.polys.matrices.domainmatrix.DomainMatrix.nullspace_from_rref

The higher-level direct equivalent of this function.

sympy.polys.matrices.ddm.DDM.nullspace_from_rref

The equivalent function for dense DDM matrices.

rref()[source]#

Returns reduced-row echelon form and list of pivots for the SDM

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{0:QQ(1), 1:QQ(2)}, 1:{0:QQ(2), 1:QQ(4)}}, (2, 2), QQ)
>>> A.rref()
({0: {0: 1, 1: 2}}, )

rref_den()[source]#

Returns reduced-row echelon form (RREF) with denominator and pivots.

Examples

>>> from sympy import QQ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{0:QQ(1), 1:QQ(2)}, 1:{0:QQ(2), 1:QQ(4)}}, (2, 2), QQ)
>>> A.rref_den()
({0: {0: 1, 1: 2}}, 1, )

scc()[source]#

Strongly connected components of a square matrix A.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{0: ZZ(2)}, 1:{1:ZZ(1)}}, (2, 2), ZZ)
>>> A.scc()
[, ]

sub(B)[source]#

Subtracts two SDM matrices

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import SDM
>>> A = SDM({0:{1: ZZ(2)}, 1:{0:ZZ(1)}}, (2, 2), ZZ)
>>> B  = SDM({0:{0: ZZ(3)}, 1:{1:ZZ(4)}}, (2, 2), ZZ)
>>> A.sub(B)
{0: {0: -3, 1: 2}, 1: {0: 1, 1: -4}}

to_ddm()[source]#

Convert a SDM object to a DDM object

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> A = SDM({0:{1:QQ(2)}, 1:{}}, (2, 2), QQ)
>>> A.to_ddm()
[[0, 2], [0, 0]]

to_dfm()[source]#

Convert a SDM object to a DFM object

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> A = SDM({0:{1:QQ(2)}, 1:{}}, (2, 2), QQ)
>>> A.to_dfm()
[[0, 2], [0, 0]]

to_dfm_or_ddm()[source]#

Convert to DFM if possible, else DDM.

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> A = SDM({0:{1:QQ(2)}, 1:{}}, (2, 2), QQ)
>>> A.to_dfm_or_ddm()
[[0, 2], [0, 0]]
>>> type(A.to_dfm_or_ddm())  # depends on the ground types
<class 'sympy.polys.matrices._dfm.DFM'>

to_dok()[source]#

Convert to dictionary of keys (dok) format.

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> A = SDM({0: {1: QQ(2)}, 1: {0: QQ(3)}}, (2, 2), QQ)
>>> A.to_dok()
{(0, 1): 2, (1, 0): 3}

to_flat_nz()[source]#

Convert SDM to a flat list of nonzero elements and data.

Explanation

This is used to operate on a list of the elements of a matrix and then reconstruct a modified matrix with elements in the same positions using from_flat_nz(). Zero elements are omitted from the list.

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> A = SDM({0:{1:QQ(2)}, 1:{0: QQ(3)}}, (2, 2), QQ)
>>> elements, data = A.to_flat_nz()
>>> elements
[2, 3]
>>> A == A.from_flat_nz(elements, data, A.domain)
True

to_list()[source]#

Convert a SDM object to a list of lists.

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> elemsdict = {0:{1:QQ(2)}, 1:{}}
>>> A = SDM(elemsdict, (2, 2), QQ)
>>> A.to_list()
[[0, 2], [0, 0]]

to_list_flat()[source]#

Convert SDM to a flat list.

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> A = SDM({0:{1:QQ(2)}, 1:{0: QQ(3)}}, (2, 2), QQ)
>>> A.to_list_flat()
[0, 2, 3, 0]
>>> A == A.from_list_flat(A.to_list_flat(), A.shape, A.domain)
True

to_sdm()[source]#

Convert to SDM format (returns self).

transpose()[source]#

Returns the transpose of a SDM matrix

Examples

>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> A = SDM({0:{1:QQ(2)}, 1:{}}, (2, 2), QQ)
>>> A.transpose()
{1: {0: 2}}

vstack(*B)[source]#

Vertically stacks SDM matrices.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices.sdm import SDM

>>> A = SDM({0: {0: ZZ(1), 1: ZZ(2)}, 1: {0: ZZ(3), 1: ZZ(4)}}, (2, 2), ZZ)
>>> B = SDM({0: {0: ZZ(5), 1: ZZ(6)}, 1: {0: ZZ(7), 1: ZZ(8)}}, (2, 2), ZZ)
>>> A.vstack(B)
{0: {0: 1, 1: 2}, 1: {0: 3, 1: 4}, 2: {0: 5, 1: 6}, 3: {0: 7, 1: 8}}

>>> C = SDM({0: {0: ZZ(9), 1: ZZ(10)}, 1: {0: ZZ(11), 1: ZZ(12)}}, (2, 2), ZZ)
>>> A.vstack(B, C)
{0: {0: 1, 1: 2}, 1: {0: 3, 1: 4}, 2: {0: 5, 1: 6}, 3: {0: 7, 1: 8}, 4: {0: 9, 1: 10}, 5: {0: 11, 1: 12}}

classmethod zeros(shape, domain)[source]#

Returns a SDM of size shape, belonging to the specified domain

In the example below we declare a matrix A where,

$\begin{split}A := \left[\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \end{array} \right]\end{split}$
>>> from sympy.polys.matrices.sdm import SDM
>>> from sympy import QQ
>>> A = SDM.zeros((2, 3), QQ)
>>> A
{}

sympy.polys.matrices.sdm.sdm_berk(M, n, K)[source]#

Berkowitz algorithm for computing the characteristic polynomial.

Explanation

The Berkowitz algorithm is a division-free algorithm for computing the characteristic polynomial of a matrix over any commutative ring using only arithmetic in the coefficient ring. This implementation is for sparse matrices represented in a dict-of-dicts format (like SDM).

Examples

>>> from sympy import Matrix
>>> from sympy.polys.matrices.sdm import sdm_berk
>>> from sympy.polys.domains import ZZ
>>> M = {0: {0: ZZ(1), 1:ZZ(2)}, 1: {0:ZZ(3), 1:ZZ(4)}}
>>> sdm_berk(M, 2, ZZ)
{0: 1, 1: -5, 2: -2}
>>> Matrix([[1, 2], [3, 4]]).charpoly()
PurePoly(lambda**2 - 5*lambda - 2, lambda, domain='ZZ')


sympy.polys.matrices.domainmatrix.DomainMatrix.charpoly

The high-level interface to this function.

sympy.polys.matrices.dense.ddm_berk

The dense version of this function.

References

sympy.polys.matrices.sdm.sdm_irref(A)[source]#

RREF and pivots of a sparse matrix A.

Compute the reduced row echelon form (RREF) of the matrix A and return a list of the pivot columns. This routine does not work in place and leaves the original matrix A unmodified.

The domain of the matrix must be a field.

Examples

This routine works with a dict of dicts sparse representation of a matrix:

>>> from sympy import QQ
>>> from sympy.polys.matrices.sdm import sdm_irref
>>> A = {0: {0: QQ(1), 1: QQ(2)}, 1: {0: QQ(3), 1: QQ(4)}}
>>> Arref, pivots, _ = sdm_irref(A)
>>> Arref
{0: {0: 1}, 1: {1: 1}}
>>> pivots
[0, 1]


The analogous calculation with MutableDenseMatrix would be

>>> from sympy import Matrix
>>> M = Matrix([[1, 2], [3, 4]])
>>> Mrref, pivots = M.rref()
>>> Mrref
Matrix([
[1, 0],
[0, 1]])
>>> pivots
(0, 1)


Notes

The cost of this algorithm is determined purely by the nonzero elements of the matrix. No part of the cost of any step in this algorithm depends on the number of rows or columns in the matrix. No step depends even on the number of nonzero rows apart from the primary loop over those rows. The implementation is much faster than ddm_rref for sparse matrices. In fact at the time of writing it is also (slightly) faster than the dense implementation even if the input is a fully dense matrix so it seems to be faster in all cases.

The elements of the matrix should support exact division with /. For example elements of any domain that is a field (e.g. QQ) should be fine. No attempt is made to handle inexact arithmetic.

sympy.polys.matrices.domainmatrix.DomainMatrix.rref

The higher-level function that would normally be used to call this routine.

sympy.polys.matrices.dense.ddm_irref

The dense equivalent of this routine.

sdm_rref_den

Fraction-free version of this routine.

sympy.polys.matrices.sdm.sdm_nullspace_from_rref(A, one, ncols, pivots, nonzero_cols)[source]#

Get nullspace from A which is in RREF

sympy.polys.matrices.sdm.sdm_particular_from_rref(A, ncols, pivots)[source]#

Get a particular solution from A which is in RREF

sympy.polys.matrices.sdm.sdm_rref_den(A, K)[source]#

Return the reduced row echelon form (RREF) of A with denominator.

The RREF is computed using fraction-free Gauss-Jordan elimination.

Explanation

The algorithm used is the fraction-free version of Gauss-Jordan elimination described as FFGJ in [R744]. Here it is modified to handle zero or missing pivots and to avoid redundant arithmetic. This implementation is also optimized for sparse matrices.

The domain $$K$$ must support exact division (K.exquo) but does not need to be a field. This method is suitable for most exact rings and fields like ZZ, QQ and QQ<a>. In the case of QQ or K(x) it might be more efficient to clear denominators and use ZZ or K[x] instead.

For inexact domains like RR and CC use ddm_irref instead.

Examples

>>> from sympy.polys.matrices.sdm import sdm_rref_den
>>> from sympy.polys.domains import ZZ
>>> A = {0: {0: ZZ(1), 1: ZZ(2)}, 1: {0: ZZ(3), 1: ZZ(4)}}
>>> A_rref, den, pivots = sdm_rref_den(A, ZZ)
>>> A_rref
{0: {0: -2}, 1: {1: -2}}
>>> den
-2
>>> pivots
[0, 1]


sympy.polys.matrices.domainmatrix.DomainMatrix.rref_den

Higher-level interface to sdm_rref_den that would usually be used instead of calling this function directly.

sympy.polys.matrices.sdm.sdm_rref_den

The SDM method that uses this function.

sdm_irref

Computes RREF using field division.

ddm_irref_den

The dense version of this algorithm.

References

[R744] (1,2)

Fraction-free algorithms for linear and polynomial equations. George C. Nakos , Peter R. Turner , Robert M. Williams. https://dl.acm.org/doi/10.1145/271130.271133

class sympy.polys.matrices._dfm.DFM(rowslist, shape, domain)[source]#

Dense FLINT matrix. This class is a wrapper for matrices from python-flint.

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.matrices.dfm import DFM
>>> dfm = DFM([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], (2, 2), ZZ)
>>> dfm
[[1, 2], [3, 4]]
>>> dfm.rep
[1, 2]
[3, 4]
>>> type(dfm.rep)
<class 'flint._flint.fmpz_mat'>


Usually, the DFM class is not instantiated directly, but is created as the internal representation of DomainMatrix. When $$SYMPY_GROUND_TYPES$$ is set to $$flint$$ and $$python-flint$$ is installed, the DFM class is used automatically as the internal representation of DomainMatrix in dense format if the domain is supported by python-flint.

>>> from sympy.polys.matrices.domainmatrix import DM
>>> dM = DM([[1, 2], [3, 4]], ZZ)
>>> dM.rep
[[1, 2], [3, 4]]


A DomainMatrix can be converted to DFM by calling the to_dfm() method:

>>> dM.to_dfm()
[[1, 2], [3, 4]]


applyfunc(func, domain)[source]#

Apply a function to each entry of a DFM matrix.

charpoly()[source]#

Compute the characteristic polynomial of the matrix using FLINT.

Examples

>>> from sympy import Matrix
>>> M = Matrix([[1, 2], [3, 4]])
>>> dfm = M.to_DM().to_dfm()  # need ground types = 'flint'
>>> dfm
[[1, 2], [3, 4]]
>>> dfm.charpoly()
[1, -5, -2]


Notes

Calls the .charpoly() method of the underlying FLINT matrix.

For ZZ or QQ this calls fmpz_mat_charpoly or fmpq_mat_charpoly respectively.

At the time of writing the implementation of fmpq_mat_charpoly clears a denominator from the whole matrix and then calls fmpz_mat_charpoly. The coefficients of the characteristic polynomial are then multiplied by powers of the denominator.

The fmpz_mat_charpoly method uses a modular algorithm with CRT reconstruction. The modular algorithm uses nmod_mat_charpoly which uses Berkowitz for small matrices and non-prime moduli or otherwise the Danilevsky method.

sympy.polys.matrices.domainmatrix.DomainMatrix.charpoly

Higher level interface to compute the characteristic polynomial of a matrix.

convert_to(domain)[source]#

Convert to a new domain.

copy()[source]#

Return a copy of self.

det()[source]#

Compute the determinant of the matrix using FLINT.

Examples

>>> from sympy import Matrix
>>> M = Matrix([[1, 2], [3, 4]])
>>> dfm = M.to_DM().to_dfm()
>>> dfm
[[1, 2], [3, 4]]
>>> dfm.det()
-2


Notes

Calls the .det() method of the underlying FLINT matrix.

For ZZ or QQ this calls fmpz_mat_det or fmpq_mat_det respectively.

At the time of writing the implementation of fmpz_mat_det uses one of several algorithms depending on the size of the matrix and bit size of the entries. The algorithms used are:

• Cofactor for very small (up to 4x4) matrices.

• Bareiss for small (up to 25x25) matrices.

• Modular algorithms for larger matrices (up to 60x60) or for larger matrices with large bit sizes.

• Modular “accelerated” for larger matrices (60x60 upwards) if the bit size is smaller than the dimensions of the matrix.

The implementation of fmpq_mat_det clears denominators from each row (not the whole matrix) and then calls fmpz_mat_det and divides by the product of the denominators.

sympy.polys.matrices.domainmatrix.DomainMatrix.det

Higher level interface to compute the determinant of a matrix.

classmethod diag(elements, domain)[source]#

Return a diagonal matrix.

diagonal()[source]#

Return the diagonal of a DFM matrix.

extract(rowslist, colslist)[source]#

Extract a submatrix.

extract_slice(rowslice, colslice)[source]#

Slice a DFM.

classmethod eye(n, domain)[source]#

Return the identity matrix of size n.

classmethod from_ddm(ddm)[source]#

Convert from a DDM.

classmethod from_flat_nz(elements, data, domain)[source]#

Inverse of to_flat_nz().

classmethod from_list(rowslist, shape, domain)[source]#

Construct from a nested list.

classmethod from_list_flat(elements, shape, domain)[source]#

Inverse of to_list_flat().

getitem(i, j)[source]#

Get the (i, j)-th entry.

hstack(*others)[source]#

Horizontally stack matrices.

inv()[source]#

Compute the inverse of a matrix using FLINT.

Examples

>>> from sympy import Matrix, QQ
>>> M = Matrix([[1, 2], [3, 4]])
>>> dfm = M.to_DM().to_dfm().convert_to(QQ)
>>> dfm
[[1, 2], [3, 4]]
>>> dfm.inv()
[[-2, 1], [3/2, -1/2]]
>>> dfm.matmul(dfm.inv())
[[1, 0], [0, 1]]


Notes

Calls the .inv() method of the underlying FLINT matrix.

For now this will raise an error if the domain is ZZ but will use the FLINT method for QQ.

The FLINT methods for ZZ and QQ are fmpz_mat_inv and fmpq_mat_inv respectively. The fmpz_mat_inv method computes an inverse with denominator. This is implemented by calling fmpz_mat_solve (see notes in lu_solve() about the algorithm).

The fmpq_mat_inv method clears denominators from each row and then multiplies those into the rhs identity matrix before calling fmpz_mat_solve.

sympy.polys.matrices.domainmatrix.DomainMatrix.inv

Higher level method for computing the inverse of a matrix.

is_diagonal()[source]#

Return True if the matrix is diagonal.

is_lower()[source]#

Return True if the matrix is lower triangular.

is_upper()[source]#

Return True if the matrix is upper triangular.

is_zero_matrix()[source]#

Return True if the matrix is the zero matrix.

lll(delta=0.75)[source]#

Compute LLL-reduced basis using FLINT.

See lll_transform() for more information.

Examples

>>> from sympy import Matrix
>>> M = Matrix([[1, 2, 3], [4, 5, 6]])
>>> M.to_DM().to_dfm().lll()
[[2, 1, 0], [-1, 1, 3]]


sympy.polys.matrices.domainmatrix.DomainMatrix.lll

Higher level interface to compute LLL-reduced basis.

lll_transform

Compute LLL-reduced basis and transform matrix.

lll_transform(delta=0.75)[source]#

Compute LLL-reduced basis and transform using FLINT.

Examples

>>> from sympy import Matrix
>>> M = Matrix([[1, 2, 3], [4, 5, 6]]).to_DM().to_dfm()
>>> M_lll, T = M.lll_transform()
>>> M_lll
[[2, 1, 0], [-1, 1, 3]]
>>> T
[[-2, 1], [3, -1]]
>>> T.matmul(M) == M_lll
True


sympy.polys.matrices.domainmatrix.DomainMatrix.lll

Higher level interface to compute LLL-reduced basis.

lll

Compute LLL-reduced basis without transform matrix.

lu()[source]#

Return the LU decomposition of the matrix.

lu_solve(rhs)[source]#

Solve a matrix equation using FLINT.

Examples

>>> from sympy import Matrix, QQ
>>> M = Matrix([[1, 2], [3, 4]])
>>> dfm = M.to_DM().to_dfm().convert_to(QQ)
>>> dfm
[[1, 2], [3, 4]]
>>> rhs = Matrix([1, 2]).to_DM().to_dfm().convert_to(QQ)
>>> dfm.lu_solve(rhs)
[, [1/2]]


Notes

Calls the .solve() method of the underlying FLINT matrix.

For now this will raise an error if the domain is ZZ but will use the FLINT method for QQ.

The FLINT methods for ZZ and QQ are fmpz_mat_solve and fmpq_mat_solve respectively. The fmpq_mat_solve method uses one of two algorithms:

• For small matrices (<25 rows) it clears denominators between the matrix and rhs and uses fmpz_mat_solve.

• For larger matrices it uses fmpq_mat_solve_dixon which is a modular approach with CRT reconstruction over QQ.

The fmpz_mat_solve method uses one of four algorithms:

• For very small (<= 3x3) matrices it uses a Cramer’s rule.

• For small (<= 15x15) matrices it uses a fraction-free LU solve.

• Otherwise it uses either Dixon or another multimodular approach.

sympy.polys.matrices.domainmatrix.DomainMatrix.lu_solve

Higher level interface to solve a matrix equation.

matmul(other)[source]#

Multiply two DFM matrices.

mul(other)[source]#

Multiply a DFM matrix from the right by a scalar.

mul_elementwise(other)[source]#

Elementwise multiplication of two DFM matrices.

neg()[source]#

Negate a DFM matrix.

nnz()[source]#

Return the number of non-zero elements in the matrix.

nullspace()[source]#

Return a basis for the nullspace of the matrix.

nullspace_from_rref(pivots=None)[source]#

Return a basis for the nullspace of the matrix.

classmethod ones(shape, domain)[source]#

Return a one DFM matrix.

particular()[source]#

Return a particular solution to the system.

rmul(other)[source]#

Multiply a DFM matrix from the left by a scalar.

scc()[source]#

Return the strongly connected components of the matrix.

setitem(i, j, value)[source]#

Set the (i, j)-th entry.

sub(other)[source]#

Subtract two DFM matrices.

to_ddm()[source]#

Convert to a DDM.

to_dfm()[source]#

Return self.

to_dfm_or_ddm()[source]#

Convert to a DFM.

This DFM method exists to parallel the DDM and SDM methods. For DFM it will always return self.

to_dok()[source]#

Convert to a DOK.

to_flat_nz()[source]#

Convert to a flat list of non-zeros.

to_list()[source]#

Convert to a nested list.

to_list_flat()[source]#

Convert to a flat list.

to_sdm()[source]#

Convert to a SDM.

transpose()[source]#

Transpose a DFM matrix.

vstack(*others)[source]#

Vertically stack matrices.

classmethod zeros(shape, domain)[source]#

Return a zero DFM matrix.

sympy.polys.matrices.normalforms.smith_normal_form(m)[source]#

Return the Smith Normal Form of a matrix $$m$$ over the ring $$domain$$. This will only work if the ring is a principal ideal domain.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy.polys.matrices.normalforms import smith_normal_form
>>> m = DomainMatrix([[ZZ(12), ZZ(6), ZZ(4)],
...                   [ZZ(3), ZZ(9), ZZ(6)],
...                   [ZZ(2), ZZ(16), ZZ(14)]], (3, 3), ZZ)
>>> print(smith_normal_form(m).to_Matrix())
Matrix([[1, 0, 0], [0, 10, 0], [0, 0, -30]])

sympy.polys.matrices.normalforms.hermite_normal_form(A, *, D=None, check_rank=False)[source]#

Compute the Hermite Normal Form of DomainMatrix A over ZZ.

Parameters:

A : $$m \times n$$ DomainMatrix over ZZ.

D : ZZ, optional

Let $$W$$ be the HNF of A. If known in advance, a positive integer D being any multiple of $$\det(W)$$ may be provided. In this case, if A also has rank $$m$$, then we may use an alternative algorithm that works mod D in order to prevent coefficient explosion.

check_rank : boolean, optional (default=False)

The basic assumption is that, if you pass a value for D, then you already believe that A has rank $$m$$, so we do not waste time checking it for you. If you do want this to be checked (and the ordinary, non-modulo D algorithm to be used if the check fails), then set check_rank to True.

Returns:

DomainMatrix

The HNF of matrix A.

Raises:

DMDomainError

If the domain of the matrix is not ZZ, or if D is given but is not in ZZ.

DMShapeError

If the mod D algorithm is used but the matrix has more rows than columns.

Examples

>>> from sympy import ZZ
>>> from sympy.polys.matrices import DomainMatrix
>>> from sympy.polys.matrices.normalforms import hermite_normal_form
>>> m = DomainMatrix([[ZZ(12), ZZ(6), ZZ(4)],
...                   [ZZ(3), ZZ(9), ZZ(6)],
...                   [ZZ(2), ZZ(16), ZZ(14)]], (3, 3), ZZ)
>>> print(hermite_normal_form(m).to_Matrix())
Matrix([[10, 0, 2], [0, 15, 3], [0, 0, 2]])


References

[R745]

Cohen, H. A Course in Computational Algebraic Number Theory. (See Algorithms 2.4.5 and 2.4.8.)