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