# V- and H-representation

Short summary and conventions

Both cones and polyhedra can be described either by giving generators, the so-called V-representation or by giving inequalities, the so-called H-representation. We have the following conventions:

1. Rays, vertices, and generators of the lineality space are given as columns of matrices.

2. Inequalities and hyperplanes are given as rows of matrices.

3. The inequality description of a cone is $A\cdot x\ge 0$.

4. The inequality description of a polyhedron is $A\cdot x\le b$.

Conventions for cones

For cones we have the convention that the scalar product of generators with inequalities is positive:

 i1 : C = coneFromVData matrix {{1,0,0},{1,1,0},{1,0,1},{1,1,1}} o1 = C o1 : Cone i2 : rays C o2 = | 0 0 1 | | 1 0 1 | | 0 1 1 | | 1 1 1 | 4 3 o2 : Matrix ZZ <--- ZZ i3 : facets C o3 = | 0 -1 0 1 | | 0 0 -1 1 | | 0 1 1 -1 | 3 4 o3 : Matrix ZZ <--- ZZ i4 : (facets C) * (rays C) o4 = | 0 1 0 | | 1 0 0 | | 0 0 1 | 3 3 o4 : Matrix ZZ <--- ZZ

The hyperplanes of a cone evaluate to zero with the rays of a cone, just like the linealitySpace evaluates to zero with the facets.

 i5 : (hyperplanes C) * (rays C) o5 = 0 1 3 o5 : Matrix ZZ <--- ZZ i6 : (facets C) * (linealitySpace C) o6 = 0 3 o6 : Matrix ZZ <--- 0

Conventions for polyhedra

For a polyhedron the situation is slightly different, as we have a right hand side to take into account, since we are dealing with affine hyperplanes instead of just hyperplanes.

 i7 : P = hypercube(2,0,1) o7 = P o7 : Polyhedron i8 : V = vertices P o8 = | 0 1 0 1 | | 0 0 1 1 | 2 4 o8 : Matrix QQ <--- QQ i9 : (A, b) = facets P o9 = (| -1 0 |, | 0 |) | 1 0 | | 1 | | 0 -1 | | 0 | | 0 1 | | 1 | o9 : Sequence i10 : A * V o10 = | 0 -1 0 -1 | | 0 1 0 1 | | 0 0 -1 -1 | | 0 0 1 1 | 4 4 o10 : Matrix QQ <--- QQ

The convention is that for any point $p$ in the polyhedron we have $A\cdot p\le b$. This means we have $0\le b - A\cdot p$. Again, this may be handled differently elsewhere.

 i11 : for i from 0 to numColumns V - 1 do ( test := b - A*V_{i}; << "Vertex " << i << " " << (flatten entries V_{i}) << ": " << all(flatten entries test, e -> e>= 0) << endl; ) Vertex 0 {0, 0}: true Vertex 1 {1, 0}: true Vertex 2 {0, 1}: true Vertex 3 {1, 1}: true

From the above convention it follows that the facets evaluate negatively with the rays and linealitySpace of a polyhedron. Conversely to hyperplanes evaluate to constants on the vertices of a polyhedron.

 i12 : P = convexHull(matrix{{1,0},{0,1},{2,2}}, matrix {{1},{1},{2}}) o12 = P o12 : Polyhedron i13 : vertices P o13 = | 1 0 | | 0 1 | | 2 2 | 3 2 o13 : Matrix QQ <--- QQ i14 : rays P o14 = | 1 | | 1 | | 2 | 3 1 o14 : Matrix QQ <--- QQ i15 : (A, b) = facets P o15 = (| 2 0 -1 |, 0) | 0 2 -1 | | -2 -2 1 | o15 : Sequence i16 : A * (vertices P) o16 = | 0 -2 | | -2 0 | | 0 0 | 3 2 o16 : Matrix QQ <--- QQ i17 : A * (rays P) o17 = | 0 | | 0 | | -2 | 3 1 o17 : Matrix QQ <--- QQ i18 : (E, v) = hyperplanes P o18 = (| 1 1 -1 |, | -1 |) o18 : Sequence i19 : E * (rays P) o19 = 0 1 1 o19 : Matrix QQ <--- QQ i20 : E * (vertices P) o20 = | -1 -1 | 1 2 o20 : Matrix QQ <--- QQ

Full representations

1. The pair (rays, linealitySpace) is a valid V-representation of a cone.

2. The pair (facets, hyperplanes) is a valid H-representation of a cone.

3. The triple (vertices, rays, linealitySpace) is a valid V-representation of a polyhedron.

4. The triple (facets, hyperplanes) is a valid H-representation of a polyhedron.

That means we have the following identities:

 i21 : C == coneFromVData(rays C, linealitySpace C) o21 = true i22 : C == coneFromRays(rays C, linealitySpace C) o22 = true i23 : C == coneFromHData(facets C, hyperplanes C) o23 = true i24 : C == coneFromInequalities(facets C, hyperplanes C) o24 = true i25 : P == convexHull (vertices P, rays P, linealitySpace P) o25 = true i26 : F = facets P o26 = (| 2 0 -1 |, 0) | 0 2 -1 | | -2 -2 1 | o26 : Sequence i27 : H = hyperplanes P o27 = (| 1 1 -1 |, | -1 |) o27 : Sequence i28 : P == polyhedronFromHData(F#0, F#1, H#0, H#1) o28 = true i29 : P == polyhedronFromInequalities(F#0, F#1, H#0, H#1) o29 = true