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.
Definitions
Transform Given a d {\displaystyle d} -dimensional polytope, with n {\displaystyle n} vertices, adjoin 1 to the Cartesian coordinates of each vertex, to obtain a ( d + 1 ) {\displaystyle (d+1)} -dimensional column vector. The matrix A {\displaystyle A} of these n {\displaystyle n} column vectors has dimensions ( d + 1 ) × n {\displaystyle (d+1)\times n} , defining a linear mapping from n {\displaystyle n} -space to ( d + 1 ) {\displaystyle (d+1)} -space, surjective with rank d + 1 {\displaystyle d+1} . The kernel of A {\displaystyle A} describes linear dependencies among the n {\displaystyle n} original vertices with coefficients summing to zero; this kernel has dimension n − d − 1 {\displaystyle n-d-1} . The Gale transform of A {\displaystyle A} is a matrix B {\displaystyle B} of dimension n × ( n − d − 1 ) {\displaystyle n\times (n-d-1)} , whose column vectors are a chosen basis for the kernel of A {\displaystyle A} . Then B {\displaystyle B} has n {\displaystyle n} row vectors of dimension n − d − 1 {\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. Note that the vectors in the Gale diagram are in natural bijection with the n {\displaystyle n} vertices of the original d {\displaystyle d} -dimensional polytope, but the dimension of the Gale diagram is smaller whenever n ≤ 2 d {\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.
Linear diagram Because the Gale transform is defined only up to a linear transformation, its nonzero vectors can be normalized to all be ( n − d − 1 ) {\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.
Affine diagram Given a Gale diagram of a polytope, that is, a set of n {\displaystyle n} unit vectors in an ( n − d − 1 ) {\displaystyle (n-d-1)} -dimensional space, one can choose a ( n − d − 2 ) {\displaystyle (n-d-2)} -dimensional subspace S {\displaystyle S} through the origin that avoids all of the vectors, and a parallel subspace S ′ {\displaystyle S'} that does not pass through the origin. Then, a central projection from the origin to S ′ {\displaystyle S'} will produce a set of ( n − d − 2 ) {\displaystyle (n-d-2)} -dimensional points. This projection loses the information about which vectors lie above S {\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. Gale transforms and linear and affine Gale diagrams can also be described through the duality of oriented matroids. 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.
… excerpt ends here. Continue reading the full article.
