Reciprocal Matrices and Ranking Things
An n-by-n and entry-wise positive matrix A = (aij) is called
"reciprocal" if,
for every pair i, j, aijaji = 1. Such a matrix is viewed
as a complete set of independent, pair-wise, ratio comparisons among n items. Typically, the goal is to deduce
a ranking (cardinal or ordinal) of the n items from the reciprocal data. When the data is "consistent":
aij = wi/wj for some positive vector w,
this is clear-cut. Vector w provides the natural choice. However, consistency of the independently made ratio comparisons
is unlikely. Saaty, who suggested a model based upon reciprocal matrices in the 70's, proposed the right Perron eigenvector
of A, as the cardinal ranking vector. However, over time, difficulties with this choice were recognized (by this author and
others). This led to a hiatus in the development of the subject. But, in the last decade or so, there has been a resurgence
of interest, both mathematically and because of applications. A remarkable number of papers have appeared.
This has included the notion of Pareto optimal vectors, known as "efficient"
vectors in the subject, to provide possible consistent approximations to A, and thus cardinal
ranking vectors to deduce from the data. Positive vector w is said to be efficient for A if,
for any other positive vector v
A - (vi/vj) ≤ A - (wi/wj), entry-wise
in absolute value, implies v=w, projectively. Typically, though, there are infinitely
efficient vectors for a given A and they are difficult to find.
In these talks, we will review the background of this area, and present recent ideas that have advanced the subject dramatically.
Given w, there is a directed graph G(A,w) whose strong connectivity
is equivalent to the efficiency of w
for A. So, any candidate vector may be checked for efficiency. This may be used, though not trivially, to generate all
efficient vectors for A. It turns out that every column of A, and any entry-wise, weighted geometric mean of columns of A,
is efficent. Generally, the set E(A) of all efficient vectors for A, is not closed under geometric means and is not so nicely structured.
However for n < 5, it is possible to explicitly give all efficient vectors, which is useful in applications. Several details and proofs
will be given.
There are several ways in which reciprocal matrices have arisen and are of interest to us. First is the classical business/
societal application of ranking projects that may be implemented. Second (and, so far, novel) is classical social choice/voting.
A group preference matrix produced from individual preference orderings of candidates may naturally be converted to a
reciprocal matrix, and the efficient vectors of this matrix correspond to possible voting outcomes. Third, note that at any
point in time, the pair-wise exchange rates among a basket of currencies constitutes a reciprocal matrix, and this matrix need
not be consistent.
My interest in this area has kindly been rekindled by my co-author, Susana Furtado, who is responsible for many of new
ideas in the subject.
The Mysteries of Nonnegative Matrices ..... and a few Answers
Nonnegative Matrices are ubiquitous, yet their spectral structure is a remarkable mystery. The infamous nonnegative inverse eigenvalue problem
(NIEP) and its variants are unlikely to be effectively solved without an unexpected breakthrough elsewhere.
We mention a few parts of the NIEP and some tidbits of solutions.
