Applications of Mathematics, Vol. 64, No. 1, pp. 1-31, 2019


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

Jan Brandts, Abdullah Cihangir

Received August 1, 2018.   Published online December 21, 2018.

Abstract:  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. 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$. 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. 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.
Keywords:  acute simplex; nonobtuse simplex; orthogonal simplex; $0/1$-matrix; doubly stochastic matrix; fully indecomposable matrix; partly decomposable matrix
Classification MSC:  05B20


References:
[1] R. B. Bapat, T. E. S. Raghavan: Nonnegative Matrices and Applications. Encyclopedia of Mathematics and Applications 64, Cambridge University Press, Cambridge (1997). DOI 10.1017/CBO9780511529979 | MR 1449393 | Zbl 0879.15015
[2] A. Berman, R. J. Plemmons: Nonnegative Matrices in the Mathematical Sciences. Classics in Applied Mathematics 9, SIAM, Philadelphia (1994). DOI 10.1137/1.9781611971262 | MR 1298430 | Zbl 0815.15016
[3] D. Braess: Finite Elements. Theory, Fast Solvers, and Applications in Solid Mechanics. Cambridge University Press, Cambridge (2001). DOI 10.1017/CBO9780511618635 | MR 1827293 | Zbl 0976.65099
[4] J. Brandts, A. Cihangir: Counting triangles that share their vertices with the unit $n$-cube. Proc. Conf. Applications of Mathematics 2013 (J. Brandts et al., eds.). Institute of Mathematics AS CR, Praha, 2013, pp. 1-12. MR 3204425 | Zbl 1340.52020
[5] J. Brandts, A. Cihangir: Geometric aspects of the symmetric inverse M-matrix problem. Linear Algebra Appl. 506 (2016), 33-81. DOI 10.1016/j.laa.2016.05.015 | MR 3530670 | Zbl 1382.15047
[6] J. Brandts, A. Cihangir: Enumeration and investigation of acute $0/1$-simplices modulo the action of the hyperoctahedral group. Spec. Matrices 5 (2017), 158-201. DOI 10.1515/spma-2017-0014 | MR 3707128 | Zbl 1392.05019
[7] J. Brandts, S. Dijkhuis, V. de Haan, M. Křížek: There are only two nonobtuse triangulations of the unit $n$-cube. Comput. Geom. 46 (2013), 286-297. DOI 10.1016/j.comgeo.2012.09.005 | MR 2994435 | Zbl 1261.65020
[8] J. Brandts, S. Korotov, M. Křížek: Dissection of the path-simplex in $\mathbb{R}^n$ into $n$ path-subsimplices. Linear Algebra Appl. 421 (2007), 382-393. DOI 10.1016/j.laa.2006.10.010 | MR 2294350 | Zbl 1112.51006
[9] J. Brandts, S. Korotov, M. Křížek: The discrete maximum principle for linear simplicial finite element approximations of a reaction-diffusion problem. Linear Algebra Appl. 429 (2008), 2344-2357. DOI 10.1016/j.laa.2008.06.011 | MR 2456782 | Zbl 1154.65086
[10] J. Brandts, S. Korotov, M. Křížek, J. Šolc: On nonobtuse simplicial partitions. SIAM Rev. 51 (2009), 317-335. DOI 10.1137/060669073 | MR 2505583 | Zbl 1172.51012
[11] S. C. Brenner, L. R. Scott: The Mathematical Theory of Finite Element Methods. Texts in Applied Mathematics 15, Spinger, New York (1994). DOI 10.1007/978-1-4757-4338-8 | MR 1278258 | Zbl 0804.65101
[12] R. A. Brualdi: Combinatorial Matrix Classes. Encyclopedia of Mathematics and Its Applications 108, Cambridge University Press, Cambridge (2006). DOI 10.1017/CBO9780511721182 | MR 2266203 | Zbl 1106.05001
[13] R. A. Brualdi, H. J. Ryser: Combinatorial Matrix Theory. Encyclopedia of Mathematics and Its Applications 39, Cambridge University Press, Cambridge (1991). DOI 10.1017/CBO9781107325708 | MR 1130611 | Zbl 0746.05002
[14] M. Fiedler: Über qualitative Winkeleigenschaften der Simplexe. Czech. Math. J. 7 (1957), 463-478. (In German.) MR 0094740 | Zbl 0093.33602
[15] N. A. Grigor'ev: Regular simplices inscribed in a cube and Hadamard matrices. Proc. Steklov Inst. Math. 152 (1982), 97-98. MR 0603815 | Zbl 0502.52009
[16] J. Hadamard: Résolution d'une question relative aux déterminants. Darboux Bull. (2) 17 (1893), 240-246. (In French.) JFM 25.0221.02
[17] C. R. Johnson: Inverse $M$-matrices. Linear Algebra Appl. 47 (1982), 195-216. DOI 10.1016/0024-3795(82)90238-5 | MR 0672744 | Zbl 0488.15011
[18] C. R. Johnson, R. L. Smith: Inverse $M$-matrices II. Linear Algebra Appl. 435 (2011), 953-983. DOI 10.1016/j.laa.2011.02.016 | MR 2807211 | Zbl 1218.15015
[19] G. Kalai, G. M. Ziegler, (Eds.): Polytopes - Combinatorics and Computation. DMV Seminar 29, Birkhäuser, Basel (2000). DOI 10.1007/978-3-0348-8438-9 | MR 1785290 | Zbl 0944.00089

Affiliations:   Jan Brandts, Abdullah Cihangir, Korteweg-de Vries Institute for Mathematics, University of Amsterdam, P.O. Box 94248, 1090 GE Amsterdam, The Netherlands, e-mail: janbrandts@gmail.com, A.Cihangir@UvA.nl


 
PDF available at: