Sujet Supélec MP 2016

Note

Vous pouvez télécharger ici le contenu de la page ci-dessous. Ce sera plus joli à lire !

Partie 1 : rayon spectral inférieur à 1

I.A.1) $N(A)$ est une norme :

  • $N(0_n) = 0$ et $N(A) = 0 \Rightarrow A = 0$ comme somme d’éléments positifs.
  • $A \mapsto N(A)$ est bien à valeurs dans $\mathbb{R}^+$.
  • $N(\lambda A) = | \lambda |.N(A)$ de façon évidente.
  • On a bien $N(A+B) \leq N(A) + N(B)$ car pour tous $i, j \in [\![1,n]\!]$, $|a_{ij} + b_{ij}| \leq |a_{ij}| + |b_{ij}|$.

$A \mapsto N(A)$ est une norme. Montrons maintenant la sous-multiplicativité en calculant le produit de $A\times B$.

Pour calculer la norme, on doit sommer les valeurs absolues des éléments de $A\times B$, soit les $|\sum_{k = 1}^n a_{ik}b_{kj}|$.

On peut écrire avec la valeur absolue :

$$
\left|\sum_{k = 1}^n a_{ik}b_{kj}\right| \leq \sum_{k = 1}^n |a_{ik}b_{kj}|
$$

En sommant sur les $j$ et en passant au max, nous avons directement :

$$N(A.B) = \max_{1\leq i \leq n} \sum_{j=1}^n \left|\sum_{k = 1}^n a_{ik}b_{kj}\right| \leq \max_{1 \leq i \leq n} \sum_{j = 1}^n \sum_{k = 1}^n |a_{ik}b_{kj}|$$

Les deux sommes possèdent des indices indépendants, donc la double-somme des $|a_{ik}|.|b_{kj}|$ s’inverse. Nous pouvons sortir $a_{ik}$ de $\sum_{j = 1}^n$, ce qui fait apparaître $\sum_{k = 1}^n |b_{kj}| \leq N(B)$. On a ainsi :

$$\begin{aligned}
N(A.B) & = \max_{i \in [\![1,n]\!]} \left( \sum_{j=1}^n \left|\sum_{k = 1}^n a_{ik}b_{kj}\right| \right) \\
& \leq \max_{i \in [\![1,n]\!]} \left( \sum_{k = 1}^n |a_{ik}|.\sum_{j = 1}^n |b_{kj}| \right) \\
& \leq N(B).\sum_{k = 1}^n |a_{ik}| \leq N(A).N(B)
\end{aligned}$$

et le résultat.

I.A.2) Montrons que $\| . \|_Q$ est une norme :

  • On voit clairement que $\| A \|_Q \geq 0$.
  • $\| A \|_Q = 0 \Leftrightarrow Q^{-1} A Q = 0 \Leftrightarrow A= 0$ car $A \mapsto Q^{-1}AQ$ est une bijection et $Q^{-1}0_n Q = 0$.
  • `$| \lambda.A |_Q = N(Q^{-1} \lambda.A Q) = |\lambda|.|A|_Q$
  • Inégalité triangulaire : On a $Q^{-1}(A+B)Q = Q^{-1}A Q + Q^{-1}B Q$, donc en passant à la norme $N$, on a $\|A+B\|_Q \leq \|A\|_Q + \|B\|_Q$.
  • Sous-multiplicativité : si $Q \in GL_n(\mathbb{K})$, on a $\|A.B\|_Q = N(Q^{-1}A B Q) = N(Q^{-1}A Q Q^{-1} B Q) \leq \|A\|_Q.\|B\|_Q$.

I.B.1) Le produit est stable pour les matrices triangulaires supérieures ; en particulier, pour $i > j$, on indice un élément du triangle bas-gauche de la matrice. Cet élément est nul dans la matrice produit, car il vaut

$$ \sum_{k \in [\![1,n]\!]} a_{ik} b_{kj}$$

Quand $k \leq i-1, a_{ik} = 0$ et quand $k > j, b_{kj} = 0$. Or $i-1 \leq j$ donc pour tout $k$ le produit le produit est nul.

Ainsi la matrice $\widehat{T}=\Delta^{-1}T\Delta$ est triangulaire supérieure. Pour voir qu’on peut choisir $\delta$ tel que $N(\widehat{T}) \le 1$, on s’assurera que chaque somme sur une ligne (à $i$ fixé) peut être inférieure à 1, ce qui donnera le résultat.

Pour $i$ fixé et en faisant le produit des matrices, on a

\begin{equation}\widehat{t}_{ij} = \sum_{k\in [\![1,n]\!]} \sum_{l\in [\![1,n]\!]}
    \delta'_{il}.t_{lk}.\delta_{kj}\label{tchapeau}\end{equation}

ou les $\delta_{kl}$ et $\delta'_{kl}$ sont les éléments de $\Delta$ et $\Delta^{-1}$ respectivement.

Ces deux matrices étant des matrices colonnes et $T$ une matrice triangulaire, les sommes de \eqref{tchapeau} disparaissent et on a, pour les éléments du triangle supérieur :

$$ \forall i \leq j, \widehat{t}_{ij} = \delta^{j-i} t_{ij}$$

Car $\delta_{kl} = 0$ si $k \neq l$, $\delta_{ll} = \delta^{l-1}$, et $\delta'_{ll} = \delta^{-(l-1)}$.

Les $\widehat{t}_{ii}$ sont tous strictement inférieurs à 1 : en effet, $\rho(\widehat{T}) = \rho(T) = \rho(A)$ car le polynôme caractéristique est inchangé par changement de base.

Les éléments $\widehat{t}_{ii}$ sont donc égaux à $t_{ii}$ et les autres éléments du triangle supérieur sont tous multipliés par une puissance de delta. Donc dans le calcul de $N(\widehat{T})$, la somme des $|\widehat{t}_{ij}|$ est égale à $|t_ii| + \delta.\sum_{j=i+1}^n \delta^{j-i-1}.|t_{ij}|$. Ce dernier terme, en choisissant $\delta$, est aussi petit que l’on veut (somme finie). En particulier, on peut choisir $\delta$ tel que cette somme soit toujours inférieure à $\min_{1\leq i \leq n} (1-t_{ii})$, et le résultat.

I.B.2) On a $\|A\|_Q = N((P\Delta)^{-1} A P\Delta) = N(\widehat{T}) < 1$. Par une récurrence directe en utilisant la sous-multiplicativité, $\|A^m\|_Q \leq \|A\|_Q^m$.

Les normes sont toutes équivalentes dans un e.v.n de dimension finie, donc avec la norme sup cela équivaut à dire que $\|A^m\|_\infty \leq \|A\|_\infty^m$. Comme $\|A\|_\infty < 1$, on a bien $\lim_{x \rightarrow \infty} A^m = 0$.

Partie 2 : Chemins dans les matrices positives

II.A a) Supposons qu’il existe un chemin élémentaire de $i$ vers $j$. Alors de manière directe ce chemin comporte au plus n éléments (puisqu’il s’agit d’entiers distincts dans $[\![1,n]\!]$). La longueur du chemin est inférieure ou égale à $n-1$.

Supposons qu’il existe un chemin non élémentaire de longueur $m$ (i.e. il comporte deux indices égaux $i_k$ et $i_l, l > k$). Alors nous pouvons réduire le chemin à

$$i_0, i_1, \ldots i_k, i_{l+1}, i_{l+2}, \ldots i_m$$

On construit ainsi l’algorithme suivant :

Tant que le chemin n'est pas élémentaire,
  Retirer une boucle

Le processus se termine au bout d’un nombre fini d’étapes car le nombre d’indices est fini. Le chemin trouvé est élémentaire, et comme vu plus tôt il est de longueur strictement inférieure à $n$.

b) Dans le cas où le chemin est un circuit (i.e. $i_m = i_0$), alors on retire le dernier terme et l’on applique l’algorithme précédent. Notons que cela conserve toujours $i_{m-1}$, et donc que nous terminons toujours le chemin dans la matrice par l’élément $a_{i_{m-1}i_m}$. Le circuit obtenu est élémentaire, donc de longueur $n+1$.

II.B) On souhaite montrer par récurrence la proposition de l’énoncé.

On vérifie de façon évidente la proposition pour $m=1$.

Supposons que pour tous $i, j \in [\![1,n]\!]$ la proposition soit vraie au rang $m$. Alors un élément $i,j$ de $A^{m+1}$ vaut :

$$a{ij}^{(m+1)} = \sum{k=1}^n a{ik}^{(m)} a{kj}$$

Il vient que $a_{ij}^{(m+1)} > 0$ si et seulement s’il existe $k \in [\![1,n]\!]$ tel que $a_{ik}^{(m)} > 0$ et $a_{kj} > 0$. En utilisant la propriété vraie au rang $n$, toujours par équivalence, il existe un chemin de longueur $m$ entre $i$ et $k$. $a_{kj}$ étant non nul, ajoutons $j$ au chemin trouvé précédemment et celui-ci, de longueur $n+1$, est un chemin valide.

Nous avons l’hérédité de la proposition et l’équivalence, donc la récurrence donne le résultat.

II.C) Cette propriété est directement issue de la précédente : il existe un chemin de longueur $l$ dans $A^m$ ssi les $a_{ij}$ correspondants sont strictement positifs, i.e. ssi pour tout $k \in [\![1,l]\!]$ il existe un chemin de longueur m dans $A$ de $i$ à $j$. Ces chemins se suivent (car la suite dans $A^m$ est un chemin valide), ce qui permet d’aller à Rome, et le résultat.

III.A A est primitive. Soit $m \ge 1$ tel que $A^m$ > 0.

En particulier le chemin $(i,\ldots, n,1, \ldots, j)$ est valide dans $A^n$. D’après II.C), il existe dans A un chemin d’origine i, d’extrémité j et de longueur $m(n-1)$. On le réduit comme en II.A), et le résultat.

Ceci étant vrai pour tous i et j, il existe aussi un cemin d’origine f et d’extrémité j de longueur $m(n+1)$ dans A. On concatène les deux en retirant les terminaisons du deuxième chemin, et nous obtenons un circuit. On le réduit comme en II.A), et le résultat. De plus, les chemins élémentaires obtenus sont de longueur $l \le n - 1$ et les circuits élémentaires de longueur $l < n$.

III.B.1) La matrice $A = \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix}$ est primitive mais non strictement positive.

III.B.2) Si $x\le 0$ et si $x \ne 0$ dans $\mathbb{R}^n$, il existe $k \in \{1, \ldots, n\}, x_k \ne 0$. Alors $(Bx)_i = \sum_{j=1}^n b_{ij}x_j \ge b_{ik}x_k >0$ comme somme de termes positifs. Ceci est vrai pour tout $i$, donc $Bx > 0$.

III.B.3) Récurrence à partir de m :

  • $A^m > 0$ ;
  • Si $A^p > 0 (p \ge m)$, on a : 1) Pour tous $i,j \in \{1, \ldots, n\}$, il existe un chemin $(i, \ldots, \alpha_j, j)$ dans A, $\alpha_j$ étant un entier de $\{1, \ldots, n\}$. On a $a_{\alpha_j,j}>0$, et ce pour tout j. 2) Toute colonne de A est non nulle et $A^p > 0$. Donc avec III.B.2), toute colonne de $A^{p+1}$ est strictement positive.

On a ainsi $A^{p+1}$ et le résultat.

III.B.4) Soit $k\ge1$ et $m\ge1$ tel que $A^m > 0$. Alors il existe $p\in\mathbb{N}$ tel que $k\times p \ge m$. Ainsi, ${(A^k)}^p = A^{kp} >0$ d’après le résultat de la question précédente.

III.B.5) Soit $Q\in GL_n(\mathbb{R}), Q^{-1}AQ$ est triangulaire supérieure. Supposons $\rho(A)=0$. Alors $Q^{-1}AQ$ est triangulaire supérieure stricte (de diagonale nulle). On montre facilement que celle-ci est nilpotente, i.e il existe $p$ tel que $(Q^{-1}AQ)^p = 0$. Ceci donne $Q^{-1}A^pQ = 0$ en simplifiant, et alors $A^p=0$. Donc A n’est pas primitive (contradiction). Donc $\rho(A)>0$.

III.C.1) En calculant le déterminant par la dernière ligne :

$$
\begin{aligned}
det(W_n-XI_n) &=& det \begin{pmatrix}
1 &0& \ldots & & 0\\
-X&1&\ldots & & \\
&\ddots&\ddots&&\\
0&&& -X & 1\end{pmatrix} - det\begin{pmatrix}-X & & & \\
&1& & \\
& & \ddots & \\
& & & 1\end{pmatrix} + \\
& & (-1)^{n+1}.(-X).det \begin{pmatrix}-X & 1 & 0 & \ldots & 0\\
0& -X & 1 & \ldots& 0\\
&&\ddots&\ddots&\\
&&&-X&1\\
&&&&-X \end{pmatrix}
\\
& = & 1+X+(-1)^{n+1}.(-1)^{n+2}.X.X^{n+1} \\
& = & 1 + X + X^n
\end{aligned}
$$

(Abandon de la suite de cette question)

III.C.2) Pour tout $k \ne n, a_{k,j}>0 \Rightarrow j=k+1$. Ainsi le chemin $(k, k+1)$ est le seul valide dans W à partir de k. Par une récurrence évidente, le chemin $(1, 2, \ldots, n)$ est donc le seul chemin de 1 à $n$. De plus, $(a_{k,1}>0) \Rightarrow k=n$. Le circuit obtenu est de longueur $n$, il est élémentaire et de longueur minimale d’après la récurrence ci-dessus.

On montre de la même manière que le circuit minimal passant par 2 est le circuit $(2, 3, \ldots, n, 2)$, qui est de longueur $n-1$.

Ainsi tout circuit est l’assemblage de circuits de longueur n et $n-1$.

D’après II.B), ($W_n^{(n-1)^2}>0$) est vrai si et seulement si $\forall i, j \in [\!\|1, n]\!\|$, il existe un chemin de longueur $(n-1)^2$ dans $W_n$. Il faut en particulier qu’il existe un chemin de cette longueur d’origine 1 et d’extrémité 1.

D’après ce que nous avons vu, on a donc :

\begin{equation}\label{arith}($W_n^{(n-1)^2}>0$) \Rightarrow
\exists k,p \in \mathbb{N}, k \ne 0, kn + p(n-1) = (n-1)^2
\end{equation}

Ceci exprimant le fait qu’il existe un circuit de longueur $(n-1)^2$ passant par 1, composé de $p$ boucles passant par 1, et $q$ boucles ne passant pas par 1.

$n$ et $n-1$ sont premiers entre eux (théorème de Bezout) car en particulier on a $n - (n-1) = 1$. Ainsi, l’équation $\eqref{arith}$ n’a pas de solutions dans $\mathbb{N}^2$. On a alors $w_{1,1}^{(n-1)^2 = 0$ et le résultat.

III.C.3) Le circuit élémentaire $(1 \rightarrow \ldots \rightarrow n)$ est valide dans $W_n$ et il comporte tous les indices. En supposant $i > j$, il vient que les chemins $(i \rightarrow \ldots \rightarrow j)$ et $(j \rightarrow \ldots n \rightarrow 1 \rightarrow \ldots \rightarrow i)$ sont tous deux valides dans $W_n$. Ces deux chemins sont une troncature du circuit élémentaire minimal passant par 1. Comme $i \ne j$, ces deux chemins sont de longueur inférieure ou égale à $(n-1)$.

(abandon de la question)