Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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 metadata
Contributor : TelecomParis HAL Connect in order to contact the contributor
Submitted on : Friday, September 13, 2019 - 3:34:43 PM
Last modification on : Monday, January 24, 2022 - 8:26:29 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