On the combinatorial structure of $0/1$-matrices representing nonobtuse simplices

Brandts, Jan ; Cihangir, Abdullah

Applications of Mathematics, Tome 64 (2019) no. 1, pp. 1-31.

Résumé

A $0/1$-simplex is the convex hull of $n+1$ affinely independent vertices of the unit $n$-cube $I^n$. It is nonobtuse if none of its dihedral angles is obtuse, and acute if additionally none of them is right. Acute $0/1$-simplices in $I^n$ can be represented by $0/1$-matrices $P$ of size $n\times n$ whose Gramians $G=P^\top P$ have an inverse that is strictly diagonally dominant, with negative off-diagonal entries. \endgraf In this paper, we will prove that the positive part $D$ of the transposed inverse $P^{-\top }$ of $P$ is doubly stochastic and has the same support as $P$. In fact, $P$ has a fully indecomposable doubly stochastic pattern. The negative part $C$ of $P^{-\top }$ is strictly row-substochastic and its support is complementary to that of $D$, showing that $P^{-\top }=D-C$ has no zero entries and has positive row sums. As a consequence, for each facet $F$ of an acute $0/1$-facet $S$ there exists at most one other acute $0/1$-simplex $\widehat {S}$ in $I^n$ having $F$ as a facet. We call $\widehat {S}$ the acute neighbor of $S$ at $F$. \endgraf If $P$ represents a $0/1$-simplex that is merely nonobtuse, the inverse of $G=P^\top P$ is only weakly diagonally dominant and has nonpositive off-diagonal entries. These matrices play an important role in finite element approximation of elliptic and parabolic problems, since they guarantee discrete maximum and comparison principles. Consequently, $P^{-\top }$ can have entries equal to zero. We show that its positive part $D$ is still doubly stochastic, but its support may be strictly contained in the support of $P$. This allows $P$ to have no doubly stochastic pattern and to be partly decomposable. In theory, this might cause a nonobtuse $0/1$-simplex $S$ to have several nonobtuse neighbors $\widehat {S}$ at each of its facets. \endgraf In this paper, we study nonobtuse $0/1$-simplices $S$ having a partly decomposable matrix representation $P$. We prove that if $S$ has such a matrix representation, it also has a block diagonal matrix representation with at least two diagonal blocks. Moreover, all matrix representations of $S$ will then be partly decomposable. This proves that the combinatorial property of having a fully indecomposable matrix representation with doubly stochastic pattern is a geometrical property of a subclass of nonobtuse $0/1$-simplices, invariant under all $n$-cube symmetries. We will show that a nonobtuse simplex with partly decomposable matrix representation can be split in mutually orthogonal simplicial facets whose dimensions add up to $n$, and in which each facet has a fully indecomposable matrix representation. Using this insight, we are able to extend the one neighbor theorem for acute simplices to a larger class of nonobtuse simplices.

Détail

DOI : 10.21136/AM.2018.0207-18

Classification : 05B20
Keywords: acute simplex; nonobtuse simplex; orthogonal simplex; $0/1$-matrix; doubly stochastic matrix; fully indecomposable matrix; partly decomposable matrix