Site Map Polytopes Dynkin Diagrams Vertex Figures, etc. Incidence Matrices Index

Incidence Matrices

Any polytope, honeycomb or hyperbolic tiling is abstractly defined by its constituents (those geometric elements of different dimensionalities) and the incidence relation thereof. Even more general figures consisting of elements of different "dimensions" with any correlating incidence might be tabulated in matrices.



The 0-1 Matrix   (up)

There are different ways to list those incidences. Often these can be found in the form of 0-1-matrices correlating any element of "dimension" n with those of "dimension" m. Clearly those matrices can be combined to a larger square matrix, listing all elements of any "dimension" together with their correlating incidence. It is convenient to provide in such a large listing kind of blockings of the different "dimensionalities". For instance for the tetrahedron we thus would get the matrix

v0,0,1 | 1 0 0 0 | 1 1 1 0 0 0 | 1 1 1 0
v0,0,2 | 0 1 0 0 | 1 0 0 1 1 0 | 1 1 0 1
v0,0,3 | 0 0 1 0 | 0 1 0 1 0 1 | 1 0 1 1
v0,0,4 | 0 0 0 1 | 0 0 1 0 1 1 | 0 1 1 1
------+---------+-------------+--------
e0,1,2 | 1 1 0 0 | 1 0 0 0 0 0 | 1 1 0 0
e0,1,3 | 1 0 1 0 | 0 1 0 0 0 0 | 1 0 1 0
e0,1,4 | 1 0 0 1 | 0 0 1 0 0 0 | 0 1 1 0
e0,2,3 | 0 1 1 0 | 0 0 0 1 0 0 | 1 0 0 1
e0,2,4 | 0 1 0 1 | 0 0 0 0 1 0 | 0 1 0 1
e0,3,4 | 0 0 1 1 | 0 0 0 0 0 1 | 0 0 1 1
------+---------+-------------+--------
f1,2,3 | 1 1 1 0 | 1 1 0 1 0 0 | 1 0 0 0
f1,2,4 | 1 1 0 1 | 1 0 1 0 1 0 | 0 1 0 0
f1,3,4 | 1 0 1 1 | 0 1 1 0 0 1 | 0 0 1 0
f2,3,4 | 0 1 1 1 | 0 0 0 1 1 1 | 0 0 0 1

Already this simple example displays several things. First it shows its notational hugeness despite describing such a simple figure as the tetrahedron. Further it is absolutely independent which topological representant of a tetrahedron is chosen; special symmetrical variants are not at all distinguished. On the other hand this matrix is clearly symmetrical (in the matrix sense).



Symmetry Equivalence Classes   (up)

There is an other type of incidence matrices which takes account to symmetries. This is due to the fact that the symmetry permutes not only equivalent elements on their own, but moreover permutes complete flags, i.e. it maintains the incidence relations of classes: if a vertex is incident to a face, and this vertex is symmetry equivalent to an other vertex, then there is a (possibly other) face incident to that other vertex, which is in the same symmetry class as the former face. Thus that other type of incidence matrices represents not single elements but whole equivalence classes of symmetry. The diagonal elements thereof, instead of being small identity matrices, which than no longer provide any information about the total counts of the different elements, can be exchanged by diagonal matrices giving the total counts of each equivalence class. In order to show that these diagonal blocks are meant in this different sense, the non-diagonal elements of those diagonal blocks, which have no real sense any longer, are denoted just by asterices.

To provide an example of such a compacter matrix, which shows up equivalence classes of symmetries, here the tetrahedron (tet) is given again in its symmetry as a digonal antiprism:

vertices           | 4 | 1 2 | 3
-------------------+---+-----+--
top- & bottom-edge | 2 | 2 * | 2
lateral edges      | 2 | * 4 | 2
-------------------+---+-----+--
faces              | 3 | 1 2 | 4

For other quite small and thus easy examples, showing different equivalence groupings of the same polyhedron, look at the tetragonal pyramid (see squippy).

As both, incidence relations and symmetry, can be seen as a concept of abstract polytopes, different symmetry preserving "realizations", i.e. isomorphic figures, will clearly have the same incidence matrix. For instance the incidence matrix of a pentagon and a pentagram are indistinguishable. The same for o-3-o-5-x (doe) and o-3-o-5/2-x (gissid), for x-3-o-5-o (ike) and x-3-o-5/2-o (gike), for x-5/2-o-5-o (sissid) and x-5-o-5/2-o (gad), for x-4/3-x-3-x (quitco) and x-4-x-3-x (girco), and lots of others more.



Some Relations   (up)

Obviously those symmetry respecting incidence matrices are no longer bound to be symmetrical. But still there is some kind of intercorrelation of numbers which nearly halves the effort (just as for 0-1-matrices). If Ii,j is the matrix element of the i-th row and the j-th column, we have the equation

Ii,i * Ii,j = Ij,i * Ij,j

This relation is true, independent to whether the corresponding boundaries are incident or not; for in the latter case the non-diagonal elements will be both zero.

Further, for the diagonal elements clearly the Euler equation (possibly with genus or other extension) holds. The same for all subdiagonal elements of each row (the subpolytopes), and alike for all super-diagonal elements of each row (the figures of complementary space to each kind of subpolytope, such as vertex figures, edge figures, etc.).

Even the group order can be read from the (second kind of) incidence matrices. Choose any element of the last diagonal block (some facet count), multiply it with some facet count of the corresponding (n-1)-subpolytope, multiply that by some facet count of the corresponding (n-2)-subpolytope, and so on until you end in a vertex-edge incidence number. For n=2 this is depicted below:

.  .   . | .  .   . | .  .   .
.  .   . | .  .   . | .  .   .
.  .   . | .  .   . | .  .   .
---------+----------+---------
.  .   . | .  .   . | .  .   .
. I0,1   .<--.  .   . | .  .   .
.  .   . | .  ^   . | .  .   .
---------+----:-----+---------
.  .   . | .  :   . | .  .   .
.  .   . | . I1,2   .<--. I2,2   .
.  .   . | .  .   . | .  .   .
 
I0,1 * I1,2 * I2,2 = g

Reading an incidence diagram (Hasse diagram) of an abstract polytope top-down, one gets the incidence diagram of the dual abstract polytope. That is, (n-k-1)-subploytopes correspond to k-subpolytopes of the dual polytope. But again this is a feature of the flag: if a set of subpolytopial elements of different dimensionalities is mutually incident, then the set of piecewise dual elements is mutually incident too. And as flag features loop through by symmetry equivalences, the incidence matrix of any polytope should be quite nicely correlated to the one of its dual partner. Indeed, just turn the matrix by 180 degrees:

tesseract (tes)  <-dual->  hexadecachoron (hex)
 
16 |  4 |  6 | 4          8 |  6 | 12 |  8
---+----+----+--          --+----+----+---
 2 | 32 |  3 | 3  ,-->    2 | 24 |  4 |  4
---+----+----+--  |180|  --+----+----+---
 4 |  4 | 24 | 2    <--'  3 |  3 | 32 |  2
---+----+----+--          --+----+----+---
 8 | 12 |  6 | 8          4 |  6 |  4 | 16


If we would restrict to polytopes with a linear Dynkin diagram, that is to polytopes with Schläfli symbol {a,b,...,c,d}, where a, b, ..., c, d are the rational subdivisors of π of the angles between the corresponding mirrors, together with all their truncates, i.e. the polytopes tw,x,...,y,z{a,b,...,c,d}, then further relations can be deduced, correlating the incidence matrix numbers for the different truncates. So consider in the following any arbitrary group [a,b,...,c,d] to be fixed, and abreviate the truncates just by their truncation-prefix. Then we have the following relations:

The number of vertices of a truncated polytope, I0,0(tw,x,...,y,z), is related to the matrix entries of the untruncated one, Ii,j(t0), by

I0,0(tw,x,...,y,z) = Iz,z(t0) * Iz,y(t0) *...* Ix,w(t0).

The number of a given type of edges of a polytope having a certain truncated Schläfli symbol is identical with the number of vertices of that polytope which has its vertices at the center of edges of the former. The Dynkin diagram of the latter has all the nodes of the former ringed, plus the neighbouring nodes of that node corresponding to the edge under consideration, minus that single node. Hence, f.i. for polychora

I1,1(t1,3,4)|1 = I0,0(t0,2,3,4),
I1,1(t1,3,4)|3 = I0,0(t1,2,4),
I1,1(t1,3,4)|4 = I0,0(t1,3).

The number of a given type of a higher dimensional boundary of a polytope having a certain truncated Schläfli symbol finally is identical with the number of vertices of that polytope which has its vertices at the center of those boundaries. Using a kind of iteration of the former, getting nothing but an infinitely iterated projection of the Wythoff point into the related hyperplanes, one comes up with the final truncated Schläfli symbol (Dynkin diagram) of the second polytope. It has all nodes of the former ringed, plus the neighbours of those nodes which correspond to the Dynkin diagram of the boundary, minus those nodes of the boundary itself. Hence, f.i. for polychora

I2,2(t1,4)|0,1 = I0,0(t2,4),
I2,2(t1,4)|1,2 = I0,0(t0,3,4),
I2,2(t1,4)|1,4 = I0,0(t0,2,3),
I2,2(t1,4)|3,4 = I0,0(t1,2).


The set of uniform polytopes also is easily recognizable from their incidence matrices. Those necessarily ask for n0 = 1, i.e. use only a single class of symmetry-equivalent vertices. (In fact, this latter restriction equates to what is called isogonality. The further restriction to unit-sized edge lengths only would not be transported into the incidence matrix numbers for sure.) – Likewise any noble polytope can be easily translated into incidence matrix restrictions: There we ought to have n0 = nD-1 = 1, i.e. with only a single class of symmetry-equivalent vertices and additionally a single class of symmetry-equivalent facets. – Regular polytopes finally would be exactly those, which have nk = 1 for any subdimension k.



Incidence Matrices for Compounds

Like polytopes of one dimension above, compounds use several polytopes of that base dimension. Accordingly their incidence matrix too will no longer show up the base-dimensional polytopes, i.e. the component polytopes, within the diagonal (which is reserved for the overall counts), but will have to add to the matrix an additional row-block for those, displaying the count of the individual component at the final, i.e. diagonal block element, so that it would look more like a matrix for a polytope of one dimension above. None the less, if base-dimension is n, although having n+1 blocks, the (individual) row-sum within the block element, positioned at the intersection of the nth block-column and (n-1)st block-row, still equals 2 (according to the Euler relation). – In comparision to (normal) polytopes of one dimension above, the same relation would be asked nominally for the block with the same description as just given, but there we would have to replace n by n+1 as well (as being one dimension above), so that in consequence this condition would take place within a different block! (Even so, in order to better distinguish these types of matrices visually, the new added block-column will be separated by a double stroke, cf. the example given below.)

The row-sum of the entries of the last block-column usually will be 1, except for the final one, which clearly counts the components. This is true as long all elements, whether completely coincident or not, are counted separately. If, for instance, the vertices fall together pairwise, then surely they could be chosen to be identified as well. In consequence the formerly individual vertex figures will become compounds in turn. Thereby the individual vertex count is divided by some number, the coincidence count (here by 2), while all other numbers of this very row will be multiplied by the same number. This matrix transformation still fulfills the matrix relation cited in chapter Some Relations above. Thereby too the entries of the last block-column will be multiplied. Thus those show up, in this case, the number of components of the vertex figure compound. To provide an example, we look at rhom, the compound of 5 cubes within a doe. (Note the vertex figure numbers "6" in the right matrix below: Those describe a (non-regular) compound of 2 triangles, kind of a mutually rotated star of David.)

           coincident vertices, 
taken separately:       being identified:

40 |  3 |  3 || 1       20 |  6 |  6 || 2
---+----+----++--       ---+----+----++--
 2 | 60 |  2 || 1        2 | 60 |  2 || 1
---+----+----++--       ---+----+----++--
 4 |  4 | 30 || 1        4 |  4 | 30 || 1
---+----+----++--       ---+----+----++--
 8 | 12 |  6 || 5        8 | 12 |  6 || 5

As can be seen already in that single example: the vertex figure element counts are no longer the full super-diagonal parts of the rows of the first row-block, instead they have to be terminated before the additional last column-block (i.e. the double-stroke). The same holds true for the edge figures etc. Alternatively one could consider that additional elements as body counts of the corresponding dimensionality. – Seen in that view, even incidence matrices of "normal" polytopes could be given that same extension of the last row and column; just that all entries of the last column there would be 1, and the non-diagonal elements of the last row would copy the number of the corresponding diagonal element. (In fact, this trivial form of those is why they will not be used for "normal" polytopes.)

Strictly speaking, only those figures, with a non-unit number within the final block (at the lower left end) and with all other final entries being 1, can be called true compounds. All other cases would already step somehow towards the mere (single) polytope by means of the applied unifications, as those vertex identifications (or more generally: combinations of several individual elements to a single sub-dimensional compound figure) would interlink the formerly still separate components. Also the entries of the lowest block-row (the components) strictly would be wrong, as those clearly use individual elements instead of combined ones. - None the less, they will be given here, within that extended incidence matrix notation, for completeness too.



Note:

Be aware of the -sign used sometimes within the incidence matrices given for higherdimensional polytopes. Those are links to the incidence matrices of the corresponding sub-polytope, possibly its vertex figure etc.
(Btw., the inverse mapping, listing the larger polytopes, where some given polytope is a facet of, is provided as separate "used as facet" page. A further similar inverse mapping is accessible as separate "used as vertex figure" page too.)

© 2004-2014
top of page