# Linear solving

## Overview of the functionality

The module `AbstractAlgebra.Solve`

provides the following four functions for solving linear systems:

`solve`

`can_solve`

`can_solve_with_solution`

`can_solve_with_solution_and_kernel`

All of these take the same set of arguments, namely:

- a matrix $A$ of type
`MatElem`

; - a vector or matrix $B$ of type
`Vector`

or`MatElem`

; - a keyword argument
`side`

which can be either`:left`

(default) or`:right`

.

If `side`

is `:left`

, the system $xA = B$ is solved, otherwise the system $Ax = B$ is solved.

The functionality of the functions can be summarized as follows.

`solve`

: return a solution, if it exists, otherwise throw an error.`can_solve`

: return`true`

, if a solution exists,`false`

otherwise.`can_solve_with_solution`

: return`true`

and a solution, if this exists, and`false`

and an empty vector or matrix otherwise.`can_solve_with_solution_and_kernel`

: like`can_solve_with_solution`

and additionally return a matrix whose rows (respectively columns) give a basis of the kernel of $A$.

## Solving with several right hand sides

Systems $xA = b_1,\dots, xA = b_k$ with the same matrix $A$, but several right hand sides $b_i$ can be solved more efficiently, by first initializing a "context object" `C`

.

`AbstractAlgebra.Solve.solve_init`

— Function`solve_init(A::MatElem)`

Return a context object `C`

that allows to efficiently solve linear systems $Ax = b$ or $xA = b$ for different $b$.

**Example**

```
julia> A = QQ[1 2 3; 0 3 0; 5 0 0];
julia> C = solve_init(A)
Linear solving context of matrix
[1//1 2//1 3//1]
[0//1 3//1 0//1]
[5//1 0//1 0//1]
julia> solve(C, [QQ(1), QQ(1), QQ(1)], side = :left)
3-element Vector{Rational{BigInt}}:
1//3
1//9
2//15
julia> solve(C, [QQ(1), QQ(1), QQ(1)], side = :right)
3-element Vector{Rational{BigInt}}:
1//5
1//3
2//45
```

Now the functions `solve`

, `can_solve`

, etc. can be used with `C`

in place of $A$. This way the time-consuming part of the solving (i.e. computing a reduced form of $A$) is only done once and the result cached in `C`

to be reused.

## Detailed documentation

`AbstractAlgebra.Solve.solve`

— Function```
solve(A::MatElem{T}, b::Vector{T}; side::Symbol = :left) where T
solve(A::MatElem{T}, b::MatElem{T}; side::Symbol = :left) where T
solve(C::SolveCtx{T}, b::Vector{T}; side::Symbol = :left) where T
solve(C::SolveCtx{T}, b::MatElem{T}; side::Symbol = :left) where T
```

Return $x$ of same type as $b$ solving the linear system $xA = b$, if `side == :left`

(default), or $Ax = b$, if `side == :right`

.

If no solution exists, an error is raised.

If a context object `C`

is supplied, then the above applies for `A = matrix(C)`

.

See also `can_solve_with_solution`

.

`AbstractAlgebra.Solve.can_solve`

— Function```
can_solve(A::MatElem{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve(A::MatElem{T}, b::MatElem{T}; side::Symbol = :left) where T
can_solve(C::SolveCtx{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve(C::SolveCtx{T}, b::MatElem{T}; side::Symbol = :left) where T
```

Return `true`

if the linear system $xA = b$ or $Ax = b$ with `side == :left`

(default) or `side == :right`

, respectively, has a solution and `false`

otherwise.

If a context object `C`

is supplied, then the above applies for `A = matrix(C)`

.

See also `can_solve_with_solution`

.

`AbstractAlgebra.Solve.can_solve_with_solution`

— Function```
can_solve_with_solution(A::MatElem{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve_with_solution(A::MatElem{T}, b::MatElem{T}; side::Symbol = :left) where T
can_solve_with_solution(C::SolveCtx{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve_with_solution(C::SolveCtx{T}, b::MatElem{T}; side::Symbol = :left) where T
```

Return `true`

and $x$ of same type as $b$ solving the linear system $xA = b$, if such a solution exists. Return `false`

and an empty vector or matrix, if the system has no solution.

If `side == :right`

, the system $Ax = b$ is solved.

If a context object `C`

is supplied, then the above applies for `A = matrix(C)`

.

See also `solve`

.

`AbstractAlgebra.Solve.can_solve_with_solution_and_kernel`

— Function```
can_solve_with_solution_and_kernel(A::MatElem{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve_with_solution_and_kernel(A::MatElem{T}, b::MatElem{T}; side::Symbol = :left) where T
can_solve_with_solution_and_kernel(C::SolveCtx{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve_with_solution_and_kernel(C::SolveCtx{T}, b::MatElem{T}; side::Symbol = :left) where T
```

Return `true`

, $x$ of same type as $b$ solving the linear system $xA = b$, together with a matrix $K$ giving the kernel of $A$ (i.e. $KA = 0$), if such a solution exists. Return `false`

, an empty vector or matrix and an empty matrix, if the system has no solution.

If `side == :right`

, the system $Ax = b$ is solved.

If a context object `C`

is supplied, then the above applies for `A = matrix(C)`

.

`AbstractAlgebra.kernel`

— Function`kernel(f::ModuleHomomorphism{T}) where T <: RingElement`

Return a pair `K, g`

consisting of the kernel object $K$ of the given module homomorphism $f$ (as a submodule of its domain) and the canonical injection from the kernel into the domain of $f$.

```
kernel(A::MatElem; side::Symbol = :left)
kernel(C::SolveCtx; side::Symbol = :left)
```

Return a matrix $K$ whose rows generate the left kernel of $A$, that is, $KA$ is the zero matrix.

If `side == :right`

, the columns of $K$ generate the right kernel of $A$, that is, $AK$ is the zero matrix.

If the base ring is a principal ideal domain, the rows or columns respectively of $K$ are a basis of the respective kernel.

If a context object `C`

is supplied, then the above applies for `A = matrix(C)`

.