Characterization of the majority matrices of profiles of equivalence relations

Olivier Hudry 1, 2
Abstract :

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.

Document type :
Journal articles
Complete list of metadatas
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 3:34:43 PM
Last modification on : Thursday, October 17, 2019 - 12:37:00 PM


  • HAL Id : hal-02286291, version 1



Olivier Hudry. Characterization of the majority matrices of profiles of equivalence relations. Mathematics and Social Sciences, 2015. ⟨hal-02286291⟩



Record views