In the mathematical discipline of
polyhedral combinatorics Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.
Research in polyhedral comb ...
, the Gale transform turns the vertices of any
convex polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
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 of points 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
David (; , "beloved one") (traditional spelling), , ''Dāwūd''; grc-koi, Δαυΐδ, Dauíd; la, Davidus, David; gez , ዳዊት, ''Dawit''; xcl, Դաւիթ, ''Dawitʿ''; cu, Давíдъ, ''Davidŭ''; possibly meaning "beloved one". w ...
, who introduced these methods in a 1956 paper on
neighborly polytope
In geometry and polyhedral combinatorics, a -neighborly polytope is a convex polytope in which every set of or fewer vertices forms a face. For instance, a 2-neighborly polytope is a polytope in which every pair of vertices is connected by an ...
s.
Definitions
Transform
Given a
-dimensional polytope, with
vertices, adjoin 1 to the
Cartesian coordinate
A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in ...
s of each vertex, to obtain a
-dimensional
column vector
In linear algebra, a column vector with m elements is an m \times 1 matrix consisting of a single column of m entries, for example,
\boldsymbol = \begin x_1 \\ x_2 \\ \vdots \\ x_m \end.
Similarly, a row vector is a 1 \times n matrix for some n, c ...
. The
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
of these
column vectors has dimensions
and rank
. The Gale transform replaces this matrix by a matrix
of dimension
, whose column vectors are a basis for the
kernel
Kernel may refer to:
Computing
* Kernel (operating system), the central component of most operating systems
* Kernel (image processing), a matrix used for image convolution
* Compute kernel, in GPGPU programming
* Kernel method, in machine learnin ...
of
. Then
has
row vectors, of dimension
. These row vectors form the Gale diagram of the polytope. There is a choice of which basis for the kernel to use, but it changes the result only by a linear transformation.
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
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
that contains the
origin
Origin(s) or The Origin may refer to:
Arts, entertainment, and media
Comics and manga
* Origin (comics), ''Origin'' (comics), a Wolverine comic book mini-series published by Marvel Comics in 2002
* The Origin (Buffy comic), ''The Origin'' (Bu ...
in its
relative interior
In mathematics, the relative interior of a set is a refinement of the concept of the interior, which is often more useful when dealing with low-dimensional sets placed in higher-dimensional spaces.
Formally, the relative interior of a set S (de ...
.
Equivalently, the subset of vertices forms a face if and only if there is no linear function that assigns non-negative values to the complementary vectors.
[, p. 170]
Linear diagram
Because the Gale transform is defined only up to a linear transformation, its nonzero vectors can be normalized to all be
-dimensional
unit vector
In mathematics, a unit vector in a normed vector space is a vector (often a spatial vector) of length 1. A unit vector is often denoted by a lowercase letter with a circumflex, or "hat", as in \hat (pronounced "v-hat").
The term ''direction vecto ...
s. The linear Gale diagram is a normalized version of the Gale transform, in which all the vectors are zero or unit vectors.
Affine diagram
Given a Gale diagram of a polytope, that is, a set of
unit vectors in an
-dimensional space, one can choose a
-dimensional subspace
through the origin that avoids all of the vectors, and a parallel subspace
that does not pass through the origin. Then, a
central projection
In mathematics, a projection is a mapping of a set (or other mathematical structure) into a subset (or sub-structure), which is equal to its square for mapping composition, i.e., which is idempotent. The restriction to a subspace of a proje ...
from the origin to
will produce a set of
-dimensional points. This projection loses the information about which vectors lie above
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.
Gale transforms and linear and affine Gale diagrams can also be described through the
duality
Duality may refer to:
Mathematics
* Duality (mathematics), a mathematical concept
** Dual (category theory), a formalization of mathematical duality
** Duality (optimization)
** Duality (order theory), a concept regarding binary relations
** Dual ...
of
oriented matroid
An oriented matroid is a mathematics, mathematical mathematical structure, structure that abstracts the properties of directed graphs, Vector space, vector arrangements over ordered fields, and Arrangement of hyperplanes, hyperplane arrangements o ...
s.
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.
[
]
Examples
The Gale diagram is particularly effective in describing polyhedra whose numbers of vertices are only slightly larger than their dimensions.
Simplices
A -dimensional polytope with vertices, the minimum possible, is a simplex
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
. In this case, the linear Gale diagram is 0-dimensional, consisting only of zero vectors. The affine diagram has gray points.[, p. 171.]
One additional vertex
In a -dimensional polytope with vertices, the linear Gale diagram is one-dimensional, with the vector representing each point being one of the three numbers , , or . 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.[
For , the only possibility is two points of each nonzero sign, representing a convex ]quadrilateral
In geometry a quadrilateral is a four-sided polygon, having four edges (sides) and four corners (vertices). The word is derived from the Latin words ''quadri'', a variant of four, and ''latus'', meaning "side". It is also called a tetragon, ...
. For , there are two possible Gale diagrams: the diagram with two points of each nonzero sign and one zero point represents a square pyramid
In geometry, a square pyramid is a pyramid having a square base. If the apex is perpendicularly above the center of the square, it is a right square pyramid, and has symmetry. If all edge lengths are equal, it is an equilateral square pyramid, ...
, while the diagram with two points of one nonzero sign and three points with the other sign represents the triangular bipyramid
In geometry, the triangular bipyramid (or dipyramid) is a type of hexahedron, being the first in the infinite set of face-transitive bipyramids. It is the dual of the triangular prism with 6 isosceles triangle faces.
As the name suggests, i ...
.[
In general, the number of distinct Gale diagrams with , and the number of combinatorial equivalence classes of -dimensional polytopes with vertices, is .][
]
Two additional vertices
In a -dimensional polytope with vertices, the linear Gale diagram consists of points on the unit circle
In mathematics, a unit circle is a circle of unit radius—that is, a radius of 1. Frequently, especially in trigonometry, the unit circle is the circle of radius 1 centered at the origin (0, 0) in the Cartesian coordinate system in the Eucl ...
(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 vertices, it is not completely trivial to determine when two Gale diagrams represent the same polytope.[
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. These include both the ]regular octahedron
In geometry, an octahedron (plural: octahedra, octahedrons) is a polyhedron with eight faces. The term is most commonly used to refer to the regular octahedron, a Platonic solid composed of eight equilateral triangles, four of which meet at ea ...
and the triangular prism
In geometry, a triangular prism is a three-sided prism; it is a polyhedron made of a triangular base, a translated copy, and 3 faces joining corresponding sides. A right triangular prism has rectangular sides, otherwise it is ''oblique''. A unif ...
. The linear Gale diagram of a regular octahedron consists of 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 . 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. The linear Gale diagram of a triangular prism consists of 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.
Applications
Gale diagrams have been used to provide a complete combinatorial enumeration
Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infini ...
of the -dimensional polytope with vertices, and to construct polytopes that have unusual properties.
Polytopes constructed in this way include:
* The Perles polytope
Perles may refer to
* Perles, Aisne, a commune in the Aisne department in Picardie in northern France
* Perles-et-Castelet, a commune in the Ariège department in southwestern France
*Perles, the French name for Pieterlen, Switzerland
* Alfred Per ...
, an 8-dimensional polytope with 12 vertices that cannot be realized with rational Cartesian coordinate
A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in ...
s. This polytope was constructed by Micha Perles
Micah (; ) is a given name.
Micah is the name of several people in the Hebrew Bible ( Old Testament), and means "Who is like God?" The name is sometimes found with theophoric extensions. Suffix theophory in '' Yah'' and in ''Yahweh'' results in ...
from the Perles configuration
In geometry, the Perles configuration is a system of nine points and nine lines in the Euclidean plane for which every combinatorially equivalent realization has at least one irrational number as one of its coordinates. It can be constructed from ...
(nine points and nine lines in the plane that cannot be realized with rational coordinates) by doubling three of the points of the Perles configuration, 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.
* The Kleinschmidt polytope Kleinschmidt is an occupational surname of German origin, which means "small smith", that is, a maker of small forged items and metal hand tools.''Dictionary of American Family Names''"Kleinschmidt Family History" Oxford University Press, 2013. Retr ...
, 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. 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.
* 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 figure
In geometry, a vertex figure, broadly speaking, is the figure exposed when a corner of a polyhedron or polytope is sliced off.
Definitions
Take some corner or Vertex (geometry), vertex of a polyhedron. Mark a point somewhere along each connect ...
s (the apex of its central pyramid) cannot be prescribed. Originally found by David W. Barnette, this example was rediscovered by Bernd Sturmfels
Bernd Sturmfels (born March 28, 1962 in Kassel, West Germany) is a Professor of Mathematics and Computer Science at the University of California, Berkeley and is a director of the Max Planck Institute for Mathematics in the Sciences in Leipzig sin ...
using Gale diagrams.[, Section 6.5(b) "Facets of 4-polytopes cannot be prescribed", pp. 173–175; , Proposition 5.1, p. 130; , Theorem 6.12, pp. 53–55]
* The construction of small "unneighborly polytopes", that is, polytopes without a universal vertex
In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. (It is not to be confused ...
, and "illuminated polytopes", in which every vertex is incident to a diagonal that passes through the interior of the polytope. The cross polytope
In geometry, a cross-polytope, hyperoctahedron, orthoplex, or cocube is a regular, convex polytope that exists in ''n''- dimensional Euclidean space. A 2-dimensional cross-polytope is a square, a 3-dimensional cross-polytope is a regular octahe ...
s 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.
Notes
References
*
*
*
*
* {{citation
, last = Ziegler , first = Günter M. , authorlink = Günter M. Ziegler
, contribution = Chapter 6: Duality, Gale Diagrams, and Applications
, doi = 10.1007/978-1-4613-8431-1_6
, isbn = 0-387-94365-X
, mr = 1311028
, pages = 149–190
, publisher = Springer-Verlag , location = New York
, series = Graduate Texts in Mathematics
, title = Lectures on Polytopes
, volume = 152
, year = 1995
Polyhedral combinatorics