# Matrix Interface

Generic matrices are supported in AbstractAlgebra.jl. Both the space of $m\times n$ matrices and the algebra (ring) of $m\times m$ matrices are supported.

As the space of $m\times n$ matrices over a commutative ring is not itself a commutative ring, not all of the Ring interface needs to be implemented for such matrices in.

In particular, the following functions do not need to be implemented: `isdomain_type`

, `needs_parentheses`

, `displayed_with_minus_in_front`

, `show_minus_one`

and `divexact`

. The `canonical_unit`

function should be implemented, but simply needs to return the corresponding value for entry $[1, 1]$ (the function is never called on empty matrices).

For matrix algebras, all of the ring interface must be implemented.

Note that AbstractAlgebra.jl matrices are not the same as Julia matrices. We store a base ring in our matrix and matrices are row major instead of column major in order to support the numerous large C libraries that use this convention.

All AbstractAlgebra.jl matrices are assumed to be mutable. This is usually critical to performance.

## Types and parents

AbstractAlgebra provides two abstract types for matrix spaces and their elements:

`MatSpace{T}`

is the abstract type for matrix space parent types`MatElem{T}`

is the abstract type for matrix types belonging to a matrix space

It also provides two abstract types for matrix algebras and their elements:

`MatAlgebra{T}`

is the abstract type for matrix algebra parent types`MatAlgElem{T}`

is the abstract type for matrix types belonging to a matrix algebra

Note that these abstract types are parameterised. The type `T`

should usually be the type of elements of the matrices.

Matrix spaces and matrix algebras should be made unique on the system by caching parent objects (unless an optional `cache`

parameter is set to `false`

). Matrix spaces and algebras should at least be distinguished based on their base (coefficient) ring and the dimensions of the matrices in the space.

See `src/generic/GenericTypes.jl`

for an example of how to implement such a cache (which usually makes use of a dictionary).

## Required functionality for matrices

In addition to the required (relevant) functionality for the Ring interface (see above), the following functionality is required for the Matrix interface.

We suppose that `R`

is a fictitious base ring (coefficient ring) and that `S`

is a space of $m\times n$ matrices over `R`

, or algebra of $m\times m$ matrices with parent object `S`

of type `MyMatSpace{T}`

or `MyMatAlgebra{T}`

, respectively. We also assume the matrices in the space have type `MyMat{T}`

, where `T`

is the type of elements of the base (element) ring.

Of course, in practice these types may not be parameterised, but we use parameterised types here to make the interface clearer.

Note that the type `T`

must (transitively) belong to the abstract type `RingElem`

.

Currently only matrices over commutative rings are supported.

### Constructors

In addition to the standard constructors, the following constructors, taking an array of elements, must be available.

```
(S::MyMatSpace{T})(A::Array{T, 2}) where T <: AbstractAlgebra.RingElem
(S::MyMatAlgebra{T})(A::Array{T, 2}) where T <: AbstractAlgebra.RingElem
```

Create the matrix in the given space/algebra whose $(i, j)$ entry is given by `A[i, j]`

.

```
(S::MyMatSpace{T})(A::Array{S, 2}) where {S <: AbstractAlgebra.RingElem, T <: AbstractAlgebra.RingElem}
(S::MyMatAlgebra{T})(A::Array{S, 2}) where {S <: AbstractAlgebra.RingElem, T <: AbstractAlgebra.RingElem}
```

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::Array{S, 1}) where {S <: AbstractAlgebra.RingElem, T <: AbstractAlgebra.RingElem}
(S::MyMatAlgebra{T})(A::Array{S, 1}) where {S <: AbstractAlgebra.RingElem, T <: AbstractAlgebra.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.

**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]
```

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). Note that to support this, matrix space parent objects don't contain a reference to their parent. Instead, parents are constructed on-the-fly if requested. (The same strategy is used for matrix algebras.)

`matrix(R::Ring, arr::Array{T, 2}) where T <: AbstractAlgebra.RingElem`

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::Array{T, 1}) where T <: AbstractAlgebra.RingElem`

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

### Views

Just as Julia supports views of matrices, AbstractAlgebra requires all matrix types to support views. These allow one to work with a submatrix of a given matrix. Modifying the submatrix also modifies the original matrix.

Note that `deepcopy`

of a view type must return the same type, but it should return a view into a `deepcopy`

of the original matrix. Julia enforces this for consistency.

To support views, generic matrices in AbstractAlgebra of type `Generic.MatSpaceElem`

have an associated `Generic.MatSpaceView`

type. Both belong to the `Generic.Mat`

abstract type, so that one can work with that in functions that can accept both views and actual matrices.

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

Note that the `parent_type`

function returns the same type for a view as for the original matrix type. This could potentially cause a problem if the `elem_type`

function is applied to the return value of `parent_type`

and then used in a type assertion. For this reason, there may be some limitations on the use of views.

The `similar`

function also returns a matrix of type `MatSpaceElem`

when applied to a view, rather than another view.

```
M = matrix(ZZ, 3, 3, BigInt[1, 2, 3, 2, 3, 4, 3, 4, 5])
N1 = @view M[1:2, :]
N2 = @view M[:, 1:2]
R = N1*N2
```

### Basic manipulation of matrices

`dense_matrix_type(::Type{T}) where T <: AbstractAlgebra.RingElem`

Return the type of dense matrices whose entries have the given type. E.g. in Nemo, which depends on AbstractAlgebra, we define `dense_matrix_type(::Type{fmpz}) = fmpz_mat`

.

`nrows(f::MyMat{T}) where T <: AbstractAlgebra.RingElem`

Return the number of rows of the given matrix.

`ncols(f::MyMat{T}) where T <: AbstractAlgebra.RingElem`

Return the number of columns of the given matrix.

`getindex(M::MyMat{T}, r::Int, c::Int) where T <: AbstractAlgebra.RingElem`

Return the $(i, j)$-th entry of the matrix $M$.

`setindex!(M::MyMat{T}, d::T, r::Int, c::Int) where T <: AbstractAlgebra.RingElem`

Set the $(i, j)$-th entry of the matrix $M$ to $d$, which is assumed to be in the base ring of the matrix. The matrix must have such an entry and the matrix is mutated in place and not returned from the function.

**Examples**

```
julia> M = matrix(ZZ, BigInt[2 3 0; 1 1 1])
[2 3 0]
[1 1 1]
julia> m = nrows(M)
2
julia> n = ncols(M)
3
julia> M[1, 2] = BigInt(4)
4
julia> c = M[1, 1]
2
```

### Transpose

`transpose(::MyMat{T}) where T <: AbstractAlgebra.RingElem`

Return the transpose of the given matrix.

The standard Julia tick notation can also be used for transposing a 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//1 t 1//1]
[ t^2 t t]
[ -2//1 t+2//1 t^2+t+1//1]
julia> B = transpose(A)
[t+1//1 t^2 -2//1]
[ t t t+2//1]
[ 1//1 t t^2+t+1//1]
julia> C = A'
[t+1//1 t^2 -2//1]
[ t t t+2//1]
[ 1//1 t t^2+t+1//1]
```

## Optional functionality for matrices

Especially when wrapping C libraries, some functions are best implemented directly, rather than relying on the generic functionality. The following are all provided by the AbstractAlgebra.jl generic code, but can optionally be implemented directly for performance reasons.

### Optional submatrices

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

`Base.getindex(M::MyMat, rows::AbstractVector{Int}, cols::AbstractVector{Int})`

Return a new matrix with the same entries as the submatrix with the given range of rows and columns.

**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]
```

### Optional row swapping

`swap_rows!(M::MyMat{T}, i::Int, j::Int) where T <: AbstractAlgebra.RingElem`

Swap the rows of `M`

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

### Optional concatenation

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

`hcat(M::MyMat{T}, N::MyMat{T}) where T <: AbstractAlgebra.RingElem`

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::MyMat{T}, N::MyMat{T}) where T <: AbstractAlgebra.RingElem`

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

### Optional similar and zero

The following functions are available for matrices in both matrix algebras and matrix spaces. Both `similar`

and `zero`

construct new matrices, with the same methods, but the entries are either undefined with `similar`

or zero-initialized with `zero`

.

```
similar(x::MyMat{T}, R::Ring=base_ring(x)) where T <: AbstractAlgebra.RingElem
zero(x::MyMat{T}, R::Ring=base_ring(x)) where T <: AbstractAlgebra.RingElem
```

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

```
similar(x::MyMat{T}, R::Ring, r::Int, c::Int) where T <: AbstractAlgebra.RingElem
similar(x::MyMat{T}, r::Int, c::Int) where T <: AbstractAlgebra.RingElem
zero(x::MyMat{T}, R::Ring, r::Int, c::Int) where T <: AbstractAlgebra.RingElem
zero(x::MyMat{T}, r::Int, c::Int) where T <: AbstractAlgebra.RingElem
```

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

).

Custom matrices and rings may choose which specific matrix type is best-suited to return for the given ring and dimensionality. If they do not specialize these functions, the default is a `Generic.MatSpaceElem`

matrix, or `Generic.MatAlgElem`

for matrix algebras. The default implementation of `zero`

calls out to `similar`

, so it's generally sufficient to specialize only `similar`

. For both `similar`

and `zero`

, only the most general method has to be implemented (e.g. `similar(x::MyMat, R::Ring, r::Int, c::Int)`

, as all other methods (which have defaults) call out to this more general method.

`Base.isassigned(M::MyMat, i, j)`

Test whether the given matrix has a value associated with indices `i`

and `j`

. It is recommended to overload this method for custom matrices.

**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
```