Characterization of the majority matrices of profiles of equivalence relations
Résumé
In the field of classification, Régnier's problem consists in summarizing a collection (called a profile) P of p equivalence relations defined on a same finite set X by an equivalence relation E* at minimum remoteness from P. The considered remoteness is based on the symmetric difference distance and measures the total number of disagreements between E* and the equivalence relations of P; E* is then called a median equivalence relation of P. It is usual to summarize P by its so-called majority matrix. The majority matrix of P is a (n, n)-matrix, where n denotes the cardinality of X, in which all the entries are integers between -p and p and have the same parity as p, and such that all the diagonal entries are equal to p. We study the converse question: which matrices may be the majority matrix of a profile of equivalence relations? We show that it is always possible to construct a profile of equivalence relations from any matrix A which is symmetric, and even or odd, when the diagonal entries of A are equal and are large enough with respect to the non-diagonal entries of A.