Matrix functionality
AbstractAlgebra.jl provides a module, implemented in src/Matrix.jl
for matrices over any ring belonging to the AbstractAlgebra abstract type hierarchy. This functionality will work for any matrix type which follows the Matrix interface.
Similarly, AbstractAlgebra.jl provides a module in src/MatRing.jl
for matrix algebras over a ring.
Generic matrix types
AbstractAlgebra.jl allows the creation of dense matrices over any computable ring $R$. Generic matrices over a ring are implemented in src/generic/Matrix.jl
.
Generic matrix rings of $m\times m$ matrices are implemented in src/generic/MatRing.jl
.
Generic matrices in AbstractAlgebra.jl have type Generic.MatSpaceElem{T}
for matrices in a matrix space, or Generic.MatRingElem{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 MatSpace{T}
. Parents of matrices in a matrix algebra have type Generic.MatRing{T}
.
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.
Abstract types
The generic matrix types (matrix spaces) belong to the abstract type MatElem{T}
and the all matrix space parents are of the concrete type MatSpace{T}
. On the other hand, the generic matrix algebra matrix types belong to the abstract type MatRingElem{T}
and the parent types belong to the abstract MatRing{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.
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.
matrix_space(R::Ring, rows::Int, cols::Int)
Construct the space of matrices with the given number of rows and columns over the given base ring.
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 = 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()
[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]
Matrix element constructors
There are a few ways to construct matrices other than by coercing elements as shown above. The first method is from an array of elements.
This can be done with either two or one dimensional arrays.
(S::MatSpace{T})(A::Matrix{S}) where {S <: RingElement, T <: RingElement}
(S::MatRing{T})(A::Matrix{S}) where {S <: RingElement, T <: RingElement}
Create the matrix in the given space/algebra whose $(i, j)$ entry is given by A[i, j]
, where S
is the type of elements that can be coerced into the base ring of the matrix.
(S::MyMatSpace{T})(A::Vector{S}) where {S <: RingElem, T <: RingElem}
(S::MyMatAlgebra{T})(A::Vector{S}) where {S <: RingElem, T <: RingElem}
Create the matrix in the given space/algebra of matrices (with dimensions $m\times n$ say), whose $(i, j)$ entry is given by A[i*(n - 1) + j]
and where S
is the type of elements that can be coerced into the base ring of the matrix.
We also 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> S = matrix_space(QQ, 2, 3)
Matrix space of 2 rows and 3 columns
over rationals
julia> T = matrix_ring(QQ, 2)
Matrix ring of degree 2
over rationals
julia> M1 = S(Rational{BigInt}[2 3 1; 1 0 4])
[2//1 3//1 1//1]
[1//1 0//1 4//1]
julia> M2 = S(BigInt[2 3 1; 1 0 4])
[2//1 3//1 1//1]
[1//1 0//1 4//1]
julia> M3 = S(BigInt[2, 3, 1, 1, 0, 4])
[2//1 3//1 1//1]
[1//1 0//1 4//1]
julia> N1 = T(Rational{BigInt}[2 3; 1 0])
[2//1 3//1]
[1//1 0//1]
julia> N2 = T(BigInt[2 3; 1 0])
[2//1 3//1]
[1//1 0//1]
julia> N3 = T(BigInt[2, 3, 1, 1])
[2//1 3//1]
[1//1 1//1]
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> 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]
It is also possible to create matrices (in a matrix space only) directly, without first creating the corresponding matrix space (the inner constructor being called directly).
matrix(R::Ring, arr::Matrix{T}) where T <: RingElement
Given an $m\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\times c$ AbstractAlgebra.jl matrix over the ring R
whose $(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\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]
julia> R = matrix_ring(ZZ, 2)
Matrix ring of degree 2
over integers
julia> M = R()
[0 0]
[0 0]
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.
AbstractAlgebra.block_diagonal_matrix
— Methodblock_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.
AbstractAlgebra.block_diagonal_matrix
— Methodblock_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.
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]
Conversion to Julia matrices, iteration and broacasting
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
— MethodMatrix(A::MatrixElem{T}) where {T<:NCRingElement}
Matrix{U}(A::MatrixElem{T}) where {U<:NCRingElement, T<:NCRingElement}
Convert A
to a Julia Matrix{U}
of the same dimensions with the same elements. If U
is omitted then eltype(M)
is used in its place.
Examples
julia> A = ZZ[1 2 3; 4 5 6]
[1 2 3]
[4 5 6]
julia> Matrix(A)
2×3 Matrix{BigInt}:
1 2 3
4 5 6
julia> Matrix{Int}(A)
2×3 Matrix{Int64}:
1 2 3
4 5 6
Core.Array
— MethodArray(A::MatrixElem{T}) where T <: NCRingElement
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 Matrix{AbstractAlgebra.Generic.Poly{BigInt}}:
1 x
x^2 x^3
Matrices also support iteration, and therefore functions accepting an iterator can be called on them, e.g.:
julia> M = matrix_space(ZZ, 2, 3); x = M(1:6)
[1 2 3]
[4 5 6]
julia> collect(x)
2×3 Matrix{BigInt}:
1 2 3
4 5 6
julia> Set(x)
Set{BigInt} with 6 elements:
5
4
6
2
3
1
Matrices also support broadcasting, which amounts to elementwise application of functions to matrices:
julia> k = GF(5);
julia> A = ZZ[1 2; 3 4];
julia> k.(A)
[1 2]
[3 4]
julia> 3 .* A .+ 2
[ 5 8]
[11 14]
julia> B = ZZ[3 4; 5 6];
julia> ((x, y) -> x^2 + y^2).(A, B)
[10 20]
[34 52]
Views
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]
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
— Methoddense_matrix_type(::Type{T}) where T<:NCRingElement
dense_matrix_type(::T) where T<:NCRingElement
dense_matrix_type(::Type{S}) where S<:NCRing
dense_matrix_type(::S) where S<:NCRing
Return the type of matrices with coefficients of type T
respectively elem_type(S)
.
AbstractAlgebra.number_of_rows
— Methodnumber_of_rows(a::MatSpace)
Return the number of rows of the given matrix space.
AbstractAlgebra.number_of_columns
— Methodnumber_of_columns(a::MatSpace)
Return the number of columns of the given matrix space.
AbstractAlgebra.number_of_rows
— Methodnumber_of_rows(a::MatrixElem{T}) where T <: NCRingElement
Return the number of rows of the given matrix.
AbstractAlgebra.number_of_columns
— Methodnumber_of_columns(a::MatrixElem{T}) where T <: NCRingElement
Return the number of columns of the given matrix.
Base.length
— Methodlength(a::MatrixElem{T}) where T <: NCRingElement
Return the number of entries in the given matrix.
Base.isempty
— Methodisempty(a::MatrixElem{T}) where T <: NCRingElement
Return true
if a
does not contain any entry (i.e. length(a) == 0
), and false
otherwise.
AbstractAlgebra.identity_matrix
— Methodidentity_matrix(R::NCRing, n::Int)
Return the $n \times n$ identity matrix over $R$.
AbstractAlgebra.identity_matrix
— Methodidentity_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)
.
AbstractAlgebra.ones_matrix
— Methodones_matrix(R::Ring, r::Int, c::Int)
Return the $r \times c$ ones matrix over $R$.
AbstractAlgebra.scalar_matrix
— Methodscalar_matrix(R::NCRing, n::Int, a::NCRingElement)
scalar_matrix(n::Int, a::NCRingElement)
Return the $n \times n$ matrix over R
with a
along the main diagonal and zeroes elsewhere. If R
is not specified, it defaults to parent(a)
.
AbstractAlgebra.diagonal_matrix
— Methoddiagonal_matrix(x::NCRingElement, 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.zero
— Methodzero(a::MatSpace)
Return the zero matrix in the given matrix space.
Base.zero
— Methodzero(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
.
Base.one
— Methodone(a::MatSpace)
Return the identity matrix of given matrix space. The matrix space must contain square matrices or else an error is thrown.
Base.one
— Methodone(a::MatrixElem{T}) where T <: NCRingElement
Return the identity matrix in the same matrix space as $a$. If the space does not contain square matrices, an error is thrown.
AbstractAlgebra.lower_triangular_matrix
— Methodlower_triangular_matrix(L::AbstractVector{T}) where {T <: NCRingElement}
Return the $n$ by $n$ matrix whose entries on and below the main diagonal are the elements of L
, and which has zeroes elsewhere. The value of $n$ is determined by the condition that L
has length $n(n+1)/2$.
An exception is thrown if there is no integer $n$ with this property.
Examples
julia> lower_triangular_matrix([1, 2, 3])
[1 0]
[2 3]
AbstractAlgebra.upper_triangular_matrix
— Methodupper_triangular_matrix(L::AbstractVector{T}) where {T <: NCRingElement}
Return the $n$ by $n$ matrix whose entries on and above the main diagonal are the elements of L
, and which has zeroes elsewhere. The value of $n$ is determined by the condition that L
has length $n(n+1)/2$.
An exception is thrown if there is no integer $n$ with this property.
Examples
julia> upper_triangular_matrix([1, 2, 3])
[1 2]
[0 3]
AbstractAlgebra.strictly_lower_triangular_matrix
— Methodstrictly_lower_triangular_matrix(L::AbstractVector{T}) where {T <: NCRingElement}
Return the $n$ by $n$ matrix whose entries below the main diagonal are the elements of L
, and which has zeroes elsewhere. The value of $n$ is determined by the condition that L
has length $(n-1)n/2$.
An exception is thrown if there is no integer $n$ with this property.
Examples
julia> strictly_lower_triangular_matrix([1, 2, 3])
[0 0 0]
[1 0 0]
[2 3 0]
AbstractAlgebra.strictly_upper_triangular_matrix
— Methodstrictly_upper_triangular_matrix(L::AbstractVector{T}) where {T <: NCRingElement}
Return the $n$ by $n$ matrix whose entries above the main diagonal are the elements of L
, and which has zeroes elsewhere. The value of $n$ is determined by the condition that L
has length $(n-1)n/2$.
An exception is thrown if there is no integer $n$ with this property.
Examples
julia> strictly_upper_triangular_matrix([1, 2, 3])
[0 1 2]
[0 0 3]
[0 0 0]
AbstractAlgebra.is_lower_triangular
— Methodis_lower_triangular(A::MatrixElem)
Return true
if $A$ 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
AbstractAlgebra.is_upper_triangular
— Methodis_upper_triangular(A::MatrixElem)
Return true
if $A$ 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
AbstractAlgebra.is_diagonal
— Methodis_diagonal(A::MatrixElem)
Return true
if $A$ 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
AbstractAlgebra.change_base_ring
— Methodchange_base_ring(R::NCRing, M::MatrixElem{T}) where T <: NCRingElement
Return the matrix obtained by coercing each entry into R
.
Base.map
— Methodmap(f, a::MatrixElem{T}) where T <: NCRingElement
Transform matrix a
by applying f
on each element. This is equivalent to map_entries(f, a)
.
Base.map!
— Methodmap!(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)
.
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 = 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 = number_of_rows(B)
3
julia> c = number_of_columns(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]
julia> M = matrix(ZZ, BigInt[2 3 0; 1 1 1])
[2 3 0]
[1 1 1]
julia> M[1, 2] = BigInt(4)
4
julia> c = M[1, 1]
2
Transpose
Base.transpose
— Methodtranspose(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]
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]
Elementary row and column operations
AbstractAlgebra.add_column
— Methodadd_column(a::MatrixElem{T}, s::RingElement, i::Int, j::Int, rows = 1:nrows(a)) where T <: RingElement
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.add_column!
— Methodadd_column!(a::MatrixElem{T}, s::RingElement, i::Int, j::Int, rows = 1:nrows(a)) where T <: RingElement
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.add_row
— Methodadd_row(a::MatrixElem{T}, s::RingElement, i::Int, j::Int, cols = 1:ncols(a)) where T <: RingElement
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.add_row!
— Methodadd_row!(a::MatrixElem{T}, s::RingElement, i::Int, j::Int, cols = 1:ncols(a)) where T <: RingElement
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.multiply_column
— Methodmultiply_column(a::MatrixElem{T}, s::RingElement, i::Int, rows = 1:nrows(a)) where T <: RingElement
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.multiply_column!
— Methodmultiply_column!(a::MatrixElem{T}, s::RingElement, i::Int, rows = 1:nrows(a)) where T <: RingElement
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.multiply_row
— Methodmultiply_row(a::MatrixElem{T}, s::RingElement, i::Int, cols = 1:ncols(a)) where T <: RingElement
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.multiply_row!
— Methodmultiply_row!(a::MatrixElem{T}, s::RingElement, i::Int, cols = 1:ncols(a)) where T <: RingElement
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]
Swapping rows and columns
AbstractAlgebra.swap_rows
— Methodswap_rows(a::MatrixElem{T}, i::Int, j::Int) where T <: NCRingElement
Return a matrix $b$ with the entries of $a$, where the $i$th and $j$th 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]
AbstractAlgebra.swap_rows!
— Methodswap_rows!(a::MatrixElem{T}, i::Int, j::Int) where T <: NCRingElement
Swap the $i$th and $j$th row of $a$ 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]
AbstractAlgebra.swap_cols
— Methodswap_cols(a::MatrixElem{T}, i::Int, j::Int) where T <: NCRingElement
Return a matrix $b$ with the entries of $a$, where the $i$th and $j$th row are swapped.
AbstractAlgebra.swap_cols!
— Methodswap_cols!(a::MatrixElem{T}, i::Int, j::Int) where T <: NCRingElement
Swap the $i$th and $j$th column of $a$ in place. The function returns the mutated matrix (since matrices are assumed to be mutable in AbstractAlgebra.jl).
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 $M$ and $N$. It is assumed that the number of rows of $M$ and $N$ are the same.
vcat(M::T, N::T) where T <: MatElem
Return the vertical concatenation of $M$ and $N$. It is assumed that the number of columns of $M$ and $N$ 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]
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\times c$ matrix with R
as base ring (which defaults to the base ring of the the given matrix). If $x$ belongs to a matrix algebra and $r \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
Symmetry testing
AbstractAlgebra.is_symmetric
— Methodis_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
AbstractAlgebra.is_skew_symmetric
— Methodis_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
Powering
AbstractAlgebra.powers
— Methodpowers(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 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]
Gram matrix
AbstractAlgebra.gram
— Methodgram(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.
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]
Trace
LinearAlgebra.tr
— Methodtr(x::MatrixElem{T}) where T <: NCRingElement
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 = 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
Content
AbstractAlgebra.content
— Methodcontent(x::MatrixElem{T}) where T <: RingElement
Return the content of the matrix $a$, 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
Permutation
Base.:*
— Method*(P::Perm, x::MatrixElem{T}) where T <: NCRingElement
Apply the pemutation $P$ to the rows of the matrix $x$ 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]
LU factorisation
LinearAlgebra.lu
— Methodlu(A::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.fflu
— Methodfflu(A::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}p_n)$ where the $p_i$ are the inverses of the diagonal entries of $L$. The denominator $d$ is set to $\pm \mathrm{det}(S)$ where $S$ is an appropriate submatrix of $A$ ($S = A$ if $A$ is square and nonsingular) and the sign is decided by the parity of the permutation.
Examples
julia> R, x = polynomial_ring(QQ, :x)
(Univariate polynomial ring in x over rationals, x)
julia> K, = residue_field(R, x^3 + 3x + 1); a = K(x);
julia> S = matrix_space(K, 3, 3)
Matrix space of 3 rows and 3 columns
over residue field of R 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.rref_rational
— Methodrref_rational(M::MatrixElem{T}) where {T <: RingElement}
Return a tuple $(r, A, d)$ 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.rref
— Methodrref(M::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.is_rref
— Methodis_rref(M::MatrixElem{T}) where {T <: RingElement}
Return true
if $M$ is in reduced row echelon form, otherwise return false
.
AbstractAlgebra.is_rref
— Methodis_rref(M::MatrixElem{T}) where {T <: RingElement}
Return true
if $M$ is in reduced row echelon form, otherwise return false
.
is_rref(M::MatrixElem{T}) where {T <: FieldElement}
Return true
if $M$ is in reduced row echelon form, otherwise return false
.
Examples
julia> R, x = polynomial_ring(QQ, :x)
(Univariate polynomial ring in x over rationals, x)
julia> K, = residue_field(R, x^3 + 3x + 1); a = K(x);
julia> S = matrix_space(K, 3, 3)
Matrix space of 3 rows and 3 columns
over residue field of R 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> is_rref(A)
true
julia> R, x = polynomial_ring(ZZ, :x)
(Univariate polynomial ring in x over integers, x)
julia> S = matrix_space(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, A, d = rref_rational(M)
(3, [-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], -x^5 - 2*x^4 - 15*x^3 - 18*x^2 - 8*x - 7)
julia> is_rref(A)
true
Determinant
LinearAlgebra.det
— Methoddet(M::MatrixElem{T}) where {T <: RingElement}
Return the determinant of the matrix $M$. We assume $M$ 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
Rank
LinearAlgebra.rank
— Methodrank(M::MatrixElem{T}) where {T <: RingElement}
Return the rank of the matrix $M$.
Examples
julia> A = QQ[1 2; 3 4];
julia> d = rank(A)
2
Nilpotency
AbstractAlgebra.is_nilpotent
— Methodis_nilpotent(A::MatrixElem{T}) where {T <: RingElement}
Return if A
is nilpotent, i.e. if there exists a natural number $k$ such that $A^k = 0$. If A
is not square an exception is raised.
Minors
AbstractAlgebra.minors
— Methodminors(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
Exterior power
AbstractAlgebra.exterior_power
— Methodexterior_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]
Pfaffian
AbstractAlgebra.pfaffian
— Methodpfaffian(M::MatElem)
Return the Pfaffian of a skew-symmetric matrix M
.
AbstractAlgebra.pfaffians
— Methodpfaffians(M::MatElem, k::Int)
Return a vector consisting of the k
-Pfaffians of a skew-symmetric matrix M
.
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
Linear solving
Inverse
Base.inv
— Methodinv(M::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.
AbstractAlgebra.is_invertible_with_inverse
— Methodis_invertible_with_inverse(A::MatrixElem{T}; side::Symbol = :left) where {T <: RingElement}
Given an $n \times m$ matrix $A$ over a ring, return a tuple (flag, B)
. If side
is :right
and flag
is true
, $B$ is a right inverse of $A$ i.e. $A B$ is the $n \times n$ unit matrix. If side
is :left
and flag
is true
, $B$ is a left inverse of $A$ i.e. $B A$ is the $m \times m$ unit matrix. If flag
is false
, no right or left inverse exists.
To get the space of all inverses, note that if $B$ and $C$ are both right inverses, then $A (B - C) = 0$, and similar for left inverses. Hence from one inverse one can find all by making suitable use of kernel
.
AbstractAlgebra.is_invertible
— Methodis_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
.
Examples
julia> R, x = polynomial_ring(QQ, :x)
(Univariate polynomial ring in x over rationals, x)
julia> K, = residue_field(R, x^3 + 3x + 1); a = K(x);
julia> S = matrix_space(K, 3, 3)
Matrix space of 3 rows and 3 columns
over residue field of R 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> is_invertible(A)
true
julia> is_invertible_with_inverse(A)
(true, [-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 = polynomial_ring(ZZ, :x)
(Univariate polynomial ring in x over integers, x)
julia> S = matrix_space(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
— Methodnullspace(M::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.
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])
nullspace(M::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.
Hessenberg form
LinearAlgebra.hessenberg
— Methodhessenberg(A::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.is_hessenberg
— Methodis_hessenberg(A::MatrixElem{T}) where {T <: RingElement}
Return true
if $M$ is in Hessenberg form, otherwise returns false
.
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> 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
AbstractAlgebra.charpoly
— Methodcharpoly(Y::MatrixElem{T}) where {T <: RingElement}
charpoly(S::PolyRing{T}, Y::MatrixElem{T}) where {T <: RingElement}
Return the characteristic polynomial $p$ of the square matrix $Y$. If a polynomial ring $S$ over the same base ring as $Y$ 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
Minimal polynomial
AbstractAlgebra.minpoly
— Methodminpoly(M::MatElem{T}, charpoly_only::Bool = false) where {T <: RingElement}
minpoly(S::PolyRing{T}, M::MatElem{T}, charpoly_only::Bool = false) where {T <: RingElement}
Return the minimal polynomial $p$ of the square matrix $M$. If a polynomial ring $S$ over the same base ring as $Y$ 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
Transforms
AbstractAlgebra.similarity!
— Methodsimilarity!(A::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, = 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))
Hermite normal form
AbstractAlgebra.hnf
— Methodhnf(A::MatrixElem{T}) where {T <: RingElement}
Return the upper right row Hermite normal form of $A$.
AbstractAlgebra.hnf_with_transform
— Methodhnf_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.is_hnf
— Methodis_hnf(M::MatrixElem{T}) where T <: RingElement
Return true
if the matrix is in Hermite normal form.
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
AbstractAlgebra.is_snf
— Methodis_snf(A::MatrixElem{T}) where T <: RingElement
Return true
if $A$ is in Smith Normal Form.
AbstractAlgebra.snf
— Methodsnf(A::MatrixElem{T}) where {T <: RingElement}
Return the Smith normal form of $A$.
AbstractAlgebra.snf_with_transform
— Methodsnf_with_transform(A)
Return the tuple $S, T, U$ consisting of the Smith normal form $S$ of $A$ together with invertible matrices $T$ and $U$ such that $TAU = S$.
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.
AbstractAlgebra.is_weak_popov
— Methodis_weak_popov(P::MatrixElem{T}, rank::Int) where T <: PolyRingElem
Return true
if $P$ is a matrix in weak Popov form of the given rank.
AbstractAlgebra.weak_popov
— Methodweak_popov(A::MatElem{T}) where {T <: PolyRingElem}
Return the weak Popov form of $A$.
AbstractAlgebra.weak_popov_with_transform
— Methodweak_popov_with_transform(A::MatElem{T}) where {T <: PolyRingElem}
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.popov
— Methodpopov(A::MatElem{T}) where {T <: PolyRingElem}
Return the Popov form of $A$.
AbstractAlgebra.popov_with_transform
— Methodpopov_with_transform(A::MatElem{T}) where {T <: PolyRingElem}
Compute a tuple $(P, U)$ where $P$ is the Popov form of $A$ and $U$ is a transformation matrix so that $P = UA$.
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]