Matrix functionality

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.

It is possible to create matrices directly, without first creating a corresponding matrix space. The following constructors are necessary, because unfortunately, Julia's matrices and linear algebra cannot be made to work in our context due to two independent problems:

  • In empty matrices (0 rows or columns) all that is known is the type of the matrix entries,

however for the complex types used in AbstractAlgebra, this information is not sufficient to create elements, hence zero(T) or friends cannot work

  • Many functions (e.g. det) assume that all types used embed into the real or complex numbers,

in Julia det(ones(Int, (1,1))) == 1.0, so the fact that this is exactly the integer 1 is lost. Furthermore, more general rings cannot be embedded into the reals at all.

matrix(R::Ring, arr::Matrix{T}) where T <: RingElement

Given an m×nm\times n Julia matrix of entries, construct the corresponding AbstractAlgebra.jl matrix over the given ring R, assuming all the entries can be coerced into R.

matrix(R::Ring, r::Int, c::Int, A::Vector{T}) where T <: RingElement

Construct the given r×cr\times c AbstractAlgebra.jl matrix over the ring R whose (i,j)(i, j) entry is given by A[c*(i - 1) + j], assuming that all the entries can be coerced into R.

zero_matrix(R::Ring, r::Int, c::Int)

Construct the r×cr\times c AbstractAlgebra.jl zero matrix over the ring R.

Examples

julia> M = matrix(ZZ, BigInt[3 1 2; 2 0 1])
[3   1   2]
[2   0   1]

julia> N = matrix(ZZ, 3, 2, BigInt[3, 1, 2, 2, 0, 1])
[3   1]
[2   2]
[0   1]

julia> P = zero_matrix(ZZ, 3, 2)
[0   0]
[0   0]
[0   0]
number_of_rowsMethod
number_of_rows(a::MatrixElem{T}) where T <: NCRingElement

Return the number of rows of the given matrix.

source
number_of_columnsMethod
number_of_columns(a::MatrixElem{T}) where T <: NCRingElement

Return the number of columns of the given matrix.

source
lengthMethod
length(a::MatrixElem{T}) where T <: NCRingElement

Return the number of entries in the given matrix.

source
isemptyMethod
isempty(a::MatrixElem{T}) where T <: NCRingElement

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

source
identity_matrixMethod
identity_matrix(R::NCRing, n::Int)

Return the n×nn \times n identity matrix over RR.

source
identity_matrixMethod
identity_matrix(M::MatElem{T}) where T <: NCRingElement

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

source
ones_matrixMethod
ones_matrix(R::Ring, r::Int, c::Int)

Return the r×cr \times c ones matrix over RR.

source
scalar_matrixMethod
scalar_matrix(R::NCRing, n::Int, a::NCRingElement)
scalar_matrix(n::Int, a::NCRingElement)

Return the n×nn \times n matrix over R with a along the main diagonal and zeroes elsewhere. If R is not specified, it defaults to parent(a).

source
diagonal_matrixMethod
diagonal_matrix(x::NCRingElement, m::Int, [n::Int])

Return the m×nm \times n matrix over RR 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]
source
zeroMethod
zero(x::MatElem{T}, R::NCRing, r::Int, c::Int) where T <: NCRingElement
zero(x::MatElem{T}, r::Int, c::Int) where T <: NCRingElement
zero(x::MatElem{T}, R::NCRing) where T <: NCRingElement
zero(x::MatElem{T}) where T <: NCRingElement

Create an zero matrix over the given ring and dimensions, with defaults based upon the given source matrix x.

source
oneMethod
one(a::MatrixElem{T}) where T <: NCRingElement

Return the identity matrix in the same matrix space as aa. If the space does not contain square matrices, an error is thrown.

source
transposeMethod
transpose(x::MatrixElem{T}) where T <: NCRingElement

Return the transpose of the given matrix.

Examples

julia> R, t = polynomial_ring(QQ, :t)
(Univariate polynomial ring in t over rationals, t)

julia> S = matrix_space(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 = transpose(A)
[t + 1   t^2            -2]
[    t     t         t + 2]
[    1     t   t^2 + t + 1]
source
transpose(A::SMat) -> SMat

Returns the transpose of AA.

source
trMethod
tr(x::MatrixElem{T}) where T <: NCRingElement

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

Examples

julia> R, t = polynomial_ring(QQ, :t)
(Univariate polynomial ring in t over rationals, t)

julia> S = matrix_space(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
source
tr(x::AbstractAssociativeAlgebraElem{T}) where T -> T

Returns the trace of xx.

source
detMethod
det(M::MatrixElem{T}) where {T <: RingElement}

Return the determinant of the matrix MM. We assume MM is square.

Examples

julia> R, x = polynomial_ring(QQ, :x)
(Univariate polynomial ring in x over rationals, x)

julia> A = R[x 1; 1 x^2];

julia> d = det(A)
x^3 - 1
source
rankMethod
rank(M::MatrixElem{T}) where {T <: RingElement}

Return the rank of the matrix MM.

Examples

julia> A = QQ[1 2; 3 4];

julia> d = rank(A)
2
source
lower_triangular_matrixMethod
lower_triangular_matrix(L::AbstractVector{T}) where {T <: NCRingElement}

Return the nn by nn matrix whose entries on and below the main diagonal are the elements of L, and which has zeroes elsewhere. The value of nn is determined by the condition that L has length n(n+1)/2n(n+1)/2.

An exception is thrown if there is no integer nn with this property.

Examples

julia> lower_triangular_matrix([1, 2, 3])
[1   0]
[2   3]
source
upper_triangular_matrixMethod
upper_triangular_matrix(L::AbstractVector{T}) where {T <: NCRingElement}

Return the nn by nn matrix whose entries on and above the main diagonal are the elements of L, and which has zeroes elsewhere. The value of nn is determined by the condition that L has length n(n+1)/2n(n+1)/2.

An exception is thrown if there is no integer nn with this property.

Examples

julia> upper_triangular_matrix([1, 2, 3])
[1   2]
[0   3]
source
strictly_lower_triangular_matrixMethod
strictly_lower_triangular_matrix(L::AbstractVector{T}) where {T <: NCRingElement}

Return the nn by nn matrix whose entries below the main diagonal are the elements of L, and which has zeroes elsewhere. The value of nn is determined by the condition that L has length (n1)n/2(n-1)n/2.

An exception is thrown if there is no integer nn with this property.

Examples

julia> strictly_lower_triangular_matrix([1, 2, 3])
[0   0   0]
[1   0   0]
[2   3   0]
source
strictly_upper_triangular_matrixMethod
strictly_upper_triangular_matrix(L::AbstractVector{T}) where {T <: NCRingElement}

Return the nn by nn matrix whose entries above the main diagonal are the elements of L, and which has zeroes elsewhere. The value of nn is determined by the condition that L has length (n1)n/2(n-1)n/2.

An exception is thrown if there is no integer nn with this property.

Examples

julia> strictly_upper_triangular_matrix([1, 2, 3])
[0   1   2]
[0   0   3]
[0   0   0]
source
is_lower_triangularMethod
is_lower_triangular(A::MatrixElem)

Return true if AA is an lower triangular matrix, that is, all entries above the main diagonal are zero. Note that this definition also applies to non-square matrices.

Alias for LinearAlgebra.istril.

Examples

julia> is_lower_triangular(QQ[1 2 ; 0 4])
false

julia> is_lower_triangular(QQ[1 0 ; 3 4])
true

julia> is_lower_triangular(QQ[1 2 ;])
false

julia> is_lower_triangular(QQ[1 ; 2])
true
source
is_upper_triangularMethod
is_upper_triangular(A::MatrixElem)

Return true if AA is an upper triangular matrix, that is, all entries below the main diagonal are zero. Note that this definition also applies to non-square matrices.

Alias for LinearAlgebra.istriu.

Examples

julia> is_upper_triangular(QQ[1 2 ; 0 4])
true

julia> is_upper_triangular(QQ[1 0 ; 3 4])
false

julia> is_upper_triangular(QQ[1 2 ;])
true

julia> is_upper_triangular(QQ[1 ; 2])
false
source
is_diagonalMethod
is_diagonal(A::MatrixElem)

Return true if AA is a diagonal matrix, that is, all entries off the main diagonal are zero. Note that this definition also applies to non-square matrices.

Alias for LinearAlgebra.isdiag.

Examples

julia> is_diagonal(QQ[1 0 ; 0 4])
true

julia> is_diagonal(QQ[1 2 ; 3 4])
false

julia> is_diagonal(QQ[1 0 ;])
true
source
change_base_ringMethod
change_base_ring(R::NCRing, M::MatrixElem{T}) where T <: NCRingElement

Return the matrix obtained by coercing each entry into R.

source
mapMethod
map(f, a::MatrixElem{T}) where T <: NCRingElement

Transform matrix a by applying f on each element. This is equivalent to map_entries(f, a).

source
map!Method
map!(f, dst::MatrixElem{T}, src::MatrixElem{U}) where {T <: NCRingElement, U <: NCRingElement}

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

source

Inverse

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

Given a non-singular n×nn\times n matrix over a ring, return an n×nn\times n matrix XX such that MX=InMX = I_n, where InI_n is the n×nn\times n identity matrix. If MM is not invertible over the base ring an exception is raised.

source
is_invertibleMethod
is_invertible(A::MatrixElem{T}) where {T <: RingElement}

Return true if a given square matrix is invertible, false otherwise. If the inverse should also be computed, use is_invertible_with_inverse.

source
is_invertible_with_inverseMethod
is_invertible_with_inverse(A::MatrixElem{T}; side::Symbol = :left) where {T <: RingElement}

Given an n×mn \times m matrix AA over a ring, return a tuple (flag, B). If side is :right and flag is true, BB is a right inverse of AA i.e. ABA B is the n×nn \times n unit matrix. If side is :left and flag is true, BB is a left inverse of AA i.e. BAB A is the m×mm \times m unit matrix. If flag is false, no right or left inverse exists.

To get the space of all inverses, note that if BB and CC are both right inverses, then A(BC)=0A (B - C) = 0, and similar for left inverses. Hence from one inverse one can find all by making suitable use of kernel.

source
pseudo_invMethod
pseudo_inv(M::MatrixElem{T}) where {T <: RingElement}

Given a non-singular n×nn\times n matrix MM over a ring return a tuple X,dX, d consisting of an n×nn\times n matrix XX and a denominator dd such that MX=dInMX = dI_n, where InI_n is the n×nn\times n identity matrix. The denominator will be the determinant of MM up to sign. If MM is singular an exception is raised.

source

Examples

julia> M = matrix(QQ, 3, 3, [1 2 3;4 5 6;0 0 1])
[1//1   2//1   3//1]
[4//1   5//1   6//1]
[0//1   0//1   1//1]

julia> X = inv(M)
[-5//3    2//3    1//1]
[ 4//3   -1//3   -2//1]
[ 0//1    0//1    1//1]

julia> is_invertible(M)
true

julia> is_invertible_with_inverse(M)
(true, [-5//3 2//3 1; 4//3 -1//3 -2; 0 0 1])

julia> pseudo_inv(M)
([5 -2 -3; -4 1 6; 0 0 -3], -3//1)

Submatrices

Submatrices are only available for matrix spaces, not for matrix algebras and generally only available for generic matrices built on Julia arrays.

Submatrices return a new matrix with the same entries as the submatrix with the given range of rows and columns. They are best illustrated with examples.

Examples

julia> M = matrix(ZZ, BigInt[1 2 3; 2 3 4; 3 4 5])
[1   2   3]
[2   3   4]
[3   4   5]

julia> N1 = M[1:2, :]
[1   2   3]
[2   3   4]

julia> N2 = M[:, :]
[1   2   3]
[2   3   4]
[3   4   5]

julia> N3 = M[2:3, 2:3]
[3   4]
[4   5]

As per Julia, AbstractAlgebra supports the construction of matrix views. These allow one to work with a submatrix of a given matrix. Modifying the submatrix also modifies the original matrix.

The syntax for views is as for Julia's own views.

Examples

julia> M = matrix(ZZ, 3, 3, BigInt[1, 2, 3, 2, 3, 4, 3, 4, 5])
[1   2   3]
[2   3   4]
[3   4   5]

julia> N1 = @view M[1:2, :]
[1   2   3]
[2   3   4]

julia> N2 = @view M[:, 1:2]
[1   2]
[2   3]
[3   4]

julia> R = N1*N2
[14   20]
[20   29]

Elementary row and column operations

add_columnMethod
add_column(a::MatrixElem{T}, s::RingElement, i::Int, j::Int, rows = 1:nrows(a)) where T <: RingElement

Create a copy of aa and add ss times the ii-th row to the jj-th row of aa.

By default, the transformation is applied to all rows of aa. This can be changed using the optional rows argument.

source
add_column!Method
add_column!(a::MatrixElem{T}, s::RingElement, i::Int, j::Int, rows = 1:nrows(a)) where T <: RingElement

Add ss times the ii-th row to the jj-th row of aa.

By default, the transformation is applied to all rows of aa. This can be changed using the optional rows argument.

source
add_rowMethod
add_row(a::MatrixElem{T}, s::RingElement, i::Int, j::Int, cols = 1:ncols(a)) where T <: RingElement

Create a copy of aa and add ss times the ii-th row to the jj-th row of aa.

By default, the transformation is applied to all columns of aa. This can be changed using the optional cols argument.

source
add_row!Method
add_row!(a::MatrixElem{T}, s::RingElement, i::Int, j::Int, cols = 1:ncols(a)) where T <: RingElement

Add ss times the ii-th row to the jj-th row of aa.

By default, the transformation is applied to all columns of aa. This can be changed using the optional cols argument.

source
multiply_columnMethod
multiply_column(a::MatrixElem{T}, s::RingElement, i::Int, rows = 1:nrows(a)) where T <: RingElement

Create a copy of aa and multiply the iith column of aa with ss.

By default, the transformation is applied to all rows of aa. This can be changed using the optional rows argument.

source
multiply_column!Method
multiply_column!(a::MatrixElem{T}, s::RingElement, i::Int, rows = 1:nrows(a)) where T <: RingElement

Multiply the iith column of aa with ss.

By default, the transformation is applied to all rows of aa. This can be changed using the optional rows argument.

source
multiply_rowMethod
multiply_row(a::MatrixElem{T}, s::RingElement, i::Int, cols = 1:ncols(a)) where T <: RingElement

Create a copy of aa and multiply the iith row of aa with ss.

By default, the transformation is applied to all columns of aa. This can be changed using the optional cols argument.

source
multiply_row!Method
multiply_row!(a::MatrixElem{T}, s::RingElement, i::Int, cols = 1:ncols(a)) where T <: RingElement

Multiply the iith row of aa with ss.

By default, the transformation is applied to all columns of aa. This can be changed using the optional cols argument.

source

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]

Swapping rows and columns

swap_rowsMethod
swap_rows(a::MatrixElem{T}, i::Int, j::Int) where T <: NCRingElement

Return a matrix bb with the entries of aa, where the iith and jjth row are swapped.

Examples

julia> M = identity_matrix(ZZ, 3)
[1   0   0]
[0   1   0]
[0   0   1]

julia> swap_rows(M, 1, 2)
[0   1   0]
[1   0   0]
[0   0   1]

julia> M  # was not modified
[1   0   0]
[0   1   0]
[0   0   1]
source
swap_rows!Method
swap_rows!(a::MatrixElem{T}, i::Int, j::Int) where T <: NCRingElement

Swap the iith and jjth row of aa in place. The function returns the mutated matrix (since matrices are assumed to be mutable in AbstractAlgebra.jl).

Examples

julia> M = identity_matrix(ZZ, 3)
[1   0   0]
[0   1   0]
[0   0   1]

julia> swap_rows!(M, 1, 2)
[0   1   0]
[1   0   0]
[0   0   1]

julia> M  # was modified
[0   1   0]
[1   0   0]
[0   0   1]
source
swap_colsMethod
swap_cols(a::MatrixElem{T}, i::Int, j::Int) where T <: NCRingElement

Return a matrix bb with the entries of aa, where the iith and jjth row are swapped.

source
swap_cols!Method
swap_cols!(a::MatrixElem{T}, i::Int, j::Int) where T <: NCRingElement

Swap the iith and jjth column of aa in place. The function returns the mutated matrix (since matrices are assumed to be mutable in AbstractAlgebra.jl).

source

Swap the rows of M in place. The function returns the mutated matrix (since matrices are assumed to be mutable in AbstractAlgebra.jl).

Concatenation

The following are only available for matrix spaces, not for matrix algebras.

hcat(M::T, N::T) where T <: MatElem

Return the horizontal concatenation of MM and NN. It is assumed that the number of rows of MM and NN are the same.

vcat(M::T, N::T) where T <: MatElem

Return the vertical concatenation of MM and NN. It is assumed that the number of columns of MM and NN are the same.

Examples

julia> M = matrix(ZZ, BigInt[1 2 3; 2 3 4; 3 4 5])
[1   2   3]
[2   3   4]
[3   4   5]

julia> N = matrix(ZZ, BigInt[1 0 1; 0 1 0; 1 0 1])
[1   0   1]
[0   1   0]
[1   0   1]

julia> P = hcat(M, N)
[1   2   3   1   0   1]
[2   3   4   0   1   0]
[3   4   5   1   0   1]

julia> Q = vcat(M, N)
[1   2   3]
[2   3   4]
[3   4   5]
[1   0   1]
[0   1   0]
[1   0   1]

Linear solving

See Linear Solving & Kernel

Block diagonal matrix constructors

It is also possible to create block diagonal matrices from a vector of existing matrices. It is also possible to construct them from Julia matrices if one supplies the base ring.

Note that if the input matrices are not square, the output matrix may not be square.

block_diagonal_matrixMethod
block_diagonal_matrix(V::Vector{<:MatElem{T}}) where T <: NCRingElement

Create the block diagonal matrix whose blocks are given by the matrices in V. There must be at least one matrix in V.

source
block_diagonal_matrix(xs::Vector{SMat})

Return the block diagonal matrix with the matrices in xs on the diagonal. Requires all blocks to have the same base ring.

source
block_diagonal_matrixMethod
block_diagonal_matrix(R::NCRing, V::Vector{<:Matrix{T}}) where T <: NCRingElement

Create the block diagonal matrix over the ring R whose blocks are given by the matrices in V. Entries are coerced into R upon creation.

source

Examples

julia> block_diagonal_matrix(ZZ, [[1 2; 3 4], [4 5 6; 7 8 9]])
[1   2   0   0   0]
[3   4   0   0   0]
[0   0   4   5   6]
[0   0   7   8   9]

julia> M = matrix(ZZ, [1 2; 3 4])
[1   2]
[3   4]

julia> N = matrix(ZZ, [4 5 6; 7 8 9])
[4   5   6]
[7   8   9]

julia> block_diagonal_matrix([M, N])
[1   2   0   0   0]
[3   4   0   0   0]
[0   0   4   5   6]
[0   0   7   8   9]

Similar and zero

Both similar and zero construct new matrices, but the entries are either undefined with similar or zero-initialized with zero.

similar(x::MatElem, R::Ring=base_ring(x))
zero(x::MatElem, R::Ring=base_ring(x))

Construct the matrix with the same dimensions as the given matrix, and the same base ring unless explicitly specified.

similar(x::MatElem, R::Ring, r::Int, c::Int)
similar(x::MatElem, r::Int, c::Int)
zero(x::MatElem, R::Ring, r::Int, c::Int)
zero(x::MatElem, r::Int, c::Int)

Construct the r×cr\times c matrix with R as base ring (which defaults to the base ring of the the given matrix). If xx belongs to a matrix algebra and rcr \neq c, an exception is raised, and it's also possible to specify only one Int as the order (e.g. similar(x, n)).

Base.isassigned(M::MatElem, i, j)

Test whether the given matrix has a value associated with indices i and j.

Examples

julia> M = matrix(ZZ, BigInt[3 1 2; 2 0 1])
[3   1   2]
[2   0   1]

julia> isassigned(M, 1, 2)
true

julia> isassigned(M, 4, 4)
false

julia> A = similar(M)
[#undef   #undef   #undef]
[#undef   #undef   #undef]

julia> isassigned(A, 1, 2)
false

julia> B = zero(M)
[0   0   0]
[0   0   0]

julia> C = similar(M, 4, 5)
[#undef   #undef   #undef   #undef   #undef]
[#undef   #undef   #undef   #undef   #undef]
[#undef   #undef   #undef   #undef   #undef]
[#undef   #undef   #undef   #undef   #undef]

julia> base_ring(B)
Integers

julia> D = zero(M, QQ, 2, 2)
[0//1   0//1]
[0//1   0//1]

julia> base_ring(D)
Rationals

LU factorisation

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

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

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

Return a tuple r,d,p,L,Ur, d, p, L, U consisting of the rank of AA, a denominator dd, a permutation pp of AA belonging to PP, a lower triangular matrix LL and an upper triangular matrix UU such that p(A)=LDUp(A) = LDU, where p(A)p(A) stands for the matrix whose rows are the given permutation pp of the rows of AA and such that DD is the diagonal matrix diag(p1,p1p2,,pn2pn1,pn1pn)(p_1, p_1p_2, \ldots, p_{n-2}p_{n-1}, p_{n-1}p_n) where the pip_i are the inverses of the diagonal entries of LL. The denominator dd is set to ±det(S)\pm \mathrm{det}(S) where SS is an appropriate submatrix of AA (S=AS = A if AA is square and nonsingular) and the sign is decided by the parity of the permutation.

source

Examples

julia> M = matrix(QQ, 3, 3, [1 2 3;4 5 6;0 0 1])
[1//1   2//1   3//1]
[4//1   5//1   6//1]
[0//1   0//1   1//1]

julia> r, P, L, U = lu(M)
(3, (), [1 0 0; 4 1 0; 0 0 1], [1 2 3; 0 -3 -6; 0 0 1])

julia> r, d, P, L, U = fflu(M)
(3, -3//1, (), [1 0 0; 4 -3 0; 0 0 -3], [1 2 3; 0 -3 -6; 0 0 -3])

Reduced row-echelon form

rref_rationalMethod
rref_rational(M::MatrixElem{T}) where {T <: RingElement}

Return a tuple (r,A,d)(r, A, d) consisting of the rank rr of MM and a denominator dd in the base ring of MM and a matrix AA such that A/dA/d is the reduced row echelon form of MM. Note that the denominator is not usually minimal.

source
rrefMethod
rref(M::MatrixElem{T}) where {T <: FieldElement}

Return a tuple (r,A)(r, A) consisting of the rank rr of MM and a reduced row echelon form AA of MM.

source
is_rrefMethod
is_rref(M::MatrixElem{T}) where {T <: RingElement}

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

source
is_rrefMethod
is_rref(M::MatrixElem{T}) where {T <: RingElement}

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

source
is_rref(M::MatrixElem{T}) where {T <: FieldElement}

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

source

Examples

julia> M = matrix(QQ, 3, 3, [1 2 3;4 5 6;0 0 1])
[1//1   2//1   3//1]
[4//1   5//1   6//1]
[0//1   0//1   1//1]

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

julia> N = matrix(ZZ, 3, 3, [1 2 3;4 5 6;0 0 1])
[1   2   3]
[4   5   6]
[0   0   1]

julia> r2, B = rref_rational(N)
(3, [-3 0 0; 0 -3 0; 0 0 -3], -3)

julia> is_rref(A)
true

julia> is_rref(B)
true

Other functionality

Symmetry testing

is_symmetricMethod
is_symmetric(M::MatrixElem)

Return true if the given matrix is symmetric with respect to its main diagonal, i.e., transpose(M) == M, otherwise return false.

Alias for LinearAlgebra.issymmetric.

Examples

julia> M = matrix(ZZ, [1 2 3; 2 4 5; 3 5 6])
[1   2   3]
[2   4   5]
[3   5   6]

julia> is_symmetric(M)
true

julia> N = matrix(ZZ, [1 2 3; 4 5 6; 7 8 9])
[1   2   3]
[4   5   6]
[7   8   9]

julia> is_symmetric(N)
false
source
is_skew_symmetricMethod
is_skew_symmetric(M::MatrixElem)

Return true if the given matrix is skew symmetric with respect to its main diagonal, i.e., transpose(M) == -M, otherwise return false.

Examples

julia> M = matrix(ZZ, [0 -1 -2; 1 0 -3; 2 3 0])
[0   -1   -2]
[1    0   -3]
[2    3    0]

julia> is_skew_symmetric(M)
true
source

Powering

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

Return an array MM of "powers" of a where M[i+1]=aiM[i + 1] = a^i for i=0..di = 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 Vector{AbstractAlgebra.Generic.MatSpaceElem{BigInt}}:
 [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]
source

Gram matrix

gramMethod
gram(x::MatElem)

Return the Gram matrix of xx, i.e. if xx is an r×cr\times c matrix return the r×rr\times r matrix whose entries i,ji, j are the dot products of the ii-th and jj-th rows, respectively.

Examples

julia> R, t = polynomial_ring(QQ, :t)
(Univariate polynomial ring in t over rationals, t)

julia> S = matrix_space(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]
source

Content

contentMethod
content(x::MatrixElem{T}) where T <: RingElement

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

Examples

julia> R, t = polynomial_ring(QQ, :t)
(Univariate polynomial ring in t over rationals, t)

julia> S = matrix_space(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
source

Permutation

*Method
*(P::Perm, x::MatrixElem{T}) where T <: NCRingElement

Apply the pemutation PP to the rows of the matrix xx and return the result.

Examples

julia> R, t = polynomial_ring(QQ, :t)
(Univariate polynomial ring in t over rationals, t)

julia> S = matrix_space(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]
source

Nilpotency

is_nilpotentMethod
is_nilpotent(A::MatrixElem{T}) where {T <: RingElement}

Return if A is nilpotent, i.e. if there exists a natural number kk such that Ak=0A^k = 0. If A is not square an exception is raised.

source

Minors

minorsMethod
minors(A::MatElem, k::Int)

Return an array consisting of the k-minors of A.

Examples

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

julia> minors(A, 2)
3-element Vector{BigInt}:
 -3
 -6
 -3
source

Exterior power

exterior_powerMethod
exterior_power(A::MatElem, k::Int) -> MatElem

Return the k-th exterior power of A.

Examples

julia> A = matrix(ZZ, 3, 3, [1, 2, 3, 4, 5, 6, 7, 8, 9]);

julia> exterior_power(A, 2)
[-3    -6   -3]
[-6   -12   -6]
[-3    -6   -3]
source

Pfaffian

pfaffianMethod
pfaffian(M::MatElem)

Return the Pfaffian of a skew-symmetric matrix M.

source
pfaffiansMethod
pfaffians(M::MatElem, k::Int)

Return a vector consisting of the k-Pfaffians of a skew-symmetric matrix M.

source

Examples

julia> R, x = polynomial_ring(QQ, ["x$i" for i in 1:6])
(Multivariate polynomial ring in 6 variables over rationals, AbstractAlgebra.Generic.MPoly{Rational{BigInt}}[x1, x2, x3, x4, x5, x6])

julia> M = R[0 x[1] x[2] x[3]; -x[1] 0 x[4] x[5]; -x[2] -x[4] 0 x[6]; -x[3] -x[5] -x[6] 0]
[  0    x1    x2   x3]
[-x1     0    x4   x5]
[-x2   -x4     0   x6]
[-x3   -x5   -x6    0]

julia> pfaffian(M)
x1*x6 - x2*x5 + x3*x4

julia> pfaffians(M, 2)
6-element Vector{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}}:
 x1
 x2
 x4
 x3
 x5
 x6
 

Nullspace

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

Return a tuple (ν,N)(\nu, N) consisting of the nullity ν\nu of MM and a basis NN (consisting of column vectors) for the right nullspace of MM, i.e. such that MNMN is the zero matrix. If MM is an m×nm\times n matrix NN will be an n×ν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.

Examples

julia> R, x = polynomial_ring(ZZ, :x)
(Univariate polynomial ring in x over integers, x)

julia> S = matrix_space(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])
source
nullspace(M::MatElem{T}) where {T <: FieldElement}

Return a tuple (ν,N)(\nu, N) consisting of the nullity ν\nu of MM and a basis NN (consisting of column vectors) for the right nullspace of MM, i.e. such that MNMN is the zero matrix. If MM is an m×nm\times n matrix NN will be an n×νn\times \nu matrix.

source

Hessenberg form

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

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

source
is_hessenbergMethod
is_hessenberg(A::MatrixElem{T}) where {T <: RingElement}

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

source

Examples

julia> R, = residue_ring(ZZ, 7);

julia> M = matrix(R, 4, 4, [1 2 4 3; 2 5 1 0;6 1 3 2; 1 1 3 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> is_hessenberg(A)
true

Characteristic polynomial

charpolyMethod
charpoly(Y::MatrixElem{T}) where {T <: RingElement}
charpoly(S::PolyRing{T}, Y::MatrixElem{T}) where {T <: RingElement}

Return the characteristic polynomial pp of the square matrix YY. If a polynomial ring SS over the same base ring as YY is supplied, the resulting polynomial is an element of it.

Examples

julia> R, = residue_ring(ZZ, 7);

julia> S = matrix_space(R, 4, 4)
Matrix space of 4 rows and 4 columns
  over residue ring of integers modulo 7

julia> T, y = polynomial_ring(R, :y)
(Univariate polynomial ring in y over R, y)

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)
y^4 + 2*y^2 + 6*y + 2

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

Minimal polynomial

minpolyMethod
minpoly(M::MatElem{T}) where {T <: RingElement}
minpoly(S::PolyRing{T}, M::MatElem{T}) where {T <: RingElement}

Return the minimal polynomial pp of the square matrix MM. If a polynomial ring SS over the same base ring as YY is supplied, the resulting polynomial is an element of it.

Examples

julia> R = GF(13)
Finite field F_13

julia> S, y = polynomial_ring(R, :y)
(Univariate polynomial ring in y over R, 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(S, M)
y^2 + 10*y

julia> A = minpoly(M)
x^2 + 10*x
source

Transforms

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

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

Examples

julia> R, = residue_ring(ZZ, 7);

julia> S = matrix_space(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))
source

Hermite normal form

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

Return the upper right row Hermite normal form of AA.

source
hnf_with_transformMethod
hnf_with_transform(A)

Return the tuple H,UH, U consisting of the upper right row Hermite normal form HH of AA together with invertible matrix UU such that UA=HUA = H.

source
is_hnfMethod
is_hnf(M::MatrixElem{T}) where T <: RingElement

Return true if the matrix is in Hermite normal form.

source

Examples

julia> A = matrix(ZZ, [2 3 -1; 3 5 7; 11 1 12])
[ 2   3   -1]
[ 3   5    7]
[11   1   12]

julia> H = hnf(A)
[1   0   255]
[0   1    17]
[0   0   281]

julia> is_hnf(H)
true

julia> H, U = hnf_with_transform(A)
([1 0 255; 0 1 17; 0 0 281], [-47 28 1; -3 2 0; -52 31 1])

julia> U*A
[1   0   255]
[0   1    17]
[0   0   281]

Smith normal form

is_snfMethod
is_snf(A::MatrixElem{T}) where T <: RingElement

Return true if AA is in Smith Normal Form.

source
snfMethod
snf(A::MatrixElem{T}) where {T <: RingElement}

Return the Smith normal form of AA.

source
snf_with_transformMethod
snf_with_transform(A)

Return the tuple S,T,US, T, U consisting of the Smith normal form SS of AA together with invertible matrices TT and UU such that TAU=STAU = S.

source

Examples

julia> A = matrix(ZZ, [2 3 -1; 3 5 7; 11 1 12])
[ 2   3   -1]
[ 3   5    7]
[11   1   12]

julia> S = snf(A)
[1   0     0]
[0   1     0]
[0   0   281]

julia> S, T, U = snf_with_transform(A)
([1 0 0; 0 1 0; 0 0 281], [1 0 0; 7 1 0; 229 31 1], [0 -3 26; 0 2 -17; -1 0 1])

julia> T*A*U
[1   0     0]
[0   1     0]
[0   0   281]

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

is_weak_popovMethod
is_weak_popov(P::MatrixElem{T}, rank::Int) where T <: PolyRingElem

Return true if PP is a matrix in weak Popov form of the given rank.

source
weak_popovMethod
weak_popov(A::MatElem{T}) where {T <: PolyRingElem}

Return the weak Popov form of AA.

source
weak_popov_with_transformMethod
weak_popov_with_transform(A::MatElem{T}) where {T <: PolyRingElem}

Compute a tuple (P,U)(P, U) where PP is the weak Popov form of AA and UU is a transformation matrix so that P=UAP = UA.

source
popovMethod
popov(A::MatElem{T}) where {T <: PolyRingElem}

Return the Popov form of AA.

source
popov_with_transformMethod
popov_with_transform(A::MatElem{T}) where {T <: PolyRingElem}

Compute a tuple (P,U)(P, U) where PP is the Popov form of AA and UU is a transformation matrix so that P=UAP = UA.

source

Examples

julia> R, x = polynomial_ring(QQ, :x);

julia> A = matrix(R, map(R, Any[1 2 3 x; x 2*x 3*x x^2; x x^2+1 x^3+x^2 x^4+x^2+1]))
[1         2           3               x]
[x       2*x         3*x             x^2]
[x   x^2 + 1   x^3 + x^2   x^4 + x^2 + 1]

julia> P = weak_popov(A)
[   1                        2                    3   x]
[   0                        0                    0   0]
[-x^3   -2*x^3 + x^2 - 2*x + 1   -2*x^3 + x^2 - 3*x   1]

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

julia> U*A
[   1                        2                    3   x]
[   0                        0                    0   0]
[-x^3   -2*x^3 + x^2 - 2*x + 1   -2*x^3 + x^2 - 3*x   1]