Incidence Matrices
by Dr Richard Klitzing
(reproduced with permission)
Taken purely abstract, polytopes are described by
their surtopial elements plus the relative incidences. The most basic way to
give those incidences are 0-1-matrices with 1 meaning "incident" and 0
"not". But already the easiest polytopes would ask for huge matrices.
This is the entrance for symmetry, the symmetry of the polytope itself. Alike
surtopial elements now can be classed together via symmetrical equivalence, and
the incidence relation will be given for the classes instead. This reduces the
size of the matrix considerably. The diagonal elements of these reduced matrices
will give the total count of elements of each of the respective equivalence
classes. The non-diagonal elements I_(n,m) will provide the numbers of incident
surtopes of class m with any of the elements of class n. The subdiagonal parts
of the rows thus still describe the surtopial element classes. The superdiagonal
parts of the rows describe their environmental aspacts, i.e. vertex figures,
edge figures etc.
Regular polytopes are bound to provide a single class of surtopes per dimension,
but in general there will be more symmetry-inequivalent elements of the same
dimensionality. Therefore it is conveniant to display the dimensional borders as
well as a superimposed guiding grid. Vertex-transitivity for instance can be
read off from an incidence matrix directly, as those polytopes show up only a
single vertex class.
Here as an example the incidence matrix of the truncated cube is given. The
Dynkin diagrams of the relative classes are provided in addition in front of the
rows.
o3x4x
. . . || 24 | 2
1 | 1 2
------++----+-------+----
. x . || 2 | 24 * | 1 1
. . x || 2 | * 12 | 0 2
------++----+-------+----
o3x . || 3 | 3
0 | 8 *
. x4x || 8 | 4
4 | * 6
This matrix shows that there are 24 vertices, all having
the same symmetry (upper-left element). The lowest
two rows show that the 2-dimensional elements have 3 or 8 vertices (lower-left
block) and therefore are triangles or octagons. The
rightmost entries of the first row show further that at each vertex 1 such
triangle and 2 octagons are incident. Further there are 2 types of edges,
the upper one is incident to 1 triangle and 1 octagon,
the other one is incident to 2 octagons only. The
middle block of the bottom two rows shows that the triangle will have all edges
of the first type clearly, but the octagons do use edges of both types (alternatingly).
Altogether there are 8 triangles and 6 octagons
(lower-right block).
Two relations on these numbers are generally valid. The one is the equation
I_(n,n)*I_(n,m)=I_(m,n)*I_(m,m). This is true whether incident representants of
those classes of subpolytopes do exist or not, as in the latter case the
corresponding non-diagonal elements are both zero. The other observation is, and
this derives right from the diagrammatic representation of the 0-1-matrix, the
so called Hasse diagram, that this diagram read top-down instead of bottom-up
would describe the dual abstract polytope. The same is even true for the reduced
matrices, where the matrix of the dual polytope can be read off by just rotating
the matrix half way around an axis orthogonal to the writing plane, thereby
interchanging counts of vertices and facets, or dualising the numbers of the
vertex figures into those of facets and vice versa. Further-on to each of the
subdiagonal parts of the rows, the superdiagonal parts of the rows, and the
diagonal itself, the Euler formula might be applied; but appropriate extensions
like genus, density etc. would have to be considered.
Note that the same polytope might be a fix-element under different symmetry
groups. Thus there could be different (reduced) incidence matrices, all
describing the same polytope. Especially the identity map, taken as reducing
symmetry, would reproduce the 0-1-matrix. On the other hand incidence matrices
just like Hasse diagrams only depend on the structure of the abstract polytope.
That is, different isomorph realisations of it would have the same incidence
matrix. For instance a convex polygon {n} abstractly can not be distinguished
from the polygram {n/d} as long there are no incidences of different types.