# 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/MatrixAlgebra.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 algebras of $m\times m$ matrices are implemented in src/generic/MatrixAlgebra.jl.

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 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 matrix space parent types belong to MatSpace{T}. Similarly the generic matrix algebra matrix types belong to the abstract type MatAlgElem{T} and the parent types belong to 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.

## 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]

## 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::MatAlgebra{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 = MatrixSpace(QQ, 2, 3)
Matrix Space of 2 rows and 3 columns over Rationals

julia> T = MatrixAlgebra(QQ, 2)
Matrix Algebra 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 = 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]

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 = MatrixAlgebra(ZZ, 2)
Matrix Algebra 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.

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.

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.

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 and iteration

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:

MatrixMethod
Matrix(A::MatrixElem{T}) where T <: RingElement

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 Matrix{BigInt}:
1  2  3
4  5  6
ArrayMethod
Array(A::MatrixElem{T}) where T <: RingElement

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 = MatrixSpace(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

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

dense_matrix_typeMethod
dense_matrix_type(R::Ring)

Return the type of matrices over the given ring.

nrowsMethod
nrows(a::MatSpace)

Return the number of rows of the given matrix space.

ncolsMethod
ncols(a::MatSpace)

Return the number of columns of the given matrix space.

nrowsMethod
nrows(a::MatrixElem{T}) where T <: NCRingElement

Return the number of rows of the given matrix.

ncolsMethod
ncols(a::MatrixElem{T}) where T <: NCRingElement

Return the number of columns of the given matrix.

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

Return the number of entries in the given matrix.

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.

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

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

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

diagonal_matrixMethod
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]
zeroMethod
zero(a::MatSpace)

Return the zero matrix in the given matrix space.

zeroMethod
zero(x::MatrixElem{T}, R::NCRing, r::Int, c::Int) where T <: NCRingElement
zero(x::MatrixElem{T}, R::NCRing=base_ring(x)) where T <: NCRingElement
zero(x::MatrixElem{T}, r::Int, c::Int) where T <: NCRingElement

Return a zero matrix similar to the given matrix, with optionally different base ring or dimensions.

oneMethod
one(a::MatSpace)

Return the identity matrix of given matrix space. The matrix space must contain square matrices or else an error is thrown.

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

lower_triangular_matrixMethod
lower_triangular_matrix(L::AbstractVector{T}) where {T <: RingElement}

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]
upper_triangular_matrixMethod
upper_triangular_matrix(L::AbstractVector{T}) where {T <: RingElement}

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]
strictly_lower_triangular_matrixMethod
strictly_lower_triangular_matrix(L::AbstractVector{T}) where {T <: RingElement}

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]
strictly_upper_triangular_matrixMethod
strictly_upper_triangular_matrix(L::AbstractVector{T}) where {T <: RingElement}

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]
is_upper_triangularMethod
is_upper_triangular(A::MatrixElem{T}) where T <: RingElement

Return true if $A$ is an upper triangular matrix.

Alias for LinearAlgebra.istriu.

change_base_ringMethod
change_base_ring(R::NCRing, M::MatrixElem{T}) where T <: NCRingElement

Return the matrix obtained by coercing each entry into R.

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

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

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]

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

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

Return the transpose of the given matrix.

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 = 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

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

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

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

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

multiply_columnMethod
multiply_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.

multiply_column!Method
multiply_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.

multiply_rowMethod
multiply_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.

multiply_row!Method
multiply_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]

[ 7   2   3]
[10   3   4]
[14   5   5]

[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 <: RingElement

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]
swap_rows!Method
swap_rows!(a::MatrixElem{T}, i::Int, j::Int) where T <: RingElement

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]
swap_colsMethod
swap_cols(a::MatrixElem{T}, i::Int, j::Int) where T <: RingElement

Return a matrix $b$ with the entries of $a$, where the $i$th and $j$th row are swapped.

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

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

is_symmetricMethod
is_symmetric(a::MatrixElem{T}) where T <: RingElement

Return true if the given matrix is symmetric with respect to its main diagonal, i.e., tr(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
is_skew_symmetricMethod
is_skew_symmetric(M::MatElem)

Return true if the given matrix is skew symmetric with respect to its main diagonal, i.e., tr(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

powersMethod
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 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

gramMethod
gram(x::MatElem)

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

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

trMethod
tr(x::AbsAlgAssElem{T}) where T -> T

Returns the trace of $x$.

tr(x::MatrixElem{T}) where T <: RingElement

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

contentMethod
content(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 = 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

*Method
*(P::perm, x::MatrixElem{T}) where T <: RingElement

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

luMethod
lu(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$.

ffluMethod
fflu(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 = 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

rref_rationalMethod
rref_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.

rrefMethod
rref(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$.

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

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

is_rrefMethod
is_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 = 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> is_rref(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, 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

detMethod
det(M::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

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

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

### 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

### Pfaffian

pfaffianMethod
pfaffian(M::MatElem)

Return the Pfaffian of a skew-symmetric matrix M.

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

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

Examples

julia> R, x = PolynomialRing(QQ, ["x$i" for i in 1:6]) (Multivariate Polynomial Ring in 6 variables x1, x2, x3, x4, ..., x6 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 solveMethod solve(a::MatElem{S}, b::MatElem{S}) where {S <: RingElement} Given an$m\times r$matrix$a$over a ring and an$m\times n$matrix$b$over the same ring, return an$r\times n$matrix$x$such that$ax = b$. If no such matrix exists, an exception is raised. See also solve_left. solve_rationalMethod solve_rational(M::MatElem{T}, b::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. can_solve_with_solutionMethod can_solve_with_solution(a::MatElem{S}, b::MatElem{S}; side::Symbol = :right) where S <: RingElement Given two matrices$a$and$b$over the same ring, try to solve$ax = b$if side is :right or$xa = b$if side is :left. In either case, return a tuple (flag, x). If a solution exists, flag is set to true and x is a solution. If no solution exists, flag is set to false and x is arbitrary. If the dimensions of$a$and$b$are incompatible, an exception is raised. can_solveMethod can_solve(a::MatElem{S}, b::MatElem{S}; side::Symbol = :right) where S <: RingElement Given two matrices$a$and$b$over the same ring, check the solubility of$ax = b$if side is :right or$xa = b$if side is :left. Return true if a solution exists, false otherwise. If the dimensions of$a$and$b$are incompatible, an exception is raised. If a solution should be computed as well, use can_solve_with_solution instead. solve_leftMethod solve_left(a::MatElem{S}, b::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. See also solve. solve_triuMethod solve_triu(U::MatElem{T}, b::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. can_solve_left_reduced_triuMethod can_solve_left_reduced_triu(r::MatElem{T}, M::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 = matrix(ZZ, 2, 2, [1, 2, 0, 2]) [1 2] [0 2] julia> b = matrix(ZZ, 2, 1, [2, 1]) [2] [1] julia> can_solve(A, b, side = :right) false julia> A = matrix(QQ, 2, 2, [3, 4, 5, 6]) [3//1 4//1] [5//1 6//1] julia> b = matrix(QQ, 1, 2, [2, 1]) [2//1 1//1] julia> can_solve_with_solution(A, b; side = :left) (true, [-7//2 5//2]) 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(transpose([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 invMethod inv(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. is_invertible_with_inverseMethod is_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 the right inverse of$A$i.e.$AB$is the$n\times n$unit matrix. If side is :left and flag is true,$B$is the left inverse of$A$i.e.$BA$is the$m\times m$unit matrix. If flag is false, no right or left inverse exists. 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. 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> 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 = 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 nullspaceMethod nullspace(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 = 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]) 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. ### Kernel kernelMethod 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. left_kernelMethod left_kernel(a::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). right_kernelMethod right_kernel(a::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 hessenbergMethod hessenberg(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. is_hessenbergMethod is_hessenberg(A::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> is_hessenberg(A) true ### Characteristic polynomial charpolyMethod charpoly(V::Ring, Y::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 minpolyMethod 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 similarity!Method similarity!(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 = 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)) ### Hermite normal form hnfMethod hnf(A::MatrixElem{T}) where {T <: RingElement} Return the upper right row Hermite normal form of$A$. hnf_with_transformMethod 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$. is_hnfMethod is_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 is_snfMethod is_snf(A::MatrixElem{T}) where T <: RingElement Return true if$A$is in Smith Normal Form. snfMethod snf(A::MatrixElem{T}) where {T <: RingElement} Return the Smith normal form of$A$. snf_with_transformMethod snf_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. is_weak_popovMethod is_weak_popov(P::MatrixElem{T}, rank::Int) where T <: PolyElem Return true if$P$is a matrix in weak Popov form of the given rank. weak_popovMethod weak_popov(A::MatElem{T}) where {T <: PolyElem} Return the weak Popov form of$A$. weak_popov_with_transformMethod weak_popov_with_transform(A::MatElem{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$. popovMethod popov(A::MatElem{T}) where {T <: PolyElem} Return the Popov form of$A$. popov_with_transformMethod popov_with_transform(A::MatElem{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\$.

Examples

julia> R, x = PolynomialRing(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]