# A note on certain ergodicity coeflcients

Special Matrices (2015)

- Volume: 3, Issue: 1, page 175-185, electronic only
- ISSN: 2300-7451

## Access Full Article

top## Abstract

top## How to cite

topFrancesco Tudisco. "A note on certain ergodicity coeflcients." Special Matrices 3.1 (2015): 175-185, electronic only. <http://eudml.org/doc/271790>.

@article{FrancescoTudisco2015,

abstract = {We investigate two ergodicity coefficients ɸ ∥∥ and τn−1, originally introduced to bound the subdominant eigenvalues of nonnegative matrices. The former has been generalized to complex matrices in recent years and several properties for such generalized version have been shown so far.We provide a further result concerning the limit of its powers. Then we propose a generalization of the second coefficient τ n−1 and we show that, under mild conditions, it can be used to recast the eigenvector problem Ax = x as a particular M-matrix linear system, whose coefficient matrix can be defined in terms of the entries of A. Such property turns out to generalize the two known equivalent formulations of the Pagerank centrality of a graph.},

author = {Francesco Tudisco},

journal = {Special Matrices},

keywords = {Ergodicity coefficients; Eigenvalues; Nonnegative matrices; Linear systems; Pagerank; ergodicity coefficients; eigenvalues; nonnegative matrices; linear systems; -matrix linear system},

language = {eng},

number = {1},

pages = {175-185, electronic only},

title = {A note on certain ergodicity coeflcients},

url = {http://eudml.org/doc/271790},

volume = {3},

year = {2015},

}

TY - JOUR

AU - Francesco Tudisco

TI - A note on certain ergodicity coeflcients

JO - Special Matrices

PY - 2015

VL - 3

IS - 1

SP - 175

EP - 185, electronic only

AB - We investigate two ergodicity coefficients ɸ ∥∥ and τn−1, originally introduced to bound the subdominant eigenvalues of nonnegative matrices. The former has been generalized to complex matrices in recent years and several properties for such generalized version have been shown so far.We provide a further result concerning the limit of its powers. Then we propose a generalization of the second coefficient τ n−1 and we show that, under mild conditions, it can be used to recast the eigenvector problem Ax = x as a particular M-matrix linear system, whose coefficient matrix can be defined in terms of the entries of A. Such property turns out to generalize the two known equivalent formulations of the Pagerank centrality of a graph.

LA - eng

KW - Ergodicity coefficients; Eigenvalues; Nonnegative matrices; Linear systems; Pagerank; ergodicity coefficients; eigenvalues; nonnegative matrices; linear systems; -matrix linear system

UR - http://eudml.org/doc/271790

ER -

## References

top- [1] C. Brezinski and M. Redivo-Zaglia. Extrapolation and minimization procedures for Pagerank vector. Dagstuhl Seminar Proceedings 07071: Web Information Retrieval and Linear Algebra Algorithms, 2007 Zbl1182.65007
- [2] C. Brezinski, M. Redivo-Zaglia, and S. Serra-Capizzano. Extrapolation methods for PageRank computations. A C. R. Acad. Sci. Paris, Ser. I 340, pages 393–397, 2005. Zbl1066.65040
- [3] S. Brin and L. Page. The anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th Int. Conf. World Wide Web, Brisbane, Aust., pages 107–117, 1998.
- [4] G. M. Del Corso, A. Gulli, and F. Romani. Fast PageRank computation via a sparse linear System. Internet Math., 2:259–281, 2005. Zbl1109.68330
- [5] D. Gleich, L. Zhukov, and P. Berkhin. Fast parallel PageRank: A linear system Approach. Yahoo! Res. techincal Rep., 2004.
- [6] G. H. Golub and C. Greif. An Arnoldi-type algorithm for computing PageRank. BIT, 46:759–771, 2006. [Crossref] Zbl1105.65034
- [7] D. Hartfiel. Coeflcients of ergodicity for imprimitive matrices. Commun. Statist. - Stochastic Models, 15:81–88, 1999. Zbl0924.15021
- [8] D. Hartfiel and U. G. Rothblum. Convergence of inhomogeneus products of matrices and coeflcients of ergodicity. Linear Algebra Appl., 277:1–9, 1998. Zbl0934.15033
- [9] T. Haveliwala and S. Kamvar. The Second Eigenvalue of the Google Matrix. Stanford Univ. Tech. Rep., 2003. Zbl1091.68044
- [10] M. Haviv, Y. Ritov, and U. G. Rothblum. Iterative Methods for Approximating the Subdominant Modulus of an Eigenvalue of a Nonnegative Matrix. Linear Algebra Appl., 87:61–75, 1987. [Crossref] Zbl0627.65035
- [11] I. C. F. Ipsen and S. Kirkland. Convergence analysis of a Pagerank updating algorithm by Langville and Meyer. SIAM J.Matrix Anal. Appl., 27:952–967, 2006. [Crossref] Zbl1108.65030
- [12] I. C. F. Ipsen and T. M. Selee. Pagerank computation, with special attention to dangling nodes. SIAM J. Matrix Anal. Appl., 29:1281–1296, 2007. [Crossref][WoS] Zbl1156.65038
- [13] I. C. F. Ipsen and T. M. Selee. Ergodicity coeflcients defined by vector norms. SIAM J. Matrix Anal. Appl., 32(1):153–200, 2011. [Crossref] Zbl1223.15043
- [14] C. R. Johnson. Row stochastic matrices similar to doubly stochastic matrices. Linear Multilinear Algebra, 10:113–130, 1981. [WoS][Crossref] Zbl0455.15019
- [15] S. Kamvar, T. Haveliwala, C. Manning, and G. Golub. Extrapolation methods for accelerating Pagerank computations. ACM 1-58113-680-3/03/0005, 2003.
- [16] A. N. Langville and C. D. Meyer. Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 41 William Street, Princeton NewYersey, 08540, 2006. Zbl1104.68042
- [17] A Rhodius. On the maximum of ergodicity coeflcients, the Dobrushin ergodicity coeflcient, and products of stochastic matrices. Linear Algebra Appl., 253:141–154, 1997. Zbl0871.15021
- [18] U. G. Rothblumand C. P. Tan. Upper Bounds on theMaximumModulus of Subdominant Eigenvalues of NonnegativeMatrices. Linear Algebra Appl., 66:45–86, 1985. [Crossref]
- [19] E. Seneta. On the historical development of the theory of finite inhomogeneus Markov chains. Proc. Cambridge Philos. Soc,, 74:507–513, 1973. Zbl0271.60074
- [20] E. Seneta. Coeflcients of ergodicity: Structure and applications. Adv. in Appl. Probab., 11:576–590, 1979. [Crossref] Zbl0406.60060
- [21] E. Seneta. Explicit forms for ergodicity coeflcients and spectrum localization. Linear Algebra Appl., 60:187–197, 1984. [Crossref] Zbl0594.15007
- [22] E. Seneta. Markov and the creation of Markov chains. Markov Anniversary Meeting. 2006.
- [23] E. Seneta. Non-Negative Matrices and Markov Chains. Springer-Verlag, revised edition, 2006. [WoS] Zbl1099.60004
- [24] S. Serra-Capizzano. Jordan canonical form of the Googlematrix: a potential contribution to the Pagerank computation. SIAM J. Matrix Anal. Appl., 27(2):305–312, 2005. [Crossref] Zbl1103.65051
- [25] F. Tudisco, V. Cardinali, and C. Di Fiore. On complex power nonnegative matrices. Linear Algebra Appl., 471:449–468, 2015. Zbl1310.15065
- [26] F. Tudisco and C. Di Fiore. A preconditioning approach to the pagerank computation problem. Linear Algebra Appl., 435(9):2222–2246, 2011. [WoS] Zbl1222.65035