Smith Normal Form and acyclic matrices
In-Jae Kim1
and Bryan L. Shader2
1Minnesota State University Department of Mathematics and Statistics Mankato MN 56001 USA
2University of Wyoming Department of Mathematics Laramie WY 82071 USA
2University of Wyoming Department of Mathematics Laramie WY 82071 USA
DOI: 10.1007/s10801-008-0121-8
Abstract
An approach, based on the Smith Normal Form, is introduced to study the spectra of symmetric matrices with a given graph. The approach serves well to explain how the path cover number (resp. diameter of a tree T) is related to the maximal multiplicity MaxMult( T) occurring for an eigenvalue of a symmetric matrix whose graph is T (resp. the minimal number q( T) of distinct eigenvalues over the symmetric matrices whose graphs are T). The approach is also applied to a more general class of connected graphs G, not necessarily trees, in order to establish a lower bound on q( G).
Pages: 63–80
Keywords: keywords Smith normal form; acyclic matrix; graph spectra
Full Text: PDF
References
1. Barioli, F., Fallat, S.M.: On two conjectures regarding an inverse eigenvalue problem for acyclic symmetric matrices. Electron. J. Linear Algebra 11, 41-50 (2004)
2. Bridges, W.G., Mena, R.: Lecture Notes. University of Wyoming, Laramie (1984)
3. Fiedler, M.: Eigenvectors of acyclic matrices. Czech. Math. J. 25, 607-618 (1975)
4. Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, New York (2001)
5. Hartley, B., Hawkes, T.O.: Rings, Modules and Linear Algebra. Chapman & Hall, London (1994)
6. Gansner, E.R.: Acyclic digraphs, Young tableaux and nilpotent matrices. SIAM J. Algebraic Discrete Methods 2, 429-440 (1981)
7. Hershkowitz, D.: Paths in directed graphs and spectral properties of matrices. Linear Algebra Appl. 212/213, 309-337 (1994)
8. Johnson, C.R., Leal Duarte, A.: The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree. Linear and Multilinear Algebra 46, 139-144 (1999)
9. Johnson, C.R., Leal Duarte, A.: On the possible multiplicities of the eigenvalues of a Hermitian matrix whose graph is a tree. Linear Algebra Appl. 348, 7-21 (2002)
10. Johnson, C.R., Leal Duarte, A., Saiago, C.M.: The Parter-Wiener theorem: refinement and generalization. SIAM J. Matrix Anal. Appl. 25, 352-361 (2003)
11. Johnson, C.R., Leal Duarte, A., Saiago, C.M.: Inverse eigenvalue problems and list of eigenvalues for matrices whose graph is a tree: the case of generalized stars and double generalized stars. Linear Algebra Appl. 373, 311-330 (2003)
12. Johnson, C.R., Leal Duarte, A., Saiago, C.M., Sutton, B.D., Witt, A.J.: On the relative position of multiple eigenvalues in the spectrum of an Hermitian matrix with a given graph. Linear Algebra Appl. 363, 147-159 (2003)
13. Leal Duarte, A.: Construction of acyclic matrices from spectral data. Linear Algebra Appl. 113, 173- 182 (1989)
14. Leal Duarte, A., Johnson, C.R.: On the minimum number of distinct eigenvalues for a symmetric matrix whose graph is a given tree. Math. Inequal. Appl. 5, 175-180 (2002)
15. Maybee, J., Olesky, D.D., van den Driessche, P., Wiener, G.: Matrices, digraphs and determinants.
2. Bridges, W.G., Mena, R.: Lecture Notes. University of Wyoming, Laramie (1984)
3. Fiedler, M.: Eigenvectors of acyclic matrices. Czech. Math. J. 25, 607-618 (1975)
4. Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, New York (2001)
5. Hartley, B., Hawkes, T.O.: Rings, Modules and Linear Algebra. Chapman & Hall, London (1994)
6. Gansner, E.R.: Acyclic digraphs, Young tableaux and nilpotent matrices. SIAM J. Algebraic Discrete Methods 2, 429-440 (1981)
7. Hershkowitz, D.: Paths in directed graphs and spectral properties of matrices. Linear Algebra Appl. 212/213, 309-337 (1994)
8. Johnson, C.R., Leal Duarte, A.: The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree. Linear and Multilinear Algebra 46, 139-144 (1999)
9. Johnson, C.R., Leal Duarte, A.: On the possible multiplicities of the eigenvalues of a Hermitian matrix whose graph is a tree. Linear Algebra Appl. 348, 7-21 (2002)
10. Johnson, C.R., Leal Duarte, A., Saiago, C.M.: The Parter-Wiener theorem: refinement and generalization. SIAM J. Matrix Anal. Appl. 25, 352-361 (2003)
11. Johnson, C.R., Leal Duarte, A., Saiago, C.M.: Inverse eigenvalue problems and list of eigenvalues for matrices whose graph is a tree: the case of generalized stars and double generalized stars. Linear Algebra Appl. 373, 311-330 (2003)
12. Johnson, C.R., Leal Duarte, A., Saiago, C.M., Sutton, B.D., Witt, A.J.: On the relative position of multiple eigenvalues in the spectrum of an Hermitian matrix with a given graph. Linear Algebra Appl. 363, 147-159 (2003)
13. Leal Duarte, A.: Construction of acyclic matrices from spectral data. Linear Algebra Appl. 113, 173- 182 (1989)
14. Leal Duarte, A., Johnson, C.R.: On the minimum number of distinct eigenvalues for a symmetric matrix whose graph is a given tree. Math. Inequal. Appl. 5, 175-180 (2002)
15. Maybee, J., Olesky, D.D., van den Driessche, P., Wiener, G.: Matrices, digraphs and determinants.