Linear inequality solving

The LinearSolve command in the RegularChains package, whose purpose is to solve systems of linear equations and inequalities, has been enhanced in several ways:

 • A more efficient algorithm based on Fourier-Motzkin elimination, has been implemented.
 • Two new options, canonical and projection, for controlling the form of the output have been added.

The examples below illustrate the use of this command and the two new options for computations with polyhedra.

Change of representation for polyhedra

There are at least two ways to mathematically describe a polyhedron, either by specifying its corners, or by specifying its bounding hyperplanes. This is illustrated using a cube of side length 1 with one corner at the origin and its three adjacent edges parallel to the three coordinate axes.

Plot the cube:

$\mathrm{with}\left(\mathrm{plots}\right):\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{with}\left(\mathrm{plottools}\right):$

$\mathrm{display}\left(\mathrm{cuboid}\left(\left[0,0,0\right],\left[1,1,1\right]\right),\mathrm{axes}=\mathrm{boxed},\mathrm{labels}=\left[x,y,z\right]\right)$

Define this cube by bounding planes:

$\mathrm{c1}≔\left[x\ge 0,x\le 1,y\ge 0,y\le 1,z\ge 0,z\le 1\right]$

 $\left[{0}{\le }{x}{,}{x}{\le }{1}{,}{0}{\le }{y}{,}{y}{\le }{1}{,}{0}{\le }{z}{,}{z}{\le }{1}\right]$ (1.1)

Alternatively, define the vertices of the same cube:

$V≔\mathrm{Matrix}\left(\left[\left[0,0,0\right],\left[0,0,1\right],\left[0,1,0\right],\left[0,1,1\right],\left[1,0,0\right],\left[1,0,1\right],\left[1,1,0\right],\left[1,1,1\right]\right]\right)$

 $\left[\begin{array}{rrr}{0}& {0}& {0}\\ {0}& {0}& {1}\\ {0}& {1}& {0}\\ {0}& {1}& {1}\\ {1}& {0}& {0}\\ {1}& {0}& {1}\\ {1}& {1}& {0}\\ {1}& {1}& {1}\end{array}\right]$ (1.2)

Suppose now that you are given the vertex representation and want to automatically derive the bounding planes representation. The cube is defined as the convex hull of all its vertices:

$\mathrm{op}\left(\mathrm{convert}\left({\mathrm{Vector}}_{\mathrm{row}}\left(\left[x,y,z\right]\right)=~\mathrm{add}\left({\mathrm{λ}}_{i}\cdot {V}_{i},i=1..8\right),\mathrm{list}\right)\right)$

 ${x}{=}{{\mathrm{λ}}}_{{5}}{+}{{\mathrm{λ}}}_{{6}}{+}{{\mathrm{λ}}}_{{7}}{+}{{\mathrm{λ}}}_{{8}}{,}{y}{=}{{\mathrm{λ}}}_{{3}}{+}{{\mathrm{λ}}}_{{4}}{+}{{\mathrm{λ}}}_{{7}}{+}{{\mathrm{λ}}}_{{8}}{,}{z}{=}{{\mathrm{λ}}}_{{2}}{+}{{\mathrm{λ}}}_{{4}}{+}{{\mathrm{λ}}}_{{6}}{+}{{\mathrm{λ}}}_{{8}}$ (1.3)

$\mathrm{add}\left({\mathrm{λ}}_{i},i=1..8\right)=1$

 ${{\mathrm{λ}}}_{{1}}{+}{{\mathrm{λ}}}_{{2}}{+}{{\mathrm{λ}}}_{{3}}{+}{{\mathrm{λ}}}_{{4}}{+}{{\mathrm{λ}}}_{{5}}{+}{{\mathrm{λ}}}_{{6}}{+}{{\mathrm{λ}}}_{{7}}{+}{{\mathrm{λ}}}_{{8}}{=}{1}$ (1.4)

$\mathrm{seq}\left({\mathrm{λ}}_{i}\ge 0,i=1..8\right)$

 ${0}{\le }{{\mathrm{λ}}}_{{1}}{,}{0}{\le }{{\mathrm{λ}}}_{{2}}{,}{0}{\le }{{\mathrm{λ}}}_{{3}}{,}{0}{\le }{{\mathrm{λ}}}_{{4}}{,}{0}{\le }{{\mathrm{λ}}}_{{5}}{,}{0}{\le }{{\mathrm{λ}}}_{{6}}{,}{0}{\le }{{\mathrm{λ}}}_{{7}}{,}{0}{\le }{{\mathrm{λ}}}_{{8}}$ (1.5)

$\mathrm{seq}\left({\mathrm{λ}}_{i}\le 1,i=1..8\right)$

 ${{\mathrm{λ}}}_{{1}}{\le }{1}{,}{{\mathrm{λ}}}_{{2}}{\le }{1}{,}{{\mathrm{λ}}}_{{3}}{\le }{1}{,}{{\mathrm{λ}}}_{{4}}{\le }{1}{,}{{\mathrm{λ}}}_{{5}}{\le }{1}{,}{{\mathrm{λ}}}_{{6}}{\le }{1}{,}{{\mathrm{λ}}}_{{7}}{\le }{1}{,}{{\mathrm{λ}}}_{{8}}{\le }{1}$ (1.6)

$\mathrm{sys}≔\left[,,,\right]:$

You can now use the LinearSolve command to eliminate all ${\mathrm{λ}}_{i}$ from this system of equations and inequalities. The projection option is used to specify that elimination is required, and the canonical option to eliminate redundant equations and inequalities.

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

$\mathrm{vars}≔\left[\mathrm{seq}\left({\mathrm{λ}}_{i},i=1..8\right),z,y,x\right]$

 $\left[{{\mathrm{λ}}}_{{1}}{,}{{\mathrm{λ}}}_{{2}}{,}{{\mathrm{λ}}}_{{3}}{,}{{\mathrm{λ}}}_{{4}}{,}{{\mathrm{λ}}}_{{5}}{,}{{\mathrm{λ}}}_{{6}}{,}{{\mathrm{λ}}}_{{7}}{,}{{\mathrm{λ}}}_{{8}}{,}{z}{,}{y}{,}{x}\right]$ (1.7)

$\mathrm{LinearSolve}\left(\mathrm{sys},\mathrm{PolynomialRing}\left(\mathrm{vars}\right),\mathrm{canonical},\mathrm{projection}=3\right)$

 $\left[{0}{\le }{x}{,}{x}{\le }{1}{,}{0}{\le }{y}{,}{y}{\le }{1}{,}{0}{\le }{z}{,}{z}{\le }{1}\right]$ (1.8)

This agrees with the representation $\mathrm{c1}$ above.

Dual polyhedra

For every convex 3-D polyhedron, there is a dual polyhedron with the roles of corners and faces swapped. Let us compute the dual polyhedron of the cube. Start with a representation of the cube with the origin as the center.

$\mathrm{c2}≔\left[x\le 1,-x\le 1,y\le 1,-y\le 1,z\le 1,-z\le 1\right]$

 $\left[{x}{\le }{1}{,}{-}{x}{\le }{1}{,}{y}{\le }{1}{,}{-}{y}{\le }{1}{,}{z}{\le }{1}{,}{-}{z}{\le }{1}\right]$ (2.1)

Now rewrite this in matrix form.

$B≔\mathrm{Matrix}\left(\left[\left[1,0,0\right],\left[-1,0,0\right],\left[0,1,0\right],\left[0,-1,0\right],\left[0,0,1\right],\left[0,0,-1\right]\right]\right)$

 $\left[\begin{array}{rrr}{1}& {0}& {0}\\ {-}{1}& {0}& {0}\\ {0}& {1}& {0}\\ {0}& {-}{1}& {0}\\ {0}& {0}& {1}\\ {0}& {0}& {-}{1}\end{array}\right]$ (2.2)

$v≔\mathrm{Vector}\left(\left[x,y,z\right]\right)$

 $\left[\begin{array}{c}{x}\\ {y}\\ {z}\end{array}\right]$ (2.3)

$c≔\mathrm{Vector}\left(\left[1,1,1,1,1,1\right]\right)$

 $\left[\begin{array}{r}{1}\\ {1}\\ {1}\\ {1}\\ {1}\\ {1}\end{array}\right]$ (2.4)

$B.v\le ~c$

 $\left[\begin{array}{c}{x}{\le }{1}\\ {-}{x}{\le }{1}\\ {y}{\le }{1}\\ {-}{y}{\le }{1}\\ {z}{\le }{1}\\ {-}{z}{\le }{1}\end{array}\right]$ (2.5)

In general, if a bounded convex polyhedron is given by a set of inequalities of the form $B.v\le 1$, then the vertices of its dual are exactly the columns of the matrix $B$. The convex hull of these six vertices defines an octahedron. Using the same method as before, compute the bounding planes for this octahedron.

$\mathrm{op}\left(\mathrm{convert}\left({\mathrm{Vector}}_{\mathrm{row}}\left(\left[x,y,z\right]\right)=~\mathrm{add}\left({\mathrm{λ}}_{i}\cdot {B}_{i},i=1..6\right),\mathrm{list}\right)\right)$

 ${x}{=}{{\mathrm{λ}}}_{{1}}{-}{{\mathrm{λ}}}_{{2}}{,}{y}{=}{{\mathrm{λ}}}_{{3}}{-}{{\mathrm{λ}}}_{{4}}{,}{z}{=}{{\mathrm{λ}}}_{{5}}{-}{{\mathrm{λ}}}_{{6}}$ (2.6)

$\mathrm{add}\left({\mathrm{λ}}_{i},i=1..6\right)=1$

 ${{\mathrm{λ}}}_{{1}}{+}{{\mathrm{λ}}}_{{2}}{+}{{\mathrm{λ}}}_{{3}}{+}{{\mathrm{λ}}}_{{4}}{+}{{\mathrm{λ}}}_{{5}}{+}{{\mathrm{λ}}}_{{6}}{=}{1}$ (2.7)

$\mathrm{seq}\left({\mathrm{λ}}_{i}\ge 0,i=1..6\right)$

 ${0}{\le }{{\mathrm{λ}}}_{{1}}{,}{0}{\le }{{\mathrm{λ}}}_{{2}}{,}{0}{\le }{{\mathrm{λ}}}_{{3}}{,}{0}{\le }{{\mathrm{λ}}}_{{4}}{,}{0}{\le }{{\mathrm{λ}}}_{{5}}{,}{0}{\le }{{\mathrm{λ}}}_{{6}}$ (2.8)

$\mathrm{seq}\left({\mathrm{λ}}_{i}\le 1,i=1..6\right)$

 ${{\mathrm{λ}}}_{{1}}{\le }{1}{,}{{\mathrm{λ}}}_{{2}}{\le }{1}{,}{{\mathrm{λ}}}_{{3}}{\le }{1}{,}{{\mathrm{λ}}}_{{4}}{\le }{1}{,}{{\mathrm{λ}}}_{{5}}{\le }{1}{,}{{\mathrm{λ}}}_{{6}}{\le }{1}$ (2.9)

$\mathrm{sys}≔\left[,,,\right]:$

$\mathrm{vars}≔\left[\mathrm{seq}\left({\mathrm{λ}}_{i},i=1..6\right),z,y,x\right]$

 $\left[{{\mathrm{λ}}}_{{1}}{,}{{\mathrm{λ}}}_{{2}}{,}{{\mathrm{λ}}}_{{3}}{,}{{\mathrm{λ}}}_{{4}}{,}{{\mathrm{λ}}}_{{5}}{,}{{\mathrm{λ}}}_{{6}}{,}{z}{,}{y}{,}{x}\right]$ (2.10)

$S≔\mathrm{LinearSolve}\left(\mathrm{sys},\mathrm{PolynomialRing}\left(\mathrm{vars}\right),\mathrm{canonical},\mathrm{projection}=3\right)$

 $\left[{-}{1}{\le }{x}{,}{x}{\le }{1}{,}{-}{x}{-}{1}{\le }{y}{,}{-}{1}{+}{x}{\le }{y}{,}{y}{\le }{1}{+}{x}{,}{y}{\le }{1}{-}{x}{,}{-}{y}{-}{x}{-}{1}{\le }{z}{,}{-}{y}{+}{x}{-}{1}{\le }{z}{,}{-}{1}{-}{x}{+}{y}{\le }{z}{,}{-}{1}{+}{x}{+}{y}{\le }{z}{,}{z}{\le }{y}{+}{x}{+}{1}{,}{z}{\le }{y}{-}{x}{+}{1}{,}{z}{\le }{1}{+}{x}{-}{y}{,}{z}{\le }{1}{-}{x}{-}{y}\right]$ (2.11)

The first two inequalities represent that projection of the octahedron onto the $x$ axis:

${S}_{1..2}$

 $\left[{-}{1}{\le }{x}{,}{x}{\le }{1}\right]$ (2.12)

Together with the following four inequalities, which involve only $x$ and $y$ but not $z$, this defines the projection of the octahedron onto the $x,y$-plane:

 $\left[{-}{x}{-}{1}{\le }{y}{,}{-}{1}{+}{x}{\le }{y}{,}{y}{\le }{1}{+}{x}{,}{y}{\le }{1}{-}{x}\right]$ (2.13)

The following plot shows this projection (blue) together with the four boundary lines.

$\mathrm{inequal}\left({S}_{3..6},x=-2..2,y=-2..2\right)$

Finally, the last 8 inequalities, i.e., the ones containing $z$, define the bounding planes of the octahedron.

${S}_{-8..-1}$

 $\left[{-}{y}{-}{x}{-}{1}{\le }{z}{,}{-}{y}{+}{x}{-}{1}{\le }{z}{,}{-}{1}{-}{x}{+}{y}{\le }{z}{,}{-}{1}{+}{x}{+}{y}{\le }{z}{,}{z}{\le }{y}{+}{x}{+}{1}{,}{z}{\le }{y}{-}{x}{+}{1}{,}{z}{\le }{1}{+}{x}{-}{y}{,}{z}{\le }{1}{-}{x}{-}{y}\right]$ (2.14)

The following 3-D plot displays the tetrahedron as well as the last of these 8 bounding planes. Rotate the plot with the mouse in order to see that the plane actually touches one of the faces.

$\mathrm{plane}≔\mathrm{Student}:-\mathrm{LinearAlgebra}:-\mathrm{PlanePlot}\left(\left(\mathrm{lhs}-\mathrm{rhs}\right)\left({S}_{-1}\right)=0,\left[x,y,z\right],\mathrm{caption}="",\mathrm{shownormal}=\mathrm{false},\mathrm{showpoint}=\mathrm{false},\mathrm{planeoptions}=\left[\mathrm{transparency}=0.3\right]\right):$

$\mathrm{display}\left(\mathrm{octahedron}\left(\left[0,0,0\right]\right),\mathrm{plane},\mathrm{axes}=\mathrm{boxed},\mathrm{labels}=\left[x,y,z\right]\right)$