EIGENSPACES OF TOURNAMENT MATRICES

James Burk

In this dissertation we investigate the eigenspaces of tournament matrices. These matrices (and their generalizations) appear in a variety of combinatorial applications (e.g., in biology, sociology, statistics, and networks); however, their most common usage comes from modeling a round-robin tournament. The results from these competitions can be encoded by using a <italic>n<\\italic>x<italic>n<\\italic> matrix <italic>A=a ij <\\sub><\\italic>. If player <italic>i<\\italic> defeats player <italic>j<\\italic>, then <italic>a ij<\\sub>=1<\\italic> and in turn <italic>aji<\\sub>=0<\\italic>; by convention, all diagonal entries of <italic>A<\\italic> are equal to 0. Consequently, if <italic>Jn<\\sub><\\italic> and <italic>In<\\sub><\\italic> respectively denote the <italic>n<\\italic>x<italic>n<\\italic> all-ones matrix and the identity matrix, then a tournament matrix <italic>A<\\italic> of size <italic>n<\\italic> is a <italic>(0,1)<\\italic>-matrix that satisfies <italic>A+A<super>t<\\super>=Jn<\\sub>- In<\\sub><\\italic>. The theory and questions associated with tournament matrices focus on ranking the players, as well as questions concerning their spectrum. This question of ranking players is closely related to problems for stochastic matrices as they appear in search engine models (cf. ranking based on eigenvectors). The ranking of players in a tournament can be determined by analyzing the corresponding normalized Perron vector for the corresponding matrix; consequently, several eigenvalue and eigenvector questions arise naturally for this class of matrices and are worth investigating. In this text we shall investigate, in detail, how this question of ranking pertains to the players in a Brualdi-Li tournament; and in turn, two different ranking methods will be given. Other questions of particular interest focus on investigating the location of the eigenvalues. A long standing conjecture, which has recently been confirmed, known as the Brualdi-Li conjecture, addresses the question of maximizing the spectral radius for even sized tournaments. To replace this conjecture, a new conjecture is formulated that we coin as the Brualdi-Li tally conjecture. In addition, it has been conjectured that no tournament matrices can have a nonzero purely imaginary eigenvalue. We investigate this question and provide a partial answer to it.

EIGENSPACES OF TOURNAMENT MATRICES

Files and links (1)

Abstract

Metrics

Details