ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 13 (2017) 31-47 Lifting symmetric pictures to polyhedral scenes Viktoria E. Kaszanitzky * Department of Operations Research, Eotvos University, Pâzmâny Péter sétâny 1/C, 1117 Budapest, Hungary and Department of Mathematics and Statistics, Lancaster University, Lancaster LA1 4YF, United Kingdom Bernd Schulze f Department of Mathematics and Statistics, Lancaster University, Lancaster LA1 4YF, United Kingdom Received 23 June 2015, accepted 21 May 2016, published online 6 October 2016 Scene analysis is concerned with the reconstruction of d-dimensional objects, such as polyhedral surfaces, from (d - 1)-dimensional pictures (i.e., projections of the objects onto a hyperplane). In this paper we study the impact of symmetry on the lifting properties of pictures. We first use methods from group representation theory to show that the lifting matrix of a symmetric picture can be transformed into a block-diagonalized form. Using this result we then derive new symmetry-extended counting conditions for a picture with a non-trivial symmetry group in an arbitrary dimension to be minimally flat (i.e., 'non-liftable'). These conditions imply very simply stated restrictions on the number of those structural components of the picture that are fixed by the various symmetry operations of the picture. We then also transfer lifting results for symmetric pictures from Euclidean (d - 1)-space to Euclidean d-space via the technique of coning. Finally, we offer some conjectures regarding sufficient conditions for a picture realized generically for a symmetry group to be minimally flat. Keywords: Incidence structure, picture, polyhedral scene, lifting, symmetry, coning. Math. Subj. Class.: 68T45, 20C99, 52C25 * Research was supported by the EPSRC First Grant EP/M013642/1 and by the Hungarian Scientific Research Fund (OTKA, grant number K109240). tResearch was supported by the EPSRC First Grant EP/M013642/1. E-mail addresses: viktoria@cs.elte.hu (Viktoria E. Kaszanitzky), b.schulze@lancaster.ac.uk (Bernd Abstract Schulze) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 32 Ars Math. Contemp. 13 (2017) 125-136 1 Introduction An important and well studied problem in Artificial Intelligence, Computer Vision and Robotics is to find efficient methods for determining whether a straight line drawing in the Euclidean plane (also known as a '2-picture') corresponds to the projection of a 3-dimensional polyhedral surface (also known as a polyhedral '3-scene'). Applications of these results include image understanding, monocular vision and automatic reconstructions of 3-dimensional polyhedral objects or environments. In the Computer Vision community, this problem was first studied by Mackworth and Huffman [12, 7]. Using 'labeling schemes' and 'reciprocal diagrams', they obtained necessary conditions for the realizability of 2-pictures as polyhedral 3-scenes. However, the geometric method of the 'reciprocal diagram' has already been used by J. C. Maxwell and L. Cremona in the 19th century as a graphical tool to analyze the statics of trusses and mechanical structures [5, 13]. This work provides a beautiful connection between the field of polyhedral scene analysis and the field of static (or equivalently, infinitesimal) rigidity of frameworks [27, 29]. For further connections between these fields and other areas of discrete geometry, such as parallel redrawings of configurations (which is the dual interpretation of liftings of pictures), Minkowski decomposability of polytopes, and projective point-line configurations, see [21, 33, 34] for example. While reciprocal diagrams provide a powerful tool to check for inconsistencies in pictures, they do not provide sufficient conditions for the realizability of pictures as polyhedral scenes. In [22,23,24] Sugihara used linear programming methods to establish both a necessary and sufficient condition for a general picture to represent a polyhedron (see also [25]). Various other necessary and sufficient conditions were subsequently obtained by Crapo, Whiteley, et al. using a variety of different methods ranging from projective geometry and Grassmann-Cayley algebra to invariant theory (see e.g. [3, 4, 14, 26, 30, 31, 32]). A fundamental tool for analyzing a given picture is the lifting matrix, whose rank, row dependencies and column dependencies completely determine the liftability properties of the picture (see e.g. [3, 31, 33, 34]). In particular, this matrix yields some simple necessary counting conditions for a (d — 1)-dimensional picture to be 'flat' (i.e., non-liftable to a d-dimensional polyhedral scene) in terms of the number of vertices, faces and incidences of the underlying combinatorial incidence structure. Following a conjecture of Sugihara [23], Whiteley showed in [31] that these counts are also sufficient for 'generic' pictures (with the same underlying incidence structure) to be flat. In this paper, we study the impact of symmetry on the lifting properties of (d — 1)-dimensional pictures. This has important practical applications since symmetry is ubiquitous in both man-made and natural structures. Moreover, there has recently been a surge of interest in studying the impact of symmetry on the static or infinitesimal rigidity properties of structures (see e.g. [2, 6, 10, 15, 18, 19]), and hence it is natural to apply similar group-theoretic methods to the lifting analysis of symmetric pictures. In Section 4 we first show that the lifting matrix of a symmetric (d — 1)-picture can be transformed into a block-diagonalized form using methods from group representation theory. This is a fundamental result, since the block-decomposition of the lifting matrix can be used to break up the lifting analysis of a symmetric picture into a number of independent subproblems, one for each block of the lifting matrix. In fact, the analogous result for the rigidity matrix of a symmetric framework (see [10,15]) is basic to most of the recent results regarding the rigidity analysis of symmetric structures (see e.g. [2, 6, 18]). Similarly to [15], the block-decomposition of the lifting matrix is obtained by showing that V E. Kaszanitzky and B. Schulze: Lifting symmetric pictures to polyhedral scenes 33 (a) (b) (c) Figure 1: A (minimally) flat 2-picture (where all four interior regions are faces) (a) which becomes sharp if realized with reflectional symmetry (b). A non-trivial (and sharp) lifting of the picture in (b) is shown in (c). it intertwines two particular matrix representations of the given symmetry group. For the lifting matrix, one of these representations is associated with the incidences of the picture and the other one is associated with the vertices and faces of the picture (see Theorem 4.1). In Section 5 we then use these results, together with some methods from character theory, to derive new necessary counting conditions for a symmetric picture to be 'minimally flat' (i.e., flat with the property that the removal of any incidence leads to a picture which does have a non-trivial lifting). Such pictures may be thought of as the basic building blocks for symmetric flat pictures, as we may (symmetrically) add further incidence constraints to a minimally flat picture to obtain classes of (over-constrained) flat pictures. We then follow the approach in [2] to derive a complete list of the necessary conditions for 2-dimensional pictures to be minimally flat, as these are the most important structures for practical applications. Similar counts for higher-dimensional pictures can easily be obtained for any symmetry group using Corollary 5.5. A well established tool in rigidity theory for transferring results from an Euclidean space to the next higher dimension (as well as to other types of metrics) is the technique of 'coning' (see e.g. [20, 28]). In the end of Section 5 we show that coning can also be used to transfer lifting results for pictures from (d — 1)-space to d-space. Finally, in Section 6 we offer some conjectures regarding combinatorial characterizations of minimally flat pictures which are as generic as possible subject to the given symmetry constraints. Moreover, we briefly discuss the question of whether a picture which is generic modulo symmetry has a 'sharp' lifting, i.e. a lifting where any two faces sharing a vertex lie in different hyperplanes. 2 Pictures, liftings, and scenes A (polyhedral) incidence structure S is an abstract set of vertices V, an abstract set of faces F, and a set of incidences I C V x F. A (d — 1)-picture is an incidence structure S together with a corresponding location map r : V ^ Rd-1, ri = (xj, yi, ■ ■ ■ , wi)T, and is denoted by S(r). A d-scene S(p, P) is an incidence structure S = (V, F; I) together with a pair of location maps, p : V ^ Rd, pi = (xi, ...,wi, zi)T, and P : F ^ Rd, Pj = (Aj,..., Cj, Dj )T, such that for each (i, j) e I we have Ajxi +... + Cj wi + zi + Dj = 0. (We assume 34 Ars Math. Contemp. 13 (2017) 125-136 that no hyperplane is vertical, i.e., is parallel to the vector (0,..., 0,1)T.) A lifting of a (d - 1)-picture S(r) is a d-scene S(p, P), with the vertical projection n(p) = r. That is, if p = (xj,..., Wj,Zj)T, then r = (xj,... ,Wj)T = n(p4). A lifting S(p, P) is trivial if all the faces lie in the same plane. Further, S(p, P) is folded (or non-trivial) if some pair of faces have different planes, and is sharp if each pair of faces sharing a vertex have distinct planes. A picture is called sharp if it has a sharp lifting. Moreover, a picture which has no non-trivial lifting is called flat (or trivial). A picture with a non-trivial lifting is called foldable. The lifting matrix forapicture S (r) is the |I1 x (|V | + d|F |) coefficient matrix M (S,r) of the system of equations for liftings of a picture S(r): For each (i, j) G I, we have the equation Aj xj + Bj yj + ... + Cj wj + zj + Dj = 0, where the variables are ordered as [..., zj,...;..., Aj, Bj,..., Dj,...]. That is the row corresponding to (i, j) G I is: (i,j) 0... 0 1 0... 0 0... 0 rj 1 0... 0 |V | d|F | Theorem 2.1 (Picture Theorem). [31, 33] A generic picture of an incidence structure S = (V, F; I) with at least two faces has a sharp lifting, unique up to lifting equivalence, if and only if |I1 = |V| + d|F| - (d + 1) and |I '| < |V'| + d|F'| - (d + 1) for all subsets I' of incidences with at least two faces. A generic picture of S has independent rows in the lifting matrix if and only if for all non-empty subsets I' of incidences, we have |I '| < |V '| + d|F '| — d. Note that it follows from the Picture Theorem that a generic picture of an incidence structure S = (V, F; I) is minimally flat, i.e. flat with independent rows in the lifting matrix, if and only if |I| = |V| + d|F| - d and |I'| < | V'| + d|F'| - d for all non-empty subsets I' of incidences. 3 Symmetric incidence structures and pictures An automorphism of an incidence structure S = (V, F; I) is a pair a = (n,a), where n is a permutation of V and a is a permutation of F such that (v, f) G I if and only if (n(v), a(f)) G I for all v G V and f G F. For simplicity, we will write a(v) for n(v) and a(f) for a(f). The automorphisms of S form a group under composition, denoted Aut(S). An action of a group r on S is a group homomorphism 0 : r ^ Aut(S). The incidence structure S is called r-symmetric (with respect to 0) if there is such an action. For simplicity, if 0 is clear from the context, we will sometimes denote the automorphism 0(y) simply by 7. Let r be an abstract group, and let S be a r-symmetric incidence structure (with respect to 0). Further, suppose there exists a group representation t : r ^ O(Rd-1). Then we say that a picture S(r) is r-symmetric (with respect to 0 and t) if t(Y)(rj) = re(7)(j) for all i G V and all 7 G r. (3.1) In this case we also say that t(r) = {t(7) 17 g r} is a symmetry group of S(r), and each element of t(r) is called a symmetry operation of S(r). Throughout this paper, we will use the Schoenflies notation for symmetry operations and symmetry groups, as this is one of the standard notations in the literature on symmetric structures [2, 6, 10, 15]. V E. Kaszanitzky and B. Schulze: Lifting symmetric pictures to polyhedral scenes 35 4 Block-decomposing the lifting matrix of a symmetric picture In this section we will show that by changing the canonical bases for R|f| and R|V|+d|F 1 to appropriate symmetry-adapted bases, the lifting matrix of a symmetric picture can be transformed into a block-decomposed form. Let r be an abstract group, and let S = (V, F; I) be a r-symmetric incidence structure (with respect to 0 : r ^ Aut(S)). Further, let S(r) be a r-symmetric (d - 1)-picture with respect to the action 0 and the homomorphism t : r ^ O(Rd-1). We fix an ordering of the vertices in V, the faces in F and the incidences in I. We let Pv : r ^ GL(R|V|) be the linear representation of r defined by Py (y) = [5e(Y)(j)]i,j, where S denotes the Kronecker delta symbol. That is, PV (7) is the permutation matrix of the permutation of V induced by 0(7). Similarly, we let PF : r ^ GL(R|F|) be the linear representation of r defined by PF(7) = [Se(Y)(j)]i,j. That is, PF(7) is the permutation matrix of the permutation of F induced by 0(7). Moreover, note that for each Y € r, the automorphism 0(7) of S clearly also induces a permutation of the incidences I of S. So, analogously to PV and PF, we let Pf : r ^ GL(Ri11) be the linear representation of r which consists of the permutation matrices of the permutations of I induced by 0. We call P/ the internal representation of r (with respect to 0 and t). The external representation of r (with respect to 0 and t) is the linear representation Py 0 (f < PF) :r ^ GL(R|V 1 0 Rd|F|), /t (y) 0 where f : r ^ O(Rd) is the augmented representation of t, definedby f(Y) = ( 0 1 Recall that given two linear representations, p1 : r ^ GL(X) and p2 : r ^ GL(Y) with representation spaces X and Y, a linear map T : X ^ Y is said to be a r-linear map of p1 and p2 if T o p1 (y) = p2 (y) 0 T for all y € r. The vector space of all r-linear maps of p1 and p2 is denoted by Homr(p1, p2). Theorem 4.1. Let S = (V, F; I) be a r-symmetric incidence structure (with respect to 0), let t : r ^ O(Rd-1) be a homomorphism, and let S(r) be a r-symmetric (d — 1)-picture (with respect to 0 and t). Then M(S, r) € Homr(PV 0 (f < PF), P/). Proof: Suppose we have M(S, r)c = b. Then we need to show that for all y € r, we have M(S, r)(Py 0 (f < Pf))(y)c = P/(y)b. Fix y € r, and let 0(y) = (n, a). The automorphism of I induced by 0(y) we denote by a. Let (i, j) € I. Further, let n(i) = k and a(j) = l. Thus, a((i, j)) = (k, l). Note that Pf (y)& is an |1 |x 1 column vector which is indexed by the incidences in I. By the definition of Pf (y), for the (k, l)-th component, (Pf (Y)b)(k,j), of Pf (Y)b we have (Pf (Y)b)(k,;) = (b)(i,j). So we need to show that (M(S,r)(Py 0 (f < Pf))(Y)c)(fc,i) = (b)(i,j). Note that (M(S, r)c)(M) = (b)(M) = zfc + A1 xfc + + ... + + D1. By the definition of Py 0 (f < Pf)(y), (M(s, r)(Py 0 (f < Pf))(y)c)(/m) is equal to zi + (xfc,yfc,...,wfc, 1) ( T0Y) 1 ( Aj \ V D j ) 36 Ars Math. Contemp. 13 (2017) 107-123 By symmetry (recall that n(i) = k, and hence t(7)(r) = rk), this is equal to zi + (*,*,...,«*, 1)( TMT( TJ í Aj \ Bj \D y Since t(7) (and hence also t(y)) is an orthogonal matrix, this is equal to zi + XiAj + ... + WiCj + Dj = (b)(i,j). This completes the proof. □ Since M(S, r) G Homr(PV © (f ( PF),P/), there are non-singular matrices A and B such that BTM(S, r)A is block-diagonalized, by Schur's lemma (see [8] e.g.). If p0,..., pn are the irreducible representations of r, then for an appropriate choice of symmetry-adapted coordinate systems, the lifting matrix takes on the following block form BtM(S, r)A := M(S,r) ( Mo(S,r) 0 (4.1) V 0 Mn(S,r) where the submatrix block Mj(5, r) corresponds to the irreducible representation pi of r. More precisely, the symmetry-adapted coordinate systems can be obtained as follows. Recall that every linear representation of r can be written uniquely, up to equivalency of the direct summands, as a direct sum of the irreducible linear representations of r. So we have Pv © (f PF) = Aopo © ... © A„p„, where Ao,..., A„ G N U {0}. (4.2) For each t = 0,..., n, there exist At subspaces (V(pt))p..., (V(pt))A of the R-vector space R|V|+d|F 1 which correspond to the At direct summands in (4.2), so that r|v |+d|F 1 = v (po) © ... © V (4.3) where V(pt) = (V(pt))1 © ... © (V(pt))At. (4.4) Similarly, for the internal representation PI of r, we have the direct sum decomposition Pi = MoPo © ... © MnPn, where Mo,..., Mn G N U {0}. (4.5) For each t = 0,..., n, there exist Mt subspaces (W(pt)) 1,..., (W(pt)) of the R-vector space R111 which correspond to the Mt direct summands in (4.5), so that R111 = W(po) © ... © W(4.6) where ( ) ( ) W(pt) = (W(It))1 © ... © (W(pt))Mt. (4.7) If we choose bases (A(pt)) 1,..., (A(pt)) for the subspaces in (4.4) and we also choose bases (B(pt))1,..., (B(pt))^ for the subspaces in (4.7), then IJIU J^I 1 (A(pt))i and IXoll1 (B(pt))i are symmetry-adapted bases with respect to which the lifting matrix is block-decomposed as shown in (4.1). V. E. Kaszanitzky and B. Schulze: Lifting symmetric pictures to polyhedral scenes 37 Definition 4.2. A vector c G R|vl+dlF 1 is symmetric with respect to the irreducible linear representation pt of r if c G V(pt). Similarly, we say that a vector b G R11 is symmetric with respect to pt if b G W(pt). Note that the kernel of the block matrix Mt(S,r) is isomorphic to the space of all liftings of the r-symmetric picture S(r) which are symmetric with respect to pt. 5 Symmetry-extended counting rules for the foldability of pictures Recall from the Picture Theorem (Theorem 2.1) that if S(r) is minimally flat, then it satisfies |11 = |V| + d|F| - d. Clearly, if |11 < |V| + d|F| - d, then S(r) has a non-trivial lifting, and if |11 > |V| + d|F| — d, then the lifting matrix M(S,r) has a non-trivial row dependence. In Section 5.1, we will use the results of the previous section to derive a symmetry-extended version of this formula, which will provide further necessary counting conditions for a symmetric picture in an arbitrary dimension to be minimally flat. As we will see, these conditions can be stated in a very simple way in terms of the numbers of structural components of the picture that are fixed by the various symmetry operations. In Section 5.2 we will then derive a complete list of the necessary counting conditions for symmetric pictures in the plane to be minimally flat. Finally, in Section 5.3 we consider the transfer of lifting results for pictures from (d — 1)-space to d-space via coning. 5.1 Symmetry-extended counting rules Recall that if p : r ^ GL(X) is a linear representation of a group r with representation space X then a subspace U of X is said to be p-invariant if p(j)(U) C U for all y G r. Proposition 5.1. Let S(r) be a picture which is r-symmetric with respect to 9 : r ^ Aut(S) and t : r ^ Rd-1. Then the space T (S, r) of trivial liftings of S(r) is a Pv © (T < PF)-invariant subspace of R|v 1 © Rd|F|. Proof: Let t be any element of T(S,r). Then t is an element of the kernel of the lifting matrix M (S, r) of the form (..., zi,...,..., Aj ,Bj ,...,Dj,.. .)T, where Aj = Ak, Bj = Bk, ..., Dj = Dk for all 1 < j,k < |F|. It follows from Theorem 4.1 that (Pv © (t < PF))(t) is also an element of the kernel of M(S,r), and it follows immediately from the definition of Pv © (T < PF) that (Pv © (t < PF))(t) is of the form (...,zi,...,..., Aj, Bj,..., Dj,.. .)T, where Aj = A'k, Bj = B'k, ..., Dj = D'k for all 1 < j,k < |F |. This gives the result. □ We denote by (Pv © (T < PF))(T) the subrepresentation of Pv © (T < PF) with representation space T(S,r). Recall that the character of a representation p : r ^ GL(X) is the row vector x(p) whose i-th component is the trace of p(^i), for some fixed ordering Y1,..., 7|r| of the elements of r. Theorem 5.2 (Symmetry-extended counting rule). Let S(r) be a (d — 1)-picture which is r-symmetric with respect to 9 and t. If S(r) is minimally flat, then we have x(Pi) = x(Pv © (T < Pf)) — x((Pv © (T < Pf))(T)). (5.1) Proof: By Maschke's Theorem (see [8] e.g.), T(S, r) has a (Pv © (t < PF))-invariant complement Q in R|v\+d\F|. We may therefore form the subrepresentation (Pv © (T < 38 Ars Math. Contemp. 13 (2017) 107-123 PF))(Q) of PV © (f < PF) with representation space Q. Since (S, r) is minimally flat, the restriction of the linear map represented by the lifting matrix M (S, r) to Q is an isomorphism onto R11|. Moreover, since M(S, r) is T-linear with respect to the representations PV ©(f ^t, then, by (4.1), there exists a non-trivial lifting of S(r) (i.e., a non-trivial element in the kernel of M(S, r)) which is symmetric with respect to pt, and if Kt < then there exists a nontrivial row dependence of M(S, r) (i.e., a non-zero element in the co-kernel of M(S, r)) which is symmetric with respect to pt. Before we illustrate this symmetry-adapted counting rule by means of an example, we show how the characters in (5.1) can be computed in a very simple way. We need the following definitions. Let S be an incidence structure and let 0 : r ^ Aut(S) be a group action on S. A vertex v of S is said to be fixed by 7 e r (with respect to 0) if 7« = v. Similarly, a face f = {vi,..., vm} of S is said to be fixed by 7 e r (with respect to 0) if 7/ = f, i.e., if 7 ({v1,..., vm}) = {v1,..., vm}. Finally, an incidence (i, j) of S is said to be fixed by 7 e r (with respect to 0) if Y((i, j)) = (i, j) The sets of vertices, faces, and incidences of a r-symmetric incidence structure S which are fixed by 7 e r are denoted by VY, FY, and IY, respectively. Remark 5.3. Note that if a (d - 1)-picture S(r) is r-symmetric (with respect to 0 and t) and a vertex i is fixed by some 7 e r, then r4 must occupy a special geometric position in Rd-i. For example, if t (7) is a reflection in the plane, then r must lie in the corresponding mirror line. Similarly, if t(7) is a rotation in the plane, then r must lie at the center of rotation (i.e., the origin). Similar geometric restrictions are imposed on any faces (or incidences) of S(r) that are fixed by an element 7 e r. V. E. Kaszanitzky and B. Schulze: Lifting symmetric pictures to polyhedral scenes 39 Proposition 5.4. Let r = {71,..., Y|r|} be an abstract group and let S(r) be a (d — 1)-picture which is T-symmetric with respect to 9 and t. Then we have (i) x(Pi) = (|/711,...,|i7|r|I); (ii) x(Pv 0 (r << Pf )) = (|V7i | + tr(f(7i)) |F7i |,..., |V7 | r 11 + tr(r(7|r|)) |F7| r 11); (iii) x((Pv 0 (r << Pf))(t)) = x(r). Proof: (i) Note that tr(Pi(7)) = |/71 for each 7 G r. (ii) Similarly, we have tr(PV(y)) = V1, tr(PF(7)) = |F71, and tr((r ® Pf)(y)) = tr(r(7))tr(PF(7)) for each 7 G r. (iii) A basis for the space T(S, r) of trivial liftings of S(r) is given by the d vectors Ti = (xi, ... ,X|V|, —ei, .. ., —ei)T, T2 = (yi, ... ,y|y|, — e2,. .., —e2)T, .. ., Td_i = (wi,...,w|v |, —ed-i,..., — ed-i)T and Td = (1,..., 1, — ed,..., —ed)T, where e4 denotes the ¿-th canonical basis vector of Rd. An elementary calculation shows that for every 7 G r, we have (Pv 0 (r Pf))(T)(7)Tj = (r(7))ijTi + • • • + (r(7))djTd. This gives the result. □ By Proposition 5.4, the symmetry-extended counting rule in (5.1) can be simplified to x(pi)= x(Pv 0 (r < pf)) — x(r), (5.2) and each of these characters can be computed very easily. (The calculations of the characters x(PI), x(PV 0 (r < PF)), and x(r) for pictures in dimension 2 are shown in Table 2.) Moreover, note that this vector equation gives one equation for each element of the group r. This leads to the following very useful corollary of Theorem 5.2, which allows us to detect non-trivial liftings in symmetric pictures by simply counting the number of structural components of the picture that are 'fixed' by a given symmetry operation of the picture. Corollary 5.5. Let (S, r) be a (d — 1)-picture which is T-symmetric with respect to 9 and t . If (S, r) is minimally flat, then for each 7 G r, |Iy | = |V71 + ir(r(7))(|F71 — 1). (5.3) Proof: This follows immediately from Theorem 5.2 and Proposition 5.4. □ The following example illustrates how to apply the symmetry-extended counting rule to a picture in dimension 2. Example 5.6. Consider the 2-picture with the reflectional symmetry group Cs = {¿d, s} in Figure 2. For this picture, we have |V| = 6, |F| = 4, |I| = 15, and hence |I| = |V| + 3|F| — 3 = 15. So, for generic positions of the vertices, we obtain flat pictures. However, using our symmetry-extended counting rule we can easily show that the mirror symmetry shown in Figure 2 induces a non-trivial lifting. The group Cs has two non-equivalent irreducible representations po and pi, each of which is of dimension 1 (see Table 1). Since tr(r(id)) = 3, tr(r(s)) = 1, |V | +3|F | = 18, and |VS| + |FS| = 2 + 2 = 4, we have x(Pv 0 (r < Pf)) — X((PV 0 (r < PF))(T)) = (18, 4) — (3,1) = (15, 3) = 9po + 6pi. 40 Ars Math. Contemp. 13 (2017) 107-123 Cs id s po 1 1 pi 1 -1 Table 1: The characters of the irreducible representations of the group Cs. Further, since |11 = 15 and |/s | = 1, we have x(Pi) = (15,1) = 8po + 7pi. Thus, we may conclude that the picture in Figure 2 has a non-trivial lifting which is symmetric with respect to p0 (i.e., the lifting preserves the mirror symmetry) and a row dependence which is symmetric with respect to p1. Note that for this particular example, we could also have used the results in [2] to see that the corresponding bar-joint framework has a self-stress, and then deduce the existence of a (sharp) lifting via the technique of the reciprocal diagram [13, 12]. Figure 2: A 2-picture with mirror symmetry which has a symmetry-induced non-trivial lifting (see also Figure 1(c)). 5.2 When is a symmetric 2-picture minimally flat? The possible non-trivial symmetry operations of a picture in dimension 2 are reflections in lines through the origin (denoted by s), and rotations about the origin by an angle of , where n > 2 (denoted by Cn). Therefore, the possible symmetry groups in the plane are the identity group C1, the rotational groups Cn, n > 2 (generated by a single rotation Cn), the reflection group Cs (generated by a single reflection s), and the dihedral groups Cnv, n > 2. In Table 2, we show the calculations of characters for the counting condition in (5.1) (or equivalently, (5.2)) for 2-pictures. In this table, |Vn|, |Fn|, and |/n| denote the numbers of vertices, faces, and incidences that are fixed by an n-fold rotation Cn, n > 2, respectively. Similarly, | Vs |, |Fs |, and |/s | denote the numbers of vertices, faces, and incidences that are fixed by a reflection s, respectively (recall also the notation introduced in Subsection 5.1). From equation (5.3) and Table 2, we obtain the following necessary conditions for a r-symmetric 2-picture (with respect to 0 and t) to be minimally flat. If x(PI) = x(Pv ® (f PF)) - x(f),then V. E. Kaszanitzky and B. Schulze: Lifting symmetric pictures to polyhedral scenes 41 id Cn>2 C2 s x(Pi ) |11 |1n| |12| |1s| x(Pv ® (T ® Pf)) |V | +3|F | |V„| + (1 + 2 COS 2f )|F„| |V2| — |F2| |Vs| + |Fs| X(r) 3 1 + 2 cos ^^ n —1 1 Table 2: Calculations of characters for the symmetry-extended counting rule for minimally flat pictures in dimension 2. id: |11 = |V| + 3|F|- 3 (5.4) C2: |121 = |V2|-|F2| + 1 (5.5) s: |1s| = |VS| + |FS| — 1 (5.6) 2n C„>2: |/„| = |Vn| + (|Fn| — 1)(1 + 2cos — ) (5.7) n where a given equation applies when the corresponding symmetry operation is present in t(r). Some observations on minimally flat 2-pictures, arising from this set of equations are: 1. Every symmetry group contains the identity id, and hence we must always have the standard count |11 = | V| + 3|F| — 3. 2. It follows from (5.5) that the presence of a half-turn C2 imposes limitations on the placements of vertices and faces. Note that if |V2| =0 or |F2| = 0, then |/2| = 0. Thus, we must have |F21 > 0. Also, if |V2| = 0, then we must have |F2| = 1. If |V2| = 1 then by |121 < |F21 either |121 = |F2| = 1 or |121 = 0, |F2| = 2 holds. 3. Similarly, by (5.6), presence of a mirror line implies that if | Vs | = 0, then |Fs | = 1, and if |FS| =0, then |VS| = 1. 4. By (5.7), presence of a rotation of higher order Cn>2 gives rise to the following conditions. If n = 3, then the equation in (5.7) becomes |131 = |V3|. If n = 4, then the equation in (5.7) becomes |/4| = |V4| + |F4| — 1. Therefore, if |V4| = 0, then |F4| = 1 and, if |V4| = 1 then |/4| = |F4| < 1 by |/4| < |/2|. If n = 6, then the equation in (5.7) becomes 11 = |V6| + 2|F6| — 2. Therefore, | F61 > 0 (for otherwise, | V61 = 2 and the location map of the picture would be non-injective). Further, if |V6| = 0, then |Fe| = 1 and, if |V6| = 1 then = F| = 1 holds by |/6| < |121. Finally, if Cn is present, where n ^ {2, 3,4,6}, we must have |Fn| = 1 and |/„| = |Vn|. Similarly, we may obtain lists of necessary conditions for symmetric pictures in 3- or higher-dimensional space to be minimally flat (using Corollary 5.5). 42 Ars Math. Contemp. 13 (2017) 107-123 C2 C3 C4 Cs Figure 3: Some symmetric minimally flat 2-pictures (where all interior regions are faces). C2 Cs C 3v Figure 4: Some symmetric 2-pictures with a (sharp) symmetry-induced lifting (where all interior regions are faces). 5.3 Coning (d — 1)-pictures In the following we show that the technique of 'coning' can be used to construct (minimally) flat r-symmetric d-pictures from (minimally) flat r-symmetric (d — 1)-pictures. Let S = (V, F; I) be an incidence structure and let S(r) be a (d — 1)-picture for d > 2. The coned incidence structure S = (V, F; I) is obtained by adding a new vertex v to V, replacing each face f e F by f U {v}, and adding the incidences (v, f), f e F. A realization of S as a d-picture S(r ) is called a coned picture of S(r). An example of a coned 2-picture is shown in Figure 5. Let r be a group, and let S(r) be a r-symmetric (d—1)-picture (with respect to 0 and t) with n vertices. Then S(r) is said to be r-generic if the set of coordinates of the image of r are algebraically independent over Qr, where Qr denotes the field generated by Q and the entries of the matrices in t(r). In other words, S(r) is r-generic if there does not exist a polynomial h(xi,..., x(d-1)n) with coefficients in Qr such that h((ri)i,..., (rn)d_i) = 0. (Note that if r is the trivial group, then Qr = Q. In this case, a r-generic picture is simply called generic.) Clearly, the set of all r-generic realizations of S is a dense (but not open) subset of all r-symmetric realizations of S. Moreover, all r-generic realizations of S share the same lifting properties. We say that S is r-generically (minimally) flat in Rd-1 if all r-generic realizations of S in Rd-1 are (minimally) flat. For a r-symmetric (d — 1)-picture S(r) (with respect to 0 : r ^ Aut(S) and t : r ^ O(Rd-1)), we let I : r ^ O(Rd) be the augmented representation, i.e., I(7) = V E. Kaszanitzky and B. Schulze: Lifting symmetric pictures to polyhedral scenes 43 "(7) . Moreover, for the coned incidence structure S = (V, F; /) (with cone vertex V 0 1, v), we define 0 : r ^ Aut(S) as follows: 0(7) |v = 0(7), 0(y)(v) = v, and 0(7)(/ U {v}) = (0(y)(/)) U {v} for all f e F and 7 G r. Theorem 5.7. Lei S = (V, F; I) be a r-symmetric incidence structure (with respect to 9), and let S(r) be a (d — l)-picture which is T-symmetric with respect to 9 and t. Then the following hold: (i) S(r) has a non-trivial lifting if and only if the coned d-picture S(f), with the cone vertex at the point (0,..., 0, a) G Rd, for some non-zero a G R, has a non-trivial lifting. (ii) S is T-generically (minimally) flat (with respect to 9 and t ) in Rd-1 if and only if S is T-generically (minimally) flat (with respect to 9 and t) in Rd. Proof: (i) Let r1,..., r|V| be the vertices of the picture S(r). Embed S(r) into the space Rd via r = (r4,0) for i = 1,..., |V|. Then form the coned picture S(t), with the cone vertex r0 = (0,..., 0, a) G Rd, a = 0. The lifting matrix of S( r) is of the form M (S, r) (f ) The lifting matrix of the coned picture S(t) (with the cone vertex fixed) is of the form i fj m '(S,r) = (i,fj ) (0,/j ) 0 ... 0 1 0 ... 0 0 ... 0 [xi,yi,... ,Wi, 0,1] 0 ... 0 0 ... 0 0 0 ... 0 0 ... 0 [0, 0,..., 0, a, 1] 0 ... 0 Note that we added |F| rows (one for each incidence of the form (0, fj), j = 1,..., |F|, where 0 is the cone vertex) and |F| columns. Furthermore, for each added column (under face j) we have a 0 in each row, except in the one added row corresponding to the incidence (0, fj), where the entry is equal to a. Thus we have increased the rank by |F|, and preserved the dimension of the kernel. Now, if we add the missing column for the cone 44 Ars Math. Contemp. 13 (2017) 107-123 vertex, then we obtain the lifting matrix of the coned picture S(r ): 0 i _fj m (S ,r ) = (i,f) (0,fj) 0 1 0 ... 0 1 0 ... 0 0. . . 0 0 0. . . 0 0 ... 0 [xi,Vi,...,Wi, 0,1] 0 ... 0 0 ... 0 [0, 0,..., 0, a, 1] 0 ... 0 This added a 1-dimensional space of liftings (namely the space |Ard| A g R} of all 'vertical' translations of the picture (recall the proof of Prop. 5.4)), but did not add any non-trivial liftings. The rank of the matrix has not changed, nor has the space of row-dependencies. This proves (i). (ii) Note that if there exists some (minimally) flat r-symmetric realization of an incidence structure S, then clearly all T-generic realizations of S are also (minimally) flat. Therefore, by (i), it suffices to show that S(r) is r-symmetric with respect to 0 and t if and only if the coned picture S(r ) (with the cone vertex at the point (0,..., 0, a) g Rd, a = 0) is r-symmetric with respect to 0 and f. Let ri,..., r|V| be the vertices of the picture S(r), and let f0, fi,..., fV| be the vertices of the picture S(f ), i.e., f0 = (0,0,..., 0, a), and f = (rj, 0) for i = 1,..., | V|. For all y g r, we clearly have f (7)f0 = f0 = f<9(7)(o). Furthermore, for i = 0, S(r) is r-symmetric with respect to 0 and t if and only if f (Y)fi = (t 0) = (r0(Y)(i), 0) = (re(7)(i), 0) = r0(7)(i). This gives the result. □ (a) (b) (c) Figure 5: A C4-symmetric 2-picture S(r) (where all five interior regions are faces) (a) and a C4-symmetric coned picture S(f) in 3-space with cone vertex f0 = (0,..., 0, a) and rf = (r, 0) for i = 1,..., 8 (b). A C4-generic realization of S is shown in (c). Note that S also has five faces, namely the ones corresponding to the 'interior cells' of the cube in (c) except for the 'top cell' {f0, f 1, f2, f3, f4}. 0 1 V. E. Kaszanitzky and B. Schulze: Lifting symmetric pictures to polyhedral scenes 45 6 Further work In the previous sections we have derived new necessary conditions for a symmetric picture to be minimally flat. It is now natural to ask whether these conditions, together with the standard non-symmetric counts, are also sufficient for a picture which is realized generi-cally for the given symmetry group to be minimally flat. We conjecture that this is in fact the case, for all symmetry groups in all dimensions. Conjecture 6.1. A F-generic (d — l)-picture S(r) is minimally flat if and only if (i) 1I1 = |V| + d|F| — d and \I'\ < |V'| + d|F'| — d for all nonempty subsets I' of incidences; (ii) S satisfies the conditions for F in the symmetry extended counting rule (Corollary 5.5); (iii) For every subset I' of I which induces a r'-symmetric incidence structure S' with |I'| = |V '| + d|F ' | — d (where V Ç T), S' satisfies the conditions for r' in the symmetry extended counting rule. Note that if every face of the incidence structure S is incident to exactly four vertices (i.e., if S induces a 4-uniform hypergraph), then the count |I| = |V| +3|F| — 3 in condition (i) for d =3 simplifies to |F| = | V| — 3. Thus, a natural approach to prove this conjecture for d = 3 is to first focus on incidence structures which induce 4-uniform hypergraphs and to develop a symmetry-adapted version of the recently established recursive construction of 4-uniform (1,3)-tight hypergraphs [9]. For each of the symmetric hypergraph operations in this construction scheme, we then need to check that it preserves the full rank of the lifting matrix. Finally, one could then try to extend the result to general incidence structures with the same symmetry. Using this approach, Conjecture 6.1 has recently been verified for 2-pictures with three-fold rotational symmetry [11]. All the other cases, however, remain open, and we invite the reader to join in these explorations. Note that a similar approach based on symmetry-adapted recursive Henneberg-type graph constructions was successfully used in [16, 17] to establish symmetry-adapted versions of Laman's theorem for various groups. These results provide combinatorial characterizations of symmetry-generic isostatic (i.e. minimally infinitesimally rigid) graphs in the plane. However, the recursive construction of (non-symmetric) (1, 3)-tight hyper-graphs developed in [9] is more complex than the recursive Henneberg construction of (non-symmetric) Laman graphs, and hence Conjecture 6.1 presents us with new challenges of both combinatorial and geometric nature. For practical applications of scene analysis, it is of particular interest to develop methods which allow us to determine whether there exist a (unique) sharp lifting for a given picture, rather than just a non-trivial lifting. It is therefore natural to ask whether our results can be extended to provide necessary and/or sufficient conditions for a symmetric picture to be sharp, rather than just foldable. A combinatorial characterization of those pictures which have a unique sharp lifting if realized generically in (d — 1)-space (without symmetry) is given by the Picture Theorem (recall Theorem 2.1). This result is essentially a corollary of the combinatorial characterization of generic independent pictures (i.e., pictures whose lifting matrices have independent rows) given in [31]. Therefore, in order to obtain a complete symmetry-adpated version of the Picture Theorem we need to first obtain a combinatorial characterization of those 46 Ars Math. Contemp. 13 (2017) 107-123 pictures which are independent if realized generically with respect to the given symmetry group. Note that in the non-symmetric situation, any generic independent picture is a substructure of a minimally flat picture. In general, however, this is no longer the case for symmetric pictures. For example, it is easy to construct a C3-generic picture in the plane which satisfies |V3| = 1 and |131 = |F3| > 1, so that it is not contained in a minimally flat C3-generic picture (by Corollary 5.5), but whose lifting matrix has independent rows. It follows that a combinatorial characterization of T-generic minimally flat pictures would in general not provide us with a combinatorial characterization of T-generic independent pictures. However, once a characterization of T-generic independent pictures has been established for a group r (again using a symmetric recursive construction scheme, e.g.), then we expect that the proof idea in [31] can be extended to obtain a characterization of those pictures which have a unique sharp lifting if realized generically with respect to r. For some initial results for C3-generic pictures in the plane, we refer the reader to [11]. Acknowledgements We would like to thank Walter Whiteley for useful discussions. References [1] P. W. Atkins, M. S. Child and C. S. G. Phillips, Tables for Group Theory, OUP, Oxford, 1970. [2] R. Connelly, P. W. Fowler, S. D. Guest, B. Schulze and W. Whiteley, When is a symmetric pin-jointed framework isostatic?, International Journal of Solids and Structures 46 (2009), 762-773. [3] H. Crapo, Invariant-Theoretic Methods in Scene Analysis and Structural Mechanics, J. of Symbolic Computation 11 (1991), 523-548. [4] H. Crapo and W. Whiteley, Plane Self Stresses and Projected Polyhedra I: The Basic Pattern, Structural Topology 20 (1993), 55-78. [5] L. Cremona, (T. H. Beare, trans.), Graphical Statics, Clarendon Press, London, 1890. [6] P. W. Fowler and S. D. Guest, A symmetry extension of Maxwell's rule for rigidity of frames, International Journal of Solids and Structures 37 (2000), 1793-1804. [7] D. Huffman, Realizable Configurations of Lines in Pictures of Polyhedra, Machine Intelligence 8 (1977) 493-509. [8] G. James and M. Liebeck, Representations and Characters of Groups, Cambridge University Press, 1993. [9] T. Jordan and V.E. Kaszanitzky, Sparse hypergraphs with applications in combinatorial rigidity, Discrete Applied Math. 185 (2015), 93-101. [10] R. D. Kangwai and S. D. Guest, Symmetry-adapted equilibrium matrices, International Journal ofSolids and Structures 37 (2000), 1525-1548. [11] V. E. Kaszanitzky and B. Schulze, Characterizing minimally flat symmetric hypergraphs, EGRES Tech. Report TR-2015-17 (2015). [12] A. Mackworth, Interpreting Pictures of Polyhedral Scenes, Artificial Intelligence 4 (1973), 121-137. [13] J. C. Maxwell, On reciprocal figures and diagrams of forces, Phil. Mag. 27 (1864), Ser. 4, 250-261. V. E. Kaszanitzky and B. Schulze: Lifting symmetric pictures to polyhedral scenes 47 [14] L. Ros and F. Thomas, Geometric Methods for Shape Recovery from Line Drawings of Poly-hedra, Journal of Mathematical Imaging and Vision 22 (2005), 5-18. [15] B. Schulze, Block-diagonalized rigidity matrices of symmetric frameworks and applications, Contributions to Algebra and Geometry 51 (2010), 427-466. [16] B. Schulze, Symmetric versions of Laman's Theorem, Discrete & Computational Geometry 44 (2010), 946-972. [17] B. Schulze, Symmetric Laman theorems for the groups C2 and Cs, The Electronic Journal of Combinatorics 17, R154, 1-61. [18] B. Schulze and S. Tanigawa, Infinitesimal rigidity of symmetric bar-joint frameworks, to appear in SIAMJ. Discrete Math, (arXiv:1308.6380), 2015. [19] B. Schulze and W. Whiteley, The Orbit Rigidity Matrix of a Symmetric Framework, Discrete & Comput. Geom. 46 (2011), 561-598. [20] B. Schulze and W. Whiteley, Coning, symmetry and spherical frameworks, Discrete & Comput. Geom. 48 (2012), 622-657. [21] B. Servatius and H. Servatius, The generalized Reye configuration, Ars Mathematica Contemporanea 3 (2010), 21-27. [22] K. Sugihara, Mathematical Structures of Line Drawings of Polyhedrons - Towards Man-Machine Communication by Means of Line Drawings, IEEE Trans. PAMI 4 (1982), 458-469. [23] K. Sugihara, An Algebraic and Combinatorial Approach to the Analysis of Line Drawings of Polyhedra, Discrete Appl. Math. 9 (1984), 77-104. [24] K. Sugihara, An Algebraic Approach to Shape-from-Image Problems, Artificial Intelligence 23 (1984), 59-95. [25] K. Sugihara, Machine interpretation of line drawings, MIT Press, Cambridge Mass, 1986. [26] N. White and W. Whiteley, The algebraic geometry of stresses in frameworks, SIAM J. Disc. Math. 4 (1993), 481-511. [27] W. Whiteley, Motions, stresses and projected polyhedra, Structural Topology 7 (1982), 13-38. [28] W. Whiteley, Cones, infinity and one story buildings, Structural Topology 8 (1983), 53-70. [29] W. Whiteley, A correspondence between scene analysis and motions of frameworks, Discrete Applied Math. 9 (1984), 269-295. [30] W. Whiteley, From a Line Drawing to a Polyhedron, J. Math. Psych. 31 (1987), 441-448. [31] W. Whiteley, A Matroid on Hypergraphs, with Applications in Scene Analysis and Geometry, Discrete & Comput. Geom. 4 (1989), 75-95. [32] W. Whiteley, Weavings, Sections and Projections of Spherical Polyhedra, Discrete Appl. Math. 32 (1991), 275-294. [33] W. Whiteley, Some Matroids from Discrete Applied Geometry, Contemporary Mathematics, AMS 197 (1996), 171-311. [34] W. Whiteley, Rigidity and Scene Analysis, Handbook of Discrete and Computational Geometry, J. E. Goodman, J. O'Rourke (eds), Chapman & Hall (2006), 1327-1354.