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_initFunction
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
source

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

solveFunction
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])
Experimental

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

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

source
can_solveFunction
 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.

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

source
can_solve_with_solutionFunction
 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))

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

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

See also solve and kernel.

source
kernelFunction
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$.

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

source
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$.

source
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$.

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

Return the kernel of the algebra homomorphism $f$.

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

Return the kernel of the identity algebra homomorphism.

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

source
kernel(F::AffAlgHom)

Return the kernel of F.

source
kernel(f::GAPGroupHomomorphism)

Return the kernel of f, together with its embedding into domain(f).

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

source
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)
source
kernel(h::LieAlgebraHom) -> LieAlgebraIdeal

Return the kernel of h as an ideal of the domain.

Experimental

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

source