Introduction

Nemo allow the creation of dense matricses over any computable ring $R$. There are two different kinds of implementation: a generic one for the case where no specific implementation exists, and efficient implementations of matrices over numerous specific rings, usually provided by C/C++ libraries.

The following table shows each of the matrix types available in Nemo, the base ring $R$, and the Julia/Nemo types for that kind of matrix (the type information is mainly of concern to developers).

The dimensions and base ring $R$ of a generic matrix are stored in its parent object.

All matrix element types belong to the abstract type MatElem and all of the matrix space types belong to the abstract type MatSpace. This enables one to write generic functions that can accept any Nemo matrix type.

Matrix space constructors

In Nemo we have the concept of a matrix space. This is the collection of matrices with specified dimensions and base ring.

In order to construct matrices in Nemo, one usually first constructs the matrix space itself. This is accomplished with the following constructor.

#Nemo.MatrixSpace — Method.

MatrixSpace(R::Ring, r::Int, c::Int, cached::Bool = true)

Return parent object corresponding to the space of $r\times c$ matrices over the ring $R$. If cached == true (the default), the returned parent object is cached so that it can returned by future calls to the constructor with the same dimensions and base ring.

source

We also allow matrices over a given base ring to be constructed directly. In such cases, Nemo automatically constructs the matrix space internally. See the matrix element constructors below for examples. However, note that there may be a small peformance disadvantage to doing it that way, since the matrix space needs to be looked up internally every time a matrix is constructed.

Here are some examples of creating matrix spaces and making use of the resulting parent objects to coerce various elements into the matrix space.

R, t = PolynomialRing(QQ, "t")
S = MatrixSpace(R, 3, 3)

A = S()
B = S(12)
C = S(R(11))

Matrix element constructors

Once a matrix space is constructed, there are various ways to construct matrices in that space.

In addition to coercing elements into the matrix space as above, we provide the following functions for constructing certain useful matrices.

#Base.zero — Method.

zero(a::MatSpace)

Construct the zero matrix in the given matrix space.

source

#Base.one — Method.

one(a::MatSpace)

Construct the matrix in the given matrix space with ones down the diagonal and zeroes elsewhere.

source

In addition, there are various shorthand notations for constructing matrices over a given base ring without first constructing the matrix space parent object.

R[a b c...;...]

Create the matrix over the base ring $R$ consisting of the given rows (separated by semicolons). Each entry is coerced into $R$ automatically. Note that parentheses may be placed around individual entries if the lists would otherwise be ambiguous, e.g. R[1 2; 2 (-3)].

Beware that this syntax does not support the creation of column vectors. See the notation below for creating those.

R[a b c...]

Create the row vector with entries in $R$ consisting of the given entries (separated by spaces). Each entry is coerced into $R$ automatically. Note that parentheses may be placed around individual entries if the list would otherwise be ambiguous, e.g. R[1 2 (-3)].

R[a b c...]'

Create the column vector with entries in $R$ consisting of the given entries (separated by spaces). Each entry is coerced into $R$ automatically. Observe the dash that is used to transpose the row vector notation (for free) to turn it into a column vector. Note that parentheses may be placed around individual entries if the list would otherwise be ambiguous, e.g. R[1 2 (-3)]'.

Here are some examples of constructing matrices.

R, t = PolynomialRing(QQ, "t")
S = MatrixSpace(R, 3, 3)

A = zero(S)
B = one(S)

C = R[t + 1 1; t^2 0]
D = R[t + 1 2 t]
F = R[1 2 t]'

Basic functionality

All matric modules in Nemo must provide the functionality listed in this section. (Note that only some of these functions are useful to a user.)

Developers who are writing their own matrix module, whether as an interface to a C library, or as some kind of generic module, must provide all of these functions for custom matrix types in Nemo.

We write U for the type of the matrices in the matrix space and T for the type of elements of the base ring.

All of these functions are provided for all existing matrix types in Nemo.

parent_type{U <: MatElem}(::Type{U})

Given the type of matrix elements, should return the type of the corresponding parent object.

elem_type(R::MatSpace)

Given a parent object for the matrix space, return the type of elements of the matrix space.

Base.hash(a::MatElem, h::UInt)

Return a UInt hexadecimal hash of the matrix $a$. This should be xor'd with a fixed random hexadecimal specific to the matrix type. The hash of each entry should be xor'd with the supplied parameter h as part of computing the hash.

deepcopy(a::MatElem)

Construct a copy of the given matrix and return it. This function must recursively construct copies of all of the internal data in the given matrix. Nemo matricess are mutable and so returning shallow copies is not sufficient.

To access entries of a Nemo matrix, we overload the square bracket notation.

M[r::Int, c::Int]

One can both assign to and access a given entry at row $r$ and column $c$ of a matrix $M$ with this notation. Note that Julia and Nemo matrices are $1$-indexed, i.e. the first row has index $1$, not $0$, etc. This is in accordance with many papers on matrices and with systems such as Pari/GP.

Given a parent object S for a matrix space, the following coercion functions are provided to coerce various elements into the matrix space. Developers provide these by overloading the call operator for the matrix parent objects.

S()

Coerce zero into the space $S$.

S(n::Integer)
S(n::fmpz)

Return the diagonal matrix with the given integer along the diagonal and zeroes elsewhere.

S(n::T)

Coerces an element of the base ring, of type T into $S$.

S(A::Array{T, 2})

Take a Julia two dimensional array of elements in the base ring, of type T and construct the matrix with those entries.

S(f::MatElem)

Take a matrix that is already in the space $S$ and simply return it. A copy of the original is not made.

S(c::RingElem)

Try to coerce the given ring element into the matrix space (as a diagonal matrix). This only succeeds if $c$ can be coerced into the base ring.

In addition to the above, developers of custom matrices must ensure the parent object of a matrix type constains a field base_ring specifying the base ring, and fields rows and cols to specify the dimensions. They must also ensure that each matrix element contains a field parent specifying the parent object of the matrix, or that there is at least a function parent(a::MatElem) which returns the parent of the given matrix.

Typically a developer will also overload the MatrixSpace generic function to create matrices of the custom type they are implementing.

Basic manipulation

Numerous functions are provided to manipulate matricess and to set and retrieve entries and other basic data associated with the matrices. Also see the section on basic functionality above.

base_ring(::MatSpace)

#Nemo.base_ring — Method.

base_ring(r::MatElem)

Return the base ring $R$ of the matrix space that the supplied matrix $r$ belongs to.

source

#Base.parent — Method.

parent(a::MatElem)

Return the parent object of the given matrix.

source

#Nemo.rows — Method.

rows(a::MatElem)

Return the number of rows of the given matrix.

source

#Nemo.cols — Method.

cols(a::MatElem)

Return the number of columns of the given matrix.

source

#Nemo.iszero — Method.

iszero(a::MatElem)

Return true if the supplied matrix $a$ is the zero matrix, otherwise return false.

source

#Nemo.isone — Method.

isone(a::MatElem)

Return true if the supplied matrix $a$ is diagonal with ones along the diagonal, otherwise return false.

source

Here are some examples of basic manipulation of matrices.

R, t = PolynomialRing(QQ, "t")
S = MatrixSpace(R, 3, 3)

A = S([t + 1 t R(1); t^2 t t; R(-2) t + 2 t^2 + t + 1])
B = S([R(2) R(3) R(1); t t + 1 t + 2; R(-1) t^2 t^3])

C = zero(S)
D = one(S)

f = iszero(C)
g = isone(D)
r = rows(B)
c = cols(B)
U = base_ring(C)
V = base_ring(S)
W = parent(D)

Arithmetic operators

All the usual arithmetic operators are overloaded for Nemo matrices. Note that Julia uses the single slash for floating point division. Therefore to perform exact division by a constant we use divexact.

An exception is raised if the matrix dimensions are not compatible for the given operation. The divexact function computes a*inv(b) where inv(b) is the inverse of the matrix $b$. This assumes that $b$ can be inverted.

The following ad hoc operators are also provided.

The following function is also provided.

#Nemo.powers — Method.

powers{T <: RingElem}(a::MatElem{T}, d::Int)

Return an array of matrices $M$ wher $M[i + 1] = a^i$ for $i = 0..d$

source

If the appropriate promote_rule and coercion exists, these operators can also be used with elements of other rings. Nemo will try to coerce the operands to the dominating type and then apply the operator.

Here are some examples of arithmetic operations on matrices.

R, t = PolynomialRing(QQ, "t")
S = MatrixSpace(R, 3, 3)

A = S([t + 1 t R(1); t^2 t t; R(-2) t + 2 t^2 + t + 1])
B = S([R(2) R(3) R(1); t t + 1 t + 2; R(-1) t^2 t^3])

C = -A
D = A + B
F = A - B
G = A*B
H = 3*A
K = B + 2
M = fmpz(3) - B
N = t - A
P = A^3
Q = powers(A, 3)
R = divexact(A*3, 3)

Comparison operators

The following comparison operators are implemented for matrices in Nemo.

Function

isequal{T <: RingElem}(a::MatElem{T}, b::MatElem{T})=={T <: RingElem}(a::MatElem{T}, b::MatElem{T})

The isequal operation returns true if and only if all the entries of the matrix are precisely equal as compared by isequal. This is a stronger form of equality, used for comparing inexact coefficients, such as elements of a power series ring, the $p$-adics, or the reals or complex numbers. Two elements are precisely equal only if they have the same precision or bounds in addition to being arithmetically equal.

#Nemo.overlaps — Method.

overlaps(x::arb_mat, y::arb_mat)

Returns true if all entries of $x$ overlap with the corresponding entry of $y$, otherwise return false.

source

#Nemo.overlaps — Method.

overlaps(x::acb_mat, y::acb_mat)

Returns true if all entries of $x$ overlap with the corresponding entry of $y$, otherwise return false.

source

#Base.contains — Method.

contains(x::arb_mat, y::arb_mat)

Returns true if all entries of $x$ contain the corresponding entry of $y$, otherwise return false.

source

#Base.contains — Method.

contains(x::acb_mat, y::acb_mat)

Returns true if all entries of $x$ contain the corresponding entry of $y$, otherwise return false.

source

In addition we have the following ad hoc comparison operators.

Function

=={T <: RingElem}(a::MatElem{T}, b::T)=={T <: RingElem}(a::T, b::MatElem{T})==(a::MatElem, b::Integer)==(a::Integer, b::MatElem)==(a::MatElem, b::fmpz)==(a::fmpz, b::MatElem)

Here are some examples of comparisons.

R, t = PolynomialRing(QQ, "t")
S = MatrixSpace(R, 3, 3)

A = S([t + 1 t R(1); t^2 t t; R(-2) t + 2 t^2 + t + 1])
B = S([R(2) R(3) R(1); t t + 1 t + 2; R(-1) t^2 t^3])

A != B
A == deepcopy(A)
A != 12
fmpz(11) != A
B != t
S(11) == 11

C = RR[1 2; 3 4]
D = RR["1 +/- 0.1" "2 +/- 0.1"; "3 +/- 0.1" "4 +/- 0.1"]
overlaps(C, D)
contains(D, C)

Scaling

#Base.:<< — Method.

<<(x::fmpz_mat, y::Int)

Return $2^yx$.

source

Base.:>> — Method.

>>(x::fmpz_mat, y::Int)

source

Here are some examples of scaling matrices.

S = MatrixSpace(ZZ, 3, 3)

A = S([fmpz(2) 3 5; 1 4 7; 9 6 3])

B = A<<5
C = B>>2

Transpose

#Base.transpose — Method.

transpose(x::MatElem)

Return the transpose of the given matrix.

source

Here is an example of transposing a matrix.

R, t = PolynomialRing(QQ, "t")
S = MatrixSpace(R, 3, 3)

A = S([t + 1 t R(1); t^2 t t; R(-2) t + 2 t^2 + t + 1])

B = transpose(A)

Gram matrix

#Nemo.gram — Method.

gram(x::MatElem)

Return the Gram matrix of $x$, i.e. if $x$ is an $r\times c$ matrix return the $r\times r$ matrix whose entries $i, j$ are the dot products of the $i$-th and $j$-th rows, respectively.

source

Here is an example of computing the Gram matrix.

R, t = PolynomialRing(QQ, "t")
S = MatrixSpace(R, 3, 3)

A = S([t + 1 t R(1); t^2 t t; R(-2) t + 2 t^2 + t + 1])

B = gram(A)

Trace

#Base.LinAlg.trace — Method.

trace(x::MatElem)

Return the trace of the matrix $a$, i.e. the sum of the diagonal elements. We require the matrix to be square.

source

Here is an example of computing the trace.

R, t = PolynomialRing(QQ, "t")
S = MatrixSpace(R, 3, 3)

A = S([t + 1 t R(1); t^2 t t; R(-2) t + 2 t^2 + t + 1])

b = trace(A)

Content

#Nemo.content — Method.

content(x::MatElem)

Return the content of the matrix $a$, i.e. the greatest common divisor of all its entries, assuming it exists.

source

Here is an example of computing the content of a matrix.

R, t = PolynomialRing(QQ, "t")
S = MatrixSpace(R, 3, 3)

A = S([t + 1 t R(1); t^2 t t; R(-2) t + 2 t^2 + t + 1])

b = content(A)

Concatenation

#Base.hcat — Method.

hcat(a::MatElem, b::MatElem)

Return the horizontal concatenation of $a$ and $b$. Assumes that the number of rows is the same in $a$ and $b$.

source

#Base.vcat — Method.

vcat(a::MatElem, b::MatElem)

Return the vertical concatenation of $a$ and $b$. Assumes that the number of columns is the same in $a$ and $b$.

source

Here are some examples of concatenation.

R, t = PolynomialRing(QQ, "t")
S = MatrixSpace(R, 3, 3)

A = S([t + 1 t R(1); t^2 t t; R(-2) t + 2 t^2 + t + 1])
B = S([R(2) R(3) R(1); t t + 1 t + 2; R(-1) t^2 t^3])

hcat(A, B)
vcat(A, B)

Permutation

#Base.:* — Method.

*(P::perm, x::MatElem)

Apply the pemutation $P$ to the rows of the matrix $x$ and return the result.

source

Here is an example of applying a permutation to a matrix.

R, t = PolynomialRing(QQ, "t")
S = MatrixSpace(R, 3, 3)
G = PermGroup(3)

A = S([t + 1 t R(1); t^2 t t; R(-2) t + 2 t^2 + t + 1])
P = G([1, 3, 2])

B = P*A

LU factorisation

#Base.LinAlg.lufact — Method.

lufact{T <: FieldElem}(A::MatElem{T}, P = PermGroup(rows(A)))

Return a tuple $r, p, L, U$ consisting of the rank of $A$, a permutation $p$ of $A$ belonging to $P$, a lower triangular matrix $L$ and an upper triangular matrix $U$ such that $p(A) = LU$, where $p(A)$ stands for the matrix whose rows are the given permutation $p$ of the rows of $A$.

source

#Nemo.fflu — Method.

fflu{T <: RingElem}(A::MatElem{T}, P = PermGroup(rows(A)))

Return a tuple $r, d, p, L, U$ consisting of the rank of $A$, a denominator $d$, a permutation $p$ of $A$ belonging to $P$, a lower triangular matrix $L$ and an upper triangular matrix $U$ such that $p(A) = LD^1U$, where $p(A)$ stands for the matrix whose rows are the given permutation $p$ of the rows of $A$ and such that $D$ is the diagonal matrix diag$(p_1, p_1p_2, \ldots, p_{n-2}p_{n-1}, p_{n-1}$ where the $p_i$ are the inverses of the diagonal entries of $U$. The denominator $d$ is set to $\pm \mbox{det}(S)$ where $S$ is an appropriate submatrix of $A$ ($S = A$ if $A$ is square) and the sign is decided by the parity of the permutation.

source

Here are some examples of LU factorisation.

R, x = PolynomialRing(QQ, "x")
K, a = NumberField(x^3 + 3x + 1, "a")
S = MatrixSpace(K, 3, 3)

A = S([K(0) 2a + 3 a^2 + 1; a^2 - 2 a - 1 2a; a^2 - 2 a - 1 2a])

r, P, L, U = lufact(A)
r, d, P, L, U = fflu(A)

Reduced row-echelon form

#Nemo.rref — Method.

rref{T <: RingElem}(M::MatElem{T})

Returns a tuple $(r, d, A)$ consisting of the rank $r$ of $M$ and a denominator $d$ in the base ring of $M$ and a matrix $A$ such that $A/d$ is the reduced row echelon form of $M$. Note that the denominator is not usually minimal.

source

#Nemo.rref — Method.

rref{T <: FieldElem}(M::MatElem{T})

Returns a tuple $(r, A)$ consisting of the rank $r$ of $M$ and a reduced row echelon form $A$ of $M$.

source

#Nemo.isrref — Method.

isrref{T <: RingElem}(M::MatElem{T})

Return true if $M$ is in reduced row echelon form, otherwise return false.

source

#Nemo.isrref — Method.

isrref{T <: FieldElem}(M::MatElem{T})

Return true if $M$ is in reduced row echelon form, otherwise return false.

source

Here are some examples of computing reduced row echelon form.

R, x = PolynomialRing(QQ, "x")
K, a = NumberField(x^3 + 3x + 1, "a")
S = MatrixSpace(K, 3, 3)

M = S([K(0) 2a + 3 a^2 + 1; a^2 - 2 a - 1 2a; a^2 + 3a + 1 2a K(1)])

r, d, A = rref(M)
isrref(A)

R, x = PolynomialRing(ZZ, "x")
S = MatrixSpace(R, 3, 3)
U = MatrixSpace(R, 3, 2)

M = S([R(0) 2x + 3 x^2 + 1; x^2 - 2 x - 1 2x; x^2 + 3x + 1 2x R(1)])

r, A = rref(M)
isrref(A)

Hermite normal form

#Nemo.hnf — Method.

hnf{T <: RingElem}(A::GenMat{T}) -> GenMat{T}

Return the upper right row Hermite normal form of $A$.

source

#Nemo.hnf_with_trafo — Method.

hnf{T <: RingElem}(A::GenMat{T}) -> GenMaT{T}, GenMat{T}

Return the upper right row Hermite normal form $H$ of $A$ together with invertible matrix $U$ such that $UA = H$.

source

Determinant

#Base.LinAlg.det — Method.

det{T <: RingElem}(M::MatElem{T})

Return the determinant of the matrix $M$. We assume $M$ is square.

source

#Base.LinAlg.det — Method.

det{T <: FieldElem}(M::MatElem{T})

Return the determinant of the matrix $M$. We assume $M$ is square.

source

#Nemo.det_divisor — Method.

det_divisor(x::fmpz_mat)

Return some positive divisor of the determinant of $x$, if the determinant is nonzero, otherwise return zero.

source

#Nemo.det_given_divisor — Method.

det_given_divisor(x::fmpz_mat, d::Integer, proved=true)

Return the determinant of $x$ given a positive divisor of its determinant. If proved == true (the default), the output is guaranteed to be correct, otherwise a heuristic algorithm is used.

source

#Nemo.det_given_divisor — Method.

det_given_divisor(x::fmpz_mat, d::fmpz, proved=true)

Return the determinant of $x$ given a positive divisor of its determinant. If proved == true (the default), the output is guaranteed to be correct, otherwise a heuristic algorithm is used.

source

Here are some examples of computing the determinant.

R, x = PolynomialRing(QQ, "x")
K, a = NumberField(x^3 + 3x + 1, "a")
S = MatrixSpace(K, 3, 3)

A = S([K(0) 2a + 3 a^2 + 1; a^2 - 2 a - 1 2a; a^2 + 3a + 1 2a K(1)])

d = det(A)

S = MatrixSpace(ZZ, 3, 3)

A = S([fmpz(2) 3 5; 1 4 7; 9 6 3])

c = det_divisor(A)
d = det_given_divisor(A, c)

Rank

#Base.LinAlg.rank — Method.

rank{T <: RingElem}(M::MatElem{T})

Return the rank of the matrix $M$.

source

#Base.LinAlg.rank — Method.

rank{T <: FieldElem}(M::MatElem{T})

Return the rank of the matrix $M$.

source

Here are some examples of computing the rank of a matrix.

R, x = PolynomialRing(QQ, "x")
K, a = NumberField(x^3 + 3x + 1, "a")
S = MatrixSpace(K, 3, 3)

A = S([K(0) 2a + 3 a^2 + 1; a^2 - 2 a - 1 2a; a^2 + 3a + 1 2a K(1)])

d = rank(A)

Linear solving

solve{T <: RingElem}(::MatElem{T}, ::MatElem{T})

#Nemo.cansolve — Method.

cansolve(a::fmpz_mat, b::fmpz_mat) -> Bool, fmpz_mat

Return true and a matrix $x$ such that $ax = b$, or false and some matrix in case $x$ does not exist.

source

#Nemo.solve_rational — Method.

solve_rational{T <: RingElem}(M::MatElem{T}, b::MatElem{T})

Given a non-singular $n\times n$ matrix over a ring and an $n\times m$ matrix over the same ring, return a tuple $x, d$ consisting of an $n\times m$ matrix $x$ and a denominator $d$ such that $Ax = db$. The denominator will be the determinant of $A$ up to sign. If $A$ is singular an exception is raised.

source

#Nemo.solve_triu — Method.

solve_triu{T <: FieldElem}(U::MatElem{T}, b::MatElem{T}, unit=false)

Given a non-singular $n\times n$ matrix over a field which is upper triangular, and an $n\times m$ matrix over the same field, return an $n\times m$ matrix $x$ such that $Ax = b$. If $A$ is singular an exception is raised. If unit is true then $U$ is assumed to have ones on its diagonal, and the diagonal will not be read.

source

#Nemo.solve_dixon — Method.

solve_dixon(a::fmpz_mat, b::fmpz_mat)

Return a tuple $(x, m)$ consisting of a column vector $x$ such that $ax = b \pmod{m}$. The element $b$ must be a column vector with the same number > of rows as $a$ and $a$ must be a square matrix. If these conditions are not met or $(x, d)$ does not exist, an exception is raised.

source

#Nemo.solve_dixon — Method.

solve_dixon(a::fmpq_mat, b::fmpq_mat)

Solve $ax = b$ by clearing denominators and using Dixon's algorithm. This is usually faster for large systems.

source

Here are some examples of linear solving.

R, x = PolynomialRing(QQ, "x")
K, a = NumberField(x^3 + 3x + 1, "a")
S = MatrixSpace(K, 3, 3)
U = MatrixSpace(K, 3, 1)

A = S([K(0) 2a + 3 a^2 + 1; a^2 - 2 a - 1 2a; a^2 + 3a + 1 2a K(1)])
b = U([2a a + 1 (-a - 1)]')

x = solve(A, b)

A = S([a + 1 2a + 3 a^2 + 1; K(0) a^2 - 1 2a; K(0) K(0) a])
b = U([2a a + 1 (-a - 1)]')

x = solve_triu(A, b, false)

R, x = PolynomialRing(ZZ, "x")
S = MatrixSpace(R, 3, 3)
U = MatrixSpace(R, 3, 2)

A = S([R(0) 2x + 3 x^2 + 1; x^2 - 2 x - 1 2x; x^2 + 3x + 1 2x R(1)])
b = U([2x x + 1 (-x - 1); x + 1 (-x) x^2]')

x, d = solve_rational(A, b)

S = MatrixSpace(ZZ, 3, 3)
T = MatrixSpace(ZZ, 3, 1)

A = S([fmpz(2) 3 5; 1 4 7; 9 2 2])   
B = T([fmpz(4), 5, 7])

X, d = solve_rational(A, B)
X, m = solve_dixon(A, B)

Inverse

#Base.inv — Method.

inv{T <: RingElem}(M::MatElem{T})

Given a non-singular $n\times n$ matrix over a ring the tuple $X, d$ consisting of an $n\times n$ matrix $X$ and a denominator $d$ such that $AX = dI_n$, where $I_n$ is the $n\times n$ identity matrix. The denominator will be the determinant of $A$ up to sign. If $A$ is singular an exception is raised.

source

#Base.inv — Method.

inv{T <: FieldElem}(M::MatElem{T})

Given a non-singular $n\times n$ matrix over a field, return an $n\times n$ matrix $X$ such that $AX = I_n$ where $I_n$ is the $n\times n$ identity matrix. If $A$ is singular an exception is raised.

source

#Base.inv — Method.

inv(M::arb_mat)

Given a $n\times n$ matrix of type arb_mat, return an $n\times n$ matrix $X$ such that $AX$ contains the identity matrix. If $A$ cannot be inverted numerically an exception is raised.

source

#Base.inv — Method.

inv(M::acb_mat)

Given a $n\times n$ matrix of type acb_mat, return an $n\times n$ matrix $X$ such that $AX$ contains the identity matrix. If $A$ cannot be inverted numerically an exception is raised.

source

#Nemo.pseudo_inv — Method.

pseudo_inv(x::fmpz_mat)

Return a tuple $(z, d)$ consisting of a matrix $z$ and denominator $d$ such that $z/d$ is the inverse of $x$.

source

Here are some examples of taking the inverse of a matrix.

R, x = PolynomialRing(QQ, "x")
K, a = NumberField(x^3 + 3x + 1, "a")
S = MatrixSpace(K, 3, 3)

A = S([K(0) 2a + 3 a^2 + 1; a^2 - 2 a - 1 2a; a^2 + 3a + 1 2a K(1)])

X = inv(A)

R, x = PolynomialRing(ZZ, "x")
S = MatrixSpace(R, 3, 3)

A = S([R(0) 2x + 3 x^2 + 1; x^2 - 2 x - 1 2x; x^2 + 3x + 1 2x R(1)])

X, d = inv(A)

S = MatrixSpace(ZZ, 3, 3)

A = S([1 0 1; 2 3 1; 5 6 7])

B, d = pseudo_inv(A)

A = RR[1 0 1; 2 3 1; 5 6 7]

X = inv(A)

Nullspace

#Base.LinAlg.nullspace — Method.

nullspace{T <: RingElem}(M::MatElem{T})

Returns a tuple $(\nu, N)$ consisting of the nullity $\nu$ of $M$ and a basis $N$ (consisting of column vectors) for the right nullspace of $M$, i.e. such that $MN$ is the zero matrix. If $M$ is an $m\times n$ matrix $N$ will be an $n\times \nu$ matrix. Note that the nullspace is taken to be the vector space kernel over the fraction field of the base ring if the latter is not a field. In Nemo we use the name ``kernel'' for a function to compute an integral kernel.

source

#Base.LinAlg.nullspace — Method.

nullspace{T <: FieldElem}(M::MatElem{T})

Returns a tuple $(\nu, N)$ consisting of the nullity $\nu$ of $M$ and a basis $N$ (consisting of column vectors) for the right nullspace of $M$, i.e. such that $MN$ is the zero matrix. If $M$ is an $m\times n$ matrix $N$ will be an $n\times \nu$ matrix. Note that the nullspace is taken to be the vector space kernel over the fraction field of the base ring if the latter is not a field. In Nemo we use the name ``kernel'' for a function to compute an integral kernel.

source

#Nemo.nullspace_right_rational — Method.

nullspace_right_rational(x::fmpz_mat)

Return the right rational nullspace of $x$, i.e. a set of vectors over $\mathbb{Z}$ giving a $\mathbb{Q}$-basis for the nullspace of $x$ considered as a matrix over $\mathbb{Q}$.

source

Here are some examples of computing the nullspace of a matrix.

R, x = PolynomialRing(ZZ, "x")
S = MatrixSpace(R, 4, 4)

M = S([-6*x^2+6*x+12 -12*x^2-21*x-15 -15*x^2+21*x+33 -21*x^2-9*x-9;
       -8*x^2+8*x+16 -16*x^2+38*x-20 90*x^2-82*x-44 60*x^2+54*x-34;
       -4*x^2+4*x+8 -8*x^2+13*x-10 35*x^2-31*x-14 22*x^2+21*x-15;
       -10*x^2+10*x+20 -20*x^2+70*x-25 150*x^2-140*x-85 105*x^2+90*x-50])

n, N = nullspace(M)

Hessenberg form

#Nemo.hessenberg — Method.

hessenberg{T <: RingElem}(A::MatElem{T})

Returns the Hessenberg form of $M$, i.e. an upper Hessenberg matrix which is similar to $M$. The upper Hessenberg form has nonzero entries above and on the diagonal and in the diagonal line immediately below the diagonal.

source

#Nemo.ishessenberg — Method.

ishessenberg{T <: RingElem}(A::MatElem{T})

Returns true if $M$ is in Hessenberg form, otherwise returns false.

source

Here are some examples of computing the Hessenberg form.

R = ResidueRing(ZZ, 7)
S = MatrixSpace(R, 4, 4)

M = S([R(1) R(2) R(4) R(3); R(2) R(5) R(1) R(0);
       R(6) R(1) R(3) R(2); R(1) R(1) R(3) R(5)])

A = hessenberg(M)
ishessenberg(A) == true

Characteristic polynomial

#Nemo.charpoly — Method.

charpoly{T <: RingElem}(V::Ring, Y::MatElem{T})

Returns the characteristic polynomial $p$ of the matrix $M$. The polynomial ring $R$ of the resulting polynomial must be supplied and the matrix is assumed to be square.

source

Here are some examples of computing the characteristic polynomial.

R = ResidueRing(ZZ, 7)
S = MatrixSpace(R, 4, 4)
T, x = PolynomialRing(R, "x")

M = S([R(1) R(2) R(4) R(3); R(2) R(5) R(1) R(0);
       R(6) R(1) R(3) R(2); R(1) R(1) R(3) R(5)])

A = charpoly(T, M)

Minimal polynomial

#Nemo.minpoly — Method.

minpoly{T <: RingElem}(S::Ring, M::MatElem{T}, charpoly_only = false)

Returns the minimal polynomial $p$ of the matrix $M$. The polynomial ring $R$ of the resulting polynomial must be supplied and the matrix must be square.

source

#Nemo.minpoly — Method.

minpoly{T <: FieldElem}(S::Ring, M::MatElem{T}, charpoly_only = false)

Returns the minimal polynomial $p$ of the matrix $M$. The polynomial ring $R$ of the resulting polynomial must be supplied and the matrix must be square.

source

minpoly{T <: RingElem}(S::Ring, M::MatElem{T}, charpoly_only = false)

Returns the minimal polynomial $p$ of the matrix $M$. The polynomial ring $R$ of the resulting polynomial must be supplied and the matrix must be square.

source

Here are some examples of computing the minimal polynomial of a matrix.

R, x = FiniteField(13, 1, "x")
T, y = PolynomialRing(R, "y")

M = R[7 6 1;
      7 7 5;
      8 12 5]

A = minpoly(T, M)

Transforms

#Nemo.similarity! — Method.

similarity!{T <: RingElem}(A::MatElem{T}, r::Int, d::T)

Applies a similarity transform to the $n\times n$ matrix $M$ in-place. Let $P$ be the $n\times n$ identity matrix that has had all zero entries of row $r$ replaced with $d$, then the transform applied is equivalent to $M = P^{-1}MP$. We require $M$ to be a square matrix. A similarity transform preserves the minimal and characteristic polynomials of a matrix.

source

Here is an example of applying a similarity transform to a matrix.

R = ResidueRing(ZZ, 7)
S = MatrixSpace(R, 4, 4)

M = S([R(1) R(2) R(4) R(3); R(2) R(5) R(1) R(0);
       R(6) R(1) R(3) R(2); R(1) R(1) R(3) R(5)])

similarity!(M, 1, R(3))

Modular reduction

#Nemo.reduce_mod — Method.

reduce_mod(x::fmpz_mat, y::Integer)

Reduce the entries of $x$ modulo $y$ and return the result.

source

#Nemo.reduce_mod — Method.

reduce_mod(x::fmpz_mat, y::fmpz)

Reduce the entries of $x$ modulo $y$ and return the result.

source

Here are some examples of modular reduction.

S = MatrixSpace(ZZ, 3, 3)

A = S([fmpz(2) 3 5; 1 4 7; 9 2 2])

reduce_mod(A, ZZ(5))
reduce_mod(A, 2)

Lifting

#Nemo.lift — Method.

lift(a::nmod_mat)

Return a lift of the matrix $a$ to a matrix over $\mathbb{Z}$, i.e. where the entries of the returned matrix are those of $a$ lifted to $\mathbb{Z}$.

source

Here are some examples of lifting.

R = ResidueRing(ZZ, 7)
S = MatrixSpace(R, 3, 3)

a = S([4 5 6; 7 3 2; 1 4 5])

 b = lift(a)

Special matrices

#Nemo.hadamard — Method.

hadamard(R::FmpzMatSpace)

Return the Hadamard matrix for the given matrix space. The number of rows and columns must be equal.

source

#Nemo.ishadamard — Method.

ishadamard(x::fmpz_mat)

Return true if the given matrix is Hadamard, otherwise return false.

source

#Nemo.hilbert — Method.

hilbert(R::FmpqMatSpace)

Return the Hilbert matrix in the given matrix space. This is the matrix with entries $H_{i,j} = 1/(i + j - 1)$.

source

Here are some examples of computing special matrices.

R = MatrixSpace(ZZ, 3, 3)
S = MatrixSpace(QQ, 3, 3)

A = hadamard(R)
ishadamard(A)
B = hilbert(R)

Hermite Normal Form

#Nemo.hnf — Method.

hnf(x::fmpz_mat)

Return the Hermite Normal Form of $x$.

source

#Nemo.hnf_with_transform — Method.

hnf_with_transform(x::fmpz_mat)

Compute a tuple $(H, T)$ where $H$ is the Hermite normal form of $x$ and $T$ is a transformation matrix so that $H = Tx$.

source

#Nemo.hnf_modular — Method.

hnf_modular(x::fmpz_mat, d::fmpz)

Compute the Hermite normal form of $x$ given that $d$ is a multiple of the determinant of the nonzero rows of $x$.

source

#Nemo.hnf_modular_eldiv — Method.

hnf_modular_eldiv(x::fmpz_mat, d::fmpz)

Compute the Hermite normal form of $x$ given that $d$ is a multiple of the largest elementary divisor of $x$. The matrix $x$ must have full rank.

source

#Nemo.ishnf — Method.

ishnf(x::fmpz_mat)

Return true if the given matrix is in Hermite Normal Form, otherwise return false.

source

Here are some examples of computing the Hermite Normal Form.

S = MatrixSpace(ZZ, 3, 3)

A = S([fmpz(2) 3 5; 1 4 7; 19 3 7])

B = hnf(A)
H, T = hnf_with_transform(A)
M = hnf_modular(A, fmpz(27))
N = hnf_modular_eldiv(A, fmpz(27))
ishnf(M)

(Weak) Popov form

Nemo provides algorithms for computing the (weak) Popov of a matrix with entries in a univariate polynomial ring over a field.

weak_popov{T <: PolyElem}(::GenMat{T})
weak_popov_with_trafo{T <: PolyElem}(::GenMat{T})
popov{T <: PolyElem}(::GenMat{T})
popov_with_trafo{T <: PolyElem}(::GenMat{T})
det_popov{T <: PolyElem}(::GenMat{T})

Lattice basis reduction

Nemo provides LLL lattice basis reduction. Optionally one can specify the setup using a context object created by the following function.

lll_ctx(delta::Float64, eta::Float64, rep=:zbasis, gram=:approx)

Return a LLL context object specifying LLL parameters $\delta$ and $\eta$ and specifying the representation as either :zbasis or :gram and the Gram type as either :approx or :exact.

#Nemo.lll — Method.

lll(x::fmpz_mat, ctx=lll_ctx(0.99, 0.51))

Return the LLL reduction of the matrix $x$. By default the matrix $x$ is a $\mathbb{Z}$-basis and the Gram matrix is maintained throughout in approximate form. The LLL is performed with reduction parameters $\delta = 0.99$ and $\eta = 0.51$. All of these defaults can be overridden by specifying an optional context object.

source

#Nemo.lll_with_transform — Method.

Compute a tuple $(L, T)$ where $L$ is the LLL reduction of $a$ and $T$ is a transformation matrix so that $L = Ta$. All the default parameters can be overridden by supplying an optional context object.

source

#Nemo.lll_gram — Method.

lll_gram(x::fmpz_mat, ctx=lll_ctx(0.99, 0.51, :gram))

Given the Gram matrix $x$ of a matrix, compute the Gram matrix of its LLL reduction.

source

#Nemo.lll_gram_with_transform — Method.

lll_gram_with_transform(x::fmpz_mat, ctx=lll_ctx(0.99, 0.51, :gram))

Given the Gram matrix $x$ of a matrix $M$, compute a tuple $(L, T)$ where $L$ is the gram matrix of the LLL reduction of the matrix and $T$ is a transformation matrix so that $L = TM$.

source

#Nemo.lll_with_removal — Method.

lll_with_removal(x::fmpz_mat, b::fmpz, ctx=lll_ctx(0.99, 0.51))

Compute the LLL reduction of $x$ and throw away rows whose norm exceeds the given bound $b$. Return a tuple $(r, L)$ where the first $r$ rows of $L$ are the rows remaining after removal.

source

#Nemo.lll_with_removal_transform — Method.

lll_with_removal_transform(x::fmpz_mat, b::fmpz, ctx=lll_ctx(0.99, 0.51))

Compute a tuple $(r, L, T)$ where the first $r$ rows of $L$ are those remaining from the LLL reduction after removal of vectors with norm exceeding the bound $b$ and $T$ is a transformation matrix so that $L = Tx$.

source

Here are some examples of lattice basis reduction.

S = MatrixSpace(ZZ, 3, 3)

A = S([fmpz(2) 3 5; 1 4 7; 19 3 7])

L = lll(A, lll_ctx(0.95, 0.55, :zbasis, :approx)
L, T = lll_with_transform(A)

G == lll_gram(gram(A))
G, T = lll_gram_with_transform(gram(A))

r, L = lll_with_removal(A, fmpz(100))
r, L, T = lll_with_removal_transform(A, fmpz(100))

Smith Normal Form

#Nemo.snf — Method.

snf(x::fmpz_mat)

Compute the Smith normal form of $x$.

source

#Nemo.snf_diagonal — Method.

snf_diagonal(x::fmpz_mat)

Given a diagonal matrix $x$ compute the Smith normal form of $x$.

source

#Nemo.issnf — Method.

issnf(x::fmpz_mat)

Return true if $x$ is in Smith normal form, otherwise return false.

source

Here are some examples of computing the Smith Normal Form.

S = MatrixSpace(ZZ, 3, 3)

A = S([fmpz(2) 3 5; 1 4 7; 19 3 7])

B = snf(A)
issnf(B) == true

B = S([fmpz(2) 0 0; 0 4 0; 0 0 7])

C = snf_diagonal(B)

Strong Echelon Form

#Nemo.strong_echelon_form — Method.

strong_echelon_form(a::nmod_mat)

Return the strong echeleon form of $a$. The matrix $a$ must have at least as many rows as columns.

source

Here is an example of computing the strong echelon form.

R = ResidueRing(ZZ, 12)
S = MatrixSpace(R, 3, 3)

A = S([4 1 0; 0 0 5; 0 0 0 ])

B = strong_echelon_form(A)

Howell Form

#Nemo.howell_form — Method.

howell_form(a::nmod_mat)

Return the Howell normal form of $a$. The matrix $a$ must have at least as many rows as columns.

source

Here is an example of computing the Howell form.

R = ResidueRing(ZZ, 12)
S = MatrixSpace(R, 3, 3)

A = S([4 1 0; 0 0 5; 0 0 0 ])

B = howell_form(A)

Gram-Schmidt Orthogonalisation

#Nemo.gso — Method.

gso(x::fmpq_mat)

Return the Gram-Schmidt Orthogonalisation of the matrix $x$.

source

Here are some examples of computing the Gram-Schmidt Orthogonalisation.

S = MatrixSpace(QQ, 3, 3)

A = S([4 7 3; 2 9 1; 0 5 3])

B = gso(A)

Exponential

#Base.exp — Method.

exp(x::arb_mat)

Returns the exponential of the matrix $x$.

source

#Base.exp — Method.

exp(x::acb_mat)

Returns the exponential of the matrix $x$.

source

Here are some examples of computing the exponential function of matrix.

A = RR[2 0 0; 0 3 0; 0 0 1]

B = exp(A)

Norm

#Nemo.bound_inf_norm — Method.

bound_inf_norm(x::arb_mat)

Returns a nonnegative element $z$ of type arb, such that $z$ is an upper bound for the infinity norm for every matrix in $x$

source

#Nemo.bound_inf_norm — Method.

bound_inf_norm(x::acb_mat)

Returns a nonnegative element $z$ of type acb, such that $z$ is an upper bound for the infinity norm for every matrix in $x$

source

Here are some examples of computing bounds on the infinity norm of a matrix.

A = RR[1 2 3; 4 5 6; 7 8 9]

d = bound_inf_norm(A)

Shifting

#Base.Math.ldexp — Method.

ldexp(x::acb_mat, y::Int)

Return $2^yx$. Note that $y$ can be positive, zero or negative.

source

#Base.Math.ldexp — Method.

ldexp(x::acb_mat, y::Int)

Return $2^yx$. Note that $y$ can be positive, zero or negative.

source

Here are some examples of shifting.

A = RR[1 2 3; 4 5 6; 7 8 9]

B = ldexp(A, 4)

overlaps(16*A, B)

Predicates

#Base.isreal — Method.

isreal(M::acb_mat)

Returns whether every entry of $M$ has vanishing imaginary part.

source

Here are some examples for predicates.

A = CC[1 2 3; 4 5 6; 7 8 9]

isreal(A)

isreal(onei(CC)*A)

Conversion to Julia matrices

Julia matrices use a different data structure than Nemo matrices. Conversion to Julia matrices is usually only required for interfacing with other packages. It isn't necessary to convert Nemo matrices to Julia matrices in order to manipulate them.

This conversion can be performed with standard Julia syntax, such as the following, where A is a fmpz_mat:

Matrix{Int}(A)
Matrix{BigInt}(A)

In case the matrix cannot be converted without loss, an InexactError is thrown: in this case, cast to a matrix of BigInts rather than Ints.