I have a list of $n$ items, where each item gives a score to every other item, so I get a $n\times n$ square matrix $M$ of scores. Each score is a natural number. Items also score themselves. Example for $n=4$:
$$ \begin{array}{c|lcr} scores & A & B & C & D \\ \hline A & 3 & 3 & 9 & 11 \\ B & 7 & 1 & 12 & 5 \\ C & 11 & 9 & 8 & 7\\ D & 5 & 12 & 8 & 3 \end{array} $$
Each row $i$ represents the scores that item $i$ give to everyone else, and each column $j$ represents the scores that item $j$ got from everyone else. I'm looking for a way to build a preorder of the $n$ items in a way that is independent on the original order, it relies only on the matrix, and maximices the number of "equivalence classes".
Once items are sorted, each item will be "relabelled" by using as new label the index of its position in the sorted list. If two items are equivalent/equal to each other under the new criteria, both will get a same new label. I want to maximice the number of equivalence classes (be as close as possible to a total order) so that I have as many non-repeated labels as possible.
Using the example above, a method could be to sort the numbers of each column and then lexicographically sort them to get an initial ordering $B < A = D < C$ (since $A=D$ at this point, they are in the same "equivalence class" so far).
To break the equality $A = D$, both items represented by the sorted vector $(3, 5, 7, 11)$, we can exploit the fact that $5$ is the first score where the item, $B$, that gave that score to $D$, is less (under the current sorting) than the item, $D$, that gave that score to $A$. In other words, $M(B, D) = 5$ and $M(D, A) = 5$. Since $B < D$ in the initial ordering, the relationship is spread to $D$ and $A$ so we establish that $D < A$, and the items are now fully sorted as $B < D < A < C$. The lowest score $3$, doesn't help here because $M(A, D) = M(D, A) = 3$. The origins of such score for both items comes from the same "equivalence class". The next score, $5$, comes from different "equivalence classes" that can help break the equality.
That ad-hoc method is just an example to show that I want to exploit any single difference between rows and columns so that I can be as closer to a total order as allowed by the contents of the matrix.
Is there any algorithm related to the problem above?
