Geodesic
Bounds on the subdominant eigenvalue involving group inverses with applications to graphs
Czechoslovak Mathematical Journal, Tome 48 (1998) no. 1, pp. 1-20 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $A$ be an $n\times n$ symmetric, irreducible, and nonnegative matrix whose eigenvalues are $\lambda _1 > \lambda _2 \ge \ldots \ge \lambda _n$. In this paper we derive several lower and upper bounds, in particular on $\lambda _2$ and $\lambda _n$, but also, indirectly, on $\mu = \max _{2\le i \le n} |\lambda _i|$. The bounds are in terms of the diagonal entries of the group generalized inverse, $Q^{\#}$, of the singular and irreducible M-matrix $Q=\lambda _1 I-A$. Our starting point is a spectral resolution for $Q^{\#}$. We consider the case of equality in some of these inequalities and we apply our results to the algebraic connectivity of undirected graphs, where now $Q$ becomes $L$, the Laplacian of the graph. In case the graph is a tree we find a graph-theoretic interpretation for the entries of $L^{\#}$ and we also sharpen an upper bound on the algebraic connectivity of a tree, which is due to Fiedler and which involves only the diagonal entries of $L$, by exploiting the diagonal entries of $L^{\#}$.
Let $A$ be an $n\times n$ symmetric, irreducible, and nonnegative matrix whose eigenvalues are $\lambda _1 > \lambda _2 \ge \ldots \ge \lambda _n$. In this paper we derive several lower and upper bounds, in particular on $\lambda _2$ and $\lambda _n$, but also, indirectly, on $\mu = \max _{2\le i \le n} |\lambda _i|$. The bounds are in terms of the diagonal entries of the group generalized inverse, $Q^{\#}$, of the singular and irreducible M-matrix $Q=\lambda _1 I-A$. Our starting point is a spectral resolution for $Q^{\#}$. We consider the case of equality in some of these inequalities and we apply our results to the algebraic connectivity of undirected graphs, where now $Q$ becomes $L$, the Laplacian of the graph. In case the graph is a tree we find a graph-theoretic interpretation for the entries of $L^{\#}$ and we also sharpen an upper bound on the algebraic connectivity of a tree, which is due to Fiedler and which involves only the diagonal entries of $L$, by exploiting the diagonal entries of $L^{\#}$.
Classification : 05C40, 05C50, 15A09, 15A18, 15A42, 15A48 
@article{CMJ_1998_48_1_a0,
     author = {Kirkland, Stephen J. and Neumann, Michael and Shader, Bryan L.},
     title = {Bounds on the subdominant eigenvalue involving group inverses with applications to graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {1--20},
     year = {1998},
     volume = {48},
     number = {1},
     mrnumber = {1614056},
     zbl = {0931.15012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a0/}
}
TY  - JOUR
AU  - Kirkland, Stephen J.
AU  - Neumann, Michael
AU  - Shader, Bryan L.
TI  - Bounds on the subdominant eigenvalue involving group inverses with applications to graphs
JO  - Czechoslovak Mathematical Journal
PY  - 1998
SP  - 1
EP  - 20
VL  - 48
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a0/
LA  - en
ID  - CMJ_1998_48_1_a0
ER  - 
%0 Journal Article
%A Kirkland, Stephen J.
%A Neumann, Michael
%A Shader, Bryan L.
%T Bounds on the subdominant eigenvalue involving group inverses with applications to graphs
%J Czechoslovak Mathematical Journal
%D 1998
%P 1-20
%V 48
%N 1
%U http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a0/
%G en
%F CMJ_1998_48_1_a0
Kirkland, Stephen J.; Neumann, Michael; Shader, Bryan L. Bounds on the subdominant eigenvalue involving group inverses with applications to graphs. Czechoslovak Mathematical Journal, Tome 48 (1998) no. 1, pp. 1-20. http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a0/

[1] A. Ben-Israel and T. N. Greville: Generalized Inverses: Theory and Applications. Academic Press, New-York, 1973.

[2] A. Berman and R. J. Plemmons: Nonnegative Matrices in the Mathematical Sciences. Academic Press, New-York, 1979. | MR

[3] S. L. Campbell and C. D. Meyer, Jr.: Generalized Inverses of Linear Transformations. Dover Publications, New York, 1991. | MR

[4] M. Fiedler: Algebraic connectivity of graphs. Czechoslovak Math. J. 23 (1973), 298–305. | MR | Zbl

[5] M. Fiedler: A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory. Czechoslovak Math. J. 25 (1975), 619–633. | MR

[6] C. D. Meyer, Jr.: The role of the group generalized inverse in the theory of finite Markov chains. SIAM Rev. 17 (1975), 443–464. | DOI | MR | Zbl

[7] C. D. Meyer: The condition of a finite Markov chain and perturbations bounds for the limiting probabilities. SIAM J. Alg. Disc. Meth. 1 (1980), 273–283. | DOI | MR

[8] C. D. Meyer: Sensitivity of the stationary distribution of a Markov chain. SIAM J. Matrix Anal. Appl. 15 (1994), 715–728. | DOI | MR | Zbl

[9] C. D. Meyer, Jr. and G. W. Stewart: Derivatives and perturbations of eigenvectors. SIAM J. Numer. Anal. 25 (1988), 679–691. | DOI | MR

[10] R. Merris: Laplacian matrices and graphs: a survey. Lin. Alg. Appl. 197, 198 (1994), 143–176. | DOI | MR

[11] B. Mohar: Eigenvalues, diameter, and mean distance in graphs. Graphs Combin. 7 (1991), 53–64. | DOI | MR | Zbl

[12] M. Neumann and R. J. Plemmons: Convergent nonnegative matrices and iterative methods for consistent linear systems. Numer. Math. 31 (1978), 265–279. | DOI | MR

[13] D. L. Powers: Graph partitioning by eigenvectors. Lin. Alg. Appl. 101 (1988), 121–133. | DOI | MR | Zbl

[14] E. Seneta: Non-negative Matrices and Markov Chains. Second Edition. Springer Verlag, New-York, 1981. | MR

[15] R. S. Varga: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1962. | MR

[16] J. H. Wilkinson: The Algebraic Eigenvalue Problem. Oxford Univ. Press, London, 1965. | MR | Zbl