Soit {A} une matrice de {\mathcal M_n(\mathbb K)}. Une décomposition « LU » de {A} est une égalité {A=LU}, où {L} est une matrice triangulaire inférieure ({L} pour « Low ») à diagonale unité (tous les coefficients diagonaux valent {1}), et où {U} est une matrice triangulaire supérieure ({U} pour « Up »).
Par exemple, la matrice{A=\begin{pmatrix}2&-3&1&-1\\[4pt]-2&2&-3&2\\[4pt]4&-9&-2&3\\[4pt]-2&5&5&-4\end{pmatrix}}admet la décomposition {A=LU}, avec{L=\begin{pmatrix}1&0&0&0\\[4pt]-1&1&0&0\\[4pt]2&3&1&0\\[4pt]-1&-2&1&1\end{pmatrix}}{U=\begin{pmatrix}2&-3&1&-1\\[4pt]0&-1&-2&1\\[4pt]0&0&2&2\\[4pt]0&0&0&-5\end{pmatrix}}
Pour tout entier {k\in\{1,\ldots,n\}}, on appelle sous-matrice principale d’ordre {k} de {A} la sous-matrice {A_k} formée à l’intersection des {k} premières lignes et des {k} premières colonnes de {A}.
Par exemple, avec la matrice {A} de l’exemple précédent :{A_1=(2),\quad A_2=\begin{pmatrix}2&-3\\[4pt]-2&2\end{pmatrix}}{A_3=\begin{pmatrix}2&-3&1\\[4pt]-2&2&-3\\[4pt]4&-9&-2\end{pmatrix}}{A_4=\begin{pmatrix}2&-3&1&-1\\[4pt]-2&2&-3&2\\[4pt]4&-9&-2&3\\[4pt]-2&5&5&-4\end{pmatrix}}
Dans tout le problème, la matrice {A} est supposée inversible.
Partie I
Dans cette partie, on voit une condition nécessaire et suffisante portant sur la matrice {A} pour qu’elle admette une décomposition {LU}.
1. Montrer que la décomposition {LU} de {A}, si elle existe, est unique.
2. Montrer que la matrice{A=\begin{pmatrix}1&2\\[4pt]0&3\end{pmatrix}}possède une décomposition {LU}. Montrer en revanche que la matrice{B=\begin{pmatrix}0&3\\[4pt]1&2\end{pmatrix}}n’en possède pas.
3. On suppose que la matrice {A} possède une décomposition {LU}. Montrer que toutes ses sous-matrices principales sont inversibles.
Pour cela, on utilisera une décomposition par blocs de {A,L,U}, sous la forme suivante :{A=\begin{pmatrix}A_k&A'_k\\[4pt]A''_k&A'''_k\end{pmatrix}}{L=\begin{pmatrix}L_k&0\\[4pt]L''_k&L'''_k\end{pmatrix}}{U=\begin{pmatrix}U_k&U'_k\\[4pt]0&U'''_k\end{pmatrix}}
4. Montrer que la réciproque de la propriété précédente est vraie : si toutes les sous-matrices principales de {A} sont inversibles, alors {A} possède une décomposition {LU}.
Pour cela, on raisonnera par récurrence sur l’ordre {n} de {A} : dans le passage du rang {n} au rang {n+1}, on écrira{L_{n+1}=\begin{pmatrix}L_n&0\\[4pt]R_n&1\end{pmatrix}}{U_{n+1}=\begin{pmatrix}U_n&C_n\\[4pt]0&\lambda_n\end{pmatrix}}, où {R_n} est une matrice-ligne de largeur {n}, {C_n} est une matrice-colonne de hauteur {n}, et {\lambda_n} est un scalaire.
Dans cette partie, on suppose que la matrice {A} possède une décomposition {LU} et on voit comment mettre en œuvre une méthode de calcul des matrices {L} et {U}.
On note {a_{ij}}, {\ell_{ij}} et {u_{ij}} les termes généraux de {A,L,U}.
1. À titre d’exemple, trouver la décomposition {LU} de{A=\begin{pmatrix}2&-3&1\\[4pt]-2&2&-3\\[4pt]4&-9&-2\end{pmatrix}}
2. On revient maintenant au cas général. Écrire les égalités donnant {a_{ik}} en fonction des {\ell_{ij}} (avec {j\leq i}) et des {u_{jk}} (avec {j\leq k}).
4. Montrer comment les égalités obtenues permettent de calculer de proche en proche (et on précisera dans quel ordre) tous les coefficients de {L} et de {U}.
On sait qu’il existe des matrices {A} qui n’ont pas de décomposition {LU}.
Dans cette partie, on va voir que, pour une telle matrice, il est possible de trouver une matrice inversible « simple » {P} telle que {PA} admette une décomposition {LU}.
On appelle matrice de permutation toute matrice {P_\sigma} d’ordre {n} dont le terme général {p_{ij}} peut s’écrire {p_{ij}=\delta_{j,\sigma(i)}} (notations de Kronecker), où {\sigma} est une permutation de {\{1,2,\ldots,n\}}.
Si, par exemple, {n=4} et {\sigma} est définie par {\left\{\begin{array}{l}\sigma(1)=3,\\[4pt]\sigma(2)=2,\\[4pt]\sigma(3)=4,\\[4pt]\sigma(4)=1,\end{array}\right\}}alors{P_\sigma=\begin{pmatrix}0&0&1&0\\[4pt]0&1&0&0\\[4pt]0&0&0&1\\[4pt]1&0&0&0\end{pmatrix}}
1. Dans cette question, on étudie quelques propriétés des matrices de permutation.
1. (a). Que représente {P_\sigma} si {\sigma} est la permutation « identité » de {\{1,\ldots,n\}} ?
2. On va étudier l’influence du produit par une matrice de permutation.
2. (a). Avec la matrice {A} du préambule et la matrice {P_\sigma} de l’exemple ci-dessus, calculer les produits {P_\sigma A} et {AP_\sigma^{-1}}. Que remarque-t-on ?
2. (b). Plus généralement, pour toute matrice {A} d’ordre {n}, et toute matrice de permutation {P=P_\sigma}, comment passe-t-on de {A} à {PA} et de {A} à {AP^{-1}} ?
3. On va montrer que, pour toute matrice carrée {A} inversible et d’ordre {n}, il existe une matrice de permutation {P} telle que la matrice {PA} possède une décomposition {LU}.
4. (b). En appliquant l’hypothèse de récurrence à {B_n}, montrer qu’il existe une matrice de permutation {Q} telle que {QB} admette une décomposition {LU}.
Dans cette partie, {M} est une matrice quelconque d’ordre {n}, de coefficients {m_{ij}}.
On va étudier l’influence qu’ont certaines opérations sur les lignes ou les colonnes de {M} et interpréter ces opérations par des produits à gauche ou à droite par des matrices triangulaires inférieures à diagonale unité. Posons tout d’abord quelques notations.
On note {(E_{ij})} la base canonique de {\mathcal M_n(\mathbb K)} : la matrice {E_{ij}} est celle dont tous les coefficients sont nuls, sauf celui situé à l’intersection de la ligne {i} et de la colonne {j}, qui vaut {1}.
Pour tous indices {i,j} avec {i\neq j} et tout scalaire {\alpha}, on note {L_j\gg L_j-\alpha L_i} l’opération qui consiste à retrancher à la ligne d’indice {j} de {M} le produit par {\alpha} de sa ligne d’indice {i}.
On note {L_i\leftrightarrow L_j} l’opération qui consiste à échanger les lignes d’indices {i} et {j} de {M}. On définit également les opérations {C_j\gg C_j-\alpha C_i} et {C_i\leftrightarrow C_j} sur les colonnes de {M}.
Pour tout {j\in\{1,\ldots,n-1\}}, à condition que {m_{jj}\neq0}, on note {\varphi_j(M)} la matrice obtenue en appliquant successivement à {M} les opérations{L_i\gg L_i-\lambda_{ij}L_j}pour {i\in\{j+1,\ldots,n\}}, avec{\lambda_{ij}=\dfrac{m_{ij}}{m_{jj}}} Dans cette opération, dont le but est d’annuler les coefficients sous-diagonaux de la colonne d’indice {j} de {M}, le coefficient diagonal {m_{jj}} est appelé le pivot.
1. Pour tout couple d’indices {(i,j)}, comparer les lignes de la matrice {E_{ij}M} et celles de {M}. Comparer aussi les colonnes de {ME_{ij}} et celles de {M}.
2. Montrer qu’une opération du type {L_i\gg L_i-\alpha L_j}, avec {i>j}, transforme une matrice {M} en une matrice {M^{\prime}=SM}, où {S=I_n-\alpha E_{ij}} (et {S} est une matrice triangulaire inférieure à diagonale unité, ne dépendant que de {i,j,\alpha}).
4. Montrer que si on transforme {M} en une matrice {M^{\prime}} par une opération du type {\varphi_j}, alors il existe une matrice {R} triangulaire inférieure à diagonale unité telle que {RM=M^{\prime}}. Détailler les coefficients de {R}.
Dans cette partie, {A} est une matrice carrée d’ordre {n}, inversible. On reprend les notations de la partie IV, notamment en ce qui concerne les opérations {\varphi_j}.
On suppose que la matrice {A} possède une décomposition {LU}.
1. Montrer qu’on peut appliquer l’opération {\varphi_1} à la matrice {A}, et qu’on transforme ainsi {A} en une matrice {B} dont les coefficients sous-diagonaux de la colonne {1} sont nuls.
2. Soit {k\in\{2,\ldots,n\}}. On suppose qu’on a appliqué à {A} les opérations {\varphi_1,\varphi_2,\ldots,\varphi_{k-1}} (dans cet ordre) et qu’on a ainsi transformé {A} en une matrice {C} dont les coefficients sous-diagonaux des {k-1} premières colonnes sont nuls.
Montrer que le {k}-ième coefficient diagonal de {C} est non nul.
3. En déduire qu’on peut partir de {A} et appliquer successivement {\varphi_1,\varphi_2,\ldots,\varphi_{n-1}}. Montrer que la matrice obtenue est triangulaire supérieure à coefficients diagonaux non nuls, et qu’elle est la matrice {U} de la décomposition {A=LU}.
4. Montrer comment on peut construire la matrice {L} de la décomposition {A=LU}, en appliquant à la matrice {I_n} une succession d’opérations sur les colonnes, chacune de ces opérations correspondant à l’une de celles qui ont permis de passer de la matrice {A} à la matrice {U}.
Dans cette partie, {A} est une matrice carrée d’ordre {n}, qui est seulement supposée inversible.
On se propose d’obtenir une décomposition {PA=LU} (au sens de la partie III) par le biais d’opérations élémentaires sur les lignes et les colonnes.
À la panoplie des opérations {\varphi_i} définies dans la partie IV, on ajoute les opérations {\theta_i^j} : pour toute matrice {M}, {\theta_i^j(M)} est la matrice obtenue par échange des lignes d’indices {i} et {j} de {M}.
On pourra considérer que {\theta_i^i(M)=M}.
1. Montrer qu’on peut appliquer une opération {\theta_{i_1}^1} puis l’opération {\varphi_1} à la matrice {A}, de manière à la transformer en une matrice {B} dont les coefficients sous-diagonaux de la colonne {1} sont nuls.
2. Soit {k\in\{2,\ldots,n\}}. On suppose qu’on a appliqué à {A} les opérations{\theta_{i_1}^1,\varphi_1,\ldots,\theta_{i_{k-1}}^{k-1},\varphi_{k-1}}dans cet ordre, avec {i_1\geq1}, {i_2\geq2}, …, {i_{k-1}\geq k-1}.
On a ainsi transformé {A} en une matrice {C=(c_{ij})} dont les coefficients sous-diagonaux des {k-1} premières colonnes sont nuls.
Montrer que l’un au moins des coefficients {c_{ik}}, avec {i\geq k}, est non nul.
3. Montrer qu’il existe {n-1} entiers {i_1,i_2,\ldots,i_{n-1}}, avec {i_k\geq k}, tels que la succession, dans cet ordre, des opérations{\theta_{i_1}^1,\varphi_1,\ldots,\theta_{i_{n-1}}^{n-1},\varphi_{n-1}}transforme {A} en une matrice {U} triangulaire supérieure à coefficients diagonaux non nuls.