Generic matrices

AbstractAlgebra.jl allows the creation of dense matrices over any computable commutative ring $R$. Generic matrices over a commutative ring are implemented in src/generic/Matrix.jl. Much of the functionality there covers both matrix spaces and matrix algebras.

Functions specific to generic matrix algebras of $m\times m$ matrices are implemented in src/generic/MatrixAlgebra.jl.

As well as implementing the entire Matrix interface, including the optional functionality, there are many additional generic algorithms implemented for matrix spaces. We describe this functionality below.

All of this generic functionality is part of the Generic submodule of AbstractAlgebra.jl. This is exported by default, so it is not necessary to qualify names of functions.

Types and parent objects

Generic matrices in AbstractAlgebra.jl have type Generic.MatSpaceElem{T} for matrices in a matrix space, or Generic.MatAlgElem{T} for matrices in a matrix algebra, where T is the type of elements of the matrix. Internally, generic matrices are implemented using an object wrapping a Julia two dimensional array, though they are not themselves Julia arrays. See the file src/generic/GenericTypes.jl for details.

For the most part, one doesn't want to work directly with the MatSpaceElem type though, but with an abstract type called Generic.Mat which includes MatSpaceElem and views thereof.

Parents of generic matrices (matrix spaces) have type Generic.MatSpace{T}. Parents of matrices in a matrix algebra have type Generic.MatAlgebra{T}.

The generic matrix types (matrix spaces) belong to the abstract type AbstractAlgebra.MatElem{T} and the matrix space parent types belong to AbstractAlgebra.MatSpace{T}. Similarly the generic matrix algebra matrix types belong to the abstract type AbstractAlgebra.MatAlgElem{T} and the parent types belong to AbstractAlgebra.MatAlgebra{T} Note that both the concrete type of a matrix space parent object and the abstract class it belongs to have the name MatElem, therefore disambiguation is required to specify which is intended. The same is true for the abstract types for matrix spaces and their elements.

The dimensions and base ring $R$ of a generic matrix are stored in its parent object, however to allow creation of matrices without first creating the matrix space parent, generic matrices in Julia do not contain a reference to their parent. They contain the row and column numbers (or degree, in the case of matrix algebras) and the base ring on a per matrix basis. The parent object can then be reconstructed from this data on demand.

Matrix space constructors

A matrix space in AbstractAlgebra.jl represents a collection of all matrices with given dimensions and base ring.

In order to construct matrices in AbstractAlgebra.jl, one can first construct the matrix space itself. This is accomplished with the following constructor. We discuss creation of matrix algebras separately in a dedicated section elsewhere in the documentation.

MatrixSpace(R::Ring, rows::Int, cols::Int; cache::Bool=true)

Construct the space of matrices with the given number of rows and columns over the given base ring. By default such matrix spaces are cached based on the base ring and numbers of rows and columns. If the optional named parameter cached is set to false, no caching occurs.

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

Examples

julia> R, t = PolynomialRing(QQ, "t")
(Univariate Polynomial Ring in t over Rationals, t)

julia> S = MatrixSpace(R, 3, 3)
Matrix Space of 3 rows and 3 columns over Univariate Polynomial Ring in t over Rationals

julia> A = S()
[0  0  0]
[0  0  0]
[0  0  0]

julia> B = S(12)
[12   0   0]
[ 0  12   0]
[ 0   0  12]

julia> C = S(R(11))
[11   0   0]
[ 0  11   0]
[ 0   0  11]

We also allow matrices over a given base ring to be constructed directly (see the Matrix interface).

Matrix element constructors

In addition to coercing elements into a matrix space as above, we provide the following syntax for constructing literal matrices (similar to how Julia arrays can be be constructed).

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)].

Also see the Matrix interface for a list of other ways to create matrices.

Examples

julia> R, t = PolynomialRing(QQ, "t")
(Univariate Polynomial Ring in t over Rationals, t)

julia> S = MatrixSpace(R, 3, 3)
Matrix Space of 3 rows and 3 columns over Univariate Polynomial Ring in t over Rationals

julia> M = R[t + 1 1; t^2 0]
[t + 1  1]
[  t^2  0]

julia> N = R[t + 1 2 t] # create a row vector
[t + 1  2  t]

julia> P = R[1; 2; t] # create a column vector
[1]
[2]
[t]

Conversion to Julia matrices

While AbstractAlgebra matrices are not instances of AbstractArray, they are closely related to Julia matrices. For convenience, a Matrix and an Array constructors taking an AbstractAlgebra matrix as input are provided:

Base.Matrix — Method.

Matrix(A::MatrixElem)

Convert A to a Julia Matrix of the same dimensions with the same elements.

Examples

julia> A = ZZ[1 2 3; 4 5 6]
[1  2  3]
[4  5  6]

julia> Matrix(A)
2×3 Array{BigInt,2}:
 1  2  3
 4  5  6

Core.Array — Method.

Array(A::MatrixElem)

Convert A to a Julia Matrix of the same dimensions with the same elements.

Examples

julia> R, x = ZZ["x"]; A = R[x^0 x^1; x^2 x^3]
[  1    x]
[x^2  x^3]

julia> Array(A)
2×2 Array{AbstractAlgebra.Generic.Poly{BigInt},2}:
 1    x
 x^2  x^3

Matrix functionality provided by AbstractAlgebra.jl

Most of the following generic functionality is available for both matrix spaces and matrix algebras. Exceptions include functions that do not return or accept square matrices or which cannot specify a parent. Such functions include solve, kernel, and nullspace which can't be provided for matrix algebras.

For details on functionality that is provided for matrix algebras only, see the dedicated section of the documentation.

Basic matrix functionality

As well as the Ring and Matrix interfaces, the following functions are provided to manipulate matrices and to set and retrieve entries and other basic data associated with the matrices.

AbstractAlgebra.Generic.dense_matrix_type — Method.

dense_matrix_type(R::Ring)

Return the type of matrices over the given ring.

AbstractAlgebra.Generic.nrows — Method.

nrows(a::Generic.MatrixElem)

Return the number of rows of the given matrix.

AbstractAlgebra.Generic.ncols — Method.

ncols(a::Generic.MatrixElem)

Return the number of columns of the given matrix.

Base.length — Method.

length(a::Generic.MatrixElem)

Return the number of entries in the given matrix.

Base.isempty — Method.

isempty(a::Generic.MatrixElem)

Return true if a does not contain any entry (i.e. length(a) == 0), and false otherwise.

AbstractAlgebra.Generic.identity_matrix — Method.

identity_matrix(R::Ring, n::Int) -> MatElem

Return the $n \times n$ identity matrix over $R$.

AbstractAlgebra.Generic.identity_matrix — Method.

identity_matrix(M::MatElem{T}) where T <: RingElement

Construct the identity matrix in the same matrix space as M, i.e. with ones down the diagonal and zeroes elsewhere. M must be square. This is an alias for one(M).

AbstractAlgebra.Generic.diagonal_matrix — Method.

diagonal_matrix(x::RingElement, m::Int, [n::Int])

Return the $m \times n$ matrix over $R$ with x along the main diagonal and zeroes elsewhere. If n is not specified, it defaults to m.

Examples

julia> diagonal_matrix(ZZ(2), 2, 3)
[2  0  0]
[0  2  0]

julia> diagonal_matrix(QQ(-1), 3)
[-1//1   0//1   0//1]
[ 0//1  -1//1   0//1]
[ 0//1   0//1  -1//1]

Base.one — Method.

one(a::AbstractAlgebra.MatSpace)

Construct the matrix in the given matrix space with ones down the diagonal and zeroes elsewhere. The matrix space must contain square matrices.

Base.one — Method.

one(a::AbstractAlgebra.MatSpace)

Construct the identity matrix in the same matrix space as a, i.e. with ones down the diagonal and zeroes elsewhere. a must be square.

AbstractAlgebra.change_base_ring — Method.

change_base_ring(R::Ring, M::MatrixElem)

Return the matrix obtained by coercing each entry into R.

Base.map — Method.

map(f, a::MatrixElem)

Transform matrix a by applying f on each element.

This is equivalent to map_entries(f, a).

Base.map! — Method.

map!(f, dst::MatrixElem, src::MatrixElem)

Like map, but stores the result in dst rather than a new matrix. This is equivalent to map_entries!(f, dst, src).

Examples

julia> R, t = PolynomialRing(QQ, "t")
(Univariate Polynomial Ring in t over Rationals, t)

julia> S = MatrixSpace(R, 3, 3)
Matrix Space of 3 rows and 3 columns over Univariate Polynomial Ring in t over Rationals

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

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

julia> T = dense_matrix_type(R)
AbstractAlgebra.Generic.MatSpaceElem{AbstractAlgebra.Generic.Poly{Rational{BigInt}}}

julia> r = nrows(B)
3

julia> c = ncols(B)
3

julia> length(B)
9

julia> isempty(B)
false

julia> M = A + B
[  t + 3        t + 3                  2]
[t^2 + t      2*t + 1            2*t + 2]
[     -3  t^2 + t + 2  t^3 + t^2 + t + 1]

julia> N = 2 + A
[t + 3      t            1]
[  t^2  t + 2            t]
[   -2  t + 2  t^2 + t + 3]

julia> M1 = deepcopy(A)
[t + 1      t            1]
[  t^2      t            t]
[   -2  t + 2  t^2 + t + 1]

julia> A != B
true

julia> isone(one(S))
true

julia> V = A[1:2, :]
[t + 1  t  1]
[  t^2  t  t]

julia> W = A^3
[    3*t^4 + 4*t^3 + t^2 - 3*t - 5           t^4 + 5*t^3 + 10*t^2 + 7*t + 4                2*t^4 + 7*t^3 + 9*t^2 + 8*t + 1]
[t^5 + 4*t^4 + 3*t^3 - 7*t^2 - 4*t              4*t^4 + 8*t^3 + 7*t^2 + 2*t                t^5 + 5*t^4 + 9*t^3 + 7*t^2 - t]
[  t^5 + 3*t^4 - 10*t^2 - 16*t - 2  t^5 + 6*t^4 + 12*t^3 + 11*t^2 + 5*t - 2  t^6 + 3*t^5 + 8*t^4 + 15*t^3 + 10*t^2 + t - 5]

julia> Z = divexact(2*A, 2)
[t + 1      t            1]
[  t^2      t            t]
[   -2  t + 2  t^2 + t + 1]

Elementary row and column operations

AbstractAlgebra.Generic.add_column — Method.

add_column(a::MatrixElem, s::RingElement, i::Int, j::Int, rows = 1:nrows(a))

Create a copy of $a$ and add $s$ times the $i$-th row to the $j$-th row of $a$.
By default, the transformation is applied to all rows of $a$. This can be changed using the optional rows argument.

AbstractAlgebra.Generic.add_column! — Method.

add_column!(a::MatrixElem, s::RingElement, i::Int, j::Int, rows = 1:nrows(a))

Add $s$ times the $i$-th row to the $j$-th row of $a$.
By default, the transformation is applied to all rows of $a$. This can be changed using the optional rows argument.

AbstractAlgebra.Generic.add_row — Method.

add_row(a::MatrixElem, s::RingElement, i::Int, j::Int, cols = 1:ncols(a))

Create a copy of $a$ and add $s$ times the $i$-th row to the $j$-th row of $a$.
By default, the transformation is applied to all columns of $a$. This can be changed using the optional cols argument.

AbstractAlgebra.Generic.add_row! — Method.

add_row!(a::MatrixElem, s::RingElement, i::Int, j::Int, cols = 1:ncols(a))

Add $s$ times the $i$-th row to the $j$-th row of $a$.
By default, the transformation is applied to all columns of $a$. This can be changed using the optional cols argument.

AbstractAlgebra.Generic.multiply_column — Method.

multiply_column(a::MatrixElem, s::RingElement, i::Int, rows = 1:nrows(a))

Create a copy of $a$ and multiply the $i$th column of $a$ with $s$.
By default, the transformation is applied to all rows of $a$. This can be changed using the optional rows argument.

AbstractAlgebra.Generic.multiply_column! — Method.

multiply_column!(a::MatrixElem, s::RingElement, i::Int, rows = 1:nrows(a))

Multiply the $i$th column of $a$ with $s$.
By default, the transformation is applied to all rows of $a$. This can be changed using the optional rows argument.

AbstractAlgebra.Generic.multiply_row — Method.

multiply_row(a::MatrixElem, s::RingElement, i::Int, cols = 1:ncols(a))

Create a copy of $a$ and multiply the $i$th row of $a$ with $s$.
By default, the transformation is applied to all columns of $a$. This can be changed using the optional cols argument.

AbstractAlgebra.Generic.multiply_row! — Method.

multiply_row!(a::MatrixElem, s::RingElement, i::Int, cols = 1:ncols(a))

Multiply the $i$th row of $a$ with $s$.
By default, the transformation is applied to all columns of $a$. This can be changed using the optional cols argument.

Examples

julia> M = ZZ[1 2 3; 2 3 4; 4 5 5]
[1  2  3]
[2  3  4]
[4  5  5]

julia> add_column(M, 2, 3, 1)
[ 7  2  3]
[10  3  4]
[14  5  5]

julia> add_row(M, 1, 2, 3)
[1  2  3]
[2  3  4]
[6  8  9]

julia> multiply_column(M, 2, 3)
[1  2   6]
[2  3   8]
[4  5  10]

julia> multiply_row(M, 2, 3)
[1   2   3]
[2   3   4]
[8  10  10]

Powering

AbstractAlgebra.powers — Method.

powers(a::Union{NCRingElement, MatElem}, d::Int)

Return an array $M$ of "powers" of a where $M[i + 1] = a^i$ for $i = 0..d$

Examples

julia> M = ZZ[1 2 3; 2 3 4; 4 5 5]
[1  2  3]
[2  3  4]
[4  5  5]

julia> A = powers(M, 4)
5-element Array{AbstractAlgebra.Generic.MatSpaceElem{BigInt},1}:
 [1 0 0; 0 1 0; 0 0 1]
 [1 2 3; 2 3 4; 4 5 5]
 [17 23 26; 24 33 38; 34 48 57]
 [167 233 273; 242 337 394; 358 497 579]
 [1725 2398 2798; 2492 3465 4044; 3668 5102 5957]

Gram matrix

AbstractAlgebra.Generic.gram — Method.

gram(x::AbstractAlgebra.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.

Examples

julia> R, t = PolynomialRing(QQ, "t")
(Univariate Polynomial Ring in t over Rationals, t)

julia> S = MatrixSpace(R, 3, 3)
Matrix Space of 3 rows and 3 columns over Univariate Polynomial Ring in t over Rationals

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

julia> B = gram(A)
[2*t^2 + 2*t + 2  t^3 + 2*t^2 + t                  2*t^2 + t - 1]
[t^3 + 2*t^2 + t      t^4 + 2*t^2                      t^3 + 3*t]
[  2*t^2 + t - 1        t^3 + 3*t  t^4 + 2*t^3 + 4*t^2 + 6*t + 9]

Trace

LinearAlgebra.tr — Method.

tr(x::Generic.MatrixElem)

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

Examples

julia> R, t = PolynomialRing(QQ, "t")
(Univariate Polynomial Ring in t over Rationals, t)

julia> S = MatrixSpace(R, 3, 3)
Matrix Space of 3 rows and 3 columns over Univariate Polynomial Ring in t over Rationals

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

julia> b = tr(A)
t^2 + 3*t + 2

Content

AbstractAlgebra.Generic.content — Method.

content(x::Generic.MatrixElem)

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

Examples

julia> R, t = PolynomialRing(QQ, "t")
(Univariate Polynomial Ring in t over Rationals, t)

julia> S = MatrixSpace(R, 3, 3)
Matrix Space of 3 rows and 3 columns over Univariate Polynomial Ring in t over Rationals

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

julia> b = content(A)
1

Permutation

Base.:* — Method.

*(P::Generic.perm, x::Generic.MatrixElem)

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

Examples

julia> R, t = PolynomialRing(QQ, "t")
(Univariate Polynomial Ring in t over Rationals, t)

julia> S = MatrixSpace(R, 3, 3)
Matrix Space of 3 rows and 3 columns over Univariate Polynomial Ring in t over Rationals

julia> G = SymmetricGroup(3)
Full symmetric group over 3 elements

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

julia> P = G([1, 3, 2])
(2,3)

julia> B = P*A
[t + 1      t            1]
[   -2  t + 2  t^2 + t + 1]
[  t^2      t            t]

LU factorisation

LinearAlgebra.lu — Method.

lu(A::Generic.MatrixElem{T}, P = SymmetricGroup(nrows(A))) where {T <: FieldElement}

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$.

AbstractAlgebra.Generic.fflu — Method.

fflu(A::Generic.MatrixElem{T}, P = SymmetricGroup(nrows(A))) where {T <: RingElement}

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) = LDU$, 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.

Examples

julia> R, x = PolynomialRing(QQ, "x")
(Univariate Polynomial Ring in x over Rationals, x)

julia> K, a = NumberField(x^3 + 3x + 1, "a")
(Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1, x)

julia> S = MatrixSpace(K, 3, 3)
Matrix Space of 3 rows and 3 columns over Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1

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

julia> r, P, L, U = lu(A)
(2, (1,2), [1 0 0; 0 1 0; 1 0 1], [(x^2 - 2) (x - 1) (2*x); 0 (2*x + 3) (x^2 + 1); 0 0 0])

julia> r, d, P, L, U = fflu(A)
(2, 3*x^2 - 10*x - 8, (1,2), [(x^2 - 2) 0 0; 0 (3*x^2 - 10*x - 8) 0; (x^2 - 2) 0 1], [(x^2 - 2) (x - 1) (2*x); 0 (3*x^2 - 10*x - 8) (-4*x^2 - x - 2); 0 0 0])

Reduced row-echelon form

AbstractAlgebra.Generic.rref — Method.

rref(M::Generic.MatrixElem{T}) where {T <: RingElement}

Return 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.

AbstractAlgebra.Generic.rref — Method.

rref(M::Generic.MatrixElem{T}) where {T <: RingElement}

Return 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.

rref(M::Generic.MatrixElem{T}) where {T <: FieldElement}

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

AbstractAlgebra.Generic.isrref — Method.

isrref(M::Generic.MatrixElem{T}) where {T <: RingElement}

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

AbstractAlgebra.Generic.isrref — Method.

isrref(M::Generic.MatrixElem{T}) where {T <: RingElement}

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

isrref(M::Generic.MatrixElem{T}) where {T <: FieldElement}

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

Examples

julia> R, x = PolynomialRing(QQ, "x")
(Univariate Polynomial Ring in x over Rationals, x)

julia> K, a = NumberField(x^3 + 3x + 1, "a")
(Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1, x)

julia> S = MatrixSpace(K, 3, 3)
Matrix Space of 3 rows and 3 columns over Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1

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

julia> r, A = rref(M)
(3, [1 0 0; 0 1 0; 0 0 1])

julia> isrref(A)
true

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S = MatrixSpace(R, 3, 3)
Matrix Space of 3 rows and 3 columns over Univariate Polynomial Ring in x over Integers

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

julia> r, d, A = rref(M)
(3, -x^5 - 2*x^4 - 15*x^3 - 18*x^2 - 8*x - 7, [-x^5 - 2*x^4 - 15*x^3 - 18*x^2 - 8*x - 7 0 0; 0 -x^5 - 2*x^4 - 15*x^3 - 18*x^2 - 8*x - 7 0; 0 0 -x^5 - 2*x^4 - 15*x^3 - 18*x^2 - 8*x - 7])

julia> isrref(A)
true

Hermite normal form

AbstractAlgebra.Generic.hnf — Method.

hnf(A::Generic.MatrixElem{T}) where {T <: RingElement}

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

AbstractAlgebra.Generic.hnf_with_transform — Method.

hnf_with_transform(A)

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

AbstractAlgebra.Generic.ishnf — Method.

ishnf(M::Generic.MatrixElem{T}) where T <: RingElement

Return true if the matrix is in Hermite normal form.

Determinant

LinearAlgebra.det — Method.

det(M::Generic.MatrixElem{T}) where {T <: RingElement}

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

LinearAlgebra.det — Method.

det(M::Generic.MatrixElem{T}) where {T <: FieldElement}

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

det(M::Generic.MatrixElem{T}) where {T <: RingElement}

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

Examples

julia> R, x = PolynomialRing(QQ, "x")
(Univariate Polynomial Ring in x over Rationals, x)

julia> K, a = NumberField(x^3 + 3x + 1, "a")
(Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1, x)

julia> S = MatrixSpace(K, 3, 3)
Matrix Space of 3 rows and 3 columns over Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1

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

julia> d = det(A)
11*x^2 - 30*x - 5

Rank

LinearAlgebra.rank — Method.

rank(M::Generic.MatrixElem{T}) where {T <: RingElement}

Return the rank of the matrix $M$.

LinearAlgebra.rank — Method.

rank(M::Generic.MatrixElem{T}) where {T <: RingElement}

Return the rank of the matrix $M$.

rank(M::Generic.MatrixElem{T}) where {T <: FieldElement}

Return the rank of the matrix $M$.

Examples

julia> R, x = PolynomialRing(QQ, "x")
(Univariate Polynomial Ring in x over Rationals, x)

julia> K, a = NumberField(x^3 + 3x + 1, "a")
(Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1, x)

julia> S = MatrixSpace(K, 3, 3)
Matrix Space of 3 rows and 3 columns over Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1

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

julia> d = rank(A)
3

Linear solving

AbstractAlgebra.Generic.solve — Method.

solve(M::AbstractAlgebra.MatElem{T}, b::AbstractAlgebra.MatElem{T}) where {T <: FieldElement}

Given a non-singular $n\times n$ matrix over a field and an $n\times m$ matrix over the same field, return $x$ an $n\times m$ matrix $x$ such that $Ax = b$. If $A$ is singular an exception is raised.

AbstractAlgebra.Generic.solve_rational — Method.

solve_rational(M::AbstractAlgebra.MatElem{T}, b::AbstractAlgebra.MatElem{T}) where T <: RingElement

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.

AbstractAlgebra.Generic.solve_left — Method.

solve_left(a::AbstractAlgebra.MatElem{S}, b::AbstractAlgebra.MatElem{S}) where S <: RingElement

Given an $r\times n$ matrix $a$ over a ring and an $m\times n$ matrix $b$ over the same ring, return an $m\times r$ matrix $x$ such that $xa = b$. If no such matrix exists, an exception is raised.

AbstractAlgebra.Generic.solve_triu — Method.

solve_triu(U::AbstractAlgebra.MatElem{T}, b::AbstractAlgebra.MatElem{T}, unit::Bool = false) where {T <: FieldElement}

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.

AbstractAlgebra.Generic.can_solve_left_reduced_triu — Method.

can_solve_left_reduced_triu(r::AbstractAlgebra.MatElem{T},
                      M::AbstractAlgebra.MatElem{T}) where T <: RingElement

Return a tuple flag, x where flag is set to true if $xM = r$ has a solution, where $M$ is an $m\times n$ matrix in (upper triangular) Hermite normal form or reduced row echelon form and $r$ and $x$ are row vectors with $m$ columns. If there is no solution, flag is set to false and $x$ is set to the zero row.

Examples

julia> R, x = PolynomialRing(QQ, "x")
(Univariate Polynomial Ring in x over Rationals, x)

julia> K, a = NumberField(x^3 + 3x + 1, "a")
(Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1, x)

julia> S = MatrixSpace(K, 3, 3)
Matrix Space of 3 rows and 3 columns over Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1

julia> U = MatrixSpace(K, 3, 1)
Matrix Space of 3 rows and 1 columns over Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1

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

julia> b = U([2a a + 1 (-a - 1)]')
[   2*x]
[ x + 1]
[-x - 1]

julia> x = solve(A, b)
[  1984//7817*x^2 + 1573//7817*x - 937//7817]
[ -2085//7817*x^2 + 1692//7817*x + 965//7817]
[-3198//7817*x^2 + 3540//7817*x - 3525//7817]

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

julia> bb = U([2a a + 1 (-a - 1)]')
[   2*x]
[ x + 1]
[-x - 1]

julia> x = solve_triu(A, bb, false)
[ 1//3*x^2 + 8//3*x + 13//3]
[-3//5*x^2 - 3//5*x - 12//5]
[                   x^2 + 2]

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S = MatrixSpace(R, 3, 3)
Matrix Space of 3 rows and 3 columns over Univariate Polynomial Ring in x over Integers

julia> U = MatrixSpace(R, 3, 2)
Matrix Space of 3 rows and 2 columns over Univariate Polynomial Ring in x over Integers

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

julia> bbb = U([2x x + 1 (-x - 1); x + 1 (-x) x^2]')
[   2*x  x + 1]
[ x + 1     -x]
[-x - 1    x^2]

julia> x, d = solve_rational(A, bbb)
([3*x^4 - 10*x^3 - 8*x^2 - 11*x - 4 -x^5 + 3*x^4 + x^3 - 2*x^2 + 3*x - 1; -2*x^5 - x^4 + 6*x^3 + 2*x + 1 x^6 + x^5 + 4*x^4 + 9*x^3 + 8*x^2 + 5*x + 2; 6*x^4 + 12*x^3 + 15*x^2 + 6*x - 3 -2*x^5 - 4*x^4 - 6*x^3 - 9*x^2 - 4*x + 1], x^5 + 2*x^4 + 15*x^3 + 18*x^2 + 8*x + 7)

julia> S = MatrixSpace(ZZ, 3, 3)
Matrix Space of 3 rows and 3 columns over Integers

julia> T = MatrixSpace(ZZ, 3, 1)
Matrix Space of 3 rows and 1 columns over Integers

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

julia> B = T([BigInt(4), 5, 7])
[4]
[5]
[7]

Inverse

Base.inv — Method.

inv(M::Generic.MatrixElem{T}) where {T <: RingElement}

Given a non-singular $n\times n$ matrix over a ring, return an $n\times n$ matrix $X$ such that $MX = I_n$, where $I_n$ is the $n\times n$ identity matrix. If $M$ is not invertible over the base ring an exception is raised.

Examples

julia> R, x = PolynomialRing(QQ, "x")
(Univariate Polynomial Ring in x over Rationals, x)

julia> K, a = NumberField(x^3 + 3x + 1, "a")
(Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1, x)

julia> S = MatrixSpace(K, 3, 3)
Matrix Space of 3 rows and 3 columns over Residue field of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1

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

julia> X = inv(A)
[-343//7817*x^2 + 717//7817*x - 2072//7817  -4964//23451*x^2 + 2195//23451*x - 11162//23451   -232//23451*x^2 - 4187//23451*x - 1561//23451]
[ 128//7817*x^2 - 655//7817*x + 2209//7817     599//23451*x^2 - 2027//23451*x - 1327//23451  -1805//23451*x^2 + 2702//23451*x - 7394//23451]
[ 545//7817*x^2 + 570//7817*x + 2016//7817    -1297//23451*x^2 - 5516//23451*x - 337//23451  8254//23451*x^2 - 2053//23451*x + 16519//23451]

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S = MatrixSpace(R, 3, 3)
Matrix Space of 3 rows and 3 columns over Univariate Polynomial Ring in x over Integers

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

julia> X, d = pseudo_inv(A)
([4*x^2 - x + 1 -2*x^3 + 3 x^3 - 5*x^2 - 5*x - 1; -2*x^3 - 5*x^2 - 2*x - 2 x^4 + 3*x^3 + 2*x^2 + 3*x + 1 -x^4 + x^2 + 2; -x^3 + 2*x^2 + 2*x - 1 -2*x^3 - 9*x^2 - 11*x - 3 2*x^3 + 3*x^2 - 4*x - 6], -x^5 - 2*x^4 - 15*x^3 - 18*x^2 - 8*x - 7)

Nullspace

LinearAlgebra.nullspace — Method.

nullspace(M::AbstractAlgebra.MatElem{T}) where {T <: RingElement}

Return 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 AbstractAlgebra we use the name "kernel" for a function to compute an integral kernel.

LinearAlgebra.nullspace — Method.

nullspace(M::AbstractAlgebra.MatElem{T}) where {T <: RingElement}

Return 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 AbstractAlgebra we use the name "kernel" for a function to compute an integral kernel.

nullspace(M::AbstractAlgebra.MatElem{T}) where {T <: FieldElement}

Return 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.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S = MatrixSpace(R, 4, 4)
Matrix Space of 4 rows and 4 columns over Univariate Polynomial Ring in x over Integers

julia> 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])
[  -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]

julia> n, N = nullspace(M)
(2, [1320*x^4 - 330*x^2 - 1320*x - 1320 1056*x^4 + 1254*x^3 + 1848*x^2 - 66*x - 330; -660*x^4 + 1320*x^3 + 1188*x^2 - 1848*x - 1056 -528*x^4 + 132*x^3 + 1584*x^2 + 660*x - 264; 396*x^3 - 396*x^2 - 792*x 0; 0 396*x^3 - 396*x^2 - 792*x])

Kernel

AbstractAlgebra.Generic.kernel — Method.

kernel(a::MatElem{T}; side::Symbol = :right) where T <: RingElement

Return a tuple $(n, M)$, where n is the rank of the kernel and $M$ is a basis for it. If side is $:right$ or not specified, the right kernel is computed, i.e. the matrix of columns whose span gives the right kernel space. If side is $:left$, the left kernel is computed, i.e. the matrix of rows whose span is the left kernel space.

AbstractAlgebra.Generic.left_kernel — Method.

left_kernel(a::AbstractAlgebra.MatElem{T}) where T <: RingElement

Return a tuple n, M where $M$ is a matrix whose rows generate the kernel of $M$ and $n$ is the rank of the kernel. The transpose of the output of this function is guaranteed to be in flipped upper triangular format (i.e. upper triangular format if columns and rows are reversed).

AbstractAlgebra.Generic.right_kernel — Method.

right_kernel(a::AbstractAlgebra.MatElem{T}) where T <: RingElement

Return a tuple n, M where $M$ is a matrix whose columns generate the kernel of $M$ and $n$ is the rank of the kernel.

Examples

julia> S = MatrixSpace(ZZ, 4, 4)
Matrix Space of 4 rows and 4 columns over Integers

julia> M = S([1 2 0 4;
              2 0 1 1;
              0 1 1 -1;
              2 -1 0 2])
[1   2  0   4]
[2   0  1   1]
[0   1  1  -1]
[2  -1  0   2]

julia> nr, Nr = kernel(M)
(1, [-8; -6; 11; 5])

julia> nl, Nl = left_kernel(M)
(1, [0 -1 1 1])

Hessenberg form

LinearAlgebra.hessenberg — Method.

hessenberg(A::Generic.MatrixElem{T}) where {T <: RingElement}

Return 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.

AbstractAlgebra.Generic.ishessenberg — Method.

ishessenberg(A::Generic.MatrixElem{T}) where {T <: RingElement}

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

Examples

julia> R = ResidueRing(ZZ, 7)
Residue ring of Integers modulo 7

julia> S = MatrixSpace(R, 4, 4)
Matrix Space of 4 rows and 4 columns over Residue ring of Integers modulo 7

julia> 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)])
[1  2  4  3]
[2  5  1  0]
[6  1  3  2]
[1  1  3  5]

julia> A = hessenberg(M)
[1  5  5  3]
[2  1  1  0]
[0  1  3  2]
[0  0  2  2]

julia> ishessenberg(A)
true

Characteristic polynomial

AbstractAlgebra.Generic.charpoly — Method.

charpoly(V::Ring, Y::Generic.MatrixElem{T}) where {T <: RingElement}

Return 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.

Examples

julia> R = ResidueRing(ZZ, 7)
Residue ring of Integers modulo 7

julia> S = MatrixSpace(R, 4, 4)
Matrix Space of 4 rows and 4 columns over Residue ring of Integers modulo 7

julia> T, x = PolynomialRing(R, "x")
(Univariate Polynomial Ring in x over Residue ring of Integers modulo 7, x)

julia> 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)])
[1  2  4  3]
[2  5  1  0]
[6  1  3  2]
[1  1  3  5]

julia> A = charpoly(T, M)
x^4 + 2*x^2 + 6*x + 2

Minimal polynomial

AbstractAlgebra.Generic.minpoly — Method.

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

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

AbstractAlgebra.Generic.minpoly — Method.

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

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

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

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

Examples

julia> R = GF(13)
Finite field F_13

julia> T, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Finite field F_13, y)

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

julia> A = minpoly(T, M)
y^2 + 10*y

Transforms

AbstractAlgebra.Generic.similarity! — Method.

similarity!(A::Generic.MatrixElem{T}, r::Int, d::T) where {T <: RingElement}

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.

Examples

julia> R = ResidueRing(ZZ, 7)
Residue ring of Integers modulo 7

julia> S = MatrixSpace(R, 4, 4)
Matrix Space of 4 rows and 4 columns over Residue ring of Integers modulo 7

julia> 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)])
[1  2  4  3]
[2  5  1  0]
[6  1  3  2]
[1  1  3  5]

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

(Weak) Popov form

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

AbstractAlgebra.Generic.weak_popov — Method.

weak_popov(A::Mat{T}) where {T <: PolyElem}

Return the weak Popov form of $A$.

AbstractAlgebra.Generic.weak_popov_with_transform — Method.

weak_popov_with_transform(A::Mat{T}) where {T <: PolyElem}

Compute a tuple $(P, U)$ where $P$ is the weak Popov form of $A$ and $U$ is a transformation matrix so that $P = UA$.

AbstractAlgebra.Generic.popov — Method.

popov(A::Mat{T}) where {T <: PolyElem}

Return the Popov form of $A$.

AbstractAlgebra.Generic.popov_with_transform — Method.

popov_with_transform(A::Mat{T}) where {T <: PolyElem}

Compute a tuple $(P, U)$ where $P$ is the Popov form of $A$ and $U$ is a transformation matrix so that $P = UA$.