Category Archives: Exercice du jour

Matrices bistochastiques, épisode 7

Pour les notations et les résultats précédents : Ep1, Ep2, Ep3, Ep4, Ep5, Ep6.
Écrire une fonction Python traverse d’argument une matrice carrée {A=(a_{i,j})} et renvoyant la première permutation {\sigma} (au sens lexicographique) telle que les {a_{\sigma(j),j}} soient non nuls.
Dire que {\sigma} existe, c’est dire que {A} est traversable.
Si ce n’est pas le cas, traverse renverra la liste {[-1,-1,\ldots,-1]} de longueur {n}.

Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 6

Pour les notations et les résultats précédents : Ep1, Ep2, Ep3, Ep4, Ep5.
Soit {A} une matrice positive magique de somme {\mu>0}.
On sait que {A=\displaystyle\sum_{k=1}^{m}\alpha_{k}P_{k}}, (avec {\alpha_k>0}, {\displaystyle\sum_{k=1}^{m}\alpha_k=\mu}, les {P_k} matrices de permutations).
On va montrer que {m} peut être rendu inférieur ou égal à {(n\!-\!1)^2\!+\!1}.

Pour cela, on suppose {m>(n\!-\!1)^{2}\!+\!1}: l’objectif est de réduire le nombre de matrices {P_{k}} (tout en gardant les propriétés: les {\alpha_{k}>0} et de somme {\mu}).

  1. 1. Montrer que les matrices 0-magiques forment un EV de dimension {(n-1)^{2}}.
  2. 2. Montrer qu’il existe des \beta_{k} non tous nuls, tels que : {\displaystyle\sum_{k=1}^{m}\beta_{k}P_{k}=0\quad\text{et}\quad\displaystyle\sum_{k=1}^{m}\beta_{k}=0}Indication: considérer les matrices {P_{k}-P_{1}}, avec {2\le k\le m}.

  3. 3. Justifier la possibilité de choisir {j\in\{1,\ldots,m\}} tel que : {\dfrac{\alpha_{j}}{\beta_{j}}=\min\biggl\{\dfrac{\alpha_{k}}{\beta_{k}},\;1\le k\le m,\;\beta_{k}>0\biggr\}}Quitte à tout renuméroter, on suppose {j=m}.
  4. 4. Montrer que {A=\displaystyle\sum_{k=1}^{m-1}\delta_{k}P_{k}}, où {\delta_{k}=\alpha_{k}-\alpha_{m}\dfrac{\beta_{k}}{\beta_{m}}}.

    Indiquer le signe des {\delta_{k}}, et leur somme.

    Énoncer le résultat obtenu (en en donner la version bistochastique).


Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 5

Pour les notations et les résultats précédents : Ep1, Ep2, Ep3, Ep4.
Soit {A} une matrice positive magique de somme {\mu>0}.
On sait qu’il existe {\sigma_{1}} dans {\mathcal{S}_{n}} tel que {\sigma_{1}(A)=\displaystyle\prod_{j=1}^{n}a_{\sigma_1(j),j}}\gt 0.
  1. On note P_{1}=P_{\sigma_{1}}. Soit \alpha_{1}=\min\{a_{\sigma_{1}(j),j},\;1\le j\le n.
    Montrer que A_{1}=A-\alpha_{1} P_{1} est positive, magique de somme \mu'\in[0,\mu[.
    Observer que, par rapport à A elle a au moins un coefficient nul supplémentaire.
  2. Montrer qu’on peut écrire {A=\displaystyle\sum_{k=1}^{m}\alpha_{k}P_{k}}, avec des \alpha_{k}>0 tels que {\displaystyle\sum_{k=1}^{m}\alpha_{k}=\mu}, les P_{k} étant des matrices de permutation.
    Cas particulier: si A est bistochastique (\mu=1), cela signifie qu’elle peut s’écrire comme barycentre à coefficients strictement positifs de matrices de permutation.


Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 4

On reprend les définitions et les notations de l’épisode 1.
Pour {A\in\mathcal{M}_{n}(\mathbb{R})}, et pour {\sigma\in\mathcal{S}_{n}}, on note {\sigma(A)=\displaystyle\prod_{j=1}^{n}a_{\sigma(j),j}}.
On dit que {A} est traversable s’il existe {\sigma\in\mathcal{S}_{n}} telle que {\sigma(A)\ne0}.
On souhaite montrer l’équivalence des propositions:
{(\star)\quad} {A} n’est pas traversable
{(\star\star)} {A} possède une sous-matrice nulle de taille {r\times s}, où {r+s=n+1}

  1. 1. Montrer que permuter les lignes ou colonnes ne modifie pas la traversabilité.
  2. 2. Prouver que {(\star\star)} implique {(\star)}.
  3. 3. Établir que {(\star)} implique {(\star\star)} par récurrence sur {n}.
  4. 4. En déduire que toute matrice magique de somme {\mu>0} (et en particulier toute matrice bistochastique) est traversable (raisonner par l’absurde).


Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 3

On reprend les définitions et les notations de l’épisode 1.
On prouve ici la réciproque du résultat final de l’épisode 2: on va donc montrer que tout élément extrémal de {\mathcal{B}_{n}(\mathbb{R})} est une matrice de permutation P_{\sigma}.
Pour cela, soit {C=(c_{i,j})} bistochastique sans être une matrice de permutation.
On doit montrer qu’il existe {A,B} bistochastiques distinctes telles que {C\in\,]A\,;B[}.

  1. 1. Montrer qu’il existe deux suites (i_{k})_{k\ge0} et (j_{k})_{k\ge0} de {[[0,n\!-\!1]]} telles que :{\forall\, k\in\mathbb{N},\begin{cases}i_{k}\ne j_{k+1}\\j_{k}\ne j_{k+1}\end{cases}\text{ et }\begin{cases}0\lt c_{i_{k},j_{k}}\lt 1\\0\lt c_{i_{k},j_{k+1}}\lt 1\\0\lt c_{i_{k+1},j_{k+1}}\lt 1\end{cases}}Indication: choisir {(i_{0},j_{0})}, puis {j_{1}} puis {i_{1}} et repartir de {(i_{1},j_{1})}
  2. 2. La suite {(j_{k})_{k\ge0}} n’étant pas injective, certaines valeurs de {j_{k}} se répètent.
    Quitte à renuméroter, on peut dire qu’il existe {m\ge1} tel que {j_{m+1}=j_{0}}.
    On définit alors la matrice {D=(d_{i,j})} par : {\forall\, k\in[[ 0,m]],\;\begin{cases}d_{i_{k},j_{k}}=1\\d_{i_{k},j_{k+1}}=-1\end{cases}\quad\text{et}\quad d_{i,j}=0\text{ sinon}}Montrer que pour {\lambda>0} assez petit, {\begin{cases}A=C-\lambda D\\B=C+\lambda D\end{cases}} sont bistochastiques.
    Conclure.


Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 2

On reprend ici les définitions et les notations de l’épisode 1.
On établit des propriétés usuelles des matrices bistochastiques ou de permutation.
    Question 1 :
    1. Soit \sigma et s dans {{\mathcal S}_{n}}.
      Préciser {P_{\,\text{Id}}}, {P_{s}\,P_{\sigma}}, {{P_{\sigma}}^{-1}}, {{(P_{\sigma})}^{\top}} et {P_{\sigma}^{\,m}} pour tout {m} de {\mathbb{Z}}.
    2. Soit {A} dans {\mathcal{M}_{n}(\mathbb{R})}, et soit {P_{\sigma}} une matrice de permutation d’ordre {n}.
      Décrire le passage de {A} à chacune des matrices {P_{\sigma}^{-1}A}, {AP_{\sigma}}, et {P_{\sigma}^{-1}AP_{\sigma}}.
  1. Question 2 :

    1. Montrer que {\mathcal{B}_{n}(\mathbb{R})} est compact et stable pour le produit des matrices.
    2. Soit {A,B} dans {\mathcal{B}_{n}(\mathbb{R})}, et {\lambda} dans {[0,1]}.
      Montrer que {C=\lambda A+(1\!-\!\lambda)B} est dans {\mathcal{B}_{n}(\mathbb{R})}.
      L’ensemble {\mathcal{B}_{n}(\mathbb{R})} est donc convexe.
    3. Soit {A}, {B} distinctes dans {\mathcal{B}_{n}(\mathbb{R})}, et soit {P_{\sigma}\in\mathcal{M}_{n}(\mathbb{R})}.
      On suppose que {P_{\sigma}} est élément du segment {[A\,;B]}.
      Montrer que nécessairement {P=A} ou {P=B}.
      Ainsi {]A\,;B[} ne contient aucune matrice de permutation.
      On dit que les matrices de permutation sont extrémales dans {\mathcal{B}_{n}(\mathbb{R})}.


Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 1

Soit {A=(a_{i,j})_{0\le i,j\le n-1}} dans {\mathcal{M}_{n}(\mathbb{R})}.
On dit que A est {\mu}magique si la somme de chaque ligne et de chaque colonne vaut {\mu}.
On dit que {A} est bistochastique si A est {1}-magique et si les {a_{i,j}} sont positifs ou nuls.
On note {\mathcal{S}_n} l’ensemble des permutations de {[[0,n\!-\!1]]}.
Pour {\sigma\in\mathcal{S}_n} on note {P_{\sigma}} la matrice de terme général {p_{i,j}=\delta_{i,\sigma(j)}}.
On note {\mathcal{B}_n(\mathbb{R})} l’ensemble des matrices bistochastiques d’ordre n.
On note {\mathcal{P}_n(\mathbb{R})\subset\,\mathcal{B}_n(\mathbb{R})} l’ensemble des matrices de permutations {P_{\sigma}} d’ordre n.

  1. 1. Écrire une fonction matperm, d’argument une liste {L=[\sigma(0),\sigma(1),\ldots,\sigma(n\!-\!1)]} représentant une permutation {\sigma\in\mathcal{S}_{n}}, et renvoyant la matrice de permutation {P_{\sigma}}. En déduire une fonction randmatperm, d’argument {n\ge1}, renvoyant une matrice aléatoire de permutation (utiliser les bibliothèques numpy et random).
  2. 2. Écrire une fonction randbisto, d’argument {n\in\mathbb{N}^{*}}, renvoyant une matrice pseudo-aléatoire {A} de {\mathcal{B}_{n}(\mathbb{R})} (former un barycentre de {n^{2}} matrices {P_{\sigma}} aléatoires).
    Écrire une fonction randmagique, d’arguments {n\in\mathbb{N}^{*}} et {\mu\in\mathbb{N}^{*}}, renvoyant une matrice magique pseuso-aléatoire d’ordre {n}, de somme {\mu}, et à coefficients dans {\mathbb{N}}. L’unique objectif est de disposer facilement de matrices bistochastiques ou magiques de somme donnée, sans réfléchir au caractère représentatif de ces matrices pseudo-aléatoires.

Cliquer ici pour voir le corrigé

Question de point fixe

Soit {(E,\|\;\|)} un espace vectoriel normé de dimension finie.
Soit {K\subset E} un fermé borné non vide.
Soit {f:K\rightarrow K} telle que : {\forall (x,y)\in K^2}, {x\ne y} {\Rightarrow} {\|f(x)-f(y)\|\lt \|x-y\|}.
1. Montrer qu’il existe un unique {c\in K} tel que {f(c)=c}.
2. Soit {x_0\in K}. On pose: {\forall\, n\in\mathbb{N},\;x_{n+1}=f(x_n)}.
\quadMontrer que la suite {(x_n)_{n\ge0}} converge vers {c}.

Cliquer ici pour voir le corrigé

Forme linéaire, matrices semblables

Soit {\varphi} une forme linéaire sur {{\mathcal M}_{n}(\mathbb{C})}.
1. Montrer : {\exists\,!\,\,A\in{\mathcal M}_{n}(\mathbb{C}),\;\forall\, M\in{\mathcal M}_{n}(\mathbb{C}),\;\varphi(M)=\text{tr}(AM)}.
2. On suppose que : {\forall\, M\in{\mathcal M}_{n}(\mathbb{C}),\;\forall\, P \in \text{GL}_{n}(\mathbb{C}),\;\varphi(P^{-1}MP)=\varphi(M)}.
\quadMontrer : {\exists\,\lambda\in\mathbb{C},\;\forall\, M\in{\mathcal M}_{n}(\mathbb{C}),\;\varphi(M) = \lambda\,\text{tr}(M)}.

Cliquer ici pour voir le corrigé

Interversion série-intégrale

Soit {(u_n)} une suite croissante de {\mathbb{R}^{+*}}, divergente.

Montrer que : {\displaystyle\int_{0}^{+\infty}\biggl( \displaystyle\sum_{n=0}^{+\infty}(-1)^ne^{-u_nx}\biggr)\,\text{d}x=\displaystyle\sum_{n=0}^{+\infty}\dfrac{(-1)^n}{u_n}}.


Cliquer ici pour voir le corrigé