# abelian.linalg package¶

## abelian.linalg.factorizations module¶

This module contains factorization algorithms for matrices over the integers. All the inputs and outputs are of type MutableDenseMatrix.

hermite_normal_form(A)

Compute U and H such that A*U = H.

This algorithm computes the column version of the Hermite normal form, and returns a tuple of matrices (U, H) such that A*U = H. The matrix U is an unimodular transformation matrix and H is the result of the transformation, i.e. H is in Hermite normal form.

Parameters: A (MutableDenseMatrix) – The matrix to decompose. U (MutableDenseMatrix) – An unimodular matrix, i.e. integer matrix with determinant +/- 1. H (MutableDenseMatrix) – A matrix in Hermite normal form.

Examples

>>> from sympy import Matrix
>>> A = Matrix([[1, 2],
...             [3, 4]])
>>> U, H = hermite_normal_form(A)
>>> # Verify that U is unimodular (determinant +/- 1)
>>> U.det() in [1, -1]
True
>>> # Verify the decomposition
>>> A*U == H
True

smith_normal_form(A, compute_unimod=True)

Compute U,S,V such that U*A*V = S.

This algorithm computes the Smith normal form of an integer matrix. If compute_unimod is True, it returns matrices (U, S, V) such that U*A*V = S, where U and V are unimodular and S is in Smith normal form. If compute_unimod is False, it returns S and does not compute U and V.

Parameters: A (MutableDenseMatrix) – The matrix to factor. compute_unimod (bool) – Whether or not to compute and return unimodular matrices U and V. U (MutableDenseMatrix) – An unimodular matrix, i.e. integer matrix with determinant +/- 1. S (MutableDenseMatrix) – A matrix in Smith normal form. V (MutableDenseMatrix) – An unimodular matrix, i.e. integer matrix with determinant +/- 1.

Examples

>>> from sympy import Matrix
>>> A = Matrix([[1, 2],
...             [3, 4]])
>>> U, S, V = smith_normal_form(A)
>>> # Verify that U and V are both unimodular
>>> U.det() in [1, -1] and V.det() in [1, -1]
True
>>> # Verify the factorization
>>> U * A * V == S
True
>>> # Compute without U and V, verify that the result is the same
>>> K = smith_normal_form(A, compute_unimod=False)
>>> K == S
True


## abelian.linalg.factorizations_reals module¶

This module contains functions which calculate mapping properties of homomorphisms between R^n and R^m using the singular value decomposition (SVD). All the inputs and outputs are of type MutableDenseMatrix.

numerical_SVD(A)

Compute U,S,V such that U*S*V = A.

The input is converted to numerical data, the SVD is computed using the np.linalg.svd routine, which wraps the LAPACK routine _gesdd. The data is then converted to a sympy matrix and returned.

Parameters: A (MutableDenseMatrix) – A sympy matrix. U (MutableDenseMatrix) – A (close to) orthogonal sympy matrix. S (MutableDenseMatrix) – A diagonal sympy matrix matrix. V (MutableDenseMatrix) – A (close to) orthogonal sympy matrix.

Examples

>>> A = Matrix([[1, 2], [3, 4]])
>>> U, S, V = numerical_SVD(A)
>>> # U is orthogonal (up to machine precision or so)
>>> abs(abs(U.det()) - 1) < 10e-10
True
>>> # Verify that the decomposition is close to the original
>>> sum(abs(k) for k in (U*S*V - A))  < 10e-10
True

numerical_rank(A)

Convert to numerical matrix and compute rank.

Parameters: A (MutableDenseMatrix) – A sympy matrix. r – The rank of A. int

Examples

>>> A = Matrix([[1, 2], [3, 4]])
>>> numerical_rank(A)
2
>>> A = Matrix([[0, 0], [0, 10e-10]])
>>> numerical_rank(A)
1

real_coimage(A)

Find the coimage of A, when the entries are real.

Converts the matrix to a numerical input, computes the SVD, finds the coimage epimorphism (row space of A), converts back to a sympy-matrix and returns.

Parameters: A (MutableDenseMatrix) – A sympy matrix. K – The coimage of A. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> A = Matrix([[1, 0, 0],
...             [0, 1, 0]])
>>> im = real_image(A)
>>> coim = real_coimage(A)
>>> # Verify the decomposition
>>> sum(abs(k) for k in (A - im * coim)) < 10e-15
True

real_cokernel(A)

Find the cokernel of A, when the entries are real.

Converts the matrix to a numerical input, computes the SVD, finds the cokernel epimorphism (null space of A^T), converts back to a sympy-matrix and returns.

Parameters: A (MutableDenseMatrix) – A sympy matrix. K – The cokernel of A. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> A = Matrix([[1, 0],
...             [0, 1],
...             [2, 2]])
>>> coker = real_cokernel(A)
>>> # Verify the decomposition
>>> sum(abs(k) for k in (coker * A)) < 10e-15
True

real_image(A)

Find the image of A, when the entries are real.

Converts the matrix to a numerical input, computes the SVD, finds the image monomorphism (column space), converts back to a sympy-matrix and returns.

Parameters: A (MutableDenseMatrix) – A sympy matrix. K – The image of A. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> A = Matrix([[1, 0],
...             [0, 1],
...             [1, 1]])
>>> im = real_image(A)
>>> coim = real_coimage(A)
>>> # Verify the decomposition
>>> sum(abs(k) for k in (A - im * coim)) < 10e-15
True

real_kernel(A)

Find the kernel of A, when the entries are real.

Converts the matrix to a numerical input, computes the SVD, finds the kernel monomorphism (null space of A), converts back to a sympy-matrix and returns.

Parameters: A (MutableDenseMatrix) – A sympy matrix. K – The kernel of A. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> A = Matrix([[1, 0, 1],
...             [0, 1, 1],
...             [2, 2, 4]])
>>> ker = real_kernel(A)
>>> # Verify the decomposition
>>> sum(abs(k) for k in (A * ker)) < 10e-15
True


## abelian.linalg.free_to_free module¶

This module contains functions which calculate mapping properties of free-to-free homomorphisms. All the inputs and outputs are of type MutableDenseMatrix.

elements_increasing_norm(free_rank, end_value=None)

Continually yield every element in Z^r of increasing max-norm.

Parameters: free_rank (int) – The free rank (like dimension) of Z^r, i.e. free_rank = r. tuple – Elements in Z^r with increasing maxnorm.

Examples

>>> free_rank = 2 # Like dimension
>>> for count, element in enumerate(elements_increasing_norm(free_rank)):
...     if count >= 9:
...         break
...     print(count, element, max(abs(k) for k in element))
0 (0, 0) 0
1 (1, -1) 1
2 (-1, -1) 1
3 (1, 0) 1
4 (-1, 0) 1
5 (1, 1) 1
6 (-1, 1) 1
7 (0, 1) 1
8 (0, -1) 1

elements_of_maxnorm(free_rank, maxnorm_value)

Yield every element of Z^r such that max_norm(element) = maxnorm_value.

Parameters: free_rank (int) – The free rank (like dimension) of Z^r, i.e. free_rank = r. maxnorm_value (int) – The value of the maximum norm of the elements generated. tuple – Elements in Z^r that satisfy the norm criterion.

Examples

>>> free_rank = 3 # Like dimension
>>> maxnorm_value = 4
>>> elements = list(elements_of_maxnorm(free_rank, maxnorm_value))
>>> # Verify that the max norm is the correct value
>>> all(max(abs(k) for k in e) for e in elements)
True
>>> # Verify the number of elements
>>> n = maxnorm_value
>>> len(elements) == ((2*n + 1)**free_rank - (2*n - 1)**free_rank)
True

elements_of_maxnorm_FGA(orders, maxnorm_value)

Yield every element of Z_orders such that max_norm(element) = maxnorm_value.

Parameters: orders (list) – Orders in Z_orders, where 0 means infinite order, i.e. [2, 0] is Z_2 + Z. maxnorm_value (int) – The value of the maximum norm of the elements generated. tuple – Elements in Z_orders that satisfy the norm criterion.

Examples

>>> orders = [0, 0]
>>> norm_value = 1
>>> elements = list(elements_of_maxnorm_FGA(orders, norm_value))
>>> len(elements)
8
>>> orders = [0, 3]
>>> norm_value = 2
>>> for element in elements_of_maxnorm_FGA(orders, norm_value):
...     print(element)
(2, 2)
(-2, 2)
(2, 0)
(-2, 0)
(2, 1)
(-2, 1)

free_coimage(A)

Computes the free-to-free coimage epimorphism of A.

Let $$A: \mathbb{Z}^n -> \mathbb{Z}^m$$ be a homomorphism from a free (infinite order) finitely generated Abelian group (FGA) to another free FGA. Associated with this homomorphism is the coimage epimorphism. The coimage epimorphism has the property that $$A$$ factors through the composition of the coimage and image morphisms, i.e. $$\operatorname{im}(A) \circ \operatorname{coim}(A) = A$$.

Parameters: A (MutableDenseMatrix) – A sympy integer matrix. coim_A – The coimage epimorphism associated with A. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> A = Matrix([[1, 0],
...             [0, 1],
...             [1, 1]])
>>> # Clearly the image is A itself, so coim(A) must be I
>>> free_coimage(A) == Matrix.eye(2)
True
>>> # Verify the image(A) * coimage(A) = A factorization
>>> free_image(A) * free_coimage(A) == A
True

free_cokernel(A)

Computes the free-to-free cokernel epimorphism of A.

Let $$A: \mathbb{Z}^n -> \mathbb{Z}^m$$ be a homomorphism from a free (infinite order) finitely generated Abelian group (FGA) to another free FGA. Associated with this homomorphism is the cokernel epimorphism. The cokernel epimorphism has the property that $$\operatorname{coker}(A) \circ A = \mathbf{0}$$, where $$\mathbf{0}$$ denotes the zero morphism.

Parameters: A (MutableDenseMatrix) – A sympy integer matrix. coker_A – The cokernel epimorphism associated with A. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> from abelian.linalg.utils import matrix_mod_vector
>>> A = Matrix([[1, 0],
...             [0, 1],
...             [1, 1]])
>>> coker_A = free_cokernel(A)
>>> quotient = free_quotient(A)
>>> # Compute coker(A) * A and verify that it's 0 in the
>>> # target group of coker(A).
>>> product = matrix_mod_vector(coker_A * A, quotient)
>>> product == 0 * product
True

free_image(A)

Computes the free-to-free image monomorphism of A.

Let $$A: \mathbb{Z}^n -> \mathbb{Z}^m$$ be a homomorphism from a free (infinite order) finitely generated Abelian group (FGA) to another free FGA. Associated with this homomorphism is the image monomorphism. The image monomorphism has the property that $$A$$ factors through the composition of the coimage and image morphisms, i.e. $$\operatorname{im}(A) \circ \operatorname{coim}(A) = A$$.

Parameters: A (MutableDenseMatrix) – A sympy integer matrix. im_A – The image monomorphism associated with A. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> A = Matrix([[1, 0, 1],
...             [0, 1, 1]])
>>> # Clearly the image is the identity matrix
>>> free_image(A) == Matrix.eye(2)
True
>>> # Verify the image(A) * coimage(A) = A factorization
>>> free_image(A) * free_coimage(A) == A
True

free_kernel(A)

Computes the free-to-free kernel monomorphism of A.

Let $$A: \mathbb{Z}^n -> \mathbb{Z}^m$$ be a homomorphism from a free (infinite order) finitely generated Abelian group (FGA) to another free FGA. Associated with this homomorphism is the kernel monomorphism. The kernel monomorphism has the property that $$A \circ \operatorname{ker}(A) = \mathbf{0}$$, where $$\mathbf{0}$$ denotes the zero morphism.

Parameters: A (MutableDenseMatrix) – A sympy integer matrix. ker_A – The kernel monomorphism associated with A. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> A = Matrix([[1, 0, 1],
...             [0, 1, 1]])
>>> ker_A = free_kernel(A)
>>> # Verify the factorization
>>> A * ker_A == Matrix([0, 0])
True

free_quotient(A)

Compute the quotient group Z^m / im(A).

Let $$A: \mathbb{Z}^n -> \mathbb{Z}^m$$ be a homomorphism from a free (infinite order) finitely generated Abelian group (FGA) to another free FGA. Associated with this homomorphism is the cokernel epimorphism, which maps from $$A: \mathbb{Z}^n$$ to $$A: \mathbb{Z}^m / \operatorname{im}(A)$$.

Parameters: A (MutableDenseMatrix) – A sympy integer matrix. quotient – The structure of the quotient group target(A)/im(A). MutableDenseMatrix

Examples

>>> from sympy import diag
>>> A = diag(1, 2, 3)
>>> free_quotient(A) == Matrix([1, 1, 6])
True

mod(a, b)

Mod for integers, tuples and lists.

Parameters: a (int, tuple or list) – The argument. b (int, tuple or list) – The order. A mod b. int, tuple or list

Examples

>>> mod(7, 5) # Integer data
2
>>> mod((5, 8), (4, 4)) # Tuple data
(1, 0)
>>> mod([5, 8], [4, 4]) # List data
[1, 0]


## abelian.linalg.solvers module¶

This module contains equation solvers. All the inputs and outputs are of type MutableDenseMatrix.

solve(A, b, p=None)

Solve eqn Ax = b mod p over Z.

The data (A, b, p) must be integer. The equation Ax = b mod p is solved, if a solution exists. If A is an epimorphism but not a monomorphism (i.e. overdetermined), one of the possible solutions is returned. If A is a monomorphism but not an epimorphism (i.e. underdetermined), a solution will be returned if one exists. If there is no solution, None is returned.

Parameters: A (MutableDenseMatrix) – A sympy integer matrix of size m x n. b (MutableDenseMatrix) – A sympy column matrix of size m x 1. p (MutableDenseMatrix) – A sympy column matrix of size m x 1. This column matrix represents the orders of the target group of A. If None, p will be set to the zero vector, i.e. infinite order in all components. x – A solution to A*x = b mod p, where x is of size n x 1. If no solution is found, None is returned. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> from abelian.linalg.utils import vector_mod_vector
>>> A = Matrix([[5, 0, 3],
...             [0, 3, 4]])
>>> x = Matrix([2, -1, 2])
>>> p = Matrix([9, 9])
>>> b = vector_mod_vector(A*x, p)
>>> x_sol = solve(A, b, p)
>>> vector_mod_vector(A*x_sol, p) == b
True

solve_epi(A, B, p=None)

Solve the equation X * mod p * A = B, where A is an epimorphism.

The algorithm will produce a solution if (mod p * A) has a one sided inverse such that A_inv * A = I, i.e. A is an epimorphism.

Parameters: A (MutableDenseMatrix) – A sympy integer matrix of size m x n. B (MutableDenseMatrix) – A sympy column matrix of size k x n. p (MutableDenseMatrix) – A sympy column matrix of size m x 1. This column matrix represents the orders of the target group of A. If None, p will be set to the zero vector, i.e. infinite order. x – A solution to X * mod p * A = B. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> from abelian.linalg.utils import vector_mod_vector
>>> A = Matrix([[5, 0, 3],
...             [0, 3, 4]])
>>> X = Matrix([[1, 1],
...             [0, 1]])
>>> B = X * A
>>> X_sol = solve_epi(A, B)
>>> X_sol * A == B
True


## abelian.linalg.utils module¶

This module contains a set of utility functions which are used by the other modules in the linalg package. The functions defined herein operate on matrices, or are at the very least related to linear algebra computations.

columns_as_list(A)

Returns the columns of A as a list of lists.

Parameters: A (MutableDenseMatrix) – A sympy matrix. list_of_cols – A list of lists, where each sub_list is a column, e.g. structure [[col1], [col2], …]. list

Examples

>>> from sympy import Matrix
>>> A = Matrix([[1, 2],
...             [3, 4]])
>>> list_of_cols = columns_as_list(A)
>>> list_of_cols
[[1, 3], [2, 4]]

diag_times_mat(diagonal, A)

Multiply a diagonal and a dense matrix.

Multiplies a column vector diagonal with A, in that order. This algorithm exploids the diagonal structure to reduce the number of computations.

Parameters: diag (MutableDenseMatrix) – The diagonal of a matrix, represented as a sympy column vector. A (MutableDenseMatrix) – A dense matrix. product – The product diag times A. MutableDenseMatrix

Examples

>>> from sympy import Matrix, diag
>>> A = Matrix([[1, 2],
...             [3, 4]])
>>> diagonal = Matrix([2, 3])
>>> diag_times_mat(diagonal, A) == diag(2, 3) * A
True

diagonal_rank(S)

Count the number of non-zero diagonals in S, where S is in Smith normal form.

Parameters: S (MutableDenseMatrix) – A sympy matrix in Smith normal form. num_nonzeros – The number of non-zeros on the diagonal. int

Examples

>>> from sympy import diag
>>> diagonal_rank(diag(1,2,0,0,0,0))
2
>>> diagonal_rank(diag(1,2,4,8,0,0))
4

difference(iterable1, iterable2, p=None)

Compute the difference with a p-norm.

Parameters: iterable1 (MutableDenseMatrix or list) – The iterable to compute the norm over. iterable2 (MutableDenseMatrix or list) – The iterable to compute the norm over. p (float) – The p-value in the p-norm. Should be between 1 and infinity (None). norm – The computed norm of the difference. float

Examples

>>> 2 + 2
4

mat_times_diag(A, diagonal)

Multiply a dense matrix and a diagonal.

Multiplies A with a column vector diagonal, which is interpreted as the diagonal of a matrix. This algorithm exploids the diagonal structure to reduce the number of computations.

Parameters: A (MutableDenseMatrix) – A dense matrix. diag (MutableDenseMatrix) – The diagonal of a matrix, represented as a sympy column vector. product – The product A times diag. MutableDenseMatrix

Examples

>>> from sympy import Matrix, diag
>>> A = Matrix([[1, 2],
...             [3, 4]])
>>> diagonal = Matrix([2, 3])
>>> mat_times_diag(A, diagonal) == A * diag(2, 3)
True

matrix_mod_vector(A, mod_col)

Returns a copy of A with every column modded by mod_col.

Parameters: vector (MutableDenseMatrix) – A sympy matrix of size m x n. mod_col (MutableDenseMatrix) – A sympy column vector, i.e. a sympy matrix of dimension m x 1. A – A copy of the input with each column modded. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> A = Matrix([[5, 6],
...             [8, 5],
...             [3, 5]])
>>> mod_col = Matrix([4, 6, 3])
>>> A_modded = matrix_mod_vector(A, mod_col)
>>> A_modded == Matrix([[1, 2],
...                     [2, 5], [0, 2]])
True

nonzero_columns(H)

Counts the number of columns in H not identically zero.

Parameters: H (MutableDenseMatrix) – A sympy matrix. nonzero_cols – The number of columns of A not indentically zero. int

Examples

>>> from sympy import Matrix, diag
>>> A = Matrix([[0, 2],
...             [0, 4]])
>>> nonzero_columns(A)
1
>>> nonzero_columns(Matrix.eye(5))
5
>>> nonzero_columns(diag(0,1,0,3,5,0))
3

nonzero_diag_as_list(S)

Return a list of the non-zero diagonals entries of S.

Parameters: S (MutableDenseMatrix) – A sympy matrix, typically in Smith normal form. nonzero_diags – A list of the non-zero diagonal entries of S. list

Examples

>>> from sympy import diag
>>> nonzero_diag_as_list(diag(1,2,0,0,0,0))
[1, 2]
>>> nonzero_diag_as_list(diag(1,2,4,8,0,0))
[1, 2, 4, 8]

norm(vector, p=2)

The p-norm of an iterable.

Parameters: vector (MutableDenseMatrix or list) – The iterable to compute the norm over. p (float) – The p-value in the p-norm. Should be between 1 and infinity (None). norm – The computed norm. float

Examples

>>> vector = [1, 2, 3]
>>> norm(vector, 1)
6.0
>>> norm(tuple(vector), None)
3.0
>>> norm(iter(vector), None)
3.0
>>> norm(vector, None)
3.0
>>> norm(vector, 2)
3.7416573867739413
>>> from sympy import Matrix
>>> vector = Matrix(vector)
>>> norm(vector, 1)
6.0
>>> norm(vector, None)
3.0
>>> norm(vector, 2)
3.7416573867739413

order_of_vector(v, mod_vector)

Returns the order of the element v in a FGA like mod_vector.

Parameters: v (MutableDenseMatrix or a list) – An iterable object with integers. This is the group element. mod_vector (MutableDenseMatrix or a list) – An iterable object with integers. This is the orders of the group. order – The order of v in mod_vector. int

Examples

>>> from sympy import Matrix
>>> order_of_vector([1,2,3], [2,4,6]) # Order of 2
2
>>> order_of_vector([1,2,3], [0, 0, 0]) # Order of 0 (infinite order)
0
>>> order_of_vector([1,2,3], [7, 5, 2]) # lcm(7, 10, 2) is 70
70
>>> order_of_vector([0,0,0], [0,0,0]) # Identity element
1
>>> order_of_vector([0,2, 3], [0,0,0]) # Non-trivial element
0
>>> order_of_vector([1, 0, 1], [5, 0, 0])
0

reciprocal_entrywise(A)

Returns the entrywise reciprocal of a matrix or vector.

Will skip zero entries.

Parameters: A (MutableDenseMatrix) – A sympy matrix, or vector ( m x 1 matrix). reciprocal – The entrywise reciprocal of A. MutableDenseMatrix

Examples

>>> from sympy import Matrix, diag
>>> D = diag(1, 2, 3)
>>> D_inv = reciprocal_entrywise(D)
>>> D * D_inv == Matrix.eye(3)
True
>>> A = Matrix([[1, 5], [4, 1]])
>>> A_recip = reciprocal_entrywise(A)
>>> A_recip == Matrix([[1, 1/5], [1/4, 1]])
True

remove_cols(A, cols_to_remove)

Return a copy of A where the columns with indices in cols_to_remove are removed.

Parameters: A (MutableDenseMatrix) – A sympy matrix. cols_to_remove (list) – A list of column indices to remove from A. A – A copy of the input matrix with removed columns. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> A = Matrix([[5, 6, 7, 8]])
>>> B = remove_cols(A, [0, 2])
>>> B == Matrix([[6, 8]])
True

remove_rows(A, rows_to_remove)

Return a copy of A where the rows with indices in rows_to_remove are removed.

Parameters: A (MutableDenseMatrix) – A sympy matrix. rows_to_remove (list) – A list of row indices to remove from A. A – A copy of the input matrix with removed rows. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> A = Matrix([[5, 6, 7, 8]]).T
>>> B = remove_rows(A, [0, 2])
>>> B == Matrix([[6, 8]]).T
True

remove_zero_columns(M)

Return a copy of M where the columns that are identically zero are deleted.

Parameters: M (MutableDenseMatrix) – A sympy matrix with zero or more columns which are identically zero. M – A copy of the input matrix with all zero columns removed. MutableDenseMatrix

Examples

>>> from sympy import Matrix, diag
>>> A = Matrix([[0, 1],
...             [0, 2]])
>>> remove_zero_columns(A) == Matrix([1, 2])
True
>>> A = diag(0,1,2)
>>> A_del = Matrix([[0, 0],
...                 [1, 0],
...                 [0, 2]])
>>> remove_zero_columns(A) == A_del
True

vector_mod_vector(vector, mod_vector)

Return vector % mod_vector, a vectorized mod operation.

Parameters: vector (MutableDenseMatrix) – A sympy column vector, i.e. a sympy matrix of dimension m x 1. mod_vector (MutableDenseMatrix) – A sympy column vector, i.e. a sympy matrix of dimension m x 1. modded_vector – The result of the mod operation on every entry. MutableDenseMatrix

Examples

>>> from sympy import Matrix
>>> element = Matrix([5, 7, 9])
>>> mod_vect = Matrix([3, 3, 5])
>>> modded = vector_mod_vector(element, mod_vect)
>>> modded == Matrix([2, 1, 4])
True