Computing Ratings from Eigenvectors

237. R. P. Brent, Note on computing ratings from eigenvectors, 5 May 2010, 10 pages, arXiv:1005.0762v1.

Paper: pdf (152K).

Abstract

We consider the problem of computing ratings using the results of games played between a set of n players, and show how this problem can be reduced to computing the positive eigenvectors corresponding to the dominant eigenvalues of certain n × n matrices. There is a close connection with the stationary probability distributions of certain Markov chains. In practice, if n is large, then the matrices involved will be sparse, and the power method may be used to solve the eigenvalue problems efficiently. We give an algorithm based on the power method, and also derive the same algorithm by an independent method.

Remarks

This paper is dedicated in memory of my friend and mentor Gene Howard Golub 1932–2007. Gene encouraged me to write up this work, which dates from the 1970s. There are no plans to submit it for publication except on the arXiv.

Go to next publication

Return to Richard Brent's index page