×

Symmetric matrices, signed graphs, and nodal domain theorems. (English) Zbl 1512.05169

Summary: E. B. Davies et al. [Linear Algebra Appl. 336, No. 1–3, 51–60 (2001; Zbl 0990.05093)] proved discrete nodal domain theorems for eigenfunctions of generalized Laplacians, i.e., symmetric matrices with non-positive off-diagonal entries. In this paper, we establish nodal domain theorems for arbitrary symmetric matrices by exploring the induced signed graph structure. Our concepts of nodal domains for any function on a signed graph are switching invariant. When the induced signed graph is balanced, our definitions and upper bound estimates reduce to existing results for generalized Laplacians. Our approach provides a more conceptual understanding of Fiedler’s results on eigenfunctions of acyclic matrices. This new viewpoint leads to lower bound estimates for the number of strong nodal domains which improves previous results of G. Berkolaiko [Commun. Math. Phys. 278, No. 3, 803–819 (2008; Zbl 1171.05356)] and H. Xu and S.-T. Yau [J. Comb. 3, No. 4, 609–622 (2012; Zbl 1270.05065)]. We also prove a new type of lower bound estimates by a duality argument.

MSC:

05C22 Signed and weighted graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Atay, FM; Liu, S., Cheeger constants, structural balance, and spectral clustering analysis for signed graphs, Discrete. Math., 343, 26 (2020) · Zbl 1429.05120 · doi:10.1016/j.disc.2019.111616
[2] Berkolaiko, G., A lower bound for nodal count on discrete and metric graphs, Comm. Math. Phys., 278, 803-819 (2008) · Zbl 1171.05356 · doi:10.1007/s00220-007-0391-3
[3] Bıyıkoğlu, T., A discrete nodal domain theorem for trees, Linear Algebra Appl., 360, 197-205 (2003) · Zbl 1012.05114 · doi:10.1016/S0024-3795(02)00451-2
[4] Bıyıkoğlu, T., Leydold, J., Stadler, P. F.: Laplacian Eigenvectors of Graphs, Perron-Frobenius and Faber-Krahn Type Theorems. Lecture Notes in Mathematics 1915, Springer, (2007) · Zbl 1129.05001
[5] Bıyıkoğlu, T.; Leydold, J.; Stadler, PF, Nodal domain theorems and bipartite subgraphs, Electron. J. Linear Algebra, 13, 344-351 (2005) · Zbl 1090.05046 · doi:10.13001/1081-3810.1167
[6] Bıyıkoğlu, T.; Hordijk, W.; Leydold, J.; Pisanski, T.; Stadler, PF, Graph Laplacians, nodal domains, and hyperplane arrangements, Linear Algebra Appl., 390, 155-174 (2004) · Zbl 1050.05081 · doi:10.1016/j.laa.2004.04.024
[7] Bonnefont, M.; Golénia, S.; Keller, M.; Liu, S.; Münch, F., Magnetic-sparseness and Schrödinger operators on graphs, Ann. Henri Poincaré, 21, 5, 1489-1516 (2020) · Zbl 1444.81018 · doi:10.1007/s00023-020-00885-6
[8] Bonnington, CP; Little, CHC, The Foundations of Topological Graph Theory (1995), New York: Springer-Verlag, New York · Zbl 0844.05002 · doi:10.1007/978-1-4612-2540-9
[9] Chang, KC; Shao, S.; Zhang, D., Nodal domains of eigenvectors for \(1\)-Laplacian on graphs, Adv. Math., 308, 529-574 (2017) · Zbl 1366.35204 · doi:10.1016/j.aim.2016.12.020
[10] Cheng, S-Y, Eigenfunctions and nodal sets, Comment. Math. Helv., 51, 1, 43-55 (1976) · Zbl 0334.35022 · doi:10.1007/BF02568142
[11] Colin de Verdière, Y.: Multiplicités des valeurs propres. Laplaciens discrets et laplaciens continus. [Multiplicities of eigenvalues. Discrete Laplacians and continuous Laplacians] Rend. Mat. Appl. 13, 433-460 (1993) · Zbl 0802.58060
[12] Courant, R., Ein allgemeiner Satzt zur Theorie der Eigenfunktionen selbsadjungierter Differentialausdrücke, Nachr. Ges. Wiss. Göttingen, 1, 81-84 (1923) · JFM 49.0342.01
[13] Courant, R.; Hilbert, D., Methods of Mathematical Physics (1953), New York, N.Y.: Interscience Publishers Inc, New York, N.Y. · Zbl 0053.02805
[14] Cuesta, M.; DeFigueiredo, DG; Gossez, JP, A nodal domain property for the \(p\)-Laplacian, C. R. Acad. Sci. Paris Sér. I Math., 330, 8, 669-673 (2000) · Zbl 0954.35124 · doi:10.1016/S0764-4442(00)00245-7
[15] Davies, EB; Gladwell, GML; Leydold, J.; Stadler, PF, Discrete nodal domain theorems, Linear Algebra Appl., 336, 51-60 (2001) · Zbl 0990.05093 · doi:10.1016/S0024-3795(01)00313-5
[16] Duval, AM; Reiner, V., Perron-Frobenius type results and discrete versions of nodal domain theorems, Linear Algebra Appl., 294, 259-268 (1999) · Zbl 0938.15002 · doi:10.1016/S0024-3795(99)00090-7
[17] Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J., 23, 298-305 (1973) · Zbl 0265.05119 · doi:10.21136/CMJ.1973.101168
[18] Fiedler, M., Eigenvectors of acyclic matrices, Czech. Math. J., 25, 607-618 (1975) · Zbl 0325.15014 · doi:10.21136/CMJ.1975.101356
[19] Fiedler, M., A property of eigenvectors of non-negative symmetric matrices and its applications to graph theory, Czech. Math. J., 25, 619-633 (1975) · Zbl 0437.15004 · doi:10.21136/CMJ.1975.101357
[20] Friedman, J., Some geometric aspects of graphs and their eigenfunctions, Duke Math. J., 69, 3, 487-525 (1993) · Zbl 0785.05066 · doi:10.1215/S0012-7094-93-06921-9
[21] Gantmacher, F.P., Krein, M.G., Oscillation matrices and kernels and small vibrations of mechanical systems. Revised edition. In: Translation based on the: Russian original, p. 2002. AMS Chelsea Publishing, Providence, RI, Edited and with a preface by Alex Eremenko (1941) · Zbl 0060.03303
[22] Gladwell, GML; Zhu, H., Courant’s nodal line theorem and its discrete counterparts, Quart. J. Mech. Appl. Math., 55, 1, 1-15 (2002) · Zbl 0997.65125 · doi:10.1093/qjmam/55.1.1
[23] Haemers, WH, Interlacing eigenvalues and graphs, Linear Algebra Appl., 226-228, 593-616 (1995) · Zbl 0831.05044 · doi:10.1016/0024-3795(95)00199-2
[24] Harary, F., On the notion of balance of a signed graph, Mich. Math. J., 2, 54, 143-146 (1953) · Zbl 0056.42103
[25] Harary, F., Structural duality, Behav. Sci., 2, 4, 255-265 (1957) · doi:10.1002/bs.3830020403
[26] Jost, J.; Mulas, R.; Zhang, D., \(p\)-Laplace operators for oriented hypergraphs, Vietnam J. Math., 50, 323-358 (2022) · Zbl 1487.05163 · doi:10.1007/s10013-021-00525-4
[27] Jost, J., Zhang, D.: Discrete-to-continuous extensions: piecewise multilinear extension, min-max theory and spectral theory. arXiv: 2106:04116, (2021)
[28] Keller, M.; Schwarz, M., Courant’s nodal domain theorem for positivity preserving forms, J. Spectr. Theory, 10, 1, 271-309 (2020) · Zbl 1444.47004 · doi:10.4171/JST/292
[29] Lin, Y.; Lippner, G.; Mangoubi, D.; Yau, S-T, Nodal geometry of graphs on surfaces, Discrete. Contin. Dyn. Syst., 28, 3, 1291-1298 (2010) · Zbl 1214.05095 · doi:10.3934/dcds.2010.28.1291
[30] Liu, S.; Münch, F.; Peyerimhoff, N., Curvature and higher order Buser inequalities for the graph connection Laplacian, SIAM J. Discrete Math., 33, 1, 257-305 (2019) · Zbl 1404.05113 · doi:10.1137/16M1056353
[31] Lovász, L.: Discrete quantitative nodal theorem. Electron. J. Combin. 28, 6 (2021) · Zbl 1473.05179
[32] Mohammadian, A., Graphs and their real eigenvectors, Linear Multilinear Algebra, 64, 2, 136-142 (2016) · Zbl 1331.05065 · doi:10.1080/03081087.2015.1025687
[33] Powers, DL, Graph partitioning by eigenvectors, Linear Algebra Appl., 101, 121-133 (1988) · Zbl 0666.05056 · doi:10.1016/0024-3795(88)90147-4
[34] Roth, R., On the eigenvectors belonging to the minimum eigenvalue of an essentially nonnegative symmetric matrix with bipartite graph, Linear Algebra Appl., 118, 1-10 (1989) · Zbl 0668.15005 · doi:10.1016/0024-3795(89)90569-7
[35] Tudisco, F.; Hein, M., A nodal domain theorem and a higher-order Cheeger inequality for the graph \(p\)-Laplacian, J. Spectr. Theory, 8, 3, 883-908 (2018) · Zbl 1491.05126 · doi:10.4171/JST/216
[36] van der Holst, H., A short proof of the planarity characterization of Colin de Verdière, J. Combin. Theory Ser. B, 65, 2, 269-272 (1995) · Zbl 0841.05025 · doi:10.1006/jctb.1995.1054
[37] van der Holst, H.: Topological and spectral graph characterizations, Ph. D. Thesis, University of Amsterdam, 1996
[38] Xu, H.; Yau, S-T, Nodal domain and eigenvalue multiplicity of graphs, J. Comb., 3, 4, 609-622 (2012) · Zbl 1270.05065
[39] Zaslavsky, T., Signed graphs, Discrete Appl. Math., 4, 1, 47-74 (1982) · Zbl 0476.05080 · doi:10.1016/0166-218X(82)90033-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.