Gale diagram

In the mathematical discipline of polyhedral combinatorics, the Gale transform turns the vertices of any convex polytope into a set of vectors or points in a space of a different dimension, the Gale diagram of the polytope. It can be used to describe high-dimensional polytopes with few vertices, by transforming them into sets with the same number of points, but in a space of a much lower dimension. The process can also be reversed, to construct polytopes with desired properties from their Gale diagrams. The Gale transform and Gale diagram are named after David Gale, who introduced these methods in a 1956 paper on neighborly polytopes. ^[1]

Definitions

Transform

Given a ${\displaystyle d}$-dimensional polytope, with ${\displaystyle n}$ vertices, adjoin 1 to the Cartesian coordinates of each vertex, to obtain a ${\displaystyle (d+1)}$-dimensional column vector. The matrix ${\displaystyle A}$ of these ${\displaystyle n}$ column vectors has dimensions ${\displaystyle (d+1)\times n}$, defining a linear mapping from ${\displaystyle n}$-space to ${\displaystyle (d+1)}$-space, surjective with rank ${\displaystyle d+1}$. The kernel of ${\displaystyle A}$ describes linear dependencies among the ${\displaystyle n}$ original vertices with coefficients summing to zero; this kernel has dimension ${\displaystyle n-d-1}$. The Gale transform of ${\displaystyle A}$ is a matrix ${\displaystyle B}$ of dimension ${\displaystyle n\times (n-d-1)}$, whose column vectors are a chosen basis for the kernel of ${\displaystyle A}$. Then ${\displaystyle B}$ has ${\displaystyle n}$row vectors of dimension ${\displaystyle n-d-1}$. These row vectors form the Gale diagram of the polytope. A different choice of basis for the kernel changes the result only by a linear transformation. ^[2]

Note that the vectors in the Gale diagram are in natural bijection with the ${\displaystyle n}$ vertices of the original ${\displaystyle d}$-dimensional polytope, but the dimension of the Gale diagram is smaller whenever ${\displaystyle n\leq 2d}$.

A proper subset of the vertices of a polytope forms the vertex set of a face of the polytope, if and only if the complementary set of vectors of the Gale transform has a convex hull that contains the origin in its relative interior. Equivalently, the subset of vertices forms a face if and only if its affine span does not intersect the convex hull of the complementary vectors. ^[3]

Linear diagram

Because the Gale transform is defined only up to a linear transformation, its nonzero vectors can be normalized to all be ${\displaystyle (n-d-1)}$-dimensional unit vectors. The linear Gale diagram is a normalized version of the Gale transform, in which all the vectors are zero or unit vectors. ^[4]

Affine diagram

Given a Gale diagram of a polytope, that is, a set of ${\displaystyle n}$ unit vectors in an ${\displaystyle (n-d-1)}$-dimensional space, one can choose a ${\displaystyle (n-d-2)}$-dimensional subspace ${\displaystyle S}$ through the origin that avoids all of the vectors, and a parallel subspace ${\displaystyle S'}$ that does not pass through the origin. Then, a central projection from the origin to ${\displaystyle S'}$ will produce a set of ${\displaystyle (n-d-2)}$-dimensional points. This projection loses the information about which vectors lie above ${\displaystyle S}$ and which lie below it, but this information can be represented by assigning a sign (positive, negative, or zero) or equivalently a color (black, white, or gray) to each point. The resulting set of signed or colored points is the affine Gale diagram of the given polytope. This construction has the advantage, over the Gale transform, of using one less dimension to represent the structure of the given polytope. ^[5]

Gale transforms and linear and affine Gale diagrams can also be described through the duality of oriented matroids. ^[6] As with the linear diagram, a subset of vertices forms a face if and only if there is no affine function (a linear function with a possibly nonzero constant term) that assigns a non-negative value to each positive vector in the complementary set and a non-positive value to each negative vector in the complementary set. ^[7]

Examples

The Gale diagram is particularly effective in describing polyhedra whose numbers of vertices are only slightly larger than their dimensions.

Simplices

A ${\displaystyle d}$-dimensional polytope with ${\displaystyle n=d+1}$ vertices, the minimum possible, is a simplex. In this case, the linear Gale diagram is 0-dimensional, consisting only of zero vectors. The affine diagram has ${\displaystyle n}$ gray points. ^[8]

One additional vertex

In a ${\displaystyle d}$-dimensional polytope with ${\displaystyle n=d+2}$ vertices, the linear Gale diagram is one-dimensional, with the vector representing each point being one of the three numbers ${\displaystyle -1}$, ${\displaystyle 0}$, or ${\displaystyle +1}$. In the affine diagram, the points are zero-dimensional, so they can be represented only by their signs or colors without any location value. In order to represent a polytope, the diagram must have at least two points with each nonzero sign. Two diagrams represent the same combinatorial equivalence class of polytopes when they have the same numbers of points of each sign, or when they can be obtained from each other by negating all of the signs. ^[8]

For ${\displaystyle d=2}$, the only possibility is two points of each nonzero sign, representing a convex quadrilateral. For ${\displaystyle d=3}$, there are two possible Gale diagrams: the diagram with two points of each nonzero sign and one zero point represents a square pyramid, while the diagram with two points of one nonzero sign and three points with the other sign represents the triangular bipyramid. ^[8]

In general, the number of distinct Gale diagrams with ${\displaystyle n=d+2}$, and the number of combinatorial equivalence classes of ${\displaystyle d}$-dimensional polytopes with ${\displaystyle n}$ vertices, is ${\displaystyle \lfloor d^{2}/4\rfloor }$. ^[8]

Two additional vertices

In a ${\displaystyle d}$-dimensional polytope with ${\displaystyle n=d+3}$ vertices, the linear Gale diagram consists of points on the unit circle (unit vectors) and at its center. The affine Gale diagram consists of labeled points or clusters of points on a line. Unlike for the case of ${\displaystyle n=d+2}$ vertices, it is not completely trivial to determine when two Gale diagrams represent the same polytope. ^[8]

Three-dimensional polyhedra with six vertices provide natural examples where the original polyhedron is of a low enough dimension to visualize, but where the Gale diagram still provides a dimension-reducing effect.

• A regular octahedron has linear Gale diagram comprising three pairs of equal points on the unit circle (representing pairs of opposite vertices of the octahedron), dividing the circle into arcs of angle less than ${\displaystyle \pi }$. Its affine Gale diagram consists of three pairs of equal signed points on the line, with the middle pair having the opposite sign to the outer two pairs. ^[9]
• A triangular prism has linear Gale diagram comprising six points on the circle, in three diametrically opposed pairs, with each pair representing vertices of the prism that are adjacent on two square faces of the prism. The corresponding affine Gale diagram has three pairs of points on a line, like the regular octahedron, but with one point of each sign in each pair. ^[10]

Applications

Gale diagrams have been used to provide a complete combinatorial enumeration of the ${\displaystyle d}$-dimensional polytopes with ${\displaystyle n=d+3}$ vertices, ^[11] and to construct polytopes with unusual properties. These include:

• The Perles polytope, an 8-dimensional polytope with 12 vertices that cannot be realized with rational Cartesian coordinates. Micha Perles construted it from the Perles configuration (nine points and nine lines in the plane that cannot be realized with rational coordinates) by doubling three of the points, assigning signs to the resulting 12 points, and treating the resulting signed configuration as the Gale diagram of a polytope. Although irrational polytopes are known with dimension as low as four, none are known with fewer vertices. ^[12]
• The Kleinschmidt polytope, a 4-dimensional polytope with 8 vertices, 10 tetrahedral facets, and one octahedral facet, constructed by Peter Kleinschmidt. Although the octahedral facet has the same combinatorial structure as a regular octahedron, it is not possible for it to be regular. ^[13] Two copies of this polytope can be glued together on their octahedral facets to produce a 10-vertex polytope in which some pairs of realizations cannot be continuously deformed into each other. ^[14]
• The bipyramid over a square pyramid is a 4-dimensional polytope with 7 vertices having the dual property, that the shape of one of its vertex figures (the apex of its central pyramid) cannot be prescribed. Originally found by David W. Barnette, it was rediscovered by Bernd Sturmfels using Gale diagrams. ^[15]
• The construction of small "unneighborly polytopes", that is, polytopes without a universal vertex, and "illuminated polytopes", in which every vertex is incident to a diagonal that passes through the interior of the polytope. The cross polytopes have these properties, but in 16 or more dimensions there exist illuminated polytopes with fewer vertices, and in 6 or more dimensions the illuminated polytopes with the fewest vertices need not be simplicial. The construction involves Gale diagrams. ^[16]

Notes

1. Gale (1956).
2. Thomas (2006), Definition 5.2, p. 38
3. Thomas (2006), Theorem 5.6, p. 41
4. Sturmfels (1988).
5. Thomas (2006), p. 43–44.
6. Ziegler (1995), Definition 6.17, p. 168
7. Ziegler (1995), p. 170
8. Ziegler (1995), p. 171.
9. Ziegler (1995), Example 6.18, p. 169
10. Thomas (2006), pp. 39 and 44
11. Sturmfels (1988), p. 121; Ziegler (1995), p. 172
12. Ziegler (1995), Section 6.5(a) "A nonrational 8-polytope", pp. 172–173; Thomas (2006), Theorem 6.11, pp. 51–52
13. Ziegler (1995), Section 6.5(b) "Facets of 4-polytopes cannot be prescribed", pp. 173–175, and Exercise 6.18, p. 188; Sturmfels (1988), pp. 129–130
14. Ziegler (1995), Section 6.5(d) "Polytopes violating the isotopy conjecture", pp. 177–179
15. Ziegler (1995), Section 6.5(b) "Facets of 4-polytopes cannot be prescribed", pp. 173–175; Sturmfels (1988), Proposition 5.1, p. 130; Thomas (2006), Theorem 6.12, pp. 53–55
16. Wotzlaw & Ziegler (2011).

References

• Gale, David (1956), "Neighboring vertices on a convex polyhedron", Linear inequalities and related system, Annals of Mathematics Studies, no. 38, Princeton University Press, Princeton, N.J., pp. 255–263, MR   0085552
• Sturmfels, Bernd (1988), "Some applications of affine Gale diagrams to polytopes with few vertices", SIAM Journal on Discrete Mathematics, 1 (1): 121–133, doi:10.1137/0401014, MR   0936614
• Thomas, Rekha R. (2006), "Chapter 5: Gale Diagrams", Lectures in Geometric Combinatorics, Student Mathematical Library, vol. 33, Institute for Advanced Study (IAS), Princeton, NJ, pp. 37–45, doi:10.1090/stml/033, ISBN   0-8218-4140-8, MR   2237292
• Wotzlaw, Ronald F.; Ziegler, Günter M. (2011), "A lost counterexample and a problem on illuminated polytopes", American Mathematical Monthly, 118 (6): 534–543, doi:10.4169/amer.math.monthly.118.06.534, MR   2812284, S2CID   15007113
• Ziegler, Günter M. (1995), "Chapter 6: Duality, Gale Diagrams, and Applications", Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, New York: Springer-Verlag, pp. 149–190, doi:10.1007/978-1-4613-8431-1_6, ISBN   0-387-94365-X, MR   1311028