RegularChains/SemiAlgebraicSetTools/LinearSolve - Maple Help

Home : Support : Online Help : RegularChains/SemiAlgebraicSetTools/LinearSolve

RegularChains[SemiAlgebraicSetTools]

 LinearSolve
 solve a linear semi-algebraic system

 Calling Sequence LinearSolve(sys, R, options) LinearSolve(F, N, P, H, R, options)

Parameters

 R - sys - list of linear equations, inequations and inequalities of R F - list of linear polynomials over R representing equations N - list of linear polynomials over R representing nonnegativity conditions P - list of linear polynomials over R representing positivity conditions H - list of linear polynomials over R representing nonzero conditions options - (optional) equation(s) of the form keyword=value, where keyword is either 'canonical' or 'projection'

 Returns triangularized list of linear equations, inequations, and inequalities of R equivalent to sys

Options

 • 'canonical'=truefalse
 The canonical option controls the redundancy of the output. Its default value is false. If 'canonical'=true, or just 'canonical' for short, is specified, it will be guaranteed that there are no redundancies among the constraints with the same main variables in the output.
 • 'projection'=nonnegint
 The projection option determines the subcoordinate space to be projected onto. If the option 'projection'=k is specified, where $k$ is a nonnegative integer less than the number of variables, then the output provides the projection of the zero set of $S$ onto the coordinate subspace determined by the smallest $k$ variables of R.
 The algorithm behind this command is a variant of Fourier-Motzkin elimination.

Description

 • Consider the linear semi-algebraic system $S$  whose unknowns are the variables of R and whose equations, non-negative inequalities, strictly positive inequalities, and inequations are given either by sys or by F, N, P, and H, respectively.
 • The commands LinearSolve(sys, R) and LinearSolve(F, N, P, H, R) return an equivalent linear semi-algebraic system of triangular shape to the input linear semi-algebraic system $S$. This assumes that R is a polynomial ring over the field of rational numbers.
 • If $S$ has no solutions, the output is the empty list $\left[\right]$. If the solution of $S$ is the whole space, the output is $\left[\mathrm{true}\right]$. Otherwise, the output is a nonempty list of linear constraints satisfying the following properties:
 – The output constraints are in an ascending order according to the largest variable appearing in them.
 – The projection of the solutions of the input system $S$ onto any lower dimensional space, say the space formed by the smallest $i$ variables, are exactly the solutions of those constraints in the output which only involve the smallest $i$ variables.

Examples

 > $\mathrm{with}\left(\mathrm{RegularChains}\right):$
 > $\mathrm{with}\left(\mathrm{SemiAlgebraicSetTools}\right):$

Define a ring of polynomials. The order of variables is z > y > x.

 > $R≔\mathrm{PolynomialRing}\left(\left[z,y,x\right]\right)$
 ${R}{≔}{\mathrm{polynomial_ring}}$ (1)

Define a set of linear equations and inequalities.

 > $\mathrm{sys}≔\left[x+y+z=0,0\le x+y-z,x-y-z<0\right]$
 ${\mathrm{sys}}{≔}\left[{x}{+}{y}{+}{z}{=}{0}{,}{0}{\le }{x}{+}{y}{-}{z}{,}{x}{-}{y}{-}{z}{<}{0}\right]$ (2)

We eliminate variables according to the order z > y > x.

 > $T≔\mathrm{LinearSolve}\left(\mathrm{sys},R\right)$
 ${T}{≔}\left[{x}{<}{0}{,}{-}{x}{\le }{y}{,}{z}{=}{-}{x}{-}{y}\right]$ (3)

The output is a set of equivalent linear equations and inequalities sorted in ascending order according to the largest variables appearing in the constraints. It provides conditions on lower order variables such that higher order variables have solutions.

Now compute the projection of sys.

 > $T≔\mathrm{LinearSolve}\left(\mathrm{sys},R,'\mathrm{projection}'=2\right)$
 ${T}{≔}\left[{x}{<}{0}{,}{-}{x}{\le }{y}\right]$ (4)

The output is a set of linear constraints describing the projection of the zero set of sys onto $x,y$ space.

The option 'canonical' can be used to remove redundancies among constraints having the same main variables.

 > $\mathrm{sys}≔\left[x+y+z\le 1,x+y+z\le 2,0\le x+y-z\right]$
 ${\mathrm{sys}}{≔}\left[{z}{+}{y}{+}{x}{\le }{1}{,}{z}{+}{y}{+}{x}{\le }{2}{,}{0}{\le }{x}{+}{y}{-}{z}\right]$ (5)
 > $T≔\mathrm{LinearSolve}\left(\mathrm{sys},R\right)$
 ${T}{≔}\left[{z}{\le }{x}{+}{y}{,}{z}{\le }{2}{-}{y}{-}{x}{,}{z}{\le }{1}{-}{y}{-}{x}\right]$ (6)
 > $T≔\mathrm{LinearSolve}\left(\mathrm{sys},R,'\mathrm{canonical}'='\mathrm{true}'\right)$
 ${T}{≔}\left[{z}{\le }{x}{+}{y}{,}{z}{\le }{1}{-}{y}{-}{x}\right]$ (7)

Compatibility

 • The F, N, P, H and options parameters were introduced in Maple 17.
 • For more information on Maple 17 changes, see Updates in Maple 17.