DIAGRAMS AND TRANSFORMS APPLIED TO CONVEX POLYTOPES by Erik Ring Lockeberg B.Sc. Queen's University at Kingston 1971 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in the Department of Mathematics We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA August 1973 In presenting th is thesis in pa r t i a l fu l f i lment o f the r e q u i r e m e n t s f o r an advanced degree at the Un ivers i ty of B r i t i s h Columbia, I agree t h a t the L ibrary shal l make it f ree ly ava i l ab le for r e f e r e n c e and study. I fur ther agree that permission for extensive copying of th is t h e s i s for scho la r ly purposes may be granted by the Head of my Department or by his representat ives . It is understood that copying o r p u b l i c a t i o n o f th is thes is for f inanc ia l gain sha l l not be allowed without my wri t ten permission. Department of The Univers i ty of B r i t i s h Columbia Vancouver 8, Canada Date ( i ) Abstract The aim of this paper i s to present a unified treatment of diagram techniques, p a r t i c u l a r l y as applied to problems concerning convex polytopes. An attempt i s made to summarize new results ( l i s t e d below) of M. Perl'es, G.C. Sh'ep'hard and P. McMullen. A diagram technique i s one of several methods for associating to a f i n i t e subset of a finite-dimensional Euclidean space a f i n i t e subset of the same c a r d i n a l i t y i n another Euclidean space, i n general of a dif f e r e n t dimension. The second subset i s a "diagram" or "transform" of the o r i g i n a l set. The o r i g i n a l set and i t s diagram are seen to be related i n a symmetrical way to the kernel and image respectively of a certain l i n e a r map. A problem concerning a f i n i t e set corresponds to a problem concerning the diagram which may be easier to solve, p a r t i c u l a r i f the diagram i s of low dimension. Gale diagrams are used to enumerate d-polytopes with d+3 v e r t i c e s , to construct an 8-polytope not r a t i o n a l l y imbeddable, to investigate the symmetry group of polytopes and to obtain results concerning pr o j e c t i v e l y unique polytopes. I t i s shown how p o s i t i v e diagrams may be used to investigate positive bases of Euclidean space. Zonal diagrams are used to investigate the neighbourliness of ce n t r a l l y symmetric polytopes. A diagram technique for dealing with polyhedral sets, including l i n e a r systems and metric properties of polyhedral sets. A geometric int e r p r e t a t i o n of the aff i n e transform, central transform and zonal diagram i n terms of regular polytope i s given. ( i i ) Table of Contents 1. Introduction 1 2. Linear Transforms 3 3. Affine Transforms 8 4. Applications of Diagrams to Polytopes with Few Vertices 25 5. P o s i t i v e Diagrams and Polyhedral Representations 41 6. Zonal and Central Diagrams • 46 7. A Geometric Interpretation of Diagrams 69 8. Polyhedral Representations 86 Bibliography 1 0 0 ( i i i ) L i s t of Figures Fig. 1 Some 3-polytopes and their Gale diagrams 14 Fig. 2 "Pushing" and " p u l l i n g " the vertices of a polytope 21 Fig. 3 Diagram for theorem 4.1 30 Fig . 4 Diagram for theorem 4.1 31 Fig. 5 Diagram for theorem 4.7 36 Fig. 6 The 9-point configuration with, cross-ratio (A,B;E,F) = |(3-/5) 39 Fig. 7 The 9-point configuration with cross-ratio (A,B;E,F) = ^ 3+/5) 39 3 Fig. 8 The 4 positive bases of E and th e i r positive diagrams 44 Fig. 9 5 centrally symmetric 3-polytopes with 2(d+l) vertices and t h e i r central diagrams .50 Fig.10 The regular octahedron and i t s Gale diagram 56 - 1 -I, Introduction . In the past few years, a group of related notions known c o l l e c t i v e l y as diagram techniques have been developed. These techniques may be regarded as variations on a single theme: to a set of n points spanning d. d-dimensional Euclidean space E ' corresponds a set of n points i n E n ^ , the l i n e a r transform of the o r i g i n a l set. This idea i s apparently due to Whitney [14] . He did not apply i t , as we w i l l , to problems i n the realm of convexity and related topics. There i s a correspondence between the properties of the o r i g i n a l set and the properties of the transform, but often the corresponding properties of the transform are di f f e r e n t from those of the o r i g i n a l . The properties of the transform or diagram may give a more i n t u i t i v e picture than the original"., as i n the study of p o s i t i v e bases. Furthermore, the diagram or transform may l i e i n a space of low dimension, aiding i n t u i t i o n and f a c i l i t a t i n g computation. Some of the problems which have been attacked using diagram techniques are enumerating combinatorial types of polytopes, zonotopes and arrangements of hyperplanes; computing the possible neighbourliness of centra l l y symmetric polytopes; and proving that there exists combinatorial types of polytopes a l l of whose vertices cannot be r a t i o n a l points. H i s t o r i c a l l y , the idea may be seen i n Motzkin [11] and Davis [1]. Gale [2] was the f i r s t to develop diagrams e x p l i c i t l y . Perles, published i n Grlinbaum [3], used diagrams to enumerate combinatorial types of s i m p l i c i a l d-polytopes with d + 3 vertices and to construct a polytope not r a t i o n a l l y imbeddable. Subsequently, McMullen and Shepard applied variants of the l i n e a r transform to study symmetric polytopes, zonotopes, polyhedral sets and positive bases. - 2 -The exposition i n sections 2,3 and 4 r e l i e s h e avily on GrUnbaura, and work of McMullen and Shephard, both published and unpublished. 3 -2. Linear Transforms In t h i s s e c t i o n we w i l l . d e f i n e and discuss the l i n e a r transform of a f i n i t e set of points i n . There are many d i f f e r e n t ways to define the l i n e a r transform, a l l of which seem a r t i f i c i a l . One way to glimpse the basic idea i s to consider a l i n e a r map T from E N onto E . Then the image under T of the ordered set of n standard basis vectors of E N i s an ordered set X of n points spanning the image of T. C l e a r l y any ordered set of n points spanning E^ may be represented i n t h i s way. The l i n e a r transform of X associates with X an ordered set of n points i n the kernel of T , an (n-d)-space. P r e c i s e l y how this a s s o c i a t i o n i s done we w i l l see at the end of th i s s e c t i o n . Let us begin with an algebraic d e f i n i t i o n . Let X = (x^ x n) cl d be an ordered subset of E spanning E l i n e a r l y . The elements of X need not be pairwise d i s t i n c t . Let L(X) be the set of l i n e a r dependences of X ; L ( X ) =' {X N , X )|A 1X + ... + X x = 0}. 1' n 1 1 1 n n Cl e a r l y L ( X ) i s a l i n e a r subspace of E N and i s of dimension n-d since X spans E^ . Therefore we may choose a basis a. = (a... , ...» a. ), i = 1, .... n-d • l i i i n which we write as the rows of a matrix / a l l L = l l n \ (n-d)l a ( n - d ) n / ' Now define the l i n e a r transform X^ = (x^, , x ) . to be the ordered n set of columns of L considered as vectors of E n-d x. l ( a l i > ' a ( h - d ) i ) j 1 ~ !> •••> n Thus the associated matrix hi \ n n/ /x 11 \ X n l , X l d X l l ' Xnd X n l ln-d x im-d where x.. = a.. i l s a t i s f i e s I) M^OO 1 S non-singular and II) the f i r s t d columns and the l a s t n-d columns are orthogonal; that i s , n • I i = l x. . x i j i k 0 , j =1, d; k = 1, n-d Conversely any set (x^ , •••» x ) such that ^ ( X ) s a t i s f i e s I) and II) arises from a suitable choice of basis of L(X) i n the manner described above. We immediately observe: 1) there i s a canonical b i j e c t i o n from X to taking x. to x. x x 2) since L(X) contains n-d l i n e a r l y independent vectors, so does X^ , implying that X^ spans E n ^ l i n e a r l y ; 3) the elements of X^ need not be pairwise d i s t i n c t ; 4) i f n < 2d , X^ l i e s i n a space of dimension smaller than d ; 5) from the symmetry of properties I) and II) , X i s a l i n e a r transform of X^ and the f i r s t d columns of M^CX) form a basis of LCX^); 6) i f {x^, x^} i s a li n e a r transform of {x^, x^ - 5 -then {M /X , , . , . . M } • i s a l i n e a r transform of 1 1 n n ' {M.x,, ..., M x }, M. 4 0 . 1 1 n n . x . Since the choice of basis of L(X) i s a r b i t r a r y , X^ i s not uniquely t « defined. However i f we choose another basis {a T, a ,} with 1 ' n-d corresponding matrix A' , there i s a non-singular (n-d)X(n-d) matrix C = ) > defined by such that Therefore , n-d a. = 1 Cya. , j = l A' = CA . A = A C so We have proved THEOREM 1: I f = {x1', x^} and = { x ^ are. l i n e a r transforms of X £ E there i s a unique non-singular l i n e a r transformation ,n-d „n-d T : E E such that x. = x.T , i = 1, . .., n . Since X i s a l i n e a r transform of X^ , i f X = ( x ^ , X n ) and Y = {y^> y ) have the same l i n e a r transform, there exists a non-singular li n e a r transformation of taking x^ to y^ , i =. 1, . .., n . We then say X and Y are l i n e a r l y equivalent. For future reference, l e t us also prove THEOREM' 2: A subset X C i s i n l i n e a r l y general po s i t i o n i f and only n-d i f X a E i s i n l i n e a r l y general position. - 6 -Proof: I f X = {x^, .. ., x^} i s not i n l i n e a r l y general p o s i t i o n there are d points of X , which we may suppose are x^,...,x^, l y i n g i n a hyperplane through 0 with normal (u^, u^) ^ 0 . Since U - X . + . . . + u . x , + 0 . x , , - - , + 1 1 d d d+1 + 0.x = 0 , (u^, u^, 0, . .., 0) e L(X) and we may extend t h i s vector to a basis of L(X) such that V x ) / x l u l ^12 x ln-d u . x d2 x d+12 X X nn-d, Therefore x ^ + - p •••> x n a r e vectors l y i n g i n the hyperplane through 0 i n E n ^ normal to (1,0,...,0) , implying X^ i s not i n l i n e a r l y general p o s i t i o n . The converse i s proved i d e n t i c a l l y . For any W £ x , define the coset of W i n X^ to be W =' {xeX.. | x^X}. A basic theorem of a type we .w i l l see again i s THEOREM 3: A set X i s supported i n W by a hyperplane through 0 , i f and only i f 0 e r e l i n t conv W . Proof: Without loss of ge n e r a l i t y , w r i t e X = { x ^ , x^} and W = { } , r < n . There i s a hyperplane through 0 with equation <x,u> = 0 such that <x^, u> • = 0 , i = 1, . , r <x.,u> = a. > 0, i = r+1, n Thus (0,...,0,a r + 1, a ) e L(X) . Therefore a n x ,. + ...+ a x = 0 r+1 r+1 n n and i f a ~ a , . . + . . . + a , r+1 n fa . J a f x ,, + ... +(a /a)x =0 r+1 r+1 n n i s a l i n e a r combination of W wi.th s t r i c t l y p o s i t i v e c o e f f i c i e n t s , implying 0 E r e l i n t conv W . The argument i s r e v e r s i b l e . The l i n e a r transform of X = {x,, x }< E d can be defined 1 n — more concisely by considering the following diagrams: B : > X 0 > kerJ = E n ' d — £ - * E n — ^ > E d ; > 0 0 < E • <-^— E < — E < 0 X < B* The standard basis {H^, . . . , £ • } ' of E n i s . denoted B , and n* B* = A*} i s the corresponding dual basis of the dual space E The l i n e a r maps are defined by: (£. )J= x.' i = 1 n ; K i s an isomorphism onto the kernel of A, per A; T T J and K are the respective transposes. Then : i s defined by T — . (&i*)K= x , i = 1, ..., n . Since ' KJ = 0 <==> J T K T = 0 , X i s c l e a r l y a l i n e a r transform of X^ . To see that t h i s d e f i n i t i o n i s equivalent to the o r i g i n a l , note T that the matrices of J and K with respect to the standard bases are - 8 -respectively and Now, the f i r s t d columns and the l a s t n-d columns of ^ 0 0 are orthogonal i f and only i f / \ n / = 0 <=> (KT) T J = o <=> K J = 0 . The l a s t statement i s true by the d e f i n i t i o n of K and J , and since rank K + rank J = n ., M^CX) i s non-singular and therefore the two'. d e f i n i t i o n s are equivalent. We w i l l return to t h i s conception of l i n e a r transform i s the section on representations of polyhedral sets. 3. A f f i n e Transforms We have seen that two sets have the same l i n e a r transform only i f they are l i n e a r l y equivalent. We s h a l l carry out an analogous procedure with a f f i n e dependences instead of l i n e a r dependences to define the affi n e transform . Two sets, w i l l have the same affi n e transform only i f they are a f f i n e l y equivalent. Let X = (x^, X r ) , an ordered subset of . spanning E^ a f f i n e l y . Let A(X) be the vector space of af f i n e dependences of K . - 9 -Thus ' A(K) ='-{(A,, A )|(X..x. + ... + A X=-0, A. + ... + A =0}. 1' ' n 1 1 1 n n ' 1 n Observe that A(X) may be i d e n t i f i e d with L(Y) where Y = ( ( x 1 , l ) , ( x n , l ) ) < E d + 1 . Since X spans E d a f f i n e l y i f and only i f Y spans E d l i n e a r l y , the dimension of A(X) i s n-d-1 . Denote the l i n e a r transform of Y by YT . Define the af f i n e transform X, of X to be YT . The associated L A L matrix i s defined to be M A(X) = M^Y) where X, = Y. = (x.. , ..., x ) A A 1 n X l 1 X l x l x n n We observe: 1) there i s a canonical b i j e c t i o n from X to X taking x^' to x^ ; 2) the centroid of X. i s 0 ; A 3) X^ spans E° d ^ a f f i n e l y ; 4) the x_^ need not be d i s t i n c t ; and 5) i f n <_ 2d, X^ l i e s i n a space of lower dimension than X . To prove 2), note that the l a s t n-d columns of M^(X) are orthogonal to the column of 1's. Therefore x, + ... + x =0, i . e . the centroid of 1 n X^ i s 0. To prove 3), since X spans E n d ^ l i n e a r l y , for any n—d—1 . . -x c E , there are (j . , .... y not a l l zero such that x=\i x +...+U x . I n i 1 i n n 1 1 ' Let a = —(u, + . . . + ]i ) . Then n n 1 n x = p,!:. + •,,.+ -p x + na(x- + . . . + x ) 1 1 n n 1 n n ^(l^+a);^ + ... + (yn+a) x n > I (Y±+<0 = 1 , i = l so X spans E n d 1 a f f i n e l y . Corresponding to property 5) of the l i n e a r transform, i t i s easy to check that X i s an a f f i n e transform of X i f and only i f the'centroid of X i s 0 . Clearly, any f i n i t e subset A Z of E n d with centroid 0 spanning E n d ^ l i n e a r l y i s an a f f i n e transform of Z. . A The a f f i n e transform i s t r a n s l a t i o n invariant i n the sense that X i s an a f f i n e transform of X + b for any b e E d . This i s true because A(X) = A(X+b) . For i f (X 1, .. . , X^) e A(X) , A , x , + . . + X x = 0 and X. + ... + X - 0 . 1 1 n n 1 n — > X,(x,+b)'+ ... + X (x +b) = 0 . 1 1 n n Therefore A(X). c£ A(X+b) and since the dimensions are the same, A(X) = A(X+b) . Suppose X , with centroid 0 , and X' have the same affi n e transform X, = {x„ , .... x } . Then for some b e E d , X' + b has A 1 n centroid 0 , implying that X and X'+ b are l i n e a r l y equivalent. Thus X and X 1 are a f f i n e l y equivalent. We have proved THEOREM 1; Two subsets X, X' S E d are a f f i n e l y equivalent i f and only i f X A and X\ are l i n e a r l y equivalent. A set of points X <C E d i s said to be i n a f f i n e l y general p o s i t i o n , abbreviated to "general p o s i t i o n " , i f no subset of X with less than d + 1 points i s a f f i n e l y dependent, or equivalently, that every k-pointed subset of X , K < d + l , i s the set of vertices of a (K-l) - simplex. . In our case, X has at least d+1 points, so X i s i n general p o s i t i o n i f and only i f every d+1 points of X forms the set of v e r t i c e of a d-simplex. The a f f i n e analog to theorem 1.2,is THEOREM 2: A set X C. E d i s i n a f f i n e l y general p o s i t i o n i f and only i f - 11 -X i s i n l i n e a r l y general p o s i t i o n . A Proof: The set X = (x^, . .., x ) • i s i n a f f i n e l y general p o s i t i o n i f and only i f Y = ' ( ( x l ) » ( x ^ j l ) ) i s i n l i n e a r l y general p o s i t i o n , which i s true i f and only i f Y= ( ( x ^ , l ) , ( x ^ l ) ) i s i n l i n e a r l y general p o s i t i o n , which i s true i f and only i f Y = X i s i n l i n e a r l y Xi A general p o s i t i o n . Define a f a c i a l subset of X c: E d to be any set of the form X n H , where H i s a hyperplane supporting X . If S i s the set of v e r t i c e s of a polytope, the f a c i a l subsets of X are the empty set and sets of the form v e r t F where F i s a proper face of P . The f a c i a l sets are characterized by THEOREM 3: For any f i n i t e subset X spanning E d a f f i n e l y , S £ X i s a f a c i a l s e t i f and only i f 0 e r e l i n t ' conv S . Proof: Without loss of gener a l i t y , l e t X = (x.^, x ) , S = (x^,...jX^) , r < n. I f S i s empty, S = X and.since 0 i s the centroid of X , 0 e r e l i n t conv X . I f S ^ <J> , there i s a hyperplane with equation . <x,u> - a = 0 such that .<x. ,u>-. ct = 0, i = l , . . . . , r <x.,u> - a = 3. > 0, i = r+1, n . x x T These equations imply that (0, 0 , 3^ .-^ , •••» 3n) i s a l i n e a r combination (by the coordinates of u and 3) of the columns of K M Therefore (0, 0, 3 r + 1 , ..., 3 n ) e L(X ) . I f - 11 -• B = P r f l + . . . + B n then i s a convex combination with s t r i c t l y p o s i t i v e c o e f f i c i e n t s , implying that 0 E r e l i n t conv ^, •••> x^} = r e l i n t conv S . C l e a r l y , given 0 expressed as a convex combination of S, we may reverse the above procedure to f i n d a hyperplane H supporting X such; that S = X H H , proving the theorem. In the case of n = d+1, X i s the set of v e r t i c e s of a d-simplex and the a f f i n e transform consists of d+1 points at 0 . Every proper subset i s a f a c i a l set. I f X = vert P , where P i s a pyramid with apex x_^ , a l l the other points of X l i e i n some hyperplane. Thus X\.{x^} i s a f a c i a l set and so X J = 0 . I f X = vert P , where P i s a d-polytope , every {x^} i s a face, so 0 e r e l i n t conv (X \ {x.}) , i - 1, ..., n . In f a c t t h i s property A 1 characterizes transforms of the v e r t i c e s of a polytope, a theorem which i t i s more convenient to state i n the form: n*~ d — 1 THEOREM 4: A set X <_ E i s the a f f i n e transform of the set of v e r t i c e s of a polytope i f and only i f a) the centroid of X i s 0 ; b) every open halfspace with 0 on i t s boundary contains at lea s t two points of X. Proof: Since " 0 e r e l i n t conv (X \ {x}) , for a l l x e X" is. e q u i v a l e n t to b)' , i t remains to prove the "only i f " . I f the centroid of X i s 0 , X i s the a f f i n e transform of some subset X of E d . I f b). holds, 0 e r e l i n t conv (X \ {x.^}), i = so each {x ±} i s a f a c i a l subset, that i s , a vertex, of conv X . Since conv X i s a polytope P , X i s exactly the set of vertices of P . For examples of affi n e transforms, see F i g . 1. Theorem 3, characterizing f a c i a l s e t s'in terms of the af f i n e transform, motivates the following d e f i n i t i o n . Two subsets X and X' of E d are said to be isomorphic i f there i s a b i j e c t i o n <{> between X and X' such that for every S £ X 0 e r e l i n t conv S <==>; 0 E r e l i n t conv (•(S)j> Thus i f X and X' are the set of vertices of the d-polytopes P and P' , P and P' w i l l be of the same combinaorial type i f and only i f X, and X' are isomorphic to X. = (x,. x ) . The b i j e c t i o n of the A A r A 1 n J d e f i n i t i o n takes x. to x. . For any set X = ( x n , .... x ) and x x 3 . 1 n n-tuple y = (y^, V^) of s t r i c t l y p o sitive numbers, the set X = (y,x,, .... y x ) i s isomorphic to X . Thus every polytope P has y l i n n •V. /S a standard Gale diagram i n which f o r a l l x e P , x ^ 0 , we have ||x[| = 1 . For instance, a standard Gale diagram for a d-polytope with d+2 vertices consists of at least two points at +1 , at least two points at -1 and points at 0 . In section 4, standard Gale diagrams w i l l be used to enumerate combinatorial types of d-polytopes with d+2 and d+3 ve r t i c e s . See Fig. 1 for examples of standard Gale diagrams. Often we wish to find the af f i n e transform of a proper subset S of a given set X . For instance, i f F i s a face of a polytope P , we would l i k e to be able to find the transform of vert G (considered as a subset of aff F) from the transform.of vert P . In general X^ and w i l l not be of the same dimension, so that removing points of X^ - 14 -X , , X « Figure 1 Some 3-polytopes and t h e i r Gale diagrams. The polytope i s on the l e f t , the diagram on the r i g h t . In these examples the diagram i s an a f f i n e transform. not corresponding to points of S w i l l not n e c e s s a r i l y leave an a f f i n e transform of S .-THEOREM 5: Let S £ X S E d , S 4 X , card X = n . Let L = l i n S . Let TT : E n d •+ L" be^orthogonal p r o j e c t i o n onto the orthogonal subspace to L . Then TT (X^\ S) i s an a f f i n e transform of X^" . Proof: Without loss of gene r a l i t y , l e t X = (x^, x ^ ) , S = (x^,...,x^) r < n . I f -(A , A ) e A(S) , then (A , A r,0, ...,0) e A(X). Thus we may regard A(S) as a l i n e a r subspace of A(X) . In f a c t A(S) =' { ( A 1 A n) E A ( X ) | A r + 1 = ... = A n = 0} . Suppose dim A(S) = K . Then we may extend a basis of A(S) to a basis of A(X) , and write t h i s basis ..as. the columns of a matrix A B 0 C, ^ r 1 V } r } n-r K n-d-l-K. w, the rows of (0 C) are p r e c i s e l y ( x r^» •••» x n ) a n < ^ s o L = l i n { x r + 1 , x n> = {(€]_, £ n _ d _ i ) E E U1 = = 5k=0} •he rows of A are an a f f i n e transform of S and the rows of (A,0), .at i s X^ \ S , span . . . . 5 ^ ) 1 ( 5 ^ . . . = Kn_d_± - 0} = L \ Therefore, the rows of A are the images of the rows of (A,B) under TT and the theorem i s proved. Using theorem 5 we ma}r deduce THEOREM 6: I f S £ X , S 4 X , then, f o r an a f f i n e transform X A , dim S = dim l i n S + d - card S . Proof: Suppose, without loss of g e n e r a l i t y , that X = ( x ^ , x ) , S = (x n, x.)> r < n and dim S = j . Since - 16 -dim A(S) = r - j - 1 , we have, Using theorem 5, dim l i n S + r - j - l = n - d - l Therefore, dim l i n S + d - card S = (n-d-1) - (r-j-1) + d - (n-r) = -3 = dim S . The l i n e a r version of theorem 6 i s an ea s i l y proved Corollary'; I f S C X , S ^ X , then for a l i n e a r transform X ^ , dim l i n S = dim l i n S^=fd - card S . Theorems 5 and 6 are also true for Gale diagrams as w e l l as af f i n e transforms. Corollary : I f X = vert P for a d-polytope P , then for any S * conv S i s a facet of P i f and only i f 0 e r e l i n t S and conv S i s a simplex. Proof: Using theorem 6 , since dim S = dim conv S = d - 1 , dim S = dim l i n S + d - card S <==> d - 1'= dim l i n S + d - card S <==> card S= dim l i n S + 1 . Since 0 e r e l i n t conv S , conv S i s a simplex. The argument may be reversed. THEOREM' 7 ; I f X = vert p for a d-polytope P , then for any S C. X , conv S i s a s i m p l i c i a l face of P i f and only i f 0 e r e l i n t conv S and S spans E n < d l i n e a r l y . Proof: A face conv S i s a simplex i f and only i f every subset of S is the set of vertices of a face of P . I f S l i e s i n a hyperplane H through 0 , there must be a point x ^ j ^ o n e . o f the open half-space 3 determined by. H . Then -.17 -0 £ r e l i n t conv (S \ {x}) implying that conv (S \ { x » i s not a face of P , a co n t r a d i c t i o n . Therefore S spans E n d ^ . The argument may be reversed. I f X spans E d , conv X i s a d-polytope P with. v e r t P ^ X . The points x e X such that P = conv (X \ {x}) are exactly those points such that a hyperplane through 0 separates x from \ {x} . For any such redundant point x , theorem 5 may be used to f i n d an a f f i n e transform of X \ {x} . Repeating t h i s process e v e n t u a l l y . y i e l d s a transform of v e r t P . C l e a r l y , although t h i s procedure may be c a r r i e d out i n many ways, the r e s u l t i s unique up to l i n e a r equivalence. Let P be a d-polytope, and F a face of P . Then P/F . i s defined to be a polytope ( a c t u a l l y a combinatorial equivalence c l a s s of polytopes) whose f a c e - l a t t i c e i s isomorphic to ' {G e 3(P) | F & G } . If F = {x} i s a vertex of P , the vertex-figure of P at x i s a (d-1)-polytope H f] P , where H i s a hyperplane s t r i c t l y separating {x} from a l l other v e r t i c e s of P . I t may be shown that the vertex-f i g u r e of P at x i s combinatorially isomorphic to P/{x}. Finding Gale diagrams of vertex-figures i s very simple. THEOREM 9: Let F be a proper face of a polytope P . I f vert P = X, and -text F = S , S i s a Gale diagram with respect to l i n S of a set whose convex h u l l i s combinatorially isomorphic to P/F . In p a r t i c u l a r , X \ {x} i s a Gale diagram of a set whose convex h u l l i s combinatorially equivalent to the vertex-figure of P at X . Proof: Let Z be a set whose Gale diagram i s S . Note that since. 0 e r e l i n t conv S , S i s indeed a Gale diagram. ' Let S = (x , ..., x ) - 18 -and Z = {Z,, ..., Z } . For any R C S , l e t R' = {Z.eZl x.eS} . Let 1 r — 1 - i G be a face of P with v e r t G = T . Then F, £ G i f and only i f 0 e r e l i n t conv T , which i s true i f and only i f T' i s a f a c i a l set of Z , G + T 1' i s a l a t t i c e isomorphism of P/F with conv Z , concluding the proof. This nearly concludes the catalogue of correspondences between the properties of a set and the properties of i t s a f f i n e transform. Let us now digress to consider the r e l a t i o n s h i p between the l i n e a r and the a f f i n e transform of the same set. This w i l l shed some l i g h t on the question of how the a f f i n e transform responds to a perturbation of the o r i g i n a l set. The next theorem shows that i s a p a r a l l e l p r o j e c t i o n of X^ onto a hyperplane i n E n d . THEOREM 1 0 : For any X with a f f X = E d , l e t Z be the centroid.of X^ . Then Z f 0 and X^ = X^TT , where ir i s p a r a l l e l p r o j e c t i o n onto a hyperplane containing 0 not through Z taking Z to 0 . Proof: Let a basis of L ( X ) be L = a l l ... a l n a n - d l ... an-dnj where the f i r s t n-d-1 rows comprise a basis of A(X) . . By v i r t u e of the correspondence between a change of basis of L(X) and non-singular l i n e a r transformations of E n d ^ , L corresponds to some l i n e a r transformation X^T of the given l i n e a r transform. For s i m p l i c i t y , assume that L corresponds to X^f , i . e . the columns of L are the elements of X^ • Now. Z = - ( a n i + ... + a., , .... a „ + ...+ a , ) = — ( 0 , . . . , 0,Z ) , n 11 In n-dl n-dn n n where Z^ ^ 0. This i s true since the l a s t row i s l i n e a r l y independent of the others, and i f Z = 0 , would be an a f f i n e dependence of X , n implying that the rows of L form a basis of n-d vectors f o r A(X), a co n t r a d i c t i o n . Thus X, = (y, ,...,y ) = ((x..,a , . . ) , . . . , (x ,a , )) , L J 1 ' J n 1 n-dl n n-dn where X^ = (x^, x ). Thus X^ i s the perpendicular p r o j e c t i o n TT^ of X^ onto the hyperplane normal to Z. P a r a l l e l p r o j e c t i o n onto any other hyperplane not through Z gives a l i n e a r l y equivalent s e t which i s therefore also an a f f i n e transform of X . I f i t was necessary to apply an non-singular l i n e a r transformation T to X^ to get a basis f o r L(X) of the required type, we have shown that IT = Tw^T takes X^ to X^ and i s a p r o j e c t i o n of the type described i n the theorem. As before, l e t X = (x^,...,x n) _< E d and f o r any n-tuple y = (u,,...,y ) of s t r i c t l y p o s i t i v e numbers l e t X" = (y. x_ ,. . . ,y x ). 1 ' n J r y 1 1 n n Re c a l l that i f 2L = (x , ...,x )., then X = (y "'"x ,y 0^x 0,.. ,y ."'"x ) . JL x n yi-t J_ x z £. n n Let us consider the s p e c i a l case y = (y^,1,...,1). Let Z and Z be the centroids of X, and X"_ r e s p e c t i v e l y . Let H be a y L yL hyperplane through 0 containing neither Z nor Z^, and TT p a r a l l e l p r o j e c t i o n onto H taking Z to 0. By the previous theorem, X^ir i s an af f i n e transform of X with 0 = ZTT as o r i g i n and X"_ tr i s an a f f i n e yL transform of X considering Z IT as o r i g i n . Since y y Z = —(x, + ... + x ) and n 1 n Z" = — (y ^x. + x 0 + ...•+ x ) , y n 1 1 2 ii Z • « Z + - ( v " 1 - ! ) ! . y n 1 1 Since this r e l a t i o n i s preserved by p r o j e c t i o n , this d i s c u s s i o n proves 20 THEOREM 11: I f X x = ( L, ..., x ) i s an a f f i n e transform of A 1 n X = ( x p . .. ,x n) , then (x^, y ^X^» • • > x^) i s an a f f i n e transform, considering ^ - ( y ^ - l ^ as o r i g i n , of ( x ^ M j ^ , • X R ) . An example i s shown i n F i g . 2. A d d i t i o n a l l i g h t i s shed upon t h i s s i t u a t i o n by considering the case 0 e r e l i n t conv X . Then, since there i s an expression 0 = A,x, + ... + A x , A.>0 f o r i = l , . . . , n . 1 1 n n ' i » • > I f t h i s l i n e a r dependence i s extended to a basis of L(X) , the r e s u l t i n g X^ w i l l consist.- of vectors for which one coordinate, say the f i r s t , i s s t r i c t l y p o s i t i v e ; that i s there i s a hyperplane H through 0 such that X i s contained i n one of the corresponding open half-spaces, say J-j + -H . Since X_ T consists of s t r i c t l y p o s i t i v e multiples of the elements yL of X T , X _ H + . Furthermore L yL pos ^ = pos X y L and pos X O H + U {0} . -Li This shows that i f 0 e r e l i n t conv X , pos X^ i s a pointed cone supported at 0 by a hyperplane. (A pointed cone i s a cone with a s i n g l e apex. The set of apices A(C) of a set C i s A(L) =' {a e c| (l-A)a + Ac e C f o r a l l c e .C and A >_ 0}.) I f H i s such a hyperplane, the centroid Z^ of X ^ cannot l i e i n H , so p a r a l l e l p r o j e c t i o n of X onto H or any p a r a l l e l hyperplane w i l l y L y i e l d X , with appropriate choice of o r i g i n . Let H' be a hyperplane uA p a r a l l e l to H l y i n g i n H . Then by choosing y appropriately, X T £~ II* . Thus X T i s i n v a r i a n t under the p a r a l l e l p r o j e c t i o n IT yL yL 1 r J onto H' i n the d i r e c t i o n Z" . For any other X . ^ the points of X _ TT y J v vL w i l l be p o s i t i v e s c a l a r multiples ( i n H' , considering Z^ as o r i g i n ) of - 21 -the points of X . Since a Gale diagram of X v i s a Gale diagram of VA :ly ] Z IT E r e l i n t conv X X for any s t r i c t l p o s i t i v e a , we may assume v . uA *• Therefore X ^ i s a Gale diagram of every X^ , with appropriate choice of o r i g i n i n r e l i n t conv X A , Conversely, any point i n r e l i n t conv X^ A serves as the o r i g i n f o r some X^ . The r e s u l t s of t h i s d i s c u s s i o n are summarized by THEOREM 12: Let X £ E d , 0 e r e l i n t conv X . Then there i s a Gale diagram X of X such that f o r every X^ , u s t r i c t l y p o s i t i v e , there i s a point Z E r e l i n t conv X such that X i s a Gale diagram of X^ with Z considered as origin^and conversely. These ideas w i l l be developed i n a d i f f e r e n t way i n the section on representations of polyhedral sets. A p r o j e c t i v i t y K of E d. i s a map defined by xL + b xK = , <x,u>+a where L i s a l i n e a r transformation of E d , b and u are vectors of E d and a e R , such that <x,u> + a i s not zero f o r every x E E d . If the matrix (I f) i s i n v e r t i b l e , K i s said to be non-singular. This condition i s equivalent to r e q u i r i n g that K have an inverse (which i s also a p r o j e c t i v i t y ) . d The p r o j e c t i v i t y K i s defined on a l l points of E not i n the hyperplane with equation <x,u> + a = 0 . If X < E d and <x,u> + a f 0 f o r a l l x e X , K i s sa i d to be admissible 13 „d for X . Two sets X,Y E d are protectively equivalent i f there i s a b i j e c t i o n <f> from X to Y and a non-singular p r o j e c t i v i t y K admissible for X such that xK - x<j> f o r . a l l x e X . In order to characterize pr o j e c t i v e l y equivalent sets in.terms of th e i r a f f i n e transforms, define two transforms X = {x^, . .., x^ } and X' = { x \ , x'} to be equivalent i f there i s a non-singular l i n e a r 1 n —* transformation L , s t r i c t l y p o sitive scalars y^, y R and a b i j e c t i o n from X to X' (which we may assume takes x_^ to x!. ) such that y.x.L = x! , i = 1, n . a i l ' THEOREM 13: I f X = vert P and X' = vert P f for d-polytopes P and-P' i n E d , P and P' are proj e c t i v e l y equivalent i f and only i f X' and X^ are equivalent. Proof: Let X = (x., ..., x ) , X' = (x', x') . Assume that X. 1' n ' 1 n A and X' are equivalent. Since the affine transform i s defi^Heclonly up to lin e a r equivalence, assume without loss of generality that the l i n e a r transformation L appearing i n the d e f i n i t i o n of equivalence i s the i d e n t i t y . Thus the matrix M = y,x \ x' 1 y x \ n -n n \ x" 1 x' / \ n n' for scalars y^, .v . , y n where V± > 0 , i = 1, ..., n . By the d e f i n i t i o n of transform, M s a t i s f i e s I) the f i r s t d+1 columns are orthogonal to the l a s t n-d-1 columns and II) the matrix i s non-singular . Now, M s a t i s f i e s I) and II) i f and only i f / y l X « yx xx\ \ y x' y x / ^ n n n n ' s a t i s f i e s I) and II) . To see t h i s , note that I) may be checked d i r e c t l y . As f o r II) , observe that { ( x 1 , l ) , ..., ( x n , l ) } d+1 spans E l i n e a r l y i f and only i f { y 1 ( x ^ , l ) , y n ( x ^ , l ) > d+1 . spans E l i n e a r l y , since the y^ are non-zero. Thus the f i r s t d+1 columns are l i n e a r l y independent. Since the l a s t n-d-1. columns are l i n e a r l y independent, I) implies II) . That i s , both ( ( x 1 , l ) , ( x n , l ) ) and ( y ^ x ^ l ) , y n(x^.,l)) are l i n e a r transforms of . Therefore there i s a non-singular (d+ 1 )x(d+ 1 ) matrix B , which we write i n the form T V ' . . B = A u J c b a , a e R; u,b e E (where A i s a dxd matrix) such that O ^ D B = y i ( x ! ^ , l ) , • i = 1, n . This gives x A + b = y.x!, where y.• = <x.,u> + a , i - 1 , •.•> n i 1 1 i i Thus x.A + b i ^ i ~ <;x., 1> + a i , i = 1, .. . , n i e s t a b l i s h i n g the p r o j e c t i v e equivalence of X and X' .. The arg •ument i s - 25 -reversible to establish the implication i n the opposite d i r e c t i o n . Theorem 13 completes the sequence of theorems establishing correspondences between classes of polytopes and classes of transforms of their sets of ver t i c e s . Abbreviating "the affine transform (Gale diagram) of the set of vertices of a polytope "to" the transform (Gale diagram)' of a polytope" , these correspondences are 1) two polytopes are a f f i n e l y equivalent i f and only i f t h e i r transforms are l i n e a r l y equivalent; 2) two polytopes are pr o j e c t i v e l y equivalent i f and only i f t h e i r transforms are equivalent; and 3) two polytopes are combinatorially isomorphic i f and only i f x t h e i r Gale diagrams are isomorphic. 4. Applications of Diagrams to Polytopes with Few Vertices In t h i s section the results of the previous section w i l l be applied to problems involving polytopes with d+2, d+3 or d+4 ve r t i c e s . Since the af f i n e transform and.Gale diagram of such polytopes are one-, two - or three- dimensional, the diagram i s easier to work with than the o r i g i n a l polytope. Some of these problems have been solved by other means, but i f diagrams are used, the solution i n simpler and the pr i n c i p l e s involved more conspicuous. The four problems to be attacked (with varying degrees of success) are 1) how many combinatorial types (combinatorial isomorphism classes) are there of d-polytopes with n vertices? of s i m p l i c i a l d-polytopes :'with n vertices? 2) which combinatorial types contain a representative P i n . - 26 -which ,the combinatorial symmetry group i s realized by a group of congruences of P ? 3) for which combinatorial types i s i t true that any two polytopes of that combinatorial type must be p r o j e c t i v e l y equivalent? 4) does every combinatorial type contain a representative a l l of whose vertices have r a t i o n a l coordinates? Questions 1), 2) and 3) are solved for d-polytopes with d+2 or d+3 v e r t i c e s . Question 4) i s answered i n the negative by constructing a counterexample, an 8-polytope with 12 vertices not a l l of which may have r a t i o n a l coordinates. Questions 1), 3) and 4) w i l l be referred to as the problems of enumeration of combinatorial types, projective s t a b i l i t y and r a t i o n a l r e a l i z a b i l i t y , respectively. Enumeration of Combinatorial Types Recall that a standard Gale diagram i s a Gale diagram i n which a l l non-zero vectors have unit length. A standard Gale diagram consists of a subset of the unit sphere and a (possibly empty) set of points coincident at 0 . Denote the number of combinatorial types of d-polytopes with n v e r t i c e s by C(n,d) and the number of combinatorial types of s i m p l i c i a l d-polytopes with n vertices by C g( n»d). Since the only d-polytope with d+1 v e r t i c e s i s the d-simplex, C(d+ld) - C s(d+l,d) = 1 . .•THEOREM (Granbaum [3]): a) Cg(d+2),d) = [|d] b) C(d+2),d) = [-|d2] - 27 -where [n] i s the greatest integer less than or equal to n . Proof: A standard Gale diagram P of a d-polytope P with d+2 vertices consists of r points at -1 , S points at +1 and t points at 0. If we require that r j< S , then to each combinatorial type corresponds one diagram. In order that P be the diagram of a polytope, r >_ 2.. I f t > 0 , P i s a d-polytope with a facet containing d+1 v e r t i c e s , and conversely. Therefore P i s s i m p l i c i a l i f and only i f t = 0 . a) Thus we have a b i j e c t i o n between the classes of s i m p l i c i a l d-polytopes with d+2 vertices and the set { (r,s) | 2_<r<_s , r+s •= d+2} . Thus 2<r<J/|-(d+2) ] , so there are t"^] solutions to the conditions. Therefore . Cs(d+2,d) = [ f ] . b) There i s a b i j e c t i o n between the set of dh-polytopes with d+2 vertices and the set {(r,s,t)|2<r<s , r+s+t = d+2} . Some computations reveals, that the number of solutions i s C(d+2,d) = [~d2] . 1 2 [Note: Griinbaum's value i s erroneously stated as [-^d ] on p. 100 of [3], although i t i s correctly stated on p.101.] A standard Gale diagram of a d-polytope with d+3 vertices i s a (possibly empty) set of points at 0 together with a set of points on 1 2 " ' the unie c i r c l e S i n E . The diameters of a diagram of P are those diameters of S"*" containing non-zero points of P . The diagram P may be modified i n several ways to y i e l d an isomorphic diagram. Performing an operation upon a diameter means performing that operation on a l l points belonging to that diameter. An endpoint of a diameter i s empty i f no points of P l i e s at that endpoint. Any diameter may be rotated to a new p o s i t i o n as long as i t does not cross or coincide with another diameter. I f a diagram contains at l e a s t 3 diameters, two d i s t i n c t diameters are defined to be adjacent i n the obvious way: of the two open arcs on S' defined by one endpoint of one diameter and both endpoints of the other, one arc contains the endpoints of no other diameters. The two p a i r s of endpoints which determine the empty arcs are s a i d to be adjacent endpoints, the other two p a i r s are opposite endpoints. See F i g . 4. Then .two adjacent diameters with adjacent empty endpoints may be rotated to coincide, as long as neither crosses or coincides with any other diameter. Conversely, a diameter empty at one end and with K points of P at the other may be s p l i t i n t o K adjacent diameters containing one point of P . However, adjacent diameters i n which adjacent endpoints are not empty may not be coalesced without changing the isomorphism type of P . C l e a r l y , using the three operations of r o t a t i n g , coalescing and s p l i t t i n g diameters a diagram P may be transformed i n t o an isomorphic diagram i n which the number of diameters i s e i t h e r maximized or minimized. Such diagrams are denoted distended and contracted diagrams, r e s p e c t i v e l y . In a distended diagram, a diameter empty at one end contains only one point of P . In a contracted diagram, no empty ends are adjacent. Contracted an distended diagrams have convenient p r o p e r t i e s , given i n the following two theorems. THEOREM 1: Let X,Y be contracted diagrams, isomorphic v i a a b i j e c t i o n i> . Then there i s an orthogonal transformation T^ of E such that xu) = xT for each x e X . THEOREM 2 : Let X,Y be isomorphic distended diagrams. Then thirds an orthogonal transformation T^ of E such that Y = XT^ (XT^ and Y are equal as sets, not as ordered sets) . The e s s e n t i a l d i f f e r e n c e between the two theorems i s that any isomorphism of contracted diagrams may be r e a l i z e d as an orthogonal transformation; whereas t h i s i s . n o t true f o r a distended diagram which i s not also a contracted diagram. To see t h i s , l e t X be a distended diagram i n which two diameters A d^ and "d^ a n c * leaving every other point of ' X f i x e d i s an isomorphism A of X with i t s e l f that cannot be r e a l i z e d by a l i n e a r transformation. Proof of Theorem !:• Case 1 : I f X has only two diameters, each diameter must have points of X at both ends. Choose x 7^ 0 . Then the set of points on the other end of the diameter from x i s { 2 I 0 e r e l i n t conv £ x, z }}. Therefore, since X and Y are isomorphic, the set of points on the other end of the diameter of Y containing x^ i s { 2.^ | 0 £ r e l i n t conv{x,z }} . A ss - A A Therefore, f o r a l l x,y, e X. , x and y coincide i f and only i f XIJJ and yip coincide. Thus takes the (orthogonal) diameters of X i n t o the (orthogonal) diameters of Y and can therefore be r e a l i z e d by an orthogonal transformation. Case 2 : I f X has at l e a s t three diameters so does Y by case 1 ) . F i r s t we show, thatif'the diameters determined by x and y are adjacent the'.-• diameters determined by X I J J and y<Jj are adjacent. Let d^ and d^ be adjacent diameters of X . These diameters must contain a p a i r of opposite p o i n t s , x^ e d^, x^ £ d^ ; otherwise the contracted diagram c o n d i t i o n i s A v i o l a t e d . Denote the endpoint of d. not containing x. by a. . x. & 1 J x Figure 3 X X*. 8 <a, Y X The four endpoints determine open arcs A, B, C and D of S x . Using pO and x^l> , define correspondingly regions A\ Bj C\ D' f o r y . Cl e a r l y a^ i s empty i f and only ; i f al i s empty. Since the choice of A A x^ and X £ implies B A X = <(> , C H X = <f> , we must show that B' /"I Y = C 0 Y = <j> ( 1 ) Therefore, since X and Y are isomorphic, the set of points on the other end of the diameter of Y containing X I J J i s {Zip | 0 e r e l i n t conv {x,Z}} Therefore, for a l l x, y e X , x and y coincide i f and only i f xifj and A A yip coincide . Thus if takes the diamters of X in t o the diameters of Y and can therefore be r e a l i z e d by a l i n e a r transformation, which i s an orthogonal transformation since the diameters of X and of Y are orthogonal, A A Case 2 : I f X has at l e a s t three diameters so does Y by case 1 ) . F i r s t we show that i f x,y are adjacent points, xi[> , ytfr are adjacent points. For, x e "> Y e ^ ^ e ^ adjacent diameters d^ and ^ 2 * These diameters must contain a p a i r of opposite points, say x^ e d^ , x^ e &2 . Otherwise, e i t h e r one of d^ and d^ has no non-zero points - 31 -of X or the contracted diagram condition i s v i o l a t e d . Figure k Let A be the open arc determined by the endpoints of d^ and d^ not A. A, containing or ^2 ' a n ^ ^' t n e corresponding open arc determined A A. by x^ i|> and . See F i g . 3 . Now since A A A A Z e A. •<==>. 0 e r e l i n t { Z „ x ^ , X 2 ^ A A Therefore (X f\ A)u> = A' fl (Xt|>) . I f neither a^ nor i s empty, then c l e a r l y (1) holds. I f a^ (say) i s empty and a^ i s not, then B' 0 Y = d> . But i f C' H Y ^ <j) , there must be a diameter d' with a non-empty endpoint in. C' and an empty endpoint adjacent to a^ , also empty; t h i s contradicts the contracted diagram condition. Therefore both a^ and a2 are empty. Since Z e A <==> 0 e r e l i n t conv { x^ , X 2 , Z } we have Z E Z <==> Zip- E A' . (2) . . But then i f d' i s a diameter with an endpoint i n C' (say) , d' must also have an endpoint i n B'; otherwise the contracted diagram cond i t i o n i s v i o l a t e d . Therefore both endpoints of d' are non-empty , and contain A j\ , V^f say. But then e i t h e r e A or £ A , co n t r a d i c t i n g ( 2 ) , Therefore adjacent (coincident) diameters remain adjacent - 32 -(coincident) under ip. Since the diameters of X and of Y are equal i n number and equally spaced, an orthogonal transformation Tip exsists taking X to Y. The argument also shows that xu> = xTip, for a l l x e X, proving the theorem. Theorem 2 i s proved.in a s i m i l a r fashion. Theorems 1 and 2 establish that to each combinatorial type of d-polytope P with d+3 vertices corresponds e s s e n t i a l l y one distended diagram and one contracted diagram. I f P i s s i m p l i c i a l , no points of P l i e at 0 and each diameter i s empty at one end. Thus a distended diagram consists of d+3 d i s t i n c t diameters, each containing one point. Therefore C (d+3,d) i s the number of ways d+3 points may be dis t r i b u t e d at the vertices of a regular 2(d+3-)-gon such that no open half-space with the centroid on i t s boundary contains less than 2 points. This number has been calculated by Perles, using Polya's theorem. THEOREM 3 (Perles, pub, i n Grtinbaum [3]): C s(d+3,d ) - 2 [ I ] - [ i ± 4 ] + ^ h I H * < h ) 2 ^ where ff i s the set of odd divisors of-d, and if(h) i s the number of po s i t i v e integers less than, and r e l a t i v e l y prime to, h. Lloyd [4] has calculated C(d+3,d). However, there seems to be doubt about his evaluation. l d + 3 l THEOREM 4 (Lloyd [ 4 ] ) ; c(d+3,d) = y £ <J>(J)(2S-1) •, d+3 ,,,, [m/3]0m-2s ? = 1 I f ' ? [ (d-2r+l)/2 ] [m/3] 0m-2s * n=3 lm=n,2|l s=l s m J S r=0 m=0 s=0 3<m 2 [d-2r+2)/2] [m/3] 10 [(d-r+3)/2] , . ._ + 7 I ( - D I (d-2m-2r+3) J 2m-2s m-s+1 + j o ^ d-r-2m+7 2r=0 • m=0 . ~ s - 0 , ra_3s r=l r m=0 d-r-2m+3 where = -1, = 2, = 0, = -4, = 3, = 0, = -2, = 2, a 9 = -4, « 1 Q - 1. - 33 -R e a l i z a t i o n of Combinatorial Symmetry Groups as Groups of Congruences Let P be a d-polytope, X = v e r t P . The' combinatorial 'symmetry group of P i s the group of permutations a of X such that f o r a l l S ^ X • conv S is' a face of P <==> conv (So") i s a face of P . (1) Combinatorially isomorphic polytopes have isomorphic combinatorial symmetry groups, so we may write G[pj where [P] i s the set of polytopes combinatorially isomorphic to P . The group of congruences C^ of P i s the group of orthogonal a f f i n e transformations of E d mapping P i n t o i t s e l f . Since each congruence of P induces a permutation a of the vertices s a t i s f y i n g (1) , C^ i s isomorphic to a subgroup of ^ r p ] If Cp i s isomorphic to G^-j i t s e l f , we say ^ j p i i s r e a l i z e d as a group of congruences by P . For example, i f P i s an n-simplex, **rp] 1 S isomorphic to the e n t i r e group of permutations of n+1 objects and i s r e a l i z e d by the group of congruences of the regular n-simplex. The regular n-gon P^ realizes". Gj-y -j . Mani (private '.communication) has proved that ^rp] ^ s r e a l i z e d as a group of congruences for a l l 3-polytopes P . Let X. be an a f f i n e transform of X . Let a e G_, . Then a A P " \ • induces a permutation of• iX (which wewiTJL also c a l l a ). C l e a r l y A -condition ( 1 ) implies that X^ and X^a are isomorphic, so a i s an isomorphism of X A into i t s e l f . On the other hand, i f T i s a congruence . of P , then, since P and PT are a f f i n e l y equivalent, X i s l i n e a r l y . equivalent to i t s e l f v i a a l i n e a r transformation L . I f a i s the permutation of X induced by T , then L must s a t i s f y xL = xa , f o r a l l x c X. . (2) * A Conversely, i f L i s a linear transformation of and a a permutation s a t i s f y i n g (2), then X and X a . are l i n e a r l y equivalent. Therefore A A X and Xa are a f f i n e l y equivalent. Thus X and Xa are a f f i n e l y equivalent i f and only i f X and X a are l i n e a r l y equivalent . A A I t i s well-known that any f i n i t e group of a f f i n e transformations i s a f f i n e l y equivalent to a group of congruences. We may conclude, then, that i f for a l l a e G„ there i s a l i n e a r transformation L such that P a xL = x a , for a l l x e X. then there i s a polytope Q a f f i n e l y equivalent to P such that ^rp] i s r e a l i z e d as a group of congruences of Q . THEOREM 5 (Perles [3,]); Let P be a d-polytope with d+1 , d+2 , or d+3 v e r t i c e s . Then there i s a combinatorially isomorphic polytope Q whose group of congruences i s isomorphic to i t s combinatorial symmetry group. Proof: Suppose P has d+3 v e r t i c e s ; X = vert P . Let X be the contracted diagram of P . Thenby theorem 1 for every a e G^ there i s an orthogonal l i n e a r transformation L such that xa = xLtr , x £ X . We wish to find an affine transform, not just a diagram, with the same property. I f centroid X = 0 , X i t s e l f i s such a transform. I f not, l e t Z = centroid X ^ 0 . Then, since Z = centroid (Xo), Z = ZL a and L i s either the i d e n t i t y or r e f l e c t i o n i n the l i n e l i n Z. Therefore {L } „ i s either the i d e n t i t y alone, or the i d e n t i t y and r e f l e c t i o n through l i n Z . In either case, an isomorphic transform Y - 35 -may be found such that xa = xL , x e Y. . a A Any polytope Q with transform Y w i l l be a f f i n e l y equivalent to i t s e l f under a group of a f f i n i t i e s isomorphic to . Therefore there i s an a f f i n e l y equivalent polytope (isomorphic to P) r e a l i z i n g G p as a group of congruences. The proof f o r d+2 v e r t i c e s i s s i m i l a r , and for d+1 i s t r i v i a l . I t i s conjectured that Theorem 5 i s true f o r a l l d-polytopes. Nothing further i s known f o r ,d>3- .and number of v e r t i c e s greater than d+3 . - 36 -Projective Uniqueness A d-polytope P i s pr o j e c t i v e l y unique i f any combinatorially isomorphic polytope Q i s proj e c t i v e l y equivalent to P ; that i s , there i s a non-singular p r o j e c t i v i t y K such that PK = Q . Projective uniqueness i s a property of combinatorial types, not i n d i v i d u a l polytopes. Recalling the discussion of projective equivalence i n section 2, we conclude that P i s pr o j e c t i v e l y unique i f and only i f any two Gale diagrams of- P are equivalent. I t has been shown (Graiinbaum [3]) that i f P has d+2 v e r t i c e s , P i s pr o j e c t i v e l y unique. This i s immediatly obvious from the fact that P i s one-dimensional. THEOREM 6: A d-polytope with d+2 vertices i s pr o j e c t i v e l y unique. Perles has characterized p r o j e c t i v e l y unique polytopes with d+3 vertices by THEOREM 7 (Perles [3]): A d-polytope P with d+3 vertices i s p r o j e c t i v e l y unique i f and only i f a diagram of P i s one of the three forms Figure 5 (The numbers represent the m u l t i p l i c i t i e s . The in e q u a l i t i e s are those necessary to insure that the diagram i s that of a polytope.) Proof: Any polytope with a diagram containing 4 or more diameters obviously cannot be projectively unique. The remaining p o s s i b i l i t i e s may - 37 -be checked e a s i l y , to establish theorem 6. Proj e c t i v e l y unique d-polytopes with more that d+3 vertices and d>3 have not been characterized. There are 2 pr o j e c t i v e l y unique 2- polytopes (the triangle and the square) and 4 pro j e c t i v e l y unique 3- polytopes (the tetrahedron, square, pyramid, triangular bipyramid and i t s dual the triangular prism) (Grunbaum [3], p. 68) . THEOREM 8: The dual of a proj e c t i v e l y unique polytope i s pro j e c t i v e l y unique. Corollary: The cross-product of an r-simplex and an s-simplex (the dual of an (r+s)-polytope with r+s+2 vertices) i s p r o j e c t i v e l y unique. The proof i s l e f t to the reader as an exercise i n l i n e a r algebra. McMullen [9] has found several methods of constructing projectively unique polytopes from p r o j e c t i v e l y stable polytopes of lower dimension. We give these without proof. I f P^ i s a d^-polytope, P^ a d^-polytope, then i f P = conv (P^ U P^) i s a (d^+d^+l)-polytope, P i s ca l l e d the j o i n of P^ and 2^ . I f P-^ and P^ l i e i n subspaces intersecting i n exactly one vertex of each polytope, P = conv (P^ U P 2) 1 S c a l l e d the vertex-sum of P^ and ¥^ • ^ 1 i s a l i n e segment whose r e l a t i v e i n t e r i o r meets the affine h u l l off Q^. of a polytope Q i n exactly one vertex of Q , then P = conv (Q U . I ) i s said to be formed by adj oining : the segment I to the vertex x . y THEOREM 9 ([9]): The j o i n of polytopes P and P 2 i s p r o j e c t i v e l y unique i f and only i f P^ and a r e p r o j e c t i v e l y unique. THEOREM 10 ([9]): The vertex-sum of polytopes P^ and ?^ a r e p r o j e c t i v e l y unique i f and only i f . P^ and a r e p r o j e c t i v e l y unique. THEOREM 11 (McMullen' (private communication)): Let P be a polytope. The - 35 -polytope Q formed by adjoining a segment to x i s p r o j e c t i v e l y unique i f and only i f P i s pr o j e c t i v e l y unique and Q i s not a vertex-sum with x as distinguished vertex. Eleven types of p r o j e c t i v e l y unique 4-polytopes may be constructed using theorems 6-11. I t i s not known whether this l i s t i s complete. However, these were a l l that were found i n a systematic search by Shephard (private communication)'. I t i s known that not a l l p r j e c t i v e l y unique d-polytopes may be constructed i n t h i s way. This fact i s proved by constructing a p r o j e c t i v e l y unique polytope whose vertices may.not a l l have r a t i o n a l coordinates. We w i l l do t h i s construction under the next heading. Since for every Gale diagram of dimension 1 or 2 there i s an isomorphic diagram whose points a l l have r a t i o n a l coordinates, a p r o j e c t i v e l y unique polytope constructed using theorems 6 and 7 can be chosen to have vertices with r a t i o n a l coordinates. Theorems 8-11 applied to polytopes whose vertices have r a t i o n a l coordinates w i l l y i e l d polytopes with the same property.. Therefore a polytope of the smallest possible dimension which i s not r a t i o n a l l y r e a l i z a b l e may not be constructed i n any of the above ways. Rational R e a l i z a b i l i t y A d-polytope P i s said to be r a t i o n a l l y r e a l i z a b l e i f there exists a polytope combinatorially isomorphic to P a l l of whose vertices have r a t i o n a l coordinates. Clearly every polygon i s r a t i o n a l l y r e a l i z a b l e , and i t may be shown, using a theorem of S t e i n i t z (Grlinbaum [3D, that every 3-polytope i s r a t i o n a l l y r e a l i z a b l e . Perles (published i n Grunbaum [3]) has proved the' remarkable - 39 -THEOREM 12 (Perles): There i s a pr o j e c t i v e l y stable 8-polytope with 12 vertices which i s not r a t i o n a l l y r e a l i z a b l e -Proof: The proof consists i n constructing a configuration i n the plane i n which not a l l of the points may have r a t i o n a l coordinates. This 3 configuration i s then used to construct a Gale diagram i n E , such that any isomorphic diagram i s not r a t i o n a l l y r e a l i z a b l e . The corresponding polytope cannot be r a t i o n a l l y r e a l i z a b l e . A configuration i n the plane i s a set of points together with c o l l i n e a r i t y r e a l t i o n s . Define a configuration & as follows : 1) l e t the points of C be A,B,C,D,E,F,G,H,I. 2) the subsets of more that 2 points of C which are c o l l i n e a r are exactly ABEF, ADG, AHI, BCH, BGI, CEG, CFI, DEI, DFH. 2 It. i s e a s i l y checked that C may be re a l i z e d as a subset of E . i n two ways, shown i n Figs. 6 and 7 . Any r e a l i z a t i o n of i s p r o j e c t i v e l y equivalent to one or the other. Figure 6 - Figure 7 In F i g . 6, the cross-ratio (A,B;E,F) i s y(3-/5 ) and i n Fig. 7, (A,B;E,F) i s ^3+/S ) . Since the cross-ratio- i s invariant under a projective equivalence, i n any r e a l i z a t i o n of i n the plane, (AB;E,F) 1 r-i s 2"(3+/5 ) . Thus a l l of the coordinates of A, B, E, F cannot be r a t i o n a l . Now l e t us construct a Gale diagram using & , as r e a l i z e d i n F i g . 6. Let ^ l i e i n a plane i n E"^ not containing the o r i g i n . Define 3 a subset of E X = {A,B,C,D,E,F,G,H,-F,-G,-H,-I}. . I t i s r e a d i l y v e r i f i a b l e that X i s the diagram of the set of v e r t i c e s of a polytope P . The points of X determines 9 l i n e s L , . . . , L_ 1 9 through 0 . Let X' = ( x r . .., x^ 2) be a diagram isomorphic to X . The points of X' determines 9 l i n e s L p Lg through 0 , since X and X' are isomorphic. Moreover, the isomorphism implies that a subset of L , ..., L n i s coplanar i f and only i f the corresponding subset of L' ..., L' i s coplanar. This shows i y that the i n t e r s e c t i o n of L1^, L^ with a plane p a r a l l e l to none of these l i n e s gives a r e a l i z a t i o n of . i f a i i the points of X' had r a t i o n a l coordinates, ^- could be r e a l i z e d as a set of points with r a t i o n a l coordinates with respect to a plane. Let L be the plane L = { (C^, £3 U3=1>-If necessary, apply a r a t i o n a l l i n e a r transformation to X' so that none of the l i n e s L|, L^ are p a r a l l e l to L .• Then the points of i n t e r s e c t i o n of L with L^ L^ have r a t i o n a l coordinates, a c o n t r a d i c t i o n . Therefore P i s not r a t i o n a l l y r e a l i z a b l e . I t i s not known whether any d-polytopes of lower dimension are no r a t i o n a l l y r e a l i z a b l e . However, a remark under the previous heading shows that a d-polytope of d+3 v e r t i c e s i s r a t i o n a l l y r e a l i z a b l e . - 41 -5. P o s i t i v e Diagrams and Polyhedral Representations. In this section we w i l l see how Gale diagrams may be. used to investigate the properties of positive bases i n a systematic and i n t u i t i v e way. The basic idea f i r s t appeared i n Davi£ [1 ] and was developed more f u l l y Shephard [12]. As an example of the c l a r i t y achieved using Shephard's positive diagrams, we w i l l show that the fact that a p o s i t i v e bases of E d may have at most 2d elements i s an almost t r i v i a l consequence of the fact that a d-polytope has at least d+1 v e r t i c e s . We w i l l also describe very b r i e f l y Shephard's [13] method of studying polyhedral sets using Gale diagrams. . Let S = (x^, x^} span E d l i n e a r l y . Recall that for any n-tuple u = ( u ^ , l - 1 ^ °f s t r i c t l y p o s itive scalars, \ = { y l X l ' •••» y n X n } • Recall also that the po s i t i v e h u l l of X i s the set posX•= {X.x. + ... +A x A; > 0, i ^ l , . . . , n>. 1 1 n n x — d d If pos X = E , S i s i a i d to span E p o s i t i v e l y . I f no proper subset of X spans E d p o s i t i v e l y , X i s a po s i t i v e basis of E d . The structure of p o s i t i v e bases i s more complicated than that of l i n e a r bases. For instance, for d >_ 2 not a l l p o s i t i v e bases have the same number of elements. With the above notation, i t . i s easy to show THEOREM 1: The following are equivalent: 1) pos X = E d 2) posX = E d .3) 0 e i n t conv X . Each X determines a polytope conv X , cal l e d an associated u ' u polytope of X . Po s i t i v e diagrams also give information about the associated - 42 -polytopes of a set X spanning E d p o s i t i v e l y . The p o s i t i v e diagram X of X i s a Gale diagram of a s p e c i a l type discussed i n d e t a i l at the end of se c t i o n 2 . Let X^ be a l i n e a r transform of X . Since 0 e i n t conv X , pos X^ i s a pointed cone with apex 0 . Let H^ be a hyperplane supporting pos X^ at 0 and l e t H be a p a r a l l e l hyperplane not through 0 but int e r s e c t i n g " p o s . X L . Then the p o s i t i v e diagram X of X i s the set of i n t e r s e c t i o n s of rays pos {x.} with H: 1 x. = pos {x. } H H , i = 1 , .... n . An immediate consequence of the d e f i n i t i o n i s X = X^ f o r a l l u . Theorem 2 .12 states that with appropriate choice of o r i g i n X i s a Gale diagram of X , and i s an a f f i n e transform of X for some u . y Furthermore, X i s a Gale diagram (with appropriate choice of o r i g i n ) for every X . y The diagram of.a p o s i t i v e basis i s characterized by THEOREM 2 (Shephard [12]) : For any X spanning E d l i n e a r l y , X i s a p o s i t i v e basis f o r E d i f and only i f 1) 0 fj: conv X Li 2) x e conv (x \ {x} ) for a l l x e X . Proof: C l e a r l y posX = E d i f and only i f .1) holds. Suppose 1) holds, but x^ c conv (X \ x ) . Then x^ and X \ {x^} are s t r i c t l y separated by a hyperplane i n H . This hyperplane n*-d determines a hyperplane II i n E through 0 s t r i c t l y separating x^ from X \ {x^} . Suppose the equation.of H' i s <x,u> = 0 , such that - 4 3 -< X p U > = -1 <x i ?u> = 3 ± > 0 ", i = 2, .. ., n. Then the vectors (-1,3 2 > ...,$) i s a l i n e a r dependence of X , so -x- + B 0 x 0 +...+• 3 x = 0 . 1 / z n n Therefore x. = 3„x 0 +...+ 3 x , 6. > 0 , i=2, n . 1 2 / n n i -That i s , x 1e pos (X \ {x 7}) , implying that X \ {x^} spans p o s i t i v e l y and that X i s not a p o s i t i v e b a s i s . The converse may be proved by reversing the above argument.' This theorem simply states that no x e X i s a f a c i a l subset d of X . This means that the p o s i t i v e bases of E are p r e c i s e l y those sets ^ . A rt rt i n '. E. which are Gale diagrams of sets X such that no x e x i s a f a c i a l subset. 3 Examples of the four types of p o s i t i v e bases of E and t h e i r p o s i t i v e diagrams are-given i n F i g . 8 . Conv X i s an (n-d-l)-polytope. I f X i s a p o s i t i v e b a s i s , by Theorem 2 at l e a s t two points of X must coincide at each vertex of rt conv X . The next theorem was f i r s t proved by Blumenthal, reproved by DAvis [1] using e s s e n t i a l l y the above methods and f i n a l l y by Shephard [12]. THEOREM 3: If X i s a p o s i t i v e basis of E d , . d + 1 <_ card X <_ 2d . Proof: The lower bound i s t r i v i a l . To obtain the upper bound, suppose card X = n . Then conv X i s an (n-d-1)-polytope and therefore must have at l e a s t n-d v e r t i c e s . Since 7 X i s a p o s i t i v e basis at l e a s t rt two points of X coincide at each vertex. Therefore - 4 4 -a) X.'C 'O .O) Xi«< 0,1,0) . . . A X 3 s ( o , o , f ) © X, >X^ ,X3,X</ x*- (-1,-iri) X.- (1,0,0) Xt-(-M ,0) XW<>,i,o) X*° (o,o3i) Xss (O,-I , -/) A A X ( , Xj. A ^ A C) X . - - (UU) . XxMU'1,-1) X J ' H J O ; " ) X, -(i,i,-0 : x f -(1,-1,0 X ^ X i X3 8 1 A Xv >x$ d) X .-(1 , 0 , 0 ' _• XVH ,0>o) . X3= (0,1,0) . Xs - (0,0,1) . X t = (o,o,-() Figure 8 3 The 4 p o s i t i v e bases of E and t h e i r p o s i t i v e diagrams. (From Shephard [12].) - 45 -n >_ 2 (n-d) , establishing the r e s u l t . A positive basis of E d with d+1 or 2d elements i s said to be a'minimal or maximal basis, respectively. I f {y^, y^} i s a l i n e a r basis of , {yj_» •••> 3^' ~ (y-j+» • •"tyjj) }• i s a minimal basis and {y^, y^, _y^> ~ y , j ) 1 a maximal basis. d d Let X be a p o s i t i v e basis of E . I f L i s a subspace of E such that L f) X i s a minimal positive basis of L , L i s said to be a minimal subspace . Minimal subspaces are characterized by the following theorem, which we state without proof. THEOREM 4 (Shephard [12]: Let X be a positive basis of E , and X a p o s i t i v e diagram of X. Then S C2 X , S 4 X , spans p o s i t i v e l y a minimal subspace of E ' i f and only i f conv (X \ S) i s a facet of conv X. Theorem 4 may be used to prove other facts concerning minimal subspaces. For instance, that for every point x £ X there i s a facet of conv X not containing x shows that every point of a p o s i t i v e basis i s contained i n some minimal subspace. For more results concerning minimal subspaces, see Shephard [12], Results concerning the family of associated polytopes of a p o s i t i v e basis X are also easy to prove using the diagram X . Since X i s a p o s i t i v e basis, at least two points of X coincide at each vertex of conv X . Therefore X i s the Gale diagram of a polytope, regarding any point a e i n t conv X as o r i g i n . Since a Gale diagram of X may be obtained by appropriate choice of o r i g i n i n i n t conv X^, we have . that X i s the set of vertices of. X (This i s also easy to see d i r e c t l y ) u -u A simple consequence of this discussion i s that there i s exactly one combinatorial type of associated polytope ' i f and only i f X i s a set of points coicident with the vertices of a simplex. Shephard [13] has also devised a diagram technique for dealing with polyhedral sets. As this technique is similar to, but less versatile tha, a technique of McMullen [6] for representing polyhedral sets which w i l l be treated f u l l y is section 7, just the basic idea w i l l be outlined here. Let P = {xeEd| <x,u^ > £ 1, i=l, . ... ,n} be a polyhedral set. Let U = {u^, u^} and assume that U spans'E^ linearly. Then the dual P* o£ P is P* = {yeEd|<x,y> <_ 1 for a l l x. e P} = conv (U ii {0}) . . Shephard defines a polyhedral representation of P to be an affine transform {u- ..... u } of U V {0}, where 0 corresponds to u . o n r o Since the fa c i a l structure of P* determines the f a c i a l structure of P, "dualizing" the Gale diagram conditions for P enables Shephard to characterize face, unbounded faces and pa r a l l e l unbounded faces of P in terms of the polyhedral representation. For details, see Shephard [13]. 6. Zonal and Central Diagrams - So far the emphasis has been upon the affine transform. Now the linear transform w i l l be used to investigate some special families of polytopes. In this section diagrams of zonotopes and centrally symmetric (C.S.) polytopes w i l l be defined in terms of a linear transform. In the next section we w i l l consider polytopes with an axis of symmetry. The major result obtained using diagrams of C.S. polytopes is an unexpected theorem concerning neighbourliness properties. However diagrams do not aid in the.enumeration of combinatorial types. - 47 -On the other hand, diagrams of zonotopes w i l l be used to enumerate arrangements of hyperplanes i n r e a l p r o j e c t i v e space and to e s t a b l i s h a correspondence between zonotopes of d i f f e r e n t dimensions. Central Diagrams A d-polytope P i s sai d to be centrally-symmetric (abbreviated to "C.S.") i f -P i s a t r a n s l a t e of P . I f the centroid of P i s 0, P i s C.S. i f and only i f P = -P . In p a r t i c u l a r , i f the centroid of a C.S. polytope P i s 0 , then x i s a vertex of P i f and only i f -x i s a vertex of P . Henceforth we w i l l assume that the centroid of P i s 0 and that the set of X of v e r t i c e s of P i s wr i t t e n i n the standard form X = {+x. , ...,•+ x } • - 1 - n and X_j_ = {x^, ...» x^} . Cl e a r l y i f P i s a d-polytope, X + spans E d l i n e a r l y . Thus ri >_ d and so any C.S. d-polytope has at lea s t 2d v e r t i c e s . The only C.S. d-polytopes with exactly 2d v e r t i c e s i s the cross-polytopee. The regular cross-polytope.•'. i s defined to be X d = conv i+&2_> •••> + ^dJ>'-d where (&^, Jl^) i s the standard basis of E . The Gale diagram of a C.S. polytope which i s not a cross-polytope l i e s i n a higher-dimensional space that the polytope I t s e l f . A new type of representation i s needed. This, representation, f i r s t found by"McMullen and Shephard [7] , i s c a l l e d a c e n t r a l diagram of P and is. defined to be the C.S. set X = (j-x , ... >+xn) where X,T = (x,, .... x ) i s a l i n e a r transform of X, . I t follows +L I n + immediately from the properties of the l i n e a r transform that X i s a subset of E n d spanning E n d l i n e a r l y . Although X i s defined ir , terms of X , and X i s not uniquely defined, X i s defined unique up to non-singular l i n e a r transformation of E n d . For i f X| = (^x, . e x ) ,E.E{+1,-1}, + 1 1 ' ' n n x then a l i n e a r transform of X' i s + - ( e l V E n X n ) ' r e s u l t i n g i n the same c e n t r a l diagram. The c e n t r a l diagram of a cross-polytope with 2d v e r t i c e s i set of 2d points coincident at 0 . The main theorem r e l a t i n g to c e n t r a l diagrams characterizes f a c i a l subsets of X . THEOREM 1: Let P be a C.S. d-polytope i n E d with X = v e r t P = ( + X p + x n ) . Let X = ( + X p + x n ) be a c e n t r a l diagram of P . The conv (e, x„ , ..., e x ) i s a face of P i f and only i f l a l o ' ' ra ra J e, x, + ... + E x E r e l i n t conv {+x ,,' + ... + x } l a l a r a ra -. r+la - - na where a i s a permutation of {1, n} , s i ^ = + 1 and. conv {+x ,.,+... +x } - r+la - - na n—r denotes the convex h u l l of the 2 points formed by taking sums of x ., . . . . . x with a l l possible combinations of signs, r+la na Proof: Assume without loss of g e n e r a l i t y that F = conv {x-, ..., x } 1 r i s a face of P . Then there i s a hyperplane H supporting P at V By c e n t r a l symmetry, -H supports P i n -F . Assume that the equa.' - 49 -< X , U > = 1 . <x i 5 u> = 1 , i = 1 r -1 < <x ,u> = jS^ < 1 , 1 = r+1, n . .inc; the properties of the l i n e a r transform, these r e l a t i o n s imply 1, j9 r+1' j5 ) i s a l i n e a r dependence of "X_ n l+L herefore, + x + 3 r r+1 Xr+1 + + g x = 0 n n r e l i n t conv {+x i=r+l equation establishes the i m p l i c a t i o n i n one d i r e c t i o n . As usual, the -lent i s e a s i l y reversed to e s t a b l i s h the equivalence. See F i g . 9 for c e n t r a l diagrams of the f i v e combinatorial types '-.S. 3-polytopes with 8 v e r t i c e s . It i s not d i f f i c u l t to prove analogs of the various theorems L i n e a r transforms. One t r i v i a l example i s 'REM 2: A C S . polytope P i s a bipyramid with vertex x i f and only :'.n a c e n t r a l diagram X of P , x = 0 . See McMullen and Shephard,[7] further examples. Using theorem 1, i t i s easy to make a d e f i n i t i o n of isomorphic . r a l diagrams such that two C.S. polytopes w i l l be combinatorially orphic i f and only i f they have isomorphic c e n t r a l diagrams. However, analogy to Gale diagrams cannot be stretched f a r enough to provide a :ral version of standard Gale diagrams. The problem i s that the distances -so-A 3 -Xo N X, > X^ X 3 -X, X. X, X, —<? «-Xi x^ X , -X'< ~± ±r~ X^ _X< Xa —C>— - — -C G • X. Xt "XV -o-_X, X j Figure 9 The 5 c e n t r a l l y symmetric 3-polytopes w i t h 2(d+1) v e r t i c e s and t h e i r c e n t r a l diagrams. (From McMullen and Shephard [7.]). - 51 -of the points from 0 matter; that i s , given ( s t r i c t l y p o s i t i v e ) P 1» . • • •» vn > (+x 1, ..., + x n ) w i l l not i n general be isomorphic to (±'J1X1' * ' * ' y l x n ^ ' Consequently no obvious convenient canonical c e n t r a l diagram e x i s t s and even 1-dimensional c e n t r a l diagrams are not e a s i l y enumerated. The number of combinatorial types of C.S. polytopes with 2(d+1) v e r t i c e s has not been determined for d>3 . The major r e s u l t found v i a c e n t r a l diagrams concerns the neighbourline. of C.S. polytopes. An a r b i t r a r y d-polytope P • i s s a i d to be K-neighbourly i f every K-pointed subset of vert P i s the set of v e r t i c e s of a face'of P , and neighbourly i f i t i s K-neighbourly f o r K <_ ["^l • C l e a r l y , i f P i s K-neighbourly, P i s j-neighbourly f o r j <_ K . A d-simplex i s (d+1)-neighbourly. It i s a remarkable f a c t that f o r every d and every n there i s a neighbourly d-polytope with n v e r t i c e s . 1 This i s the best that can be done, as a K-neighbourly polytope, K > [yd] , must be a d-simplex. Since, i f X = {+X,, +x } i s the set of v e r t i c e s of a C.S. ' - 1 - n d-polytope P i n E d , then x^ and -x^ cannot belong to a s i n g l e proper face of P . Consequently, the d e f i n i t i o n of K-neighbourly must be modified. A C.S. d-polytope i s s a i d to be K-neighbourly i f every K-pointed subset of vert P not containing any C.S. p a i r of v e r t i c e s i s the set of v e r t i c e s of a face of P . Using t h i s d e f i n i t i o n , McMullen and Shephard [7] have proved a theorem which i s unexpected i n view of the above remarks on neighbourliness of a r b i t r a r y polytopes. THEOREM 3: Let P be a C.S. d-polytope i n E d with 2(d+K) v e r t i c e s , K > 0 . Then 1) i f K = 0 , P i s d-neighbourly; -1 •2 2) i f K = 1, P i s at most [|d]-n.eighbourly and the upper bound i s attained; 3) i f K >_ 2,. P i s at most [-|-(d+l) ]-neighbourly, and the bound i s attained (at l e a s t when K=2). Proof: Part 1) i s obvious. To prove part 2) , suppose vert P = (+x^, ..., + x ^ + 1 ^ * ^ c e n t r a l diagram (+x^, . .., + x^ +^) °f p i s then 1-dimensional and we may assume that x. > 0 , i = l , d+1 . i — I f P i s k-neighbourly, then every K-membered subset {i.. , i„} S {1, d+1} corresponds to the set of v e r t i c e s of a face and so by theorem 1, x. + . . . + X . < x. + . . . + X . , x l XK J l Jd+1-K where {3 x» • • •> Jd+l-K^ = ^ » • • • > n * ^ ' " > ^ • Averaging the i n e q u a l i t y over a l l K-membered subsets of {1, ...,n} gives 1 -rx < (d+l-r)x , where x = — ( x n + ... + x ) > 0 . ' n 1 n Therefore 2r < d+1 so r <_• [-^ d] , ex t a b l i s h i n g part 2) . Part 3) i s established by using the properties of the c e n t r a l diagram and of hexagons i n the plane to show that i f V^, V 2 and are d i s j o i n t subsets of X = ( x , , ...» x „) such that X = V V V„ U V„ , then + 1 d+2 + 1 2 J conv V p conv V^, conv cannot a l l be faces of P . If P were K-neighbourly with - 53 -d + 2 <_ 3K , X + could be p a r t i t i o n e d i n t o 3 d i s j o i n t sets V^, V^, of c a r d i n a l i t y l e s s than or equal to K . But then P i s K-neighbourly and therefore conv , conv and conv are a l l faces of P , a c o n t r a d i c t i o n . Therefore K. < -|(d+2) and so K <^ [y(d+l)], e s t a b l i s h i n g part 3 ) . In part 2). , the d-polytope whose c e n t r a l diagram i s defined by X l = * *' = Xd+1 * ° i s [yd] neighbourly, as theorem 1) c l e a r l y shows. In part 2) , the d-polytope whose c e n t r a l diagram consists of 2(d+2) points at the v e r t i c e s of a regular 2(d+2)-gon with centroid 0 i s [-j(d+l) ]-neighbourly. The c e n t r a l l y symmetric polytopes are a s p e c i a l case of polytopes with an axis of symmetry. A K-dimensional a f f i n e subspace M ^ E d i s s a i d to be a K-dimensional axis of symmetry of the d-polytope P i f P i s i n v a r i a n t under r e f l e c t i o n i n M . P i s then said to ah'axi-symmetric . polytope with axis M'. The• C . S polytopes are those polytopes with a O-dimensional axis of symmetry. McMullen and Shephard [ 8 ] have used diagrams to obtain a number of r e s u l t s concerning axisymmetric polytopes. In p a r t i c u l a r , the number of combinatorial types of d-polytopes with n vertices,and a K-dimensional axis of symmetry containing no v e r t i c e s of the polytope has been determined for some p a r t i c u l a r cases of d, n and K . For d e t a i l s , see the o r i g i n a l paper. The other sort of r e s u l t obtained i s the determination of the numbers and dimensions of the axes of symmetry of a polytope. This i s done by considering the r e l a t i o n between the symmetries of P and the 54 -symmetries of an a f f i n e transform of v e r t P . We have already discussed t h i s question to some extent i n section 3 . There we found a correspondence between the group of a f f i n e symmetries of P and the group of l i n e a r symmetries of X ,' where X = ve r t P . Every non-singular a f f i n e transformation T such that PT = P induces a permutation a of X and hence of X. . To T corresponds a non-singular l i n e a r transformaion L of X A such that A x^ = xa for a l l x e X^ • (1) This correspondence i s not n e c e s s a r i l y one-to-one, since the points of X are not n e c e s s a r i l y d i s t i n c t . Thus any a f f i n e symmetry of P inducing a permutation a such that x and xa are coincident f o r a l l x e X corresponds to the i d e n t i t y l i n e a r transformation of X^ ... McMullen and Shephard [8] c a l l the group of symmetries of P corresponding . to the i d e n t i t y l i n e a r transformation the group 6 f i n t r i n s i c symmetries of P , I(P) . Denote the group of a f f i n e symmetries of P by S(P) . Then since every a f f i n e transformation of X^ into i t s e l f leaves the centroid of X. , namely 0 , f i x e d , and i s therefore a l i n e a r transformaion, A the group of l i n e a r symmetries of X i s S(X ) . C l e a r l y I'(P) i s a A A normal subgroup of S(P) and S(P) / I(P) - s(x A) . We have already remarked that the group of a f f i n e symmetries of a polytope P may be r e a l i z e d as the group of congruences (symmetries) of some a f f i n e l y equivalent polytope. Therefore the group of permutations a such that x^ = xa for a l l x e X^ for some L e S(X^) may be inter p r e t e d e i t h e r as the' group of a f f i n e symmetries of any polytope - 5S - . P whose transform i s X or as the group of symmetries (congruences) of some p a r t i c u l a r polytope (with transform X^). Let P be a d-polytope with a K-dimensional axis of symmetry M . Suppose M i s a l i n e a r subspace, and i s the orthogonal complement of M i n E d . Then every point E d may be represented uniquely as (x,y) , x e M, y e M Then the set X of v e r t i c e s of P may be wr i t t e n as u. = (Z.,0) , i = 1, .... m 1 1 w = (x ,y ) J ) j = 1, n . w«. = (x.,-y.) Therefore P has m+2n v e r t i c e s , m l y i n g i n M and 2n forming n pai r s of v e r t i c e s symmetricial with respect to M . Define the axis f i g u r e to be the set = (Z]_, Z m, x±, x n) and the coaxis fi g u r e to be the C.S. set X C = ^ - y l ' '* * 5 - yr? ' Neither the axis fi g u r e nor the coaxis f i g u r e . i s i n general the set of ve r t i c e s of a polytope. Now we state two theorems r e l a t i n g axes of symmetry of a polytope and axes of symmetry of , i t s transform. Proofs are omitted. THEOREM 4 (McMullen and Shephard [ 8 ] ) : Let P be a d-polytope with a K-dimensional axis of symmetry M . Let P have m+2n v e r t i c e s : u, , .... u i n M and VL ,W!, W , W paired with respect to M . 1' * m 1 1 ' n m Let X = vert P . Then there i s an a f f i n e transform X, with an A (nri-n-K-l)-dimensional axis of symmetry M containing u^, u^ . Let M be the orthogonal complement of M i n j? 1 1 1"^ 1 1 d 1 ^ Then - 56 -(u_, u , W' W +W1) C M 1 m l n n — i s a l i n e a r transform of the axis f i g u r e X^ and i s a c e n t r a l diagram of the coaxis f i g u r e X . THEOREM 5 (McMullen and Shephard [8]): I f an a f f i n e transform X A of the set of v e r t i c e s of a d-polytope P with n v e r t i c e s has a b-dimensional axis of symmetry M containing m points u , > i , u of X, , then there m A i s a polytope a f f i n e l y equivalent to P with a (j(n+m)-k-l)-dimensional axis of symmetry M containing the v e r t i c e s corresponding to u^, ..., . The points u_., .... u must be chosen such that the remaining points'of 1 m X l y i n g i n M occur i n coincident p a i r s . A ' , The reason f o r the f i n a l remark of theorem 5 i s t h i s . I f u and u' are coincident i n M , a permutation a corresponding to the l i n e a r transformation r e f l e c t i o n i n M may be chosen such that u and u' are fi x e d by a or transposed by a . Then, under the corresponding permutation a of X , u and u' are fi x e d by a or transposed , r e s p e c t i v e l y . A tra n s p o s i t i o n of u and u' i s induced by r e l f e c t i o n i n some axis. For example, i n the regular octahedron P i n F i g . 10 , Vt Vr.Vt the axis M corresponds, to two d i f f e r e n t axes of P . The permutation a - 57 -interchanging V • and , and • and V,. and corresponds to r e f l e c t i o n i n the axis M . The permutation T. interchanging and s and V,. and , corresponds to r e f l e c t i o n i n the plane containing M , V, and V„ . o 1 2 Zonal Diagrams • The r e s u l t s under t h i s heading are due to McMullen (5) and t h i s presentation follows h i s . A zonotope i s the vector sum of a number of l i n e segments. We w i l l define a zonal diagram, and using the diagram, do two things: f i r s t , enumerate the-combinatorial types of zonotopes with a small number of zones, and, second, e s t a b l i s h a correspondence between zonotopes of d i f f e r e n t dimensions. Enumeration of zonotopes leads, through a n a t u r a l correspondence to enumeration of arrangements of lryperplanes. A zonotope i s the vector sum of a f i n i t e number of closed l i n e segements. We w i l l assvime that the midpoint of each l i n e segment i s the o r i g i n , so a d-zonotope P may be expressed as P = S, + . . . + S I n whence S, = conv {Z,,-Z.} , i = 1, .... n . i i x Thus P = {xlx = X..Z.. + . + X Z , |X. |<1, i = 1, . . ., n> 1 1 1 • n n ' x 1 — The set (j_Z^> • •••» + ^ n ^ •'-s K a i ^ t o ^e a generating set i n P . A face F of P may be wr i t t e n i n the standard form F = S, +..'.'+ S + z.-Z, ... + E Z l a ro r+1 (r+l)a n na where a i s a permutation of {1, ..., n} and = + 1, For suppose a hyperplane H supports P i n F . Then we have u and a such that • F = { xel?| . <x,u> = a} • r d, and P G txeE | <x,u> <_ a} . Let H q be the hyperplane p a r a l l e l to H through 0 , with equation . <x,u> = 0 . Then f o r some r and some permutation a of {1, ..., n} <Z. ,u> = 0 for i = 1, .... r <e.Z. ,u> > 0 for i = r+1, n, e.e{+l,-l}. I xa i For any Z = n ,,Z , , , . a + . . . + o Z , where 11.I < 1, ^ 'r+1 (r+1) 'n na 1 x! — <Z,u>-< < E ' n Z / i n +... + e Z ,u> — r+1 (r+1)a n na with s t r i c t i n e q u a l i t y unless Then since n. = e. , i = r+1, ..., n x x S. C H , i = 1, .. ., r xa — o ' we have F = S ' +...+S + e , 1 Z / ] . . + . . . + e Z , l a ra r+1 (r+l)a n na the r e s u l t to be established. Consequently, a l l v e r t i c e s of P are of the form e.Z. + ... + e Z , e . e { l , - l } , ' i = l , . . . , n , 1 1 n n x although not a l l points of t h i s form are n e c e s s a r i l y v e r t i c e s . The argument shows that i f F = H f l P , the normal vector to H i s normal to S. , . xa i = 1, r . Thus to each corresponds a zone of faces of the form P H H , where H i s a hyperplane whose normal i s orthogonal to . I f no two of the are p a r a l l e l , P i s said to be a zonotope with n zones If i s not hard to see that i f no two S. are p a r a l l e l , a l l the faces of i *. P are p a r a l l e l o t o p e s i f and only i f the are i n l i n e a r l y general p o s i t i o n . (A K-parallelotope i s a polytope a f f i n e l y equivalent to a K-cube) Such a zonotope i s c a l l e d a c u b i c a l zortotope and i s the analog of the s i m p l i c i a l polytope. I f a l l the S.^ but one l i e i n a hyperplane the corresponding zonotope i s a prism. Let P = S, + ... + S , S. = conv{Z.,-Z.} , i = 1, n 1 n x x x be ad-zonotope i n . Let Z = ( ± z v . . . , +zn) and l e t Z = (+Z., ... , +Z ) C E n ~ d - 1 - n — be a c e n t r a l transform of Z as defined under the previous heading. In the s p e c i a l case whei-e no two S/ are p a r a l l e l , Z i s c a l l e d a zonal diagram of the zonotope P with n zones. As usual, the faces of P may be characterized i n terms of Z (even when some of the are p a r a l l e l ) . THEOREM 6 : Let Z = (+Z., , , +Z ) be a;central transform of Z . Let - 1 - n P = S, + ... + S , S. = conv {Z. ,-Z.} , i = 1, ..., n . 1 n ' x x x Let a be a permutation of {1, n} and e^e{+l,-l}, i = r+1, n . Then F = S, + ... + S + e' Z, , . v + ... + e Z lo ra r+1 (r+1)a n na i s a face of P i f and only i f 0 r e l i n t conv { E , 1 Z / I 1 . e Z }. r+1 (r+1)a ' ' n na Proof: Without loss of ge n e r a l i t y , l e t F be a face of P , of the form F = S 1 + . .. + S + Z •'+...+ Z . 1 r r+1 n We have already seen that i f F i s a face of t h i s form, there i s a hyperplane with equation . <x,u> ~ 0 such that . <Z^,u> = 0 , i = 1, ..., r . <L .,u> • = u. > 0 . x • i • Choose u so that - u .-.+ '...+ u '= 1. r+1 n - 60 -Since ( Z ^ , ..., Z ) i s a l i n e a r transform of ( Z ^ , . . . , Z^) , a f a m i l i a r argument implies that ( 0 , 0, V 1^^' •••> V»n) 1 S a l i n e a r dependence of (Z.,, . . . , Z ) and so 1 n v . , z + ... + u z: = o . ' r+l r +l n n Since ui > 0 and y ,-+...+ y = 1 » t h i s shows that x r+l n 0 e r e l i n t conv {Z , - , . .. , Z } .' r + l n C l e a r l y the argument may be reversed. A c e n t r a l l y symmetric set z = (+zl5 +zn) spanning E D and such that Z_^ i s not a s c a l a r m u l t i p l e of .% f o r i ^ corresponds to two d i f f e r e n t polytopes: the c e n t r a l l y symmetric polytope Q = conv Z and the zonotope P with n-zones. The c e n t r a l transform may be used to characterize the faces of P and Q , although of course the c h a r a c t e r i z a t i o n s are d i f f e r e n t . In the next s e c t i o n we w i l l see that c e n t r a l l y sjTnmetric polytopes and zonotopes are, i n a sense, dual concepts THEOREM 7: Let Z = (+2 , +Z r) be a c e n t r a l l y symmetric set of points i n E N d . Then Z i s a zonal diagram of a d-zonotope with n zones i f and only i f every open half-space of E N ^ with 0 on i t s boundary contains at l e a s t 3 points of Z . Proof: • Let Z = *'"* -"^r? ^ e a c e n t r a ^ - transform of Z . Any set whose c e n t r a l transform i s Z i s l i n e a r l y equivalent to Z . The set Z generates a zonotope" P i n the usual manner. I f P i s not a zonotope, . there i s a n o n - t r i v i a l l i n e a r dependence between (say) Z^ and Z^ of the form ( A 1 > A 2 , 0 , 0) . Therefore, the f i r s t coordinate of ' Z^, ... » Z i s 0 , so-'-Z ,. •••> Z R l i e i n a hyperplane H . The two open half-spaces defined by H contain only two points of Z , establishing the implication in one direction. The argument may be reversed to obtain the equivalence. Let P = S- + ...'+ S , S. = conv { Z . , - Z , } , i = 1, . .., n; 1 n x x i P ' = Si + ... + S' S! = conv { Z ! , - Z ! } , i = 1, ..., m 1 n l l x ' be zonotopes in . If there are integers v a , . . . . v n > 0 and a non-singular linear transformation A of E^ such that P' = ( V 1 S 1 + ... + V nS n)A ,. then P and P F are said to^equivalent zonotopes. Equivalent zonotopes are combinatorially isomorphic, but combinatorially isomorphic zonotopes need not be equivalent. Those combinatorial types for which any two zonotopes of that combinatorial type are equivalent are said to be zonally stable. It i s easy'to show via zonal diagrams that zonotopes with at most d+1 zones are zonally stable, and that a zonotope with d+2 . zones i s zonally stable i f and only i f i t s zonal diagram has at most 3 distinct diameters. A zonotope P = S - + . . . + S , S . = conv { Z . , - Z . } , i = 1, n I n. i x i is equivalent to Q = V 1 S 1 + ... + V S , V. > 0 , i = 1, ..., n . I I n n x If two of the are pa r a l l e l , say ^ 0 and , then P and P' = ST + ... + S , 1 n-1 are equivalent zonotopes. Thus i f P i s a zonotope with zonal transform Z = .(+Z > . .., +Z^) , then we may f i n d from Z a zonal transform of a zonotope- P* with m zones equivalent to P . For i f - P i s not a zontope with n zones there i s an open halfspace with 0 on i t s boundary containing less than three points of Z . I f say Z^ i s a point i n such an open half-space, by the properties of l i n e a r transforms the p r o j e c t i o n of Z\{Z ,-Z } i n t o the orthogonal complement of the subspace l i n Z i s a n n n c e n t r a l transform of Z\{Z ,-Z } . Continuing t h i s process gives a zonal n n diagram of a polytope equivalent to P with m zones. Although there may be a choice of which point to eliminate at each stage, the r e s u l t i n g zonal diagram c a l l e d a reduced diagram of Z w i l l be.of a polytope equivalent to P since each step preserves equivalence. This d i s c u s s i o n e s t a b l i s h e s THEOREM 8: Let P = SV + ... + S , S. = conv {Z.,-Z.}, i.= 1, n 1 n ' l x' l ' be a zonotope. Then a zonal diagram of P i s equivalent to any reduced diagram of Z , the c e n t r a l transform of Z ~(+Z^, +Z ). Two zonal diagrams, Z and Z' are said to be isomorphic (as zonal diagrams) i f the points of the two diagrams may be l a b e l l e d Z = ( + z v + z n ) Z' = (+Z]_, +Z^) such that 0 e r e l i n t conv {e,Z. e Z., N} 1 i ( l ) ' r x(r) i f and only i f 0 e r e l i n t conv {e-Z.-^,' e Z.. N'} 1 i ( l ) r x(r) for a l l p o s s i b l e choices of e.e{+l,-l} and sets of d i s t i n c t .subscripts x { i ( l ) , ..., i ( r ) } . - $3 -Two zonal diagrams, as above, are equivalent i f there are V\ > 0 , i = 1, n and a non-singular linear transformation such that Z. = V.Z! A , i = 1, ..., n . x x x ' * ' Clearly we have THEOREM 9: Two zonotopes with n zones are combinatorially isomorphic i f and only i f their zonal diagrams are isomorphic. THEOREM 10: Two zonotopes with n zones are equivalent i f and only i f their zonal diagrams are equivalent. We also state without proof three further analogs to theorems of affine transform. THEOREM 11: With the notation of theorem 8, a zonal diagram of onto + ... + is equivalent to a reduced diagram of (+Z^, +Z ) the orthogonal complement i n E n d of l i n :(Z ^, ..., Z^) . THEOREM 12: A zonal diagram of V/(S^^, S^ ) i s equivalent to a reduced diagram of (+Z^, . .•, , +Z^) . THEOREM 13: Let F = Sn + ... + S + Z ,.. + ... + Z be a face of P . 1 r r+1 n Then f (Z Z^) is a Gale diagram of a set whose convex h u l l i s combinatorially isomorphic to P/F . One application of zonal diagrams i s to establish a correspondence between zonotopes with n zones i n E^ and zonotopes with n zones in E n ~ d . Let P = S- + ... + S , S. = conv {Z.,-Z.} , i = 1, n 1 n x x l be' a d-zonotope (where pairs of the may be para l l e l ) , and let z »• ( + z r ..., +zn) be a central transform of Z =(+£:;, .. . , +Z ) . Let S. = conv'{Z. ,-Z.}, • - 1 - n x . x x — n—d i = 1, . . ., n . Since' ' Z spans E linearly, the zonotope £4 S, + . .. + S 1 n is an (n-d)-zonotqpe in E , called the derived or associated zonotope of P . Clearly P i s a derived zonotope of P . Note that i f pairs of the may be parallel that the derived zonotope depends on the particular representation of P as a sum of line segments. If P i s a d-zonotope with n zones, the 'S ' are uniquely defined and P is uniquely defined up to a non-singular linear transformation. In this case, i f P is also to be a zonotope with n zones, Z w i l l be a zonal diagram of P and must satisfy the condition of theorem 7 . Therefore no hyperplane through 0 may contain n-2 or more of Z^ , Z^ . Denote the class of d-zonotopes with this property by . THEOREM 14: For each d >_ 2, n >_ d+2 there i s a one-to-one correspondence between the combinatorial- types of zonotopes in with n zones and zonotopes xn wxth n zones. Proof: The definitions of 1^ and zonotope with n zones imply that d >_ 2 and n-d >2. The required correspondence is given by P > P . It remains to show that, i f P —> P, Q —> Q , then P and Q are of the same combinatorial type i f and only i f P and Q are of the same combinatorial type. To do this, we f i r s t show that i f ' .... . F = S , + . . . + S + Z ,.+...+ Z is a face of P with 1 r r+1 n Z. + ... + Z E r e l i n t F , then F = Z, + ... + Z +'S ,,+...+ S is 1 n 1 r r+1 n a face of P and Z^ + ... + c r e l i n t F . The hypothesis implies that Z: :+... + Z = X.Z. + ... + X Z + Z ,. + ...+ Z ', I A . I < l , i = l , . . . , r . 1 n i l r r r+1 n 1 x' Therefore, 0 = ( l - A j Z . + ... +.(1-X)Z , 1 - A . > 0 , i = l , r x x T r x r Dividing this expression by. ^ (1-A.) shows that i=l 1 - 65 -0 e r e l i n t { Z , , ..., Z } 1 r and so F i s a face of P . Since F i s a face of P , 0 e r e l i n t { 2^, . .., Z^} and reversing the above argument shows that 0 E r e l i n t { Z ^ , Z ^ } . We have proved Lemma -1: For each choice E^E{1,-1} , i = 1, ... , n , . E . Z . + . . . + £ Z 1 1 n n i s a vertex (boundary point, i n t e r i o r point) of P i f and only i f e i , + ... + E Z 1 1 n n i s a vertex (boundary point, i n t e r i o r point) of P . Lemma 2: Suppose Z - l+Z'^, +Z.J, no hyperplane through 0 contains a l l but one of Z Z^ and Z± i 0 , i = 1, ..., n . Suppose that for each choice £ e { l , - l } - , i = 1, n i t i s known whether 1 1 n n i s a boundary point, i n t e r i o r point or vertex of P . Then the combinatorial type of P i s determined. The conditions of lemma 2 ensure that P i s a polytope with v e r t i c e s and i n t e r i o r points. Since the combinatorial type of P i s determined by which v e r t i c e s belong to each facet of P , Lemma 2 follows from the observation that the facets of P are the subsets of the form F = S, + ... + S + E N Z , +.... + E Z • l a ra r+l (r+l) a n na which are maximal with.respect to i n c l u s i o n such that every point n,Z_ + . . . + n Z + £ , n Z . , _ + ... + E Z 1 l a r na r+l (r+l)a n na where n.^ £ {+1,-1} , i = 1, r . Thus lemmas 1 and 2 imply that the combinatorial type of P determines that of P , and v i c e versa, proving that the correspondence i s Indeed a b i j e c t i o n , concluding the proof. - 66 -Corollary: For each d >_ 2 , n > d+2 there is a one-to-one correspondence between the combinatorial types of cubical d-zonotopes with n zones and cubical (n-d)-zonotopes with n zones. Proof: A d-zonotope P is cubical i f and only i f (in the notation of Theorem 7) Z^, Z^ are in linearly general position. If n >_ d+2 , no n-2 of Z^, . . ., Z^ can" l i e in a hyperplane , so P e . Furthermore, since a set is in linearly general position i f and only i f a linear transform of the set is in linearly general position, P i s also a cubical d-zonotope. The inequality d>_2 implies n >_ n-d+2 , so P e d , proving the corollary by theorem 14. The second application of zonal diagrams which we shall consider is the enumeration of combinatorial types of zonotopes with a small number of zones. This is done in much the same way as the enumeration of polytopes using standard Gale diagrams, the only essential difference being that a zonal diagram i s a centrally-symmetric set. The definition of isomorphic zonal diagrams shows that for every zonal diagram, there is an equivalent zonal diagram in which every non-zero vector is a unit vector. Such a diagram is called a standard zonal diagram. The zonal diagram of a d-zonotope with d zones consists of 2d points coincident at 0 . Thus there i s only one type, the d-cube. The standard zonal diagram of a d-zonotope with d+1 zones is 1-dimensional and consists of a centrally-symmetric set .of •'2(d+1) points lying at +1, -1 or 0 . Theorem 8 characterizing diagrams of zonotopes implies at least 3 points coincide at +1 (and -1). Therefore a diagram may have 0,2, 2(d-2) points, coicident at 0 , implying d-1 combinatorial types.' A cubical d-zonotope with d+1. zones generates a - 67 -diagram in which the points are in linearly general position, that i s , none are 0 .. There i s only one such diagram, and therefore one such 3 zonotope. In E i t is the rhombic dodecahedron. The standard zonal diagram of a d-zontope with d+2 zones 2 consists of points in E at 0 and on the unit c i r c l e . As i n the case of Gale diagrams, diameters may be rotated without changing the isomorphism type and hence without changing the combinatorial type of the corresponding zonotope. Diameters always have points at both ends, so any two diagrams have the same number of diameters. If the diameters are equally spaced, two standard diagrams are Isomorphic i f and only i f they are orthogonally equivalent. In the diagram of a cubical d-zonotope, no points may l i e at 0 , and distinct points of Z^ , Z^^ must l i e on distinct diameters. Thus the diagram is unique and consists of d+2 equally spaced diameters with a point on each end. To enumerate the other cases, i t i s necessary to compute the number of ways -2(d+2). points may be distributed in a centrally symmetric manner at the ends of K equally spaced diameters (2<K<_d+2) and at 0 , such that the zonal diagram condition (Theorem 8) holds. This number may be computed with the help of Polya's theorem and is given below. Denote the number of combinatorial types of d-zontopes with n zones by Z(n,d) and the number of types of cubical d-zonotopes with n zones by Z^(n,d) . Then the results found above are summarized by THEOREM 15: , For d >_ 1 , Z(d,d) = Z (d,d) =1. For d > 2, Z(d+l,d) = d - 1 and Z (d+l,d) = 1. For d >_ 2, Zc(d+2,d) = 1 and - 68 - d d+2 .. - „ 5 . 2 2 d even Z(d+2,d) = I [ I 2 % ( | ) ] - 5d - ±j+ "I d r = 1 S / r 7.22 d odd where <J>(2) is the number of positive integers less than and relatively prime to n and "S/r" means "S divides r and S is a positive integer). Finally we describe the relationship between zonotopes and arrangements of hyperplanes. A K-arrangement (of hyperplanes) is a f i n i t e set' of hyperplanes in real K-dimensional projective space not containing a common point. The components of the complement of these hyperplanes f o r m a set of interiors of convex polytopes. These polytopes and their faces are called the faces of the arrangement. Two arrangements are said to be combinatorially isomorphic i f there is a bijection between the faces preserving inclusion. A simple K-arrangement is an arrangement i n which the hyperplanes are i n general position, that i s , no more than K hyperplanes intersect at a point. Real K-dimenslonal projective space P may be defined as the' space obtained by identifying antipodal points of the unit K-sphere S i n K+l E . Thus a K-arrangement of hyperplanes determine a set of hyperplanes K+l through 0 i n E . The normals to these hyperplanes determine a centrally-symmetric subset of S which then generates a (K+l)-zonotope in the familiar way. The normals to the hyperplanes determine a set of points in P , which we may term a K-arrangement of points. Two such arrangements are isomorphic i f the corresponding arrangements of hyperplanes are isomorphic. It may be shown that the faces of the arrangement of hyperplanes correspond to the faces of the dual of the zonotope i n a one-to-two fashion, and that arrangements are isomorphic i f and only i f the zonotopes generated are isomorphic. Clearly, this close correspondence enables results of zonotopes to - 69 -generate results concerning hyperplanes and vice versa. We w i l l content ourselves by noting that simple K-arrangements of n hyperplanes correspond to cubical (d+1)-zonotopes with n zones, and restate the corollary to theorem 14 and part of theorem 15 as theorems about arrangements. THEOREM 16: If K >_ 1 , n >_ K+3, there is a bijection between combinatorial types of K-arrangements of n hyperplanes and simple (n-K-2)-arrangements of n hyperplanes. THEOREM 17: There is only one type of K-arrangement of n hyperplanes for n <_ K+3 . For further results, concerning Sj^lvester's problem and "ordinary hyperplanes", see the original paper. 7. A Geometric Interpretation of Diagrams Up to this point diagrams and transforms have been treated from a s t r i c t l y algebraic viewpoint. In this section a geometric interpretation due to McMullen w i l l be described, based oh representing d-polytopes as sections or projections of higher-dimensional polytopes affinely equivalent to regular polytopes. Although diagrams may be discussed using the geometric interpretation alone, the algebraic method was chosen for several reasons. F i r s t , fewer preliminearies in the theory of polytopes are required.' Second, some results are more economically proved^particularly those relating the affine and linear transforms. Third, many results concerning affine and central transforms and zonal diagrams become corollaries of properties of the linear transform. However, the algebraic point of view, while revealing one unity, obscures another. Namely, that affine and central transforms and zonal diagrams may be defined in a. s t r i c t l y analogous fashion.and the analogy cannot be extended to produce new kinds - 70 -of diagrams. F i r s t , some terminology. A regular d-polytdpe P i s a d-polytope such that for every p a i r of K-faces of P there Is a congruence (symmetry) of P interchanging them. There are 5 regular 3-polytopes: the regular tetrahedron, the cube, the regular octahedron, the regular dodecahedron (with 12 pentagonal facets and 20 v e r t i c e s ) and the regular icosahedron (with 20 t r i a n g u l a r facets and 12 v e r t i c e s ) . The tetrahedron i s dual to i t s e l f , the cube and octahedron are dual and the dodecahedron and icosahedron are dual. There are 6 regular 4-polytopes, but i n dimension 5 or more there are only 3 regular polytopes. These 3 are the analogs of the tetrahedron, cube and octahedron and may be defined as follows. Let ii-^y ...,&} be the standard basis of E n . Then the standard (n-l)-simplex i s defined to be conv {£, , ...,£'-} I n and i s to be considered as an (n-l)-polytope i n the (n-l)-space a f f ...»& n} with the centroid of (&^, H } as o r i g i n . The standard n-cube i s defined to be conv {+£., +...+ £ } , - 1 - - n where the convex h u l l i s to be taken over the Z n points formed by summing the elements of the standard basis w i t h a l l p o s s i b l e combinations of sign. The standard n-cube i s a zonotope with generating set ^ i ^ 2 / * '' *'i — ^n^ " The standard n-cross-polytope i s defined to be conv •••» +* "'• Denoting the standard n-simplex by T n, the'polar*.?; set of T n i s - T n . Except f o r n=l, T n Is not c e n t r a l l y symmetric. The polar set -11 -of the standard n-cube i s the standard n-cross-polytope (and v i c e verse, of course). C l e a r l y i f the standard basis i s replaced by an a r b i t r a r y basis i n the above d e f i n i t i o n s , the r e s u l t i n g polytopes w i l l be l i n e a r l y equivalent to the standard polytopes. The " s i m p l i c e 5 " , "cubes" and "crpss-polytopes" used to define transforms and diagrams geometrically w i l l be of t h i s type. The idea of the geometrical i n t e r p r e t a t i o n may be seen most e a s i l y (and l e a s t geometrically) f o r the l i n e a r transform. Let X = (x^,...,x n)<E d span E d l i n e a r l y . Imbed E d i n E n as the subspace L - { ( ? ! , . . . . ? n ) | ? d + 1 - ... « ? n > ' 9 > • The set X and i t s image under the imbedding may be i d e n t i f i e d without confusion. Let L be the orthogonal complement of L i n E n and l e t n J -7r and IT denote orthogonal p r o j e c t i o n of E onto L and L r e s p e c t i v e l y . Choose a basis Y = (y^> •»•» Y n) °£ ^ n such that y.ir = x. , i = 1, . . . , n . This may be done by choosing a basis f o r L from X , say x^, x^ and a b a s i s b , , , . . .... b for L . Then d+1 n ( x 1 , x d , x d + 1 + b d + 1 , x n + b n ) i s a b a s i s f o r E n of the required type. Let Y = (y^> • ••> y ) be the dual basis of (y^, y^) defined by 0 i f If j <Y->y-> = S.. where 8.. = {-, . c . i l i i IJ 1 i f l = j Then define X^ =( J b y X J = y •71 > 1 = 1 n • i i J - n-d I d e n t i f y i n g L with E , we claim that X^ i s a l i n e a r transform of X and every l i n e a r transform of X may be obtained i n t h i s way, i . e . t h i s - 72 -d e f i n i t i o n i s equivalent to the algebraic d e f i n i t i o n . To see t h i s , write the bases Y and Y i n the' form Y = ( ( x 1 , u i ) , . ( x n , u n ) ) , u ± e L X ; u. e L x Y = ( ( u 1 , x 1 ) , ( u n , x n ) ) ; Writing each basis as the rows"of a matrix, the dual basis property implies \ X n U n / 5 x \ u x / n n / where I i s the nxn i d e n t i t y matrix. Therefore / S 1 X l \ T / X l U l \ \ u x \ n n , x u • \ n , n and so = 0 . Thus, the f i r s t d and l a s t (n-d) columns of x. \ n n are orthogonal and since M^(X) i s e a s i l y checked to be non-singular, X^ s a t i s f i e s the algebraic d e f i n i t i o n of l i n e a r transform. The argument may be reversed to establish, the equivalence. 'A few f a m i l i a r basic fac t s concerning l i n e a r transform*follow immediately from the geometric d e f i n i t i o n . In p a r t i c u l a r , X may be obtain as a l i n e a r transform of by reversing the.roles of X and X^ , -13 -Y and Y^ and ?r and TT . As w e l l , since the imbedding of L and L"*" i s E n i s defined only up to non-singular l i n e a r transformation of L and L 1 , a set l i n e a r l y equivalent to i s also a l i n e a r transform. Now we are prepared to define the a f f i n e transform along the same l i n e s . Let X = (x^, X n ) E d span E d a f f i n e l y . Assume the centroid of X i s 0 . Imbed E d as a l i n e a r subspace of E n and l e t lf~ ( i d e n t i f i e d with E n d "*") be the orthogonal complement of L i n E n ^ . Let IT and TT be orthogonal p r o j e c t i o n of E n ^ onto L and L r e s p e c t i v e l y . Let Y = (y^, y^) be the set of v e r t i c e s of an (n-1)-simplex T such that n I y• = 0 ; x = y TT, i - 1, . . ., n . i = l If (say) x,, .... x, i s a basis of L and b J l l 5 b i s an a f f i n e ^ 1 d d+1 n basis of L ~ with centroid 0 , ( x 1 } x d , x d + 1 ^ + 1 > 0 > . , x n + b n) i s such a set. Now l e t T* be the polasr set of T , a simplex with v e r t i c e s Y = ( y ^ . . . , y n ) l a b e l l e d i n such a way that <y ±,y> = 1 , i f j ; i , j = 1, n . (We w i l l prove that t h i s i s p o s s i b l e l a t e r . ) Define X = (x , x ) by x. = y. IT , i = 1, . . ., n . i i . . This defines the a f f i n e transform f o r sets X with.centroid 0 . For an a r b i t r a r y f i n i t e set X' spanning E d a f f i n e l y , l e t X = X' + b be a tr a n s l a t e of X' with centroid 0 . Define the a f f i n e transform of X' to be X, as found above. A Q - 74 -Now we prove the equivalence of t h i s d e f i n i t i o n with the o r i g i n a l . The polar set T* of T i s defined by T* = { Z c E n _ 1 | <y ,Z> < 1 , i = 1, ...,-n> . Since T* i s an i n t e r s e c t i o n of n closed half-spaces H .=' { Z c E n _ 1 | <yjL,Z> < 1} , i = 1, . . . , n , and may e a s i l y be proved to be a'bounded set, T* i s an (n-l)-polytope-with n f a c e t s ; that i s , an (n-l)-simplex. Since each f a c e t F? i s contained i n the hyperplane 1-L =' {Z c E 1 1 - 1 | <y i SZ> => 1 } , i = 1, n , and since each facet of a simplex contains a l l but one of the v e r t i c e s , the l a b e l l i n g s p e c i f i e d i n the d e f i n i t i o n i s well-defined. The centroid of n T* i s 0 . To see t h i s , observe that since J y. = 0 , 1=1 1 ' n < Ii = l I y,> y,> = 0 > j = i , •••» n • i = i 1 3 Therefore, since . <y. ,y.> - 1 > 1 f' 3 » n • • l--<y±>yf = 0 i = i 3 implies ^ ' i ^ j ^ ~ ' ^ " ^ '• T n u s n < I y.>y,> = 0 , i = 1, ..., n , i = l 3 -1 n and since Y spans E n l i n e a r l y £ y. = 0 , the desired r e s u l t . Since " _ j = l 3 _ the centroid of Y i s 0 , the. centroid of X i s also 0 . (Thus the d e f i n i t i o n may be applied to X , reversing the r o l e s of Y and Y , etc, to obtain X as an a f f i n e transform of X .) ' Now the equivalence may he-proved by summarizing the r e l a t i o n between Y and Y as a matrix equation. Write Y = ((x^Uj,) , (\» u n)) > UJ: c L , i « 1, ...» n ; - 75 -Y = ((u , x ) , . . . , ( % » x n ) ) , u, e L, i = 1, Then the d u a l i t y between Y and Y implies ., n X l S l _ 1 \ / U l X l U = - n l , where I i s the nxn i d e n t i t y matrix. Then / u l X l ^ u x 1/ n n / x 1 u± - l \ \ x u -1 i \ n n / -ni This implies that i n the matrix ' X l 1 X l ^ X X X n i the f i r s t d+1 columns are orthogonal to the l a s t n-d-1 . Since the f i r s t d+1 columns are l i n e a r l y independent, as are the l a s t n-d-1 , the orthogonal also shows that the n columns are l i n e a r l y independent e s t a b l i s h i n g the non-singularity of the matrix. This proves that i s an a f f i n e , transform of X . I t i s l e f t to the reader to show that any a f f i n e transform of X may be obtained i n t h i s ^way. Some of the basic properties of the a f f i n e transform were reproved i n the course of the above proof, and some are evident from the d e f i n i t i o n . -To see how the geometric d e f i n i t i o n i s used, we reprove theorem 3.3 (characterizing f a c i a l subsets) using geometric methods. THEOREM 3.3: Let X = (x.. , . .., x ) < E d span E a af f i n e l y and l e t X x n — ' A be an a f f i n e transform of X . Then. S'CX, S ^ X , i s a f a c i a l subset of X i f and only i f 0 e r e l i n t conv S , (where S = {x.eX AI x. A S )}. i A 1 1 T Proof (by geometric methods): Suppose without loss of g e n e r a l i t y that the centroid of X i s 0 . Adopt the notation used i n the.geometric d e f i n i t i o n . Suppose S = {x^, ..., x^} , r < n , i s a f a c i a l subset of X . Then there i s a hyperplane H i n L supporting X i n S . The hyperplane does not contain 0 since 0 e i n t conv X and so the equation of H may be wri t t e n <x,u> = 1 such that . <x_j,,u> = l , i = l , . . . , r ; <x^,u> < 1 , i = r + l , n . Then c l e a r l y i f V = (u,0) e E n ^ •, the hyperplane H' i s E° ^ with equation <y,V> = 1 supports T i n {y^, y^}. Therefore <y±,V> = 1 , i = 1, ..., r ; <yi,V> < 1, i = r + l , ..., n . These equations imply that V e T* and since <y: , v > = l <=> v e F* , (where F* i s the facet of T* l y i n g i n the hyperplane with equation <y,y..> = 1) , V l i e s i n the face F* = F* n ... n F* 1 t and no smaller face of T* . That i s , V E r e l i n t F* . But since F ± = conv{ y 1 > y ± + 1 > • • • » Y n> » 1 = I» • • • > n » we:have F* «. F* f l ..." H F£ = conv{ y ^ , . .., y j • - 77 -Therefore V e r e l i n t conv (y r +2> '••» * and s i n c e VTT =' (u,0).-rr =0;, 0 e r e l i n t conv {x ,., . .... x } = r e l i n t conv S r + l n-as r e q u i r e d . The argument may be reversed to e s t a b l i s h the equivalence i n the theorem. We w i l l now d e s c r i b e another geometric d e f i n i t i o n of the a f f i n e transform, dual to the f i r s t . R e s t r i c t X to be the set of v e r t i c e s of a d-polytope P i n E D such that the c e n t r o i d of X i s 0 . This i m p l i e s that 0 e i n t P and so the p o l a r set -P* of P i s d e f i n e d and i s a d-polytope d u a l to P . The f i r s t geometric d e f i n i t i o n may be summarized ( i n the n o t a t i o n defined i n that d e f i n i t i o n ) by X A = ( v e r t -T*) TT xvhere T i s a simplex such that P = Tir . We w i l l show th a t (subject to the above r e s t r i c t i o n s on X) t h a t an e q u i v a l e n t d e f i n i t i o n of T* i s as an (n-1)-simplex T* such that L n T* = P* . In other words, we express the dual of P as a s e c t i o n of an ( n - l ) - s i m p l e x T* by a d-space L . Then the a f f i n e transform of X i s the orthogonal p r o j e c t i o n of the v e r t i c e s of T* i n t o L Lemma: Let Q be a K-polytope i n E w i t h 0 e i n t Q . Let Q* be the p o l a r set of Q i n E , l e t L be a d-dimensional l i n e a r subspace K of E , l e t IT be orthogonal p r o j e c t i o n onto L and l e t P be a d-polytope i n L . Then L C\ A* i s the p o l a r set of • P i n L I f and only i f P = QTT . *L Proof: For any X C L , l e t X denote the polar set of X with respect to L . We w i l l show that L H Q* = (QTO*L . The " i f " part follows immediately and i f P = L A Q* , then P * L= CQ,)*L . *L *L Since 0 e i n t QTT , then 0 e i n t (QTT) and so 0 e i n t P and 0 £ i n t P *L*L *L*L Therefore P = P and (QTT) = QTT , SO P = QTT , e s t a b l i s h i n g the lemma once we have proved P = (QTT) Let v e r t Q = ( V , ..., V ) where 1 n V. = (u.,u!), u. e L . u.e L , i = 1, .... n . x x x i x Then L H Q* = {xeL|<(x ,0) , V ±> < 1, i = 1, . . ., n} = { X E L | < ( X , 0 ) , ( u i } u ^ ) > <_ 1, i = 1, n} = { X E L | < X,U_^> <_ 1, i = 1, . . . , n} = {XEL|< x,V i Tr> •<_' 1 , i = 1, n} ^L = [ c o n v { V j j T , . ..,V n T r } ] , since 0 E i n t (QTT) AT = (Qrr) , proving the lemma. Applying the lemma with K = n-1 and T = Q., we deduce that P* = L C\ T* <=> P = TTT. Thus the simplex T* i n the geometric d e f i n i t i o n may be defined i n -two equivalent ways : 1) as the polar set T* of an (n-1) simplex T such that P = TIT Or 2) as an (n-l)-simplex T* such that P* = L D T* . _ 79 -We restate t h i s i n a manner designed to e x h i b i t the analogy with zonal and c e n t r a l diagrams : an a f f i n e transform of a set X = vert P i s a p r o j e c t i o n of the v e r t i c e s of a simplex defined (loosely) 1) as the dual of a simplex whose p r o j e c t i o n i s P or 2) as a simplex whose section i s a dual of P . The corresponding statements for c e n t r a l transforms and zonal diagrams are : a sonal diagram of.a zonotope P may be defined as a p r o j e c t i o n of the v e r t i c e s of a cross-polytope defined as 1) the dual of a cube whose p r o j e c t i o n i s P or 2) a cross-polytope whose section i s a dual of P ; and a c e n t r a l diagram of a c e n t r a l l y symmetric polytope P may be defined as a p r o j e c t i o n of the generating set of a cube defined as 1) the dual of a cross-polytope whose p r o j e c t i o n i s P or 2) a cube whose section i s dual to P . Observe that the analogy i s imperfect, as the a f f i n e transform and zonal diagrams are the p r o j e c t i o n of a set of v e r t i c e s , whereas the c e n t r a l diagram i s the p r o j e c t i o n of a generating set. This d i f f e r e n c e i s r e f l e c t e d p a r t i c u l a r l y i n the char a c t e r i z a t i o n s of f a c i a l sets and faces, which i s of a d i f f e r e n t nature f o r the c e n t r a l diagram than f o r the other two. We now carry out the proposed r e d e f i n i t i o n s i n d e t a i l , s t a r t i n g with zonal diagrams. THEOREM 1 ^ Let P = S, + .. . + S , S . = conv {Z. ,-Z.} , i = 1, ..., n 1 n x x x ' ' be a d-zonotope with n zones. Imbed L = E^ i n E n as a l i n e a r i - n subspace and l e t L be the orthogonal complement of L i n E . . Let TI-n J-and 7r be orthogonal p r o j e c t i o n of E onto L and L r e s p e c t i v e l y . Define an n-cross-polytope S - conv {+s 1 t ..., +s } - 1 - n using a) or b) below. Then Z = (+Z_ + Z ) , Z . = s . i T , i = l , . . . , n - 1 - n 1 x i s a zonal diagram of P and every zonal diagram of P may be obtained i n t h i s way. a) Let C be an n-cube C = T_ +•...+ T , T. = conv {t.,-t.} , i = 1,..., n 1 n ' x x' x such that Z. = t.rr. i = 1, . . . . n . Define X X S = C* = conv{+s., .... +s } such that - 1 - n <S.,t.> - S.. j i . j - 1, . . . . n . b) Let S = conv {+ + s ^ such that P* = L C\ S and the v e r t i c e s of S are l a b e l l e d so that i f • 1 l a r r a r+l (r+l/a n na (where e E{+1,-1}., i = 1, n and a i s a permutation of {l,...,n}) i s a face of P , the corresponding face of P* l i e s i n the face of S conv •{e 1s-,...,es }. 1 l a ' ' n na Proof: F i r s t we .prove the theorem f o r S defined using a). C l e a r l y since S i s an n-cross-polytope t (s^, s^) i s l i n e a r l y independent and therefore a basis of E n . But th e . r e l a t i o n s Z. = e . i T , i = l > . . . , . n .1 x <s;. ,t^.>^-5_ ; i , j - 1, n state the geometric d e f i n i t i o n of l i n e a r transform, proving that (s , 7 T , ... , s ir) i s a l i n e a r transform of (Z 1 . .... Z ). Therefore 1 i i 1 n (+S TT, +S TT) = (+ Z ,...,+ Z ) - 1 - n - 1 - n i s indeed a zonal diagram of P . I t remains to show that S i s the polar set C* of C . But n C* = {y|<y, I e±t±> < l . e ^ U . - l } - , i = 1, .. . , n} i = l n ;i n = {y = I V±s±\< I y i s i > I e ± t i > < 1, £ ^ { 1 , - 1 } , i=l,...,n} i = l i = l i = l n n = {y = I ^±s±\ I v±£± 1 1 J E i e { 1 » - 1 > > i = i , • • n} i = l i = l n n =' (y e I V.s | I |u. | < 1} i = l i = l = conv {+ s. , .... + s } - 1 - n = S . as required. The lemma of this s e c t i o n shows that the d e f i n i t i o n s a) and b) define the same class of polytopes S . The a d d i t i o n a l conditions i n b) ensure that the v e r t i c e s of S are l a b e l l e d c o r r e c t l y . For suppose . F > t. + ...+ t + T... + .'..+ T 1 r til n i s a face of C . .Then the corresponding face of S i s F* ='{yes| <y,t> = 1, for a l l ' t e F } . n n Since y e S , y = I A s , I \\.\ <_ 1 . i = l i = l Since t E F , t = t-• + ... + t + y , , t + ...+ y t , |y.| < 1, i = r+1 n. 1 r r+1 r+1 n n ' l 1 — In p a r t i c u l a r , t + ... + t e F and so n < y A . s., t, + ... + t > = i . , u n i l l r i = l Therefore A, + ... + A =1 and AJ =0 , i = r+1, n . Since t h i s 1 r • i condition i s c l e a r l y s u f f i c i e n t - 81 -r • r F * = { y e S | y = I X S. ,1 X -1, 0 < X.} i = l i = l = conv {S,, . . . . S } . 1' ' r This proves that the l a b e l l i n g described i n b) i s the correct one, and concludes the proof of the theorem. Observe that since any n-cross-polytope S = conv{+5^,..., +• S^} i s l i n e a r l y equivalent to the standard n-cross-polytope X n = conv{ + £ n , . . . , + & } - 1 - n by the non-singular l i n e a r transformation T defined by. 5 . T = 2.. , i = 1, .. ., n , i x i f f o r a zonotope P ?* = S C\ L then p * r = x n n ( L T ) . Thus the dual of a zonotope i s l i n e a r l y equivalent to a cross-section of a regular cross-polytope. I t i s possible to see t h i s d i r e c t l y i n a way which gives a simpler r e n d i t i o n of geometric d e f i n i t i o n b) . THEOREM 2 (McMullen [5]): Let X n be the standard n-cross-polytope and l e t P be as i n theorem 1. Then the l i n e a r map A : E d -—> E n defined by n x A = y < x , Z . > £ . .L., x x x=l i s a one-to-one l i n e a r map such that P*A = (E d A ) C\ X and (+Jt-^ Tf , . . . , + fc^Tr ) i s a zonal diagram of P where IT i s orthogonal p r o j e c t i o n onto the orthogonal complement of E d A i n E n . n - 83 -Proof: F i r s t compute d n P* = {xe.E |<x, I e.Z.> £ 1, e e{l,-l} , i = 1, .. . , n} . i = l 1 1 I n '= {xeE | I E.<X,Z.> <_ 1 ,E.E { 1 , - 1 } , i = 1 n} i = l n = {xeE | I |<x,Z.>| < 1}. i = l 1 The map A i s l i n e a r , and i s one-to-one since { Z^, Z^} spans E1" Since X n = {yeE n| y = £ H , £ Jx | < 1} i = l i=l; c l e a r l y y e P*A i f and only i f y e X n H (E d A ) , implying P * A = x n O (E d A ) . Since a zonal diagram of any set l i n e a r l y equivalent to P i s also a zonal diagram of P ,(+ + & n) 7 r I s 3 zonal diagram of P f o r some l a b e l l i n g of {£.. , . . . , £ > . I t i s l e f t to the reader to show that the I n i n d i c a t e d l a b e l l i n g i s the correct one. . The geometric treatment of the c e n t r a l transform i s very s i m i l a r to that of the zonal diagram. THEOREM 3: Let P. be a centrally-symmetric d-polytope i n E d w r i t t e n i n the form P = conv {+x^, + x^}. Let ' C = T, + ... + T , T. = conv {t.,-t.} , i = 1 , n 1 n i 1 l be an n-cube defined by a) or b) below. Then, l e t t i n g IT be x n orthogonal p r o j e c t i o n onto the orthogonal complement L of L i n E , the set X =(+x. , . .. , + x ) , x. « t. TT , i - 1, .. . , n v>- 1* ' - n' l i . -84 -i s a c e n t r a l transform of X = (+ x^, ..., + x ). a) Let S = conv {+ S^, . . . , + 5^} be an n-cross-polytope such that x. = S . T r , i = l , n i x ' ' where P C L = imbedded as a l i n e a r subspace of E n and TT i s orthogonal p r o j e c t i o n onto L . Define C by S A = C = T. + ... + T , T. = conv {t.,-t.} , i = 1 , n 1 n' x x' i ' where <s .,t. > = 6..; i , j = 1, ... , n . i ' x x j ' ' J ' ' b) Let C be an n-cube such that, considering P C L = E d imbedded as a l i n e a r subspace of E n , P* = L A C and C = T 1 + . . . + T , T . = conv {t., -t} , i = l , . . . 1 n ' x x x such that the facet of P dual to x. l i e s i n the facet x T + ... + T. . + t. + T.,, + ... + T . . - ; ' 1 x -1 X 1+1 n Proof: The proof i s very s i m i l a r to the corresponding theorem f o r zonal diagrams. In f a c t , d e f i n i t i o n a) ensures that (x^, x^) i n a l i n e a r transform of (x,, .... x ) and so (+x., ..., + x ) i s a c e n t r a l 1 n - 1 - n transform of (+x,, .... + x ). The proof of theorem 1 showed that - 1 ' - n C* = S and so . S* =C . Using the lemma, we obtain that b) i s equivalent to a) as a d e f i n i t i o n of C , and i t i s not hard to check that the describ l a b e l l i n g i s the correct one. In conclusion, we have seen that a f f i n e and c e n t r a l transforms and.zonal diagrams may be defined i n terms of regular n-polytopes. Since for n >_ 5» t n e only regular polytopes ,are the ones'we.have discussed, _ 85 -types form a family which cannot be enlarged while s t i l l the analogy. 7. Representations of Polyhedral Sets In this section McMullen's [6] technique of polyhedral representations w i l l be described. This technique is the result of an attempt to construct a translation-invariant "diagram" for polyhedral sets. The method thus developed supercedes Shephard's [13] polyhedral diagrams described very b r i e f l y in section 4. A l l of Shephard's objectives may be achived more simply using polyhedral representations. In fact, this method i s more general than the diagrams and transform?already described, since problems concerning linear systems of polytopes and metric properties such as volume can be treated. We shall also see that polyhedral representations may be used to define the affine transform and that, indeed, properties of the affine transform may be derived more easily i n this way. Let TJ = (u n , .... u ) be an ordered set of non-zero vectors 1' ' n d ' d in E . Denote by *P(U) the class of non-empty polyhedral sets i n E formed as the intersection of closed half-spaces whose outer normals l i e in U . Assume without loss of generality that U spans E d linearly. If P eT(U) , P may be written in the form P = {XEE^I <X,U.> < n. , i = 1, ..., n} for some n e R , i = 1, . . . , n . A set of this form need not be d-dimensional but i f i t i s , the set N(P) of outer normal vectors to facets of P i s a subset of U . The vectors in U\N(P) are redundant in the definition of P . Assuming that U is fixed, P is completely determined by the n-tuple Cn]_> •••> n n ) e • For any b e E d , P + b = {xeEd| x - b e P } = {xeE Q |<x-b,u.> < n . , i = l , . . . , n } = {xeE d |<x,u.> < n. + <b,u.>, i = 1, . . . . n } 1 x — 1 ' x Thus tr a n s l a t e s of P correspond to vectors of E n of the form (n, + <b,u-> ..... n + <b,u >) , b E d . 1 ' 1 n n ' These vectors form a d-dimensional a f f i n e subspace of E n since U spans E d . Since we do not wish to d i s t i n g u i s h between translates of P , we define a representation associated with T ( U ) to be a l i n e a r map a from ••-.n „n— d . i i , E onto E wxth kernel {(<b,u . j>, <b,un>) |beEd} . Let ( £ i , ..., I ) be the standard basis of E n , and l e t 1' ' n ' u. = £.a , i = 1, . . . , n . x x Then ( r e f e r r i n g to the "dual-space" d e f i n i t i o n of l i n e a r transform i n s e c t i o n 2) , U - ( u ^ , . . . , u n) i s a l i n e a r representation of the set U . Associated with P i s the point n p = (n., .... n )a = / n.u. . 1 n « ^ x x x=l The point p i s associated with exactly those members of T ( U ) which are translates of P . In a moment we w i l l see the connection with Gale and polyhedral diagrams, but f i r s t l e t us derive some properties of the polyhedral representation and an associated point. For the remainder of t h i s s ection we w i l l adhere to the notation outlined above. THEOREM 1: With'the above notation, i ) P f § i f and only i f p e pos V. ; and i i ) i n t P f <f> i f and only i f p e i n t pos V . Proof: Since the d e f i n i t i o n of P i s i d e n t i c a l f o r every t r a n s l a t e of P , - 88. -we may argue as follo w s . The set P 4 <{> i f and only i f f o r some t r a n s l a t e Q of P , 0 c Q. But 0 e Q i f and only i f IT >_ 0 , i = 1, - . . ., n , n _ P•= • £ n.u. e pos U , : i = l 1 X proving i ) . The second part i s proved by r e p l a c i n g the i n e q u a l i t i e s by s t r i c t i n e q u a l i t i e s . In order to cha r a c t e r i z e the faces of P i n terms of the associated point p , define F. = {xeP <x,u.> = n.} , i =1, .... n: and J 3 3 F(V) = - '{F.l u . ' c V } , V c U . .1 J ~ Every face F of P. i s of the form F(V) f o r some V C U . I f F = F(V) , V i s s a i d to be a p a r t i a l subset of U f o r F ; i f V i s maximal. I.e. F £Z V.' i f and only i f u. e V . then V i s s a i d to be a ~ 3 3 complete subset of U f o r F . "The complete subset f o r a f a c e " i s the concept'for polyhedral sets dual to "the set of v e r t i c e s of a fa c e " of a convex polytope. Denoting as before V ="{u. G V |u. I V } ' J J thi s d u a l i t y i s c r y s t a l l i z e d by THEOREM 2: With the above notation, V C U i s a complete ( p a r t i a l ) subset for a non-empty face of P i f and only i f P e V (p e pos V). Proof:• "The proof again depends on choosing a s u i t a b l e t r a n s l a t e of P . If F i s a non-empty face of P , assume without loss of g e n e r a l i t y that 0 e r e l i n t F . Then i f V i s a complete subset f o r F , n > 0 i f and only i f u. £ V . Thus • P = ) n.u. c r e l i n t pos V . Ll x x - 89 -The argument i s r e v e r s i b l e , e s t a b l i s h i n g one part of the theorem. The other part i s proved s i m i l a r l y . Theorem 2 i s reminiscent of the Gale diagram condition f o r f a c i a l subsets. In f a c t we may define the Gale diagram using polyhedral representations j u s t as we found the Gale diagram by a s u i t a b l e p r o j e c t i o n of the l i n e a r transform. For i f P = {xeEd|<x,u^> <^n^, i = 1, n} = {xeE d|<x,n.\i.> < 1, i = 1, n} i s a polytope, P i s the polar set of the polytope P* = conv ^u. , . . ., n "4j } . 1 1 ' n n Since (u,, ..., u ) i s a l i n e a r transform of (u. , ..., u ), 1' ' n 1' ' n V = (n-u,, n u ) i s a l i n e a r transform of V = ( n ^ u - , . .., n "Ki ) . 1 1 ' ' n n 1 1 ' ' n n Let P be a d-polytope with 0 e i n t P such that U i s exactly the set of outer normals to the facets of P. Then P = {xeE d| <x,uv> <n., i = 1, ..., n} 1 ' l — x where n.> 0 , i = 1, ..., n . x Writing P i n the form P = {xeE d I <x,n. "U,-><1, i = l , . . . , n } , we see that P i s the polar set of -1 -1 P* = conv {n," u,, ..., n u } . l i n n Since U = (U^, U ) i s a l i n e a r transform of U = (u^, U R ) , V = (n_u. , .... n u ) i s a l i n e a r ti-ansform of V = (n_\i.,, . . . , n "Si ) . 1 1 ' ' n n 1 1 ' n n Let ir be p a r a l l e l p r o j e c t i o n of E n d onto a hyperplane through 0 not containing p such that pir = 0 . Then by theorem 3.10, VTT i s an a f f i n e _ 90 -transform of V = vert P* , and since n^, n^ are s t r i c t l y positive, Sir i s a Gale diagram of U and hence of P* . This approach could serve as an alternative definition of the Gale diagram, and as we have already remarked, some proofs are easier. Again we have a theorem enabling the dimension of a face to be determined from the representation. The proof i s essentially the same as before. THEOREM 3: With the notation of theorem 2, i f V is. a complete subset for F , dim F = card V - dim l i n V . At the end of section 5 , Shephard's polyhedral diagrams were bri e f l y discussed. Now, the relationship between these diagrams and polyhedral representations w i l l be discovered, and we w i l l see how easily Shephard's results may be deduced using the latter technique. Shephard's method was the following: given a polyhedral set P with 0 e re l i n t P and (u^, u^) the set of outer normals to the facets of P , P may be written as P = {xeEd | <x,u<- <_ n^ ,- i = 1, n nj>0, i = 1, n}. = {xeEdI<x,n. \i.> < 1, i = 1, .... n}. 1 l x — Since the polar set of P is P* = conv {0, n/u, , . . . , n \ i } , ' 1 1 n n ' whether or not P is a polytope, the properties of P may be deduced from properties of P* . A polyhedral diagram is an affine transform of {0,n..\i.,, .. . , n. \ i } , namely ' 1 1' ' n n ' J {-p,n l U ; L, ... v , - 91 -whether or not P is a polytope, the properties of P may be deduced from properties of P* . A polyhedral diagram i s an affine transform of -1 -1 {OjU^u., n u } , namely l i n n J : using the established notation of this section. • Shephard characterized unbounded faces of P by means of v (essentially) the following: THEOREM 4 (Shephard) : Let P = {xeEd|<x,ui> <_ n , i = 1, n} be a polyhedral set and let U = (U^, U ) be a linear transform of U = (u^, u n ) ' Then a face F with complete set V is unbounded i f and only i f 0 e conv V . Proof: Without loss of generality, l e t V = (u^, u^} and suppose (since a polyhedral representation i s translation-invariant) that 0 e r e l i n t F .. Then F is unbounded i f and only i f F contains a ray; that i s , there i s a non-zero vector w e E d such that Aw e F , X >_ 0. We have <Aw,u£> = 0, i = 1, K <Aw,u.> < n., i = K+l, n; A > 0 . ' x — I — Since the last line i s true for a r b i t r a r i l y large A , g.= <w,u.> < 0, i = K+l, n . i i — This implies that (0,...., 0, 3 K + 1 , 3 n ) is a linear dependence of u ; that i s , K+ K+l n n n Upon d i v i d i n g t h i s equation by - £ 3. , we get i=K+l 1 0 e conv V . The argument may be reversed. Shephard's main r e s u l t may be obtained e a s i l y using representations THEOREM. 5(Shephard): Let q e E and B be an nxK matrix with rank K . Let Q be the polyhedral set Q = {ZSE n | ZB = q, Z>_0} . If Q i s d-dimensional the l i n e a r map a : E n •> E K defined by I.a = b., 1 = i . X x (where {£, , . . . . £ } i s the standard basis of E n) i s a representation 1 n associated with Q , considered as a polyhedral set i n the d-dimensional (d=n-K) a f f i n e subspace • M ='{ZsEn|ZB=q}. The point q i s associated with Q . [In Shephard's terminology, the conclusion i s that (-q,b , b ) • i s a polyhedral diagram .of Q ;] be an nxd matrix of rank d and l e t Proof: Let U = y = (n^, n n) e E . Let P be the polyhedral set P = {xeEd|<x.u.> < n . , i = l , ...,n} • x — x ' = {xeE d|xU T <y} . We w i l l show that P and Q aire l i n e a r l y equivalent and B =U , and also that p = q , where p i s the associated point of P . Let S = {ZeE n | z >_0} d T be the non-negative orthant. Let L = -E U . Then since f o r a l l x e P , y - xU T >_ 0, y - PU T = (y+L) f l S . If a i s a representation of P with matrix V , Ker o = L by d e f i n i t i o n of a , so L =' {ZeE n| ZU = 0} . Therefore ' y + L = {ZeE n|zu = ya} = {ZeEn|ZTJ = P} and so y - PU T = (y+L) H S = { z E E n | z O = P ,/ Z>_ 0} . T I f Q = y - PU , P and Q are c l e a r l y l i n e a r l y equivalent, so U i s the matrix of a representation associated with Q and P i s the associated point of Q , with respect to U . Now, Q i s given i n the form Q =[Z£E n |ZB = q,z>0 }. Since Q i s d-dimenstional, M and L equal i n S implies L = M . Therefore there i s a KxK non-singular matrix D such that BD = U . Thus (b^, b ^ ) ; i s a l i n e a r representation of Q and since c l e a r l y D T P =.q f o r Q = y - PU , the theorem i s proved. Now l e t us apply polyhedral representations to i n v e s t i g a t e l i n e a r systems of polytopes. Before we do t h i s , some terminology i s us e f u l . From theorem 2 i t follows that {u } i s a complete subset f o r some face F i f and only i f p e r e l i n t pos (U\{u\}) . Since i n t h i s case (U\{tu}) spans E l i n e a r l y , F i s a facet; i n f a c t , the facet F. = {xePI<x,u.> = n.} . In other words, u. i s not redundant i n the d e f i n i t i o n of P . This J motivates the d e f i n i t i o n of the inner region of pos U ; i r U = {int pos (U \ {u\. } )| j = 1, n} . . The points p e i r U are p r e c i s e l y those associated with polyhedral sets P i n which no u. i s redundant. I f some u. i s redundant, n. may be J J J replaced by any n^ . > n j i n the d e f i n i t i o n without a l t e r i n g P . Define the closed inner region of pos U by c l i r U = {pos (U ^ {u_. } ) j = 1, . .., n} . Then f o r any polyhedral set we may define a point p i n c l i r U by n _ P = J n.u. i = l 1 1 where n_^ = sup {<x,u_^ > |xeP.- , i = 1, n). This defines a map ? ^P(U) c l i r U c a l l e d the representation of P(U) , asso c i a t i n g to each' P e 'P(U) the representative of P , p = P? . Since two polyhedral sets have the same representative i f and only i f each i s a t r a n s l a t e of the other, f establishes a b i j e c t i o n between points of c l i r U and the set of t r a n s l a t i o n classes P^ ,(U) of P(U). Making P ,^di) a metric space i n the bbvious way v i a the Hausforff metric (see Grilnbaum), S i s continuous and i t i s not hard to show that % ^ i s also continuous. Later we w i l l discuss the l i n e a r i t y of S and % ^ . Given polyhedral sets P, P' e P(U) and t h e i r representatives p and p' , P and P' are of the same strong combinatorial type i f and only i f Ip e r e l i n t pos V <=> p' e r e l i n t pos V , f o r a l l V <_ U . (Two polyhedral sets are s a i d to be of the same combinatorial type;, i f and only i f they are combinatorially isomorphic i n the usual sense and corresponding faces have p a r a l l e l supporting hyperplanes). This shows that c l i r U i s p a r t i t i o n e d i n t o the r e l a t i v e i n t e r i o r s of convex cones (with apex 0 ) . These sets are c a l l e d type-cones and correspond to the, strong combinatorial types of "P(U) . The type-cone corresponding to a point p i s H{V£U|p e r e l i n t pos V} and i s therefore r e l a t i v e l y open. r Now we return to l i n e a r systems of polytopes. Let P^, P be polytopes i n E d . Then the set of polytopes of the form P =-X 1P 1 + ... + A P , X. > 0, i •= 1, r , 11 r r x — i s a l i n e a r system. I f the supporting hyperplane to P^ with normal u H. = {xeE^I <x,u> = X . } , i = l , . . . , r , i x the supporting hyperplane to P with normal u i s d r H = {xeE |.<x,u> = Tx.a.} . . ,x x x=l Thus i f F. = H. D P. , the corresponding face of P i s x x x r F = n n p = y x . F . . 1-1 1 1 This shows that i f X..X'. >0 , i = 1, .... r , then x x ' ' ' ' P =X,P, + ... + X P 11 r r and P' = X'P.. + ... + X'P 11 r r are strongly combinatorially isomorphic. The polytope P may have facets with outer normals not among the outer normals of P^, P r • However, i f the polytopes i n the l i n e a r system f o r which X_^ > 0 , i = 1, . . ., r , are d-dimensional, and a l l the outer normals to the facets belong to the set U , then every polytope i n the system belongs to P(U) , in c l u d i n g P , i = 1 , r . Furthermore, since a l l polytopes i n the system with A_ > 0 , i = 1 , r , are of the same strong combinatorial types t h e i r representatives a l l l i e i n the same type-cone, say C . The d e s c r i p t i o n of the supporting hyperplane r shows that i f p. i s the representative of P. , then T A.p. i s the i = l r r epresentative of • \ A .*P. . i = l We have already remarked that i f P T . ' P 2 that + need not belong to 'T(U) . I f P j ^ P ^ a r e associated with P^ ' ^ 2 > and P i s associated with p = p^ + p^ , then P^ + P^ <£_ P ( a f t e r a s u i t a b l e t r a n s l a t i o n ) . To see t h i s , suppose P; = {x|<x,uv> < n; , i = 1 , ..., r} 1 1 I — i ' P 2 = iy\<Y,u±> £ A ±, i = 1 , r}. Then ' . P. + P = {x+y| <x,u.> < n.;<y,u.> < A., i = 1 , r} 1 2 •' i — l y ' l — l ' <C {z|<Z,u.><n.+A.,i = l , ...,r} — ' l — i i = P . . Since i f P^ = AP 1 + ( 1-A)P 2 ; 1 >_ A >_ 0 , { p A^ 1 ;>A>0 i s a l l n e a r s y s t e m of strongly combinatorially equivalent polytopes, the corresponding representatives p o£: P^ must a l l belong to the same type - cone C. A A Therefore the representatives p^ and p 2 of P^ and P 2 belong to c l C . Thus P^ + ? 2 = P i f and only i f P ^ J P 2 e c ^ ^ o r s o m e type-cone C . Using arguments of t h i s s o r t , a number of r e s u l t s about type-cones may be proved. I f [P ].) , [P 2] e P T(U) , x ^ l \ ^ + x 2 ^ 2 ^ ± S w e l l _ d e f i n e d as [ ^ i ^ + ^ 2 ^ 2 ^ * ^ l ' ^ 2 —^ ' w e c a n d i s c u s s " t n e l i n e a r i t y of f ^~ : c l i r U ->- •'T^CU) , where l i n e a r i t y means the preservation of non-negative l i n e a r combinations. Lemma 1: Let D be a r e l a t i v e l y open convex subset of c l i r U .. Then ? i s l i n e a r on D i f and only i f D £T C f o r a type-cone C . Proof: Choose PJL>P2 e D > associated with P^» P2 e • Since D i s r e l a t i v e l y open and convex there are e - D a n& x > ^-p^? > 0 such that P l = A l q l + ( 1 - x 1 ) q 2 > P2 = V q l + ( 1 ~ X 2 ) q 2 * Therefore P^ ,1> ^ are strongly combinatorially isomorphic and so p^,'p^ l i e i n the same type-cone, say C. then D <£ C . We have already proved that f ^ i s l i n e a r on a type-cone, e s t a b l i s h i n g the lemma. ' Now type-cones may be characterized by THEOREM 6 : A subset C CZ c l i r U i s a type-cone i f and only i f C i s a maximal r e l a t i v e l y open convex subset of c l i r U on which § ^ i s l i n e a r . Proof: I f C i s a type-cone, C i s r e a l t i v e l y open and convex since C i s an i n t e r s e c t i o n of a f i n i t e number of r e l a t i v e l y open convex sets. By lemma 1, S ^ i s l i n e a r on C , and by the remarks before lemma 1, C i s maximal. In the other d i r e c t i o n , a set C with the descirbed properties i s contained i n a type-cone, which must be C i t s e l f since C i s maximal, .concluding the proof. Lemma 2: Let C±>^2 ^ e tyV&~cones i n c l i r U , with C^ C\ C I C 2 4 <!> . Then Q C c l C 2 . Proof: Let p^ e C^, p^ e C^ be representatives of P^ >Y^ e T(U) . Then for X^,\^ > 0 , ^2^2 a r e a ^ °^ s a m e s t r o n g combinatorial type. I f p^ e C . n c l C 2 , t h i s combinatorial type i s seen to that of C^ • Thus e c l C ^ , f o r any p^ e C^, so *£ c l C ^ Using Lemma 2, we prove THEOREM 7: Let C be a type-cone i n c l i r U and l e t D be a face of clC . Then r e l i n t D i s a type-cone. Proof: Since C i s a type-cone , ? ^ i s l i n e a r on clC and therefore on D . By lemma 1, r e l i n t D C E for some type-cone E . By lemma 2, E C clC . Since D i s a face, r e l i n t D i s a maximal r e l a t i v e l y open set i n clC . Therefore E = r e l i n t D , a type-cone. For completeness, we'state without proof THEOREM 8: The closures of the type-cones i n c l i r U form, a complex. These ideas w i l l now be used to prove some r e s u l t s about sums of polytopes. Two polytopes P and Q are sa i d to be homothetic i f P = b +"• XQ , for some b e E d and X > 0 . In terms of t h e i r representatives i f p,q e c l i r U represent P and Q , t h i s i s equivalent to p = Xq . If P = P^ + P 2 where P^ and P^ are not homothetic to the polytope P , P i s decomposable; otherwise P i s indecomposable. Theorem 6 implies that i f P i s indecomposable, the corresponding •cone i s 1-dimensional, since i n t h i s case P = P + P^ , then P^ = X^? 3 P 2 = X 2P for X ,X2 >_ 0 , \ + X2 = 1. SM 9: Let P e T ( U ) be represented by the point p i n the type-cone i c l i r U . Then P i s a sum of at. most dim C indercomposable polytopes i P i s decomposable, the representative p of P l i e s i n a type-cone :-'f. dimension greater than 1 . The extreme rays of C are type-cones corresponding to indercomposable types, so since p can be wr i t t e n as a sum of at most dim C points each from an extreme ray, P can be - 99 -written as a sum of at most dim C indercomposable polytopes. Referring to theorem 3 , we see that a corollary i s that a polytope P i s simple i f and only i f every subset V C. U for which n-d y p e re l i n t pos V , spans E linearly. Thus simple polytopes correspond to (n-d)-dimensional type-cones; Corollary to Theorem 9: A d-polytope with ,n .facets . can .be expressed as a sum of at most ri-d indecomposable polytopes and n-d are required only i f the polytope i s simple. THEOREM 10: A l l simple d-polytopes but the simplex are decomposable. This result i s due to Shephard[1963, published i n Grunbaum] . For further results on the number of polytopes required i n the sum, see Meyer [1973, Indecomposable polytopes. (to appear)] . The polyhedral representation technique seems promising to investigate problems involving volume and other metric properties. See [6] for a proof of a theorem of ; Minkowski (quoted on p. 332 of Grunbaum) using these ideas. 1 -100 -Bibliography 1. C. Davis, Theory of positive linear dependence. Am. J. Math., 76 (1954), 733-746. 2. D. Gale, Neighbouring vertices on a convex polyhedron. (In Linear inequalities and related systems, edited by H.W. Kuhn and A.W. Tucker, Princeton 1956.) pp. 255-263. 3. B. GrUnbaum5 Convex polytopes. John Wiley and Sons, London-New York- • Sydney 1967. 4. E.K. Lloyd, The number of d-polytopes with d+3 vertices. Mathematika 17 (1970), 120-132.. 5 . P. McMullen, On zonotopes. Trans. Am. Math. Soc. 159 (1971), 91-109. 6 . • P. McMullen, Representations of polytopes and polyhedral sets. Unpublished notes, University of British Columbia, Vancouver, 1972. •7. P. McMullen and G.C. Shephard, Diagrams for centrally symmetric polytopes. Mathematika 15 (1968), 123-138. 8. P. McMullen and G.C. Shephard, Polytopes with an axis of symmetry. Canad. J. Math. 22 (1970), 265-287. 9.. P. McMullen and G.C. Shephard, Representations and diagrams. Unpublished notes,.Michigan State University, 1970. 10. P. McMullen and G.C. Shephard, Convex polytopes and the upper bound connective. Cambridge University Press, 1971. •11. T.S. Motzkin , Linear inequalities. Mimeographed lecture notes, University of California, Los Angeles, 1951. 12. G.C. Shephard, Diagrams for Positive Bases. J. London Math. Soc. (2), 4 (1971), 165-175. 13. G.C. Shephard, Polyhedral diagrams for sections of the non-negative •: orthant. Mathematika 18 (1971), 255-263. 14. H. Whitney, The abstract properties of linear dependence. Am. J. Math., 57 (1935), 509-533.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Diagrams and transforms applied to convex polytopes
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Diagrams and transforms applied to convex polytopes Lockeberg, Erik Ring 1973
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Diagrams and transforms applied to convex polytopes |
Creator |
Lockeberg, Erik Ring |
Publisher | University of British Columbia |
Date Issued | 1973 |
Description | The aim of this paper is to present a unified treatment of diagram techniques, particularly as applied to problems concerning convex polytopes. An attempt is made to summarize new results (listed below) of M. Perles, G.C. Shephard and P. McMullen. A diagram technique is one of several methods for associating to a finite subset of a finite-dimensional Euclidean space a finite subset of the same cardinality in another Euclidean space, in general of a different dimension. The second subset is a "diagram" or "transform" of the original set. The original set and its diagram are seen to be related in a symmetrical way to the kernel and image respectively of a certain linear map. A problem concerning a finite set corresponds to a problem concerning the diagram which may be easier to solve, particular if the diagram is of low dimension. Gale diagrams are used to enumerate d-polytopes with d+3 vertices, to construct an 8-polytope not rationally imbeddable, to investigate the symmetry group of polytopes and to obtain results concerning projectively unique polytopes. It is shown how positive diagrams may be used to investigate positive bases of Euclidean space. Zonal diagrams are used to investigate the neighbourliness of centrally symmetric polytopes. A diagram technique for dealing with polyhedral sets, including linear systems and metric properties of polyhedral sets. A geometric interpretation of the affine transform, central transform and zonal diagram in terms of regular polytope is given. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-28 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0079657 |
URI | http://hdl.handle.net/2429/19291 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1975_A6_7 L62_5.pdf [ 5.13MB ]
- Metadata
- JSON: 831-1.0079657.json
- JSON-LD: 831-1.0079657-ld.json
- RDF/XML (Pretty): 831-1.0079657-rdf.xml
- RDF/JSON: 831-1.0079657-rdf.json
- Turtle: 831-1.0079657-turtle.txt
- N-Triples: 831-1.0079657-rdf-ntriples.txt
- Original Record: 831-1.0079657-source.json
- Full Text
- 831-1.0079657-fulltext.txt
- Citation
- 831-1.0079657.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0079657/manifest