Algorithmic computation of principal posets using Maple and Python

Marcin Gąsiorek ; Daniel Simson ; Katarzyna Zając

Algebra and discrete mathematics, Tome 17 (2014) no. 1, pp. 33-69

Résumé

We present symbolic and numerical algorithms for a computer search in the Coxeter spectral classification problems. One of the main aims of the paper is to study finite posets $I$ that are principal, i.e., the rational symmetric Gram matrix $G_I : = \frac{1}{2}[C_I+ C^{tr}_I]\in\mathbb{M}_I(\mathbb{Q})$ of $I$ is positive semi-definite of corank one, where $C_I\in\mathbb{M}_I(\mathbb{Z})$ is the incidence matrix of $I$. With any such a connected poset $I$, we associate a simply laced Euclidean diagram $DI\in \{\widetilde{\mathbb{A}}_n, \widetilde{\mathbb{D}}_n, \widetilde{\mathbb{E}}_6, \widetilde{\mathbb{E}}_7, \widetilde{\mathbb{E}}_8\}$, the Coxeter matrix ${\rm Cox}_I:= - C_I\cdot C^{-tr}_I$, its complex Coxeter spectrum ${\mathbf{specc}}_I$, and a reduced Coxeter number $\check {\mathbf{c}}_I$. One of our aims is to show that the spectrum ${\mathbf{specc}}_I$ of any such a poset $I$ determines the incidence matrix $C_I$ (hence the poset $I$) uniquely, up to a $\mathbb{Z}$-congruence. By computer calculations, we find a complete list of principal one-peak posets $I$ (i.e., $I$ has a unique maximal element) of cardinality $\leq 15$, together with ${\mathbf{specc}}_I$, $\check {\mathbf{c}}_I$, the incidence defect $\partial_I:\mathbb{Z}^I \to\mathbb{Z}$, and the Coxeter-Euclidean type $DI$. In case when $DI \in \{\widetilde{\mathbb{A}}_n, \widetilde{\mathbb{D}}_n , \widetilde{\mathbb{E}}_6, \widetilde{\mathbb{E}}_7, \widetilde{\mathbb{E}}_8\}$ and $n:=|I|$ is relatively small, we show that given such a principal poset $I$, the incidence matrix $ C_I$ is $\mathbb{Z}$-congruent with the non-symmetric Gram matrix $ \check G_{DI}$ of $DI$, ${\mathbf{specc}}_I = {\mathbf{specc}}_{DI}$ and $\check {\mathbf{c}}_I= \check {\mathbf{c}}_{DI}$. Moreover, given a pair of principal posets $I$ and $J$, with $|I|= |J| \leq 15$, the matrices $C_I$ and $C_J$ are $\mathbb{Z}$-congruent if and only if ${\mathbf{specc}}_I= {\mathbf{specc}}_J$.

Détail

Keywords: principal poset; edge-bipartite graph; unit quadratic form; computer algorithm; Gram matrix, Coxeter spectrum.
Mots-clés : Coxeter polynomial