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

Jan Brandts; Abdullah Cihangir

Applications of Mathematics (2019)

  • Volume: 64, Issue: 1, page 1-31
  • ISSN: 0862-7940

Abstract

top
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 × n whose Gramians G = P ⊤ 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 - ⊤ 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 - ⊤ is strictly row-substochastic and its support is complementary to that of D , showing that P - ⊤ = 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 S ^ in I n having F as a facet. We call S ^ the acute neighbor of S at F . If P represents a 0 / 1 -simplex that is merely nonobtuse, the inverse of G = P ⊤ 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 - ⊤ 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 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.

How to cite

top

Brandts, Jan, and Cihangir, Abdullah. "On the combinatorial structure of $0/1$-matrices representing nonobtuse simplices." Applications of Mathematics 64.1 (2019): 1-31. <http://eudml.org/doc/294350>.

@article{Brandts2019,
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.},
author = {Brandts, Jan, Cihangir, Abdullah},
journal = {Applications of Mathematics},
keywords = {acute simplex; nonobtuse simplex; orthogonal simplex; $0/1$-matrix; doubly stochastic matrix; fully indecomposable matrix; partly decomposable matrix},
language = {eng},
number = {1},
pages = {1-31},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On the combinatorial structure of $0/1$-matrices representing nonobtuse simplices},
url = {http://eudml.org/doc/294350},
volume = {64},
year = {2019},
}

TY - JOUR
AU - Brandts, Jan
AU - Cihangir, Abdullah
TI - On the combinatorial structure of $0/1$-matrices representing nonobtuse simplices
JO - Applications of Mathematics
PY - 2019
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 64
IS - 1
SP - 1
EP - 31
AB - 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.
LA - eng
KW - acute simplex; nonobtuse simplex; orthogonal simplex; $0/1$-matrix; doubly stochastic matrix; fully indecomposable matrix; partly decomposable matrix
UR - http://eudml.org/doc/294350
ER -

References

top
  1. Bapat, R. B., Raghavan, T. E. S., 10.1017/CBO9780511529979, Encyclopedia of Mathematics and Applications 64, Cambridge University Press, Cambridge (1997). (1997) Zbl0879.15015MR1449393DOI10.1017/CBO9780511529979
  2. Berman, A., Plemmons, R. J., 10.1137/1.9781611971262, Classics in Applied Mathematics 9, SIAM, Philadelphia (1994). (1994) Zbl0815.15016MR1298430DOI10.1137/1.9781611971262
  3. Braess, D., 10.1017/CBO9780511618635, Cambridge University Press, Cambridge (2001). (2001) Zbl0976.65099MR1827293DOI10.1017/CBO9780511618635
  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. (2013) Zbl1340.52020MR3204425
  5. Brandts, J., Cihangir, A., 10.1016/j.laa.2016.05.015, Linear Algebra Appl. 506 (2016), 33-81. (2016) Zbl1382.15047MR3530670DOI10.1016/j.laa.2016.05.015
  6. Brandts, J., Cihangir, A., 10.1515/spma-2017-0014, Spec. Matrices 5 (2017), 158-201. (2017) Zbl1392.05019MR3707128DOI10.1515/spma-2017-0014
  7. Brandts, J., Dijkhuis, S., Haan, V. de, Křížek, M., 10.1016/j.comgeo.2012.09.005, Comput. Geom. 46 (2013), 286-297. (2013) Zbl1261.65020MR2994435DOI10.1016/j.comgeo.2012.09.005
  8. Brandts, J., Korotov, S., Křížek, M., 10.1016/j.laa.2006.10.010, Linear Algebra Appl. 421 (2007), 382-393. (2007) Zbl1112.51006MR2294350DOI10.1016/j.laa.2006.10.010
  9. Brandts, J., Korotov, S., Křížek, M., 10.1016/j.laa.2008.06.011, Linear Algebra Appl. 429 (2008), 2344-2357. (2008) Zbl1154.65086MR2456782DOI10.1016/j.laa.2008.06.011
  10. Brandts, J., Korotov, S., Křížek, M., Šolc, J., 10.1137/060669073, SIAM Rev. 51 (2009), 317-335. (2009) Zbl1172.51012MR2505583DOI10.1137/060669073
  11. Brenner, S. C., Scott, L. R., 10.1007/978-1-4757-4338-8, Texts in Applied Mathematics 15, Spinger, New York (1994). (1994) Zbl0804.65101MR1278258DOI10.1007/978-1-4757-4338-8
  12. Brualdi, R. A., 10.1017/CBO9780511721182, Encyclopedia of Mathematics and Its Applications 108, Cambridge University Press, Cambridge (2006). (2006) Zbl1106.05001MR2266203DOI10.1017/CBO9780511721182
  13. Brualdi, R. A., Ryser, H. J., 10.1017/CBO9781107325708, Encyclopedia of Mathematics and Its Applications 39, Cambridge University Press, Cambridge (1991). (1991) Zbl0746.05002MR1130611DOI10.1017/CBO9781107325708
  14. Fiedler, M., Über qualitative Winkeleigenschaften der Simplexe, Czech. Math. J. 7 (1957), 463-478 German. (1957) Zbl0093.33602MR0094740
  15. Grigor'ev, N. A., Regular simplices inscribed in a cube and Hadamard matrices, Proc. Steklov Inst. Math. 152 (1982), 97-98. (1982) Zbl0502.52009MR0603815
  16. Hadamard, J., Résolution d'une question relative aux déterminants, Darboux Bull. (2) 17 (1893), 240-246 French 9999JFM99999 25.0221.02. (1893) 
  17. Johnson, C. R., 10.1016/0024-3795(82)90238-5, Linear Algebra Appl. 47 (1982), 195-216. (1982) Zbl0488.15011MR0672744DOI10.1016/0024-3795(82)90238-5
  18. Johnson, C. R., Smith, R. L., 10.1016/j.laa.2011.02.016, Linear Algebra Appl. 435 (2011), 953-983. (2011) Zbl1218.15015MR2807211DOI10.1016/j.laa.2011.02.016
  19. Kalai, G., Ziegler, G. M., (Eds.), 10.1007/978-3-0348-8438-9, DMV Seminar 29, Birkhäuser, Basel (2000). (2000) Zbl0944.00089MR1785290DOI10.1007/978-3-0348-8438-9

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.