Matrices bistochastiques
Bonjour
j'ai une question sur les matrices bistochastiques.
Soit $M$ une matrice bistochastique de taille $(n,n)$.
Soit $2n$ réels vérifiant $x_1 \le \ldots \le x_n$ et $y_1 \le \ldots \le y_n$.
On montre que pour $i\in [\![1,n]\!]$, \[
\sum_{j=i}^n\sum_{k=1}^{n} M_{jk}y_k \le
\sum_{j=i}^ny_j.
\] Ça c'est bon !
Il faut en déduire que \[
\sum_{i=1}^{n}\sum_{j=1}^{n}(y_j-x_i)^2M_{ij} \ge
\sum_{i=1}^n(y_i-x_i)^2.
\] Et là je ne vois pas.
Quand on développe les deux membres de l'inégalité à montrer, cela revient à montrer que \[\sum_{i=1}^n\sum_{j=1}^n x_iy_jM_{i,j} \le \sum_{i=1}^nx_iy_i
\] Pour résumer, il faut donc montrer \[
\forall i \in [\![1,n]\!],\ \sum_{j=i}^n\sum_{k=1}^{n} M_{jk}y_k \le
\sum_{j=i}^ny_j \Longrightarrow \sum_{i=1}^n\sum_{j=1}^n x_iy_j M_{i,j} \le \sum_{i=1}^nx_iy_i
\] ou en renommant les indices : \[
\forall i \in [\![1,n]\!],\ \sum_{j=i}^n\sum_{k=1}^{n} M_{jk}y_k \le
\sum_{j=i}^ny_j \Longrightarrow \sum_{j=1}^n\sum_{k=1}^n x_jy_kM_{j,k} \le \sum_{j=1}^nx_jy_j
\] Merci de me donner une indication si vous avez une idée.
j'ai une question sur les matrices bistochastiques.
Soit $M$ une matrice bistochastique de taille $(n,n)$.
Soit $2n$ réels vérifiant $x_1 \le \ldots \le x_n$ et $y_1 \le \ldots \le y_n$.
On montre que pour $i\in [\![1,n]\!]$, \[
\sum_{j=i}^n\sum_{k=1}^{n} M_{jk}y_k \le
\sum_{j=i}^ny_j.
\] Ça c'est bon !
Il faut en déduire que \[
\sum_{i=1}^{n}\sum_{j=1}^{n}(y_j-x_i)^2M_{ij} \ge
\sum_{i=1}^n(y_i-x_i)^2.
\] Et là je ne vois pas.
Quand on développe les deux membres de l'inégalité à montrer, cela revient à montrer que \[\sum_{i=1}^n\sum_{j=1}^n x_iy_jM_{i,j} \le \sum_{i=1}^nx_iy_i
\] Pour résumer, il faut donc montrer \[
\forall i \in [\![1,n]\!],\ \sum_{j=i}^n\sum_{k=1}^{n} M_{jk}y_k \le
\sum_{j=i}^ny_j \Longrightarrow \sum_{i=1}^n\sum_{j=1}^n x_iy_j M_{i,j} \le \sum_{i=1}^nx_iy_i
\] ou en renommant les indices : \[
\forall i \in [\![1,n]\!],\ \sum_{j=i}^n\sum_{k=1}^{n} M_{jk}y_k \le
\sum_{j=i}^ny_j \Longrightarrow \sum_{j=1}^n\sum_{k=1}^n x_jy_kM_{j,k} \le \sum_{j=1}^nx_jy_j
\] Merci de me donner une indication si vous avez une idée.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
dans la catégorie "idées en l'air"
ça ressemble à une inégalité de Jensen appliquée à la moyenne des matrice bistochastiques à une identité près ?
(la phrase est surtout là pour faire joli... donc rien de concret)
n'y aurait-il pas une erreur à la première inégalité ?
2) Essaye ensuite de faire une récurrence descendante sur p.
peut-être en partant d'une matrice de permutation et en appliquant le théorème de Mashke on parvient au résultat.
de fait la matrice est dans l'envellope convexe des permutations.
attention je ne fais que suggérer... et je ne prétends pas pas que ces idées en l'air là, vont résoudre la question posée.
bonne soirée.
Mon idée était justement d’introduire un paramètre variable en plus, mais en essayant de l’écrire, ça ne marche pas.
(A posteriori, c’était assez logique que ça ne marche pas)
J’ai une autre idée qui cette fois devrait marcher. Comme tu l’as demandé je te donne juste une indication : pars de la matrice M ; crée à partir de M une matrice de taille n^2 bien choisie, encore bistochastique ; applique le résultat précédent de façon judicieuse.
Pour la première inégalité, je pense avoir une preuve mais c’est assez long et plutôt technique. Peux-tu partager avec nous ta preuve ?
La 1ère inégalité est plus générale que ce que tu prouves : tu prouves le cas i = 1 alors qu’il faut i compris entre 1 et n.
1) On commence par montrer que
\[\forall i \in ]\!] 2,n ]\!],\, \sum_{j=i}^n\sum_{k=1}^{i-1} M_{j,k}y_k \le \sum_{j=i}^n \sum_{k=1}^{i-1}M_{k,j}y_j\]
Soit $i \in ]\!] 2,n ]\!]$. Pour tout $k \in [\![ 1,i-1 ]\!]$, on a $y_k \le y_i$. Pour tout $j \in [\![ i,n ]\!]$, par multiplication par $M_{j,k}$ qui est positif :
\[M_{j,k}y_k \le M_{j,k}y_i.\]
Par sommation
\[\sum_{j=i}^n\sum_{k=1}^{i-1} M_{j,k}y_k \le
\sum_{j=i}^n\sum_{k=1}^{i-1}M_{j,k}y_i = \sum_{j=i}^ny_i\sum_{k=1}^{i-1}M_{j,k}.\]
La matrice $M$ est bistochastique donc :
\begin{align*}
\sum_{j=i}^n\sum_{k=1}^{i-1} M_{j,k}y_k \le \sum_{j=i}^ny_i\left(1
- \sum_{k=i}^{n}M_{j,k}\right) = \sum_{j=i}^ny_i -
\sum_{j=i}^n\sum_{k=i}^{n}M_{j,k}y_i.
\end{align*}
Dans la double somme, on échange le rôle des indice $j$ et $k$ puis on intervertit les sommes :
\[\sum_{j=i}^n\sum_{k=1}^{i-1} M_{j,k}y_k \le \sum_{j=i}^ny_i -
\sum_{k=i}^n\sum_{j=i}^{n}M_{k,j}y_i = \sum_{j=i}^ny_i -
\sum_{j=i}^{n}\sum_{k=i}^nM_{k,j}y_i .\]
On a donc en utilisant une nouvelle fois le fait que $M$ est bistochastique :
\[\sum_{j=i}^n\sum_{k=1}^{i-1} M_{j,k}y_k \le \sum_{j=i}^ny_i\left(1 -
\sum_{k=i}^nM_{k,j}\right) = \sum_{j=i}^ny_i
\sum_{k=1}^{i-1}M_{k,j} = \sum_{j=i}^n \sum_{k=1}^{i-1}M_{k,j}y_i.\]
Pour tout $j$ dans $]\!] i,n ]\!]$, $y_i \le y_j$. Pour tout $k$ dans $]\!] 1,i-1 ]\!]$, par multiplication par $M_{k,j}$ qui est positif : $M_{k,j}y_i \le M_{k,j}y_j$. Par sommation :
\[\sum_{j=i}^n\sum_{k=1}^{i-1} M_{j,k}y_k \le \sum_{j=i}^n
\sum_{k=1}^{i-1}M_{k,j}y_i \le \sum_{j=i}^n \sum_{k=1}^{i-1}M_{k,j}y_j.\]
2) On montre maintenant
\[\forall i \in [\![1,n]\!],\,\sum_{j=i}^n\sum_{k=1}^nM_{j,k}y_k \le \sum_{j=i}^ny_j .\]
Soit à $i \in [\![1,n]\!]$. On a
\begin{align*}
\sum_{j=i}^n\sum_{k=1}^nM_{j,k}y_k
& = \sum_{j=i}^n\left(\sum_{k=1}^{i-1}M_{j,k}y_k +
\sum_{k=i}^{n}M_{j,k}y_k\right)\\
& = \sum_{j=i}^n\sum_{k=1}^{i-1}M_{j,k}y_k +
\sum_{j=i}^n\sum_{k=i}^{n}M_{j,k}y_k.
\end{align*}
En utilisant le 1) :
\begin{align*}
\sum_{j=i}^n\sum_{k=1}^nM_{j,k}y_k
& \le \sum_{j=i}^n\sum_{k=1}^{i-1}M_{k,j}y_j +
\sum_{j=i}^n\sum_{k=i}^{n}M_{j,k}y_k\\
& \le \sum_{j=i}^ny_j\sum_{k=1}^{i-1}M_{k,j} +
\sum_{j=i}^n\sum_{k=i}^{n}M_{j,k}y_k\\
& \le \sum_{j=i}^ny_j\left(1 - \sum_{k=i}^{n}M_{k,j}\right) +
\sum_{j=i}^n\sum_{k=i}^{n}M_{j,k}y_k\\
& \le \sum_{j=i}^ny_j -\sum_{j=i}^n\sum_{k=i}^{n}M_{k,j}y_j +
\sum_{j=i}^n\sum_{k=i}^{n}M_{j,k}y_k = \sum_{j=i}^ny_j.
\end{align*}
@zorg : joli aussi
Ma méthode consistait à partir de i=n (l’inégalité est facile à voir) puis à faire une récurrence sur la taille de M, en construisant à partir de M de taille n et bistochastique une matrice M’ de taille (n-1) bistochastique aussi.
Pour la deuxième question, la méthode que j’envisageais ne marche pas. Je vous mets quand même l’idée. On prouve que
la somme des M_ij x_i y_j est inférieure aux n plus grands nombres parmi les x_i y_j.
Je pense (il me reste à l’écrire pour vérifier que ça marche) qu’en adaptant cette idée on peut s’en sortir.
On a d’abord besoin d’un lemme : si M est une matrice qui est sous-bistochastique (ie à coefficients positifs et dont les lignes et colonnes sont de somme inférieure à 1) alors on peut plonger M dans le coin inférieur droit d’une matrice bistochastique de taille 2n.
On suppose les x_i > 0.
Il reste à multiplier les coefficients de M par des x_i / x_j quand i < j : on obtient une matrice sous-bistochastique M’. De plus, la somme cherchée peut alors s’exprimer comme une somme du type de la première question avec M’. On plonge M’ dans une matrice bistochastique de taille 2n.
On prend comme « scalaires » n fois 0 puis les x_i y_i .
Cela me fait penser aux preuves en géométrie où pour démontrer un résultat dans le plan on passe dans l'espace.
je trouve que c'est un problème super difficile, et je suis heureux de voir plusieurs méthodes.