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

.

`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

`solve`

— Function```
Oscar.solve(f::ZZPolyRingElem; max_prec::Int=typemax(Int))
Oscar.solve(f::QQPolyRingElem; max_prec::Int=typemax(Int))
```

Compute a presentation of the roots of `f`

in a radical tower. The necessary roots of unity are not themselves computed as radicals.

See also `galois_group`

.

**VERBOSE**

Supports `set_verbosity_level(:SolveRadical, i)`

to obtain information.

**Examples**

```
julia> Qx,x = QQ["x"];
julia> K, r = solve(x^3+3*x+5)
(Relative number field over with defining polynomial x^3 + (3*z_3 + 3//2)*a2 + 135//2
over Relative number field over with defining polynomial x^2 + 783
over Number field over Rational Field with defining polynomial x^2 + x + 1, Any[((1//81*z_3 + 1//162)*a2 - 5//18)*a3^2 + 1//3*a3, ((-1//162*z_3 + 1//162)*a2 + 5//18*z_3 + 5//18)*a3^2 + 1//3*z_3*a3, ((-1//162*z_3 - 1//81)*a2 - 5//18*z_3)*a3^2 + (-1//3*z_3 - 1//3)*a3])
julia> #z_3 indicates the 3-rd root-of-1 used
julia> map(x^3+3*x+5, r)
3-element Vector{Hecke.RelSimpleNumFieldElem{Hecke.RelSimpleNumFieldElem{AbsSimpleNumFieldElem}}}:
0
0
0
julia> solve(cyclotomic(12, x)) #zeta_12 as radical
(Relative number field over with defining polynomial x^2 - 3//4
over Number field over Rational Field with defining polynomial x^2 + 1, Any[a2 + 1//2*a1, a2 - 1//2*a1, -a2 - 1//2*a1, -a2 + 1//2*a1])
```

This function is part of the experimental code in Oscar. Please read here for more details.

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

.

`can_solve`

— Function` can_solve(f::QuadBin, n::IntegerUnion) -> Bool`

For a binary quadratic form `f`

with negative discriminant and an integer `n`

, return whether `f`

represents `n`

.

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

.

`can_solve_with_solution`

— Function```
can_solve_with_solution(f::QuadBin, n::IntegerUnion)
-> Bool, Tuple{ZZRingElem, ZZRingElem}
```

For a binary quadratic form `f`

with negative discriminant and an integer `n`

, return the tuple `(true, (x, y))`

if $f(x, y) = n$ for integers `x`

, `y`

. If no such integers exist, return `(false, (0, 0))`

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

.

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

.

`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(M::SMat{T}; side::Symbol = :left) where {T <: FieldElement}`

Return a matrix $N$ containing a basis of the kernel of $M$. If `side`

is `:left`

(default), the left kernel is computed, i.e. the matrix of rows whose span gives the left kernel space. If `side`

is `:right`

, the right kernel is computed, i.e. the matrix of columns whose span is the right kernel space.

`kernel(h::FinGenAbGroupHom) -> FinGenAbGroup, Map`

Let $G$ be the domain of $h$. This function returns an abelian group $A$ and an injective morphism $f \colon A \to G$, such that the image of $f$ is the kernel of $h$.

`kernel(f::TorQuadModuleMap) -> TorQuadModule, TorQuadModuleMap`

Given an abelian group homomorphism `f`

between two torsion quadratic modules `T`

and `U`

, return the kernel `S`

of `f`

as well as the injection $S \to T$.

`kernel(f::AbstractAlgebra.Map(SAlgHom))`

Return the kernel of the algebra homomorphism $f$.

`kernel(f::AbstractAlgebra.Map(SIdAlgHom))`

Return the kernel of the identity algebra homomorphism.

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

.

`kernel(F::AffAlgHom)`

Return the kernel of `F`

.

`kernel(f::GAPGroupHomomorphism)`

Return the kernel of `f`

, together with its embedding into `domain`

(`f`

).

`kernel(chi::GAPGroupClassFunction)`

Return `C, f`

where `C`

is the kernel of `chi`

(i.e. the largest normal subgroup of the underlying group `G`

of `chi`

such that `chi`

maps each element of `C`

to `chi[1]`

) and `f`

is the embedding morphism of `C`

into `G`

.

**Examples**

```
julia> t = character_table(symmetric_group(4));
julia> chi = t[3]; chi[1]
2
julia> C, f = kernel(chi); order(C)
4
```

`kernel(a::FreeModuleHom)`

Return the kernel of `a`

as an object of type `SubquoModule`

.

Additionally, if `K`

denotes this object, return the inclusion map `K`

$\to$ `domain(a)`

.

**Examples**

```
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])
julia> F = free_module(R, 3)
Free module of rank 3 over R
julia> G = free_module(R, 2)
Free module of rank 2 over R
julia> V = [y*G[1], x*G[1]+y*G[2], z*G[2]];
julia> a = hom(F, G, V);
julia> kernel(a)
(Submodule with 1 generator
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations., Map with following data
Domain:
=======
Submodule with 1 generator
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations.
Codomain:
=========
Free module of rank 3 over R)
```

```
julia> Rg, (x, y, z) = graded_polynomial_ring(QQ, ["x", "y", "z"]);
julia> F = graded_free_module(Rg, 3);
julia> G = graded_free_module(Rg, 2);
julia> V = [y*G[1], x*G[1]+y*G[2], z*G[2]];
julia> a = hom(F, G, V);
julia> kernel(a)
(Graded submodule of F
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations, Graded submodule of F
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations -> F
x*z*e[1] - y*z*e[2] + y^2*e[3] -> x*z*e[1] - y*z*e[2] + y^2*e[3]
Homogeneous module homomorphism)
```

`kernel(a::SubQuoHom)`

Return the kernel of `a`

as an object of type `SubquoModule`

.

Additionally, if `K`

denotes this object, return the inclusion map `K`

$\to$ `domain(a)`

.

`kernel(a::ModuleFPHom)`

Return the kernel of `a`

as an object of type `SubquoModule`

.

Additionally, if `K`

denotes this object, return the inclusion map `K`

$\to$ `domain(a)`

.

**Examples**

```
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"]);
julia> F = free_module(R, 3);
julia> G = free_module(R, 2);
julia> W = R[y 0; x y; 0 z]
[y 0]
[x y]
[0 z]
julia> a = hom(F, G, W);
julia> K, incl = kernel(a);
julia> K
Submodule with 1 generator
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations.
julia> incl
Map with following data
Domain:
=======
Submodule with 1 generator
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations.
Codomain:
=========
Free module of rank 3 over R
```

```
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"]);
julia> F = free_module(R, 1);
julia> A = R[x; y]
[x]
[y]
julia> B = R[x^2; y^3; z^4]
[x^2]
[y^3]
[z^4]
julia> M = SubquoModule(F, A, B)
Subquotient of Submodule with 2 generators
1 -> x*e[1]
2 -> y*e[1]
by Submodule with 3 generators
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1]
julia> N = M;
julia> V = [y^2*N[1], x*N[2]]
2-element Vector{SubquoModuleElem{QQMPolyRingElem}}:
x*y^2*e[1]
x*y*e[1]
julia> a = hom(M, N, V);
julia> K, incl = kernel(a);
julia> K
Subquotient of Submodule with 3 generators
1 -> (-x + y^2)*e[1]
2 -> x*y*e[1]
3 -> -x*y*e[1]
by Submodule with 3 generators
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1]
julia> incl
Map with following data
Domain:
=======
Subquotient of Submodule with 3 generators
1 -> (-x + y^2)*e[1]
2 -> x*y*e[1]
3 -> -x*y*e[1]
by Submodule with 3 generators
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1]
Codomain:
=========
Subquotient of Submodule with 2 generators
1 -> x*e[1]
2 -> y*e[1]
by Submodule with 3 generators
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1]
```

```
julia> Rg, (x, y, z) = graded_polynomial_ring(QQ, ["x", "y", "z"]);
julia> F = graded_free_module(Rg, 1);
julia> A = Rg[x; y];
julia> B = Rg[x^2; y^3; z^4];
julia> M = SubquoModule(F, A, B)
Graded subquotient of submodule of F generated by
1 -> x*e[1]
2 -> y*e[1]
by submodule of F generated by
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1]
julia> N = M;
julia> V = [y^2*N[1], x^2*N[2]];
julia> a = hom(M, N, V)
M -> M
x*e[1] -> x*y^2*e[1]
y*e[1] -> x^2*y*e[1]
Graded module homomorphism of degree [2]
julia> kernel(a)
(Graded subquotient of submodule of F generated by
1 -> y*e[1]
2 -> -x*y*e[1]
by submodule of F generated by
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1], Graded subquotient of submodule of F generated by
1 -> y*e[1]
2 -> -x*y*e[1]
by submodule of F generated by
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1] -> M
y*e[1] -> y*e[1]
-x*y*e[1] -> -x*y*e[1]
Homogeneous module homomorphism)
```

`kernel(h::LieAlgebraHom) -> LieAlgebraIdeal`

Return the kernel of `h`

as an ideal of the domain.

This function is part of the experimental code in Oscar. Please read here for more details.