# Matrices

Nemo allow the creation of dense matrices over any computable ring $R$. There are two different kinds of implementation: a generic one for the case where no specific implementation exists (provided by AbstractAlgebra.jl), 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).

Base ringLibraryElement typeParent type
Generic ring $R$AbstractAlgebra.jlGeneric.Mat{T}Generic.MatSpace{T}
$\mathbb{Z}$FlintZZMatrixZZMatrixSpace
$\mathbb{Z}/n\mathbb{Z}$ (small $n$)FlintzzModMatrixzzModMatrixSpace
$\mathbb{Z}/n\mathbb{Z}$ (large $n$)FlintZZModMatrixZZModMatrixSpace
$\mathbb{Q}$FlintQQMatrixQQMatrixSpace
$\mathbb{Z}/p\mathbb{Z}$ (small $p$)FlintfpMatrixfpMatrixSpace
$\mathbb{F}_{p^n}$ (small $p$)FlintfqPolyRepMatrixfqPolyRepMatrixSpace
$\mathbb{F}_{p^n}$ (large $p$)FlintFqPolyRepMatrixFqPolyRepMatrixSpace
$\mathbb{R}$ (arbitrary precision)ArbRealMatRealMatSpace
$\mathbb{C}$ (arbitrary precision)ArbComplexMatComplexMatSpace
$\mathbb{R}$ (fixed precision)Arbarb_matArbMatSpace
$\mathbb{C}$ (fixed precision)Arbacb_matAcbMatSpace

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.

Note that the preferred way to create matrices is not to use the type constructors but to use the matrix function, see also the Matrix element constructors section of the AbstractAlgebra manual.

## Matrix functionality

All matrix spaces in Nemo provide the matrix functionality of AbstractAlgebra:

https://nemocas.github.io/AbstractAlgebra.jl/stable/matrix

Some of this functionality is provided in Nemo by C libraries, such as Flint, for various specific rings.

In the following, we list the functionality which is provided in addition to the generic matrix functionality, for specific rings in Nemo.

### Comparison operators

Nemo.overlapsMethod
overlaps(x::RealMat, y::RealMat)

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

source
Nemo.overlapsMethod
overlaps(x::ComplexMat, y::ComplexMat)

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

source
Base.containsMethod
contains(x::RealMat, y::RealMat)

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

source
Base.containsMethod
contains(x::ComplexMat, y::ComplexMat)

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

source

Examples

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

Examples

S = matrix_space(ZZ, 3, 3)

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

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

### Determinant

Nemo.det_divisorMethod
det_divisor(x::ZZMatrix)

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

source
Nemo.det_given_divisorMethod
det_given_divisor(x::ZZMatrix, 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_divisorMethod
det_given_divisor(x::ZZMatrix, d::ZZRingElem, 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

Examples

S = matrix_space(ZZ, 3, 3)

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

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

### Linear solving

Nemo.cansolveMethod
cansolve(a::ZZMatrix, b::ZZMatrix) -> Bool, ZZMatrix

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

source
Nemo.solve_dixonMethod
solve_dixon(a::ZZMatrix, b::ZZMatrix)

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_dixonMethod
solve_dixon(a::QQMatrix, b::QQMatrix)

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

source

Examples

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

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

X, m = solve_dixon(A, B)

### Pseudo inverse

Examples

S = matrix_space(ZZ, 3, 3)

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

B, d = pseudo_inv(A)

### Nullspace

Nemo.nullspace_right_rationalMethod
nullspace_right_rational(x::ZZMatrix)

Return a tuple $(r, U)$ consisting of a matrix $U$ such that the first $r$ columns form 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

### Modular reduction

Examples

S = matrix_space(ZZ, 3, 3)

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

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

### Lifting

AbstractAlgebra.liftMethod
lift(a::T) where {T <: Zmodn_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
AbstractAlgebra.liftMethod
lift(a::fpMatrix)

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

Examples

R = residue_ring(ZZ, 7)
S = matrix_space(R, 3, 3)

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

b = lift(a)

### Special matrices

Nemo.hadamardMethod
hadamard(R::ZZMatrixSpace)

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

source
Nemo.is_hadamardMethod
is_hadamard(x::ZZMatrix)

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

source
Nemo.hilbertMethod
hilbert(R::QQMatrixSpace)

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

source

Examples

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

B = hilbert(R)

### Hermite Normal Form

Nemo.hnf_modularMethod
hnf_modular(x::ZZMatrix, d::ZZRingElem)

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_eldivMethod
hnf_modular_eldiv(x::ZZMatrix, d::ZZRingElem)

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
AbstractAlgebra.is_hnfMethod
is_hnf(x::ZZMatrix)

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

source

Examples

S = matrix_space(ZZ, 3, 3)

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

B = hnf(A)
H, T = hnf_with_transform(A)
M = hnf_modular(A, ZZ(27))
N = hnf_modular_eldiv(A, ZZ(27))
is_hnf(M)

### 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.lllMethod
lll(x::ZZMatrix, ctx::lll_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_transformMethod
lll_with_transform(x::ZZMatrix, ctx::lll_ctx = lll_ctx(0.99, 0.51))

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_gramMethod
lll_gram(x::ZZMatrix, ctx::lll_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_transformMethod
lll_gram_with_transform(x::ZZMatrix, ctx::lll_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_removalMethod
lll_with_removal(x::ZZMatrix, b::ZZRingElem, ctx::lll_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_transformMethod
lll_with_removal_transform(x::ZZMatrix, b::ZZRingElem, ctx::lll_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
Nemo.lll!Method
lll!(x::ZZMatrix, ctx::lll_ctx = lll_ctx(0.99, 0.51))

Perform the LLL reduction of the matrix $x$ inplace. 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_gram!Method
lll_gram!(x::ZZMatrix, ctx::lll_ctx = lll_ctx(0.99, 0.51, :gram))

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

source

Examples

S = matrix_space(ZZ, 3, 3)

A = S([ZZ(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, ZZ(100))
r, L, T = lll_with_removal_transform(A, ZZ(100))

### Smith Normal Form

Examples

S = matrix_space(ZZ, 3, 3)

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

B = snf(A)
is_snf(B) == true

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

C = snf_diagonal(B)

### Strong Echelon Form

Examples

R = residue_ring(ZZ, 12)
S = matrix_space(R, 3, 3)

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

B = strong_echelon_form(A)

### Howell Form

Nemo.howell_formMethod
howell_form(a::zzModMatrix)

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

source
Nemo.howell_formMethod
howell_form(a::fpMatrix)

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

source

Examples

R = residue_ring(ZZ, 12)
S = matrix_space(R, 3, 3)

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

B = howell_form(A)

### Gram-Schmidt Orthogonalisation

Nemo.gram_schmidt_orthogonalisationMethod
gram_schmidt_orthogonalisation(x::QQMatrix)

Takes the columns of $x$ as the generators of a subset of $\mathbb{Q}^m$ and returns a matrix whose columns are an orthogonal generating set for the same subspace.

Examples

julia> S = matrix_space(QQ, 3, 3);

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

julia> B = gram_schmidt_orthogonalisation(A)
[4   -11//5     95//123]
[2    22//5   -190//123]
[0        5    209//123]
source

### Exponential

Examples

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

B = exp(A)

### Norm

Nemo.bound_inf_normMethod
bound_inf_norm(x::RealMat)

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_normMethod
bound_inf_norm(x::ComplexMat)

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

Examples

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

d = bound_inf_norm(A)

### Shifting

Examples

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

B = ldexp(A, 4)

overlaps(16*A, B)

### Predicates

Examples

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 an ZZMatrix:

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.

### Eigenvalues and Eigenvectors (experimental)

LinearAlgebra.eigvalsMethod
eigvals(A::ComplexMat)

Returns the eigenvalues of A as a vector of tuples (ComplexFieldElem, Int). Each tuple (z, k) corresponds to a cluster of k eigenvalues of $A$.

This function is experimental.

source
Nemo.eigvals_simpleMethod
eigvals_simple(A::ComplexMat, algorithm::Symbol = :default)

Returns the eigenvalues of A as a vector of acb. It is assumed that A has only simple eigenvalues.

The algorithm used can be changed by setting the algorithm keyword to :vdhoeven_mourrain or :rump.

This function is experimental.

source
A = CC[1 2 3; 0 4 5; 0 0 6]
eigvals_simple(A)
A = CC[2 2 3; 0 2 5; 0 0 2])
eigvals(A)`