Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group
2015
The convex hull of n+1 affinely independent vertices of the unit n-cube Cn is called a 0/1-simplex. It is nonobtuse if none its dihedral angles is obtuse, and acute if additionally none of them is right. In terms of linear algebra, acute 0/1-simplices in Cn can be described by nonsingular 0/1-matrices P of size n x n whose Gramians have an inverse that is strictly diagonally dominant, with negative off-diagonal entries.
The first part of this paper deals with giving a detailed description of how to efficiently compute, by means of a computer program, a representative from each orbit of an acute 0/1-simplex under the action of the hyperoctahedral group Bn of symmetries of Cn. A side product of the investigations is a simple code that computes the cycle index of Bn, which can in explicit form only be found in the literature for n < 7. Using the computed cycle indices in combination with Polya's theory of enumeration shows that acute 0/1-simplices are extremely rare among all 0/1-simplices.
In the second part of the paper, we study the 0/1-matrices that represent the acute 0/1-simplices that were generated by our code from a mathematical perspective. One of the patterns observed in the data involves unreduced upper Hessenberg 0/1-matrices of size n x n, block-partitioned according to certain integer compositions of n. These patterns will be fully explained using a so-called One Neighbor Theorem. Additionally, we are able to prove that the volumes of the corresponding acute simplices are in one-to-one correspondence with the part of Kepler's Tree of Fractions that enumerates the rationals between 0 and 1. Another key ingredient in the proofs is the fact that the Gramians of the unreduced upper Hessenberg matrices involved are strictly ultrametric matrices.
Keywords:
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
15
References
1
Citations
NaN
KQI