| Title:
|
On the combinatorial structure of $0/1$-matrices representing nonobtuse simplices (English) |
| Author:
|
Brandts, Jan |
| Author:
|
Cihangir, Abdullah |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
64 |
| Issue:
|
1 |
| Year:
|
2019 |
| Pages:
|
1-31 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
acute simplex |
| Keyword:
|
nonobtuse simplex |
| Keyword:
|
orthogonal simplex |
| Keyword:
|
$0/1$-matrix |
| Keyword:
|
doubly stochastic matrix |
| Keyword:
|
fully indecomposable matrix |
| Keyword:
|
partly decomposable matrix |
| MSC:
|
05B20 |
| idZBL:
|
Zbl 07031674 |
| idMR:
|
MR3913881 |
| DOI:
|
10.21136/AM.2018.0207-18 |
| . |
| Date available:
|
2019-02-08T10:00:50Z |
| Last updated:
|
2021-03-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147590 |
| . |
| Reference:
|
[1] Bapat, R. B., Raghavan, T. E. S.: Nonnegative Matrices and Applications.Encyclopedia of Mathematics and Applications 64, Cambridge University Press, Cambridge (1997). Zbl 0879.15015, MR 1449393, 10.1017/CBO9780511529979 |
| Reference:
|
[2] Berman, A., Plemmons, R. J.: Nonnegative Matrices in the Mathematical Sciences.Classics in Applied Mathematics 9, SIAM, Philadelphia (1994). Zbl 0815.15016, MR 1298430, 10.1137/1.9781611971262 |
| Reference:
|
[3] Braess, D.: Finite Elements. Theory, Fast Solvers, and Applications in Solid Mechanics.Cambridge University Press, Cambridge (2001). Zbl 0976.65099, MR 1827293, 10.1017/CBO9780511618635 |
| Reference:
|
[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. Zbl 1340.52020, MR 3204425 |
| Reference:
|
[5] Brandts, J., Cihangir, A.: Geometric aspects of the symmetric inverse M-matrix problem.Linear Algebra Appl. 506 (2016), 33-81. Zbl 1382.15047, MR 3530670, 10.1016/j.laa.2016.05.015 |
| Reference:
|
[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. Zbl 1392.05019, MR 3707128, 10.1515/spma-2017-0014 |
| Reference:
|
[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. Zbl 1261.65020, MR 2994435, 10.1016/j.comgeo.2012.09.005 |
| Reference:
|
[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. Zbl 1112.51006, MR 2294350, 10.1016/j.laa.2006.10.010 |
| Reference:
|
[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. Zbl 1154.65086, MR 2456782, 10.1016/j.laa.2008.06.011 |
| Reference:
|
[10] Brandts, J., Korotov, S., Křížek, M., Šolc, J.: On nonobtuse simplicial partitions.SIAM Rev. 51 (2009), 317-335. Zbl 1172.51012, MR 2505583, 10.1137/060669073 |
| Reference:
|
[11] Brenner, S. C., Scott, L. R.: The Mathematical Theory of Finite Element Methods.Texts in Applied Mathematics 15, Spinger, New York (1994). Zbl 0804.65101, MR 1278258, 10.1007/978-1-4757-4338-8 |
| Reference:
|
[12] Brualdi, R. A.: Combinatorial Matrix Classes.Encyclopedia of Mathematics and Its Applications 108, Cambridge University Press, Cambridge (2006). Zbl 1106.05001, MR 2266203, 10.1017/CBO9780511721182 |
| Reference:
|
[13] Brualdi, R. A., Ryser, H. J.: Combinatorial Matrix Theory.Encyclopedia of Mathematics and Its Applications 39, Cambridge University Press, Cambridge (1991). Zbl 0746.05002, MR 1130611, 10.1017/CBO9781107325708 |
| Reference:
|
[14] Fiedler, M.: Über qualitative Winkeleigenschaften der Simplexe.Czech. Math. J. 7 (1957), 463-478 German. Zbl 0093.33602, MR 0094740 |
| Reference:
|
[15] Grigor'ev, N. A.: Regular simplices inscribed in a cube and Hadamard matrices.Proc. Steklov Inst. Math. 152 (1982), 97-98. Zbl 0502.52009, MR 0603815 |
| Reference:
|
[16] Hadamard, J.: Résolution d'une question relative aux déterminants.Darboux Bull. (2) 17 (1893), 240-246 French \99999JFM99999 25.0221.02. |
| Reference:
|
[17] Johnson, C. R.: Inverse $M$-matrices.Linear Algebra Appl. 47 (1982), 195-216. Zbl 0488.15011, MR 0672744, 10.1016/0024-3795(82)90238-5 |
| Reference:
|
[18] Johnson, C. R., Smith, R. L.: Inverse $M$-matrices II.Linear Algebra Appl. 435 (2011), 953-983. Zbl 1218.15015, MR 2807211, 10.1016/j.laa.2011.02.016 |
| Reference:
|
[19] Kalai, G., Ziegler, G. M., (Eds.): Polytopes---Combinatorics and Computation.DMV Seminar 29, Birkhäuser, Basel (2000). Zbl 0944.00089, MR 1785290, 10.1007/978-3-0348-8438-9 |
| . |
