Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

How to make the Perron eigenvector simple

  • Published:
Calcolo Aims and scope Submit manuscript

Abstract

Multiple Perron eigenvectors of non-negative matrices occur in applications, where they often become a source of trouble. A usual way to avoid it and to make the Perron eigenvector simple is a regularization of matrix: an initial non-negative matrix A is replaced by \(A + \varepsilon M\), where M is a strictly positive matrix and \(\varepsilon > 0\) is small. However, this operation is numerically unstable and may lead to a significant increase of the Perron eigenvalue, especially in high dimensions. We define a selected Perron eigenvector of A as the limit of normalized Perron eigenvectors of the regularizations \(A + \varepsilon M\) as \(\varepsilon \rightarrow 0\). It is shown that if the matrix M is rank-one, then the limit eigenvector can be found by an explicit formula and, moreover, is efficiently computed by the power method. The role of the rank-one condition is explained.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anderson, J.: Distance to the nearest stable Metzler matrix. In: IEEE 56th Annual Conference on Decision and Control (CDC), pp. 6567–6572 (2017)

  2. Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences. Acedemic Press, Now York (1979)

    MATH  Google Scholar 

  3. Byers, R.: A bisection method for measuring the distance of a stable to unstable matrices. SIAM J. Sci. Stat. Comput. 9, 875–881 (1988)

    Article  MathSciNet  Google Scholar 

  4. Cicone, A., Serra-Capizzano, S.: Google pageranking problem: the model and the analysis. J. Comput. Appl. Math. 234(11), 3140–3169 (2010)

    Article  MathSciNet  Google Scholar 

  5. Cvetkovic, A., Protasov, V.: The greedy strategy in optimizing the Perron eigenvalue. submitted to Math. Progr. arXiv:1807.05099

  6. Gantmacher, F.R.: The Theory of Matrices. Chelsea, New York (2013)

    Google Scholar 

  7. Guglielmi, N., Manetta, M.: Approximating real stability radii. IMA J. Numer. Anal. 35(3), 1402–1425 (2015)

    Article  MathSciNet  Google Scholar 

  8. Guglielmi, N., Protasov, V.: On the closest stable/unstable nonnegative matrix and related stability radii. SIAM J. Matrix Anal. 39(4), 1642–1669 (2018)

    Article  MathSciNet  Google Scholar 

  9. Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990)

    MATH  Google Scholar 

  10. Kato, T.: Perturbation Theory for Linear Operators, Classics in Mathematics. Springer, Berlin (2013)

    Google Scholar 

  11. Krause, U.: Swarm dynamics and positive dynamical systems. In: Differential and Difference Equations with Applications. Springer Proceedings in Mathematics and Statistics, vol. 47, pp. 69–81 (2013)

    Chapter  Google Scholar 

  12. Nesterov, Y., Nemirovski, A.: Finding the stationary states of Markov chains by iterative methods. Appl. Math. Comput. 255, 58–65 (2015)

    MathSciNet  MATH  Google Scholar 

  13. Nesterov, Y., Protasov, V.Y.: Optimizing the spectral radius. SIAM J. Matrix Anal. Appl. 34(3), 999–1013 (2013)

    Article  MathSciNet  Google Scholar 

  14. Protasov, V.Y.: The spectral simplex method. Math. Prog. 156, 485–511 (2016)

    Article  MathSciNet  Google Scholar 

  15. Serra-Capizzano, S.: Jordan Canonical form of the Google matrix: a potential contribution to the pagerank computation. SIAM J. Matrix Anal. Appl. 27(2), 305–312 (2006)

    Article  MathSciNet  Google Scholar 

  16. Stewart, G.W., Sun, J.G.: Matrix Perturbation Theory. Academic Press, New York (1990)

    MATH  Google Scholar 

  17. Valcher, M.E., Misra, P.: On the stabilizability and consensus of positive homogeneous multi-agent dynamical systems. IEEE Trans. Autom. Control 59, 1936–1941 (2014)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The author is grateful to the anonymous Referees for attentive reading and for many valuable comments and suggestions. The article was prepared within the framework of the HSE University Basic Research Program and funded by the Russian Academic Excellence Project ‘5-100’.

Author information

Authors and Affiliations

  1. University of L’Aquila, L’Aquila, Italy

    Vladimir Yu. Protasov

  2. Faculty of Computer Science of National Research University Higher School of Economics, Moscow, Russia

    Vladimir Yu. Protasov

Authors
  1. Vladimir Yu. Protasov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vladimir Yu. Protasov.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Scientific results of Sections 3 and 4 of this paper were obtained with support of RSF Grant 17-11-01927.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Protasov, V.Y. How to make the Perron eigenvector simple. Calcolo 56, 17 (2019). https://doi.org/10.1007/s10092-019-0314-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10092-019-0314-7

Keywords

Mathematics Subject Classification

Search

Navigation