Skip to Main content Skip to Navigation
Journal articles

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 : Friday, July 31, 2020 - 11:28:04 AM


  • 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