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

https://hal.telecom-paristech.fr/hal-02286291
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 3:34:43 PM
Last modification on : Saturday, September 14, 2019 - 1:39:06 AM

Identifiers

  • HAL Id : hal-02286291, version 1

Collections

Citation

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

Share

Metrics

Record views

5