Suprenante (?) égalité de multiset
Soit $M$ une matrice carrée de taille $n$ à valeurs dans $\{0,1\}$.
Que des 1 sur et en dessous de la diagonale
À droite de la diagonale il existe pour chaque ligne $i$, un entier $j_i$ tel que de $i$ à $j_i$ on a que des 0 et de$ j_i $ à $n$ on a que des 1, et aussi, détail sans lequel ça ne marche plus $i \mapsto j_i$ est croissante.
Alors $(1,1,1,\ldots,1).M$ et $(1,1,\ldots,1)M^t$ sont égales à permutation près.
J'ai crû que c'était faux, ou trivial, mais à part une preuve par récurrence (pas très compliquée), je n'ai pas d'argument simple et "parlant"
Y en a-t-il ? Si quelqu'un voit...
Que des 1 sur et en dessous de la diagonale
À droite de la diagonale il existe pour chaque ligne $i$, un entier $j_i$ tel que de $i$ à $j_i$ on a que des 0 et de$ j_i $ à $n$ on a que des 1, et aussi, détail sans lequel ça ne marche plus $i \mapsto j_i$ est croissante.
Alors $(1,1,1,\ldots,1).M$ et $(1,1,\ldots,1)M^t$ sont égales à permutation près.
J'ai crû que c'était faux, ou trivial, mais à part une preuve par récurrence (pas très compliquée), je n'ai pas d'argument simple et "parlant"
Y en a-t-il ? Si quelqu'un voit...
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Soit $g$ la fonction ("transposée de $f$")définie de $\{0, \dots, n\}$ dans $\{0,\dots,n\}$ par $g(i)=\max \{j \in E| f(j) \geq i\}$.
Alors, pour tout $k\in E$, l'ensemble $F_k$ des points $(i,j)\in \{1, \dots, n\} \times E$ appartenant au graphe de $f$ tel que $i+j=k$, a le même cardinal que l'ensemble $G_k$ des point $(i,j) \in \{1, \dots, n\} \times E$ appartenant au graphe de $g$ tel que $i+j=k$.
On place le curseur dans la colonne $i$, juste au dessus de la première ligne (en dehors de la matrice donc). On ne tient pas compte des $1$ sur et en dessous de la diagonale, et on descend (toujours dans la colonne $i$) jusqu'à la case la plus basse qui contienne un $1$. Si la colonne ne contient pas de $1$, on ne déplace pas le curseur. Ensuite, on se déplace en diagonale vers la droite et vers le bas, jusqu'à la première case qui contient un $1$ (ou bien si il n'y a pas de $1$, jusqu'à ce que l'on "sorte de la matrice" et que l'on se trouve ainsi juste à droite de la dernière colonne). La ligne, où se trouve le curseur, est alors la ligne $s(i)$.
En attendant je post au prochain post des tentatives de géneralisations et de renforcement de ce résultat (assez amusant non?)
2) On pourrait essayer d'obtenir une condition nécessaure et suffisante d'égalité des scores ligne/colonne, ou renforcer les hypothèses pour que sous les hypothèses renforcées (par exemple connexité des deux blocs, ou encore les 1 du bloc du haut (resp. 0 du bloc du bas) touchent les bords et sont tous consécutifs) la condition ici, suffusante d'égalité, (avoir des tableaux de Young*) soit aussi nécessaire
3)Je pense qu'il y a un lien entre les tronçons de 0 consécutifs pour chaque colonnes/ligne et la ressemblance du score ligne avec le score colonne
4)* Je parle de tableau de Young avec "rien dans les cases, enfin des cases constantes, mais on peut peut-être aussi voir ce qui se passe quand on met autre chose que des 1 ou 0... et pourquoi pas des nombres négatifs...
Pas la peine de lire 5) si vous n'êtes pas intéressés par le post suivant, ou si vous ne l'avez pas lu (tournois tocar-Handicapés) : [mettre le lien d'un pc]
5) car même si 4) ne m'intéresse pas encore trop, la façon de lier le problême au tournois que j'ai qualifiés de TH dans un autre post, en particulier le lier au parenthésage d'un scoring (voir le lien que je mettrai plus tard) risque de rendre 4) utile, car faire rentrer les parenthèses dans tout le damier de façon à ce qu'il y ait décroissance et non interference des tableaux de Young ne peut se faire qu'en ayant des parenthèses ouvertes puis fermées à caser dans le même coté du damier. C'est sans doute du chinois pour le lecteur...mais pour donner un exemple, si le score d'un tournois ne croit jamais de plus d'une unité, le parenthesage associé est une suite de bloc décroissant au sens large et en glissant les blocs (les $s_i-i$) suivant les tableau de Young (les ouverts= positifs en haut et les fermés=négatifs en bas) on obtient une permutation des scores qui à mon avis doit avoir un gros rapport avec la façon d'indexer le tournois TH qu'on cherche, uniquement determiné, quand il existe, par la permutation particulière du score, "scoring") De toute façon le problème est résolu pour ces scores croissant d'au plus 1, mais la généralisation est peut être amusante à tenter, le problème c'est que pour obtenir une union de parenthesages décroissants associés à une permuration d'un score, on risque de se retrouver soit avec des parenthésages négatifs doit des tableaux de Young qui s'interfèrent, d'oû l'interêt pour moi de 4)