Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
acute simplex; nonobtuse simplex; orthogonal simplex; $0/1$-matrix; doubly stochastic matrix; fully indecomposable matrix; partly decomposable matrix
acute simplex; nonobtuse simplex; orthogonal simplex; $0/1$-matrix; doubly stochastic matrix; fully indecomposable matrix; partly decomposable matrix
Summary:
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.
References:
[1] Bapat, R. B., Raghavan, T. E. S.: 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] Berman, A., Plemmons, R. J.: 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] Braess, D.: 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] Brandts, J., Cihangir, A.: Counting triangles that share their vertices with the unit $n$-cube. Proc. Conf. Applications of Mathematics 2013 J. Brandts et al. Institute of Mathematics AS CR, Praha (2013), 1-12. MR 3204425 | Zbl 1340.52020
[5] Brandts, J., Cihangir, A.: 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] Brandts, J., Cihangir, A.: 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] Brandts, J., Dijkhuis, S., Haan, V. de, Křížek, M.: 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] Brandts, J., Korotov, S., Křížek, M.: 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] Brandts, J., Korotov, S., Křížek, M.: 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] Brandts, J., Korotov, S., Křížek, M., Šolc, J.: On nonobtuse simplicial partitions. SIAM Rev. 51 (2009), 317-335. DOI 10.1137/060669073 | MR 2505583 | Zbl 1172.51012
[11] Brenner, S. C., Scott, L. R.: 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] Brualdi, R. A.: 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] Brualdi, R. A., Ryser, H. J.: 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] Fiedler, M.: Über qualitative Winkeleigenschaften der Simplexe. Czech. Math. J. 7 (1957), 463-478 German. MR 0094740 | Zbl 0093.33602
[15] Grigor'ev, N. A.: Regular simplices inscribed in a cube and Hadamard matrices. Proc. Steklov Inst. Math. 152 (1982), 97-98. MR 0603815 | Zbl 0502.52009
[16] Hadamard, J.: Résolution d'une question relative aux déterminants. Darboux Bull. (2) 17 (1893), 240-246 French \99999JFM99999 25.0221.02.
[17] Johnson, C. R.: Inverse $M$-matrices. Linear Algebra Appl. 47 (1982), 195-216. DOI 10.1016/0024-3795(82)90238-5 | MR 0672744 | Zbl 0488.15011
[18] Johnson, C. R., Smith, R. L.: 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] Kalai, G., Ziegler, G. M., (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
Search
Partner of
