Connectez-vous pour consulter le corrigé.
Notations et objectifs :
Soit \(E\) un espace vectoriel réel et \(A\) une partie non vide de \(E\).
Soit \(a\) un élément de \(A\), on dit que \(a\) est un point extrémal de \(A\) si : \[\forall (x,y)\in A^2,\ \left( \frac{x+y}{2} =a\right) \Rightarrow (x=y=a).\]
Les parties \(0\) et \(I\) permettent de se familiariser avec la notion de point extrémal.
La partie II prouve que les points d’une partie donnant le diamètre de cette partie sont extrémaux.
Enfin la partie III étudie des propriétés des matrices de permutation, en particulier de l’isobarycentre de ces matrices. On obtient finalement une preuve du fait que les points extrémaux de l’ensemble des matrices bistochastiques sont les matrices de permutation.
On prend ici \(E=\mathbb{R}\) et \(A=\left]0,1\right[\), montrer qu’aucun point de \(A\) n’est extrémal.
On considère maintenant \(E=\mathbb{R}\) et \(A=[0,1]\), montrer que les points extrémaux de \(A\) sont \(0\) et \(1\).
Dans cette partie, on note \(A_2\) l’ensemble \[\left\lbrace M_\alpha=\begin{pmatrix} \alpha & 1-\alpha \\ 1-\alpha & \alpha \end{pmatrix}\in\mathcal{M}_2(\mathbb{R}),\ \alpha \in [0,1] \right\rbrace\]
et \(J\) la matrice \(\begin{pmatrix} 0& 1\\1 & 0 \end{pmatrix}\). Par ailleurs, \(I_2\) désigne la matrice identité de \(\mathcal{M}_2(\mathbb{R})\).
Description et propriétés des éléments de \(A_2\).
Vérifier que : \(A_2= \{ \alpha I_2 + \left( 1-\alpha \right) J,\, \alpha \in [0,1] \}\).
Soient \((\alpha,\beta)\) de \([0,1]^2\) et \((M_\alpha,M_\beta)\) dans \(A_2^2\), montrer que : \[\dfrac{1}{2}\left( M_\alpha + M_\beta \right) \in A_2.\]
Déterminer les éléments \(M_\alpha\) de \(A_2\) qui sont inversibles dans \(\mathcal{M}_2(\mathbb{R})\). Pour ceux-ci, donner l’expression de \((M_\alpha)^{-1}\) et préciser pour quelles valeurs de \(\alpha\) de \([0,1]\) \((M_\alpha)^{-1}\) appartient à \(A_2\).
Points extrémaux de \(A_2\).
Montrer que \(I_2\) et \(J\) sont des points extrémaux de \(A_2\).
Soit \(\alpha\) dans \(\left] 0,\dfrac{1}{2} \right]\), vérifier que : \(M_\alpha = \dfrac{1}{2}\left( M_{2\alpha} + J \right)\) ; en déduire que \(M_\alpha\) n’est pas extrémal.
Par une méthode similaire, montrer que si \(\alpha\) est dans \(\left[ \dfrac{1}{2},1\right[\), \(M_{\alpha}\) n’est pas extrémal.
Réduction simultanée des matrices de \(A_2\).
Déterminer les valeurs propres et espaces propres de la matrice \(J\).
Montrer qu’il existe une matrice inversible \(P\) dans \(GL_2(\mathbb{R})\) telle que, pour tout \(\alpha\) de \([0,1]\), \(P^{-1}M_\alpha P\) est une matrice diagonale \(D_\alpha\), on précisera \(P\) et \(D_\alpha\).
On note \(u_\alpha\) l’endomorphisme de \(\mathbb{R}^2\) représenté par la matrice \(M_\alpha\) dans la base canonique de \(\mathbb{R}^2\). Déterminer les réels \(\alpha\) de \(]0,1]\) tels que \(u_\alpha\) soit un projecteur de \(\mathbb{R}^2\). On précisera l’image et le noyau du ou des projecteurs ainsi trouvés.
Dans cette partie, on suppose que \(E\) est un espace euclidien de dimension finie non nulle, muni d’un produit scalaire noté \(\left \langle \cdot \,\vert \, \cdot \right \rangle\). On note \(\left\| \cdot \right\|\) la norme euclidienne associée.
On considère \(A\) une partie non vide de \(E\) telle qu’il existe un réel \(R\) positif tel que, pour tout vecteur \(v\) de \(A\), on ait : \(\left\| v \right\| \leqslant R\).
Montrer que l’ensemble \(\{ \left\| v-w \right\|\, ; \; (v,w)\in A^2 \}\) est une partie non vide et majorée de \(\mathbb{R}\).
Cet ensemble admet donc une borne supérieure.
On note alors \(\delta(A) = \sup \{ \left\| v-w \right\| \, ; \; (v,w)\in A^2\}\), \(\delta(A)\) est appelé diamètre de \(A\).
Dans la suite de cette partie, on suppose que la partie \(A\) vérifie la propriété \((H)\) suivante : \[(H) \text{ : Il existe } (a,b) \text{ dans } A^2 \text{ tel que } \delta(A) = \left\| b-a \right\|.\]
On se propose de démontrer que \(a\) est un point extrémal de \(A\).
On considère donc \((c,d)\) dans \(A^2\) tel que : \(\dfrac{c+d}{2}=a\).
Vérifier que : \(\left\| a-b \right\| \leqslant \dfrac{1}{2} \left( \left\| c-b \right\| + \left\| d-b \right\| \right) \leqslant \left\| a-b \right\|\).
En déduire que : \(\left\| c-b \right\|=\left\| d-b \right\| = \delta(A)\).
Vérifier que : \(\left\| c-b \right\|^2 = \left\| c-a \right\|^2+ \left\| a-b \right\|^2 + 2\left \langle c-a \,\vert \, a-b \right \rangle\).
En déduire que : \(\left\| c-a \right\|^2 = -2 \left \langle c-a \,\vert \, a-b \right \rangle\).
Montrer de même que : \(\left\| d-a \right\|^2 = - 2 \left \langle d-a \,\vert \, a-b \right \rangle\).
Montrer alors que \(c-d\) et \(a-b\) sont orthogonaux.
En déduire que \(a,c\) et \(d\) sont égaux et conclure.
Dans toute la suite du problème, \(n\) est un entier supérieur ou égal à \(2\) et on note \(E=\mathcal{M}_n(\mathbb{R})\). On note aussi : \[\begin{gathered} A_n=\left \lbrace M=(m_{i,j})_{(i,j)\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^2} \in\mathcal{M}_n(\mathbb{R}) \ / \ \forall (i,j)\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^2,\ m_{i,j}\geqslant 0,\right. \\ \left. \forall i\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right],\ \sum_{j=1}^n m_{i,j}=1 \quad\text{et}\quad\forall j\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right],\ \sum_{i=1}^n m_{i,j}=1 \right\rbrace \end{gathered}\]
l’ensemble des matrices bistochastiques de \(\mathcal{M}_n(\mathbb{R})\) et : \[\begin{gathered} F_n=\left \lbrace M=(m_{i,j})_{(i,j)\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^2} \in\mathcal{M}_n(\mathbb{R}) \ / \ \forall i\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right],\ \sum_{j=1}^n m_{i,j}=0 \right. \\ \left. \quad\text{et}\quad\forall j\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right],\ \sum_{i=1}^n m_{i,j}=0 \right\rbrace \end{gathered}\]
On munit \(\mathbb{R}^n\) de sa structure euclidienne usuelle.
Enfin, \(B_0=(e_1,\dots,e_n)\) désigne la base canonique de \(\mathbb{R}^n\).
Premières propriétés de \(A_n\).
Soit \((M,M')\) dans \(A_n^2\), montrer que : \(\dfrac{1}{2}\left( M+M' \right) \in A_n\), et que : \({}^t\!M\in A_n\) (\({}^t\!M\) désigne la matrice transposée de \(M\)). On note \(X_0=\begin{pmatrix} 1\\ \vdots \\ 1 \end{pmatrix} \in \mathcal{M}_{n,1}(\mathbb{R})\) (toutes les composantes de \(X_0\) sont égales à \(1\)).
Soit \(M\) de \(A_n\), montrer que : \(MX_0=X_0\).
Réciproquement, soit \(M=(m_{i,j})_{(i,j)\in \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^2}\) de \(\mathcal{M}_n(\mathbb{R})\) telle que pour tout \((i,j)\) de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^2\) \(m_{i,j} \geqslant 0\), \(MX_0=X_0\) et \(\left( {}^t\!M\right) X_0=X_0\), montrer que : \(M\in A_n\).
Soit \((M,M')\) de \(A_n^2\), montrer que : \(MM'\in A_n\).
Endomorphismes et matrices de permutation.
On note \(S_n\) l’ensemble des permutations de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\), c’est-à-dire l’ensemble des bijections de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) sur lui-même. Le cardinal de \(S_n\) est \(n!\).
Soit \(\sigma\) de \(S_n\), on note \(f_\sigma\) l’endomorphisme de \(\mathbb{R}^n\) tel que : pour tout \(j\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\), \(f_\sigma(e_j)=e_{\sigma(j)}\).
On note \(M_\sigma\) la matrice de \(f_\sigma\) dans la base \(B_0\), on dit que \(M_\sigma\) est la matrice de permutation associée à \(\sigma\).
Si \(\sigma\) est l’identité de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) (pour tout \(i\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\), \(\sigma(i)=i\)), que sont \(f_\sigma\) et \(M_\sigma\) ?
Si \(\sigma\) est une permutation de \(S_n\), montrer que \(M_\sigma\in A_n\). Déterminer \(\tau\) de \(S_n\) telle que \({}^t\!M_\sigma=M_\tau\).
Soit \((\sigma,\sigma')\) de \((S_n)^2\), montrer que \(f_\sigma \circ f_{\sigma'} = f_{\sigma\circ \sigma'}\) ; en déduire que \(M_\sigma\) est inversible et déterminer \((M_\sigma)^{-1}\).
Justifier que les matrices \(M_\sigma\) sont des matrices orthogonales.
Justifier que les matrices \(M_\sigma\) sont exactement les matrices présentant sur chaque ligne et chaque colonne une fois la valeur \(1\) et \(n-1\) fois la valeur \(0\).
Soit \(\sigma\) de \(S_n\), montrer que \(M_\sigma\) est un point extrémal de \(A_n\).
Étude d’un projecteur : on note \(p=\dfrac{1}{n!}\displaystyle\sum_{\sigma\in S_n} f_\sigma\) et \(P=\dfrac{1}{n!}\displaystyle\sum_{\sigma\in S_n} M_\sigma\).
Soit \(\tau\) fixé dans \(S_n\), montrer que l’application \(\phi_\tau:\sigma\mapsto \tau \circ \sigma\) est une bijection de \(S_n\) dans lui-même. Montrer alors que : \(f_\tau \circ p = p\).
En déduire que \(p\) est un projecteur de \(\mathbb{R}^n\).
Montrer que : \(\mathrm{Im}(p) = \{ x\in\mathbb{R}^n \ / \ \forall \sigma \in S_n,\ f_\sigma(x)=x \}\).
Montrer alors que : \(\mathrm{Im}(p) = \mathrm{Vect}(x_0)\) où \(x_0=\displaystyle\sum_{i=1}^n e_i\).
Calculer \({}^t\!P\) ; en déduire que \(p\) est un projecteur orthogonal et déterminer \(P\).
Vérifier que \(P\in A_n\).
Diamètre de \(A_n\).
Si \(M=(m_{i,j})_{(i,j)\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^2}\) et \(N=(n_{i,j})_{(i,j)\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^2}\) sont deux matrices de \(E\), calculer \(\mathrm{Tr}({}^t\!MN)\).
Montrer que l’application \((M,N)\mapsto \mathrm{Tr}({}^t\!MN)\) est un produit scalaire sur \(E\).
Si \((M,N)\) sont dans \(E\), on note \(\left \langle M \,\vert \, N \right \rangle = \mathrm{Tr}({}^t\!MN)\) et \(\left\| M \right\|_2=\sqrt{\mathrm{Tr}({}^t\!MM)}\).
Soit \(\sigma\) de \(S_n\), calculer \(\left\| M_\sigma \right\|_2\).
Dans cette question seulement, on suppose que \(n=2\). Soit \((\alpha,\beta)\) dans \([0,1]^2\) et \((M_\alpha,M_\beta)\) de \(A_2^2\), calculer \(\left\| M_\alpha-M_\beta \right\|_2\). Montrer alors que \(\delta(A_2)=2\).
On revient au cas général : \(n\geqslant 2\). Soit \(M\) de \(A_n\), montrer que \(\left\| M \right\|_2^2 \leqslant n\).
Montrer alors que, pour tout \((M,N)\) de \(A_n^2\), \(\left\| M-N \right\|_2 \leqslant \sqrt{2n}\).
Soit \(\sigma\) dans \(S_n\), construire \(\tau\) dans \(S_n\) tel que \(\left \langle M_\sigma \,\vert \, M_\tau \right \rangle=0\).
En déduire le diamètre de \(A_n\) et retrouver que les matrices de permutation sont des points extrémaux de \(A_n\).
Structure et dimension de \(F_n\).
Vérifier que \(F_n\) est un sous-espace vectoriel de \(E\).
Soit \(\Phi:F_n \to \mathcal{M}_{n-1}(\mathbb{R})\) qui, à toute matrice \(M=(m_{i,j})_{(i,j)\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^2}\) de \(F_n\), associe la matrice \(\Phi(M)=(m_{i,j})_{(i,j)\in\left[\kern-0.15em\left[ {1,n-1} \right]\kern-0.15em\right]^2}\). Montrer que \(\Phi\) est un isomorphisme de \(F_n\) dans \(\mathcal{M}_{n-1}(\mathbb{R})\). En déduire la dimension de \(F_n\).
On désire montrer que les matrices de permutation sont les seuls points extrémaux de \(A_n\).
On raisonne par récurrence sur \(n\geqslant 2\), on note \((P_n)\) la proposition :
\((P_n)\) Si \(M\) est un point extrémal de \(A_n\), \(M\) est une matrice de permutation.
Vérifier, à l’aide de la partie I, que la proposition \((P_2)\) est réalisée.
On considère \(n\) un entier naturel supérieur ou égal à \(3\) tel que \((P_{n-1})\) soit réalisée et on se donne \(M=(m_{i,j})_{(i,j)\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^2} \in E\) un point extrémal de \(A_n\).
On suppose d’abord que la matrice \(M\) a au moins \(2n\) coefficients non nuls : il existe \(2n\) couples \((i_k,j_k)_{k\in\left[\kern-0.15em\left[ {1,2n} \right]\kern-0.15em\right]}\) deux à deux distincts tels que \(m_{i_k,j_k}\) est non nul.
On pose alors \(H=\mathrm{Vect}(E_{i_k,j_k}\, ;\; k\in\left[\kern-0.15em\left[ {1,2n} \right]\kern-0.15em\right])\) où les matrices \((E_{i,j})_{(i,j)\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^2}\) sont les matrices élémentaires de \(\mathcal{M}_n(\mathbb{R})\), c’est-à-dire : \(E_{i,j}\) est la matrice de \(\mathcal{M}_n(\mathbb{R})\) ayant \(n^2-1\) coefficients nuls et un seul valant \(1\), placé en position \((i,j)\).
Montrer que \(H\cap F_n\neq \{0\}\).
On prend \(N\) dans \(H\cap F_n\) avec \(N\neq 0\) et, pour \(t\) réel, on note \(Q_t = M+tN\). Montrer qu’il existe \(\varepsilon>0\) tel que, pour tout \(t\) de \(]-\varepsilon,\varepsilon[\), \(Q_t\) est dans \(A_n\).
En considérant \(t\) de \(]-\varepsilon,\varepsilon[\) et les matrices \(Q_t\) et \(Q_{-t}\), montrer que l’on aboutit à une contradiction.
On a donc prouvé que la matrice \(M\) a au plus \(2n-1\) coefficients non nuls.
Montrer alors qu’il existe une colonne de \(M\) n’ayant qu’un terme non nul et que ce terme vaut \(1\).
On note \(s\) l’indice d’une telle colonne et \(r\) l’indice de la ligne telle que \({m_{r,s}=1}\).
Justifier que la ligne \(r\) de \(M\) a tous ses coefficients nuls sauf \(m_{r,s}\).
On considère alors la matrice \(M'\) obtenue à partir de \(M\) en lui enlevant la colonne d’indice \(s\) et la ligne d’indice \(r\), montrer que \(M'\) est dans \(A_{n-1}\) et que \(M'\) est un point extrémal de \(A_{n-1}\).
En déduire que \(M'\) est une matrice de permutation de \(A_{n-1}\) et que \(M\) est une matrice de permutation de \(A_n\).
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.
