\documentclass[a4paper,12pt]{amsart}
\usepackage{kbexo}

\course{Algèbre et calcul formel -- Agrégation}
\num{10}

%%%%%%%%%%%%%%%%%%%%%
%% Alice's packages
%%%%%%%%%%%%%%%%%%%%%
\usepackage{xcolor}

%%%%%%%%%%%%%%%%%%%
%% Alice's macros
%%%%%%%%%%%%%%%%%%%
\newcommand{\comment}[1]{{\color{gray}#1}}

\begin{document}
\exotitle[Algèbre linéaire : décompositions de matrices]
\bigskip

\section{Matrices définies sur un corps}

%%%%%%%%%%%
%% Jordan
%%%%%%%%%%%
\exo[Forme de Jordan]

Nous avons déjà travaillé sur la diagonalisation des matrices. Sur un corps
algébriquement clos, les matrices non diagonalisables peuvent-être
triangulées, et même mises sous forme de Jordan. Pour cela, on dispose de la
fonction {\tt Jordan\_form}.

On va construire un exemple de matrice non diagonalisable sur $\CM$, dont la
réduction est formée de plusieurs blocs de Jordan.

\begin{verbatim}
  J1 = jordan_block(5,3)
  J2 = jordan_block(2,5)
  J3 = jordan_block(1,4)
  J = block_diagonal_matrix(J1,J2,J3)
\end{verbatim}

Cela doit donner une matrice sous forme de Jordan, dont on peut prendre un
conjugué, pour construire un exemple non-trivial.
%\begin{verbatim}
%  N1 = jordan_block(0,12)
%  N2 = transpose(N1)
%  D = diagonal_matrix([1]+[2 for i in range(11)])
%  P = N1+N2+D
%  A = P^(-1)*J*P
%\end{verbatim}
%On s'est arrangé pour que $\det P=1$. 
Pour construire notre conjugué, on peut soit construire une matrice de passage $P$ particulière dont on sait qu'elle est inversible, soit prendre une matrice $P$ au hasard jusqu'à ce qu'elle soit inversible (ce qui a de grandes chances d'arriver).
\begin{verbatim}
  M12Q = MatrixSpace(QQ,12)
  P = M12Q.random_element()
  A = P^(-1)*J*P
\end{verbatim}

\Q Calculer la forme de Jordan de $A$ en utilisant {\tt A.jordan\_form()} et vérifier que c'est bien ce à quoi on s'attend.

%Quelle est la décomposition de Dunford de la matrice $A$ précédente?
%Soit $K$ un corps. On rappelle que la décomposition de Dunford d'une matrice
%$A$ de $\mathcal M_n(K)$ est l'écriture de $A$ sous la forme
%$A=D+N$ où $DN=ND$, où $N$ est nilpotente et où $D$ est diagonalisable
%dans une clôture algébrique de $K$. Je ne connais pas de commande directe
%sur \texttt{sage} pour cette décomposition. Nous verrons plus tard un
%algorithme qui la calcule.

%Exemple piège à faire sans calculs: quelle est la décomposition de Dunford de
%$\smallmat{1&2\\0&3}$?

\smallskip

\misctitle{Remarque} On a construit ci-dessus des matrices
diagonales par blocs en utilisant {\tt block\_diagonal\_matrix}. Remarquons
au passage l'existence de la fonction {\tt block\_matrix}, qui permet la
construction de matrices par blocs.

%%%%%%%%%%%%%%%%%%%%%%
%% Décomposition LU
%%%%%%%%%%%%%%%%%%%%%%
\exo[Décomposition LU]
\label{LU}

\begin{theo}
Soient $K$ un corps et $A\in\Gl_n(K)$. Alors il existe une matrice de
permutation $P$, une matrice triangulaire supérieure $U$ et une matrice
triangulaire inférieure $L$ dont les éléments diagonaux sont égaux à $1$
telles que $A=PLU$. De plus, pour $P$ fixée, cette décomposition est unique
si elle existe.
\end{theo}

Cette décomposition s'obtient grâce à l'algorithme du pivot de Gauss. Une
décomposition $A=LU$ (c'est-à-dire où $P=I_n$) existe si et seulement si on
ne rencontre pas de «pivot nul» dans cet algorithme. En fait, on 
montre que la décomposition $A=LU$ existe si et seulement si pour tout
$k\in[[1,n]]$, $\det A_k\neq0$, où $A_k$ est la sous-matrice supérieure gauche
de taille $k$ de $A$. Par exemple, les matrices de $\Gl_n(\CM)$ à
\emph{diagonale strictement dominante} admettent une décomposition $A=LU$,
ainsi que les matrices réelles \emph{symétriques définies positives} et les
matrices complexes \emph{hermitiennes définies positives}.

Sur Sage, la décomposition $A=PLU$ de $A$ est donnée par {\tt A.LU()}.

Soit
$A=
\begin{pmatrix}
1&4&7\\
2&5&8\\
3&6&10
\end{pmatrix}.
$
Donner la décomposition $LU$ de $A$ (on pourra essayer la fonction
{\tt LU} sans option, et aussi avec l'option {\tt pivot='nonzero'}).

\Q Soit
$B=
\begin{pmatrix}
1\\
3\\
5
\end{pmatrix}.
$
Pour entrer $B$, on peut utiliser {\tt vector}. En utilisant cette
décomposition $LU$, et en résolvant deux systèmes triangulaires sur papier,
résoudre $AX=B$.

\Q Définir la concaténée $C$ de $A$ et $B$, appliquer la fonction {\tt LU} à $C$
et retrouver la solution de l'équation par résolution d'une équation
triangulaire.

\Q Vérifier le résultat obtenu en utilisant {\tt A.solve\_right(B)}.

\Q Même exercice avec
$A=
\begin{pmatrix}
1&4&7\\
2&8&8\\
3&6&10
\end{pmatrix}
$
et
$B=
\begin{pmatrix}
1\\
3\\
5
\end{pmatrix}.
$

\medskip
Soit maintenant une matrice $A$ qui n'est pas supposée inversible, ni même
carrée. Soit $A\in\mathcal M_{m,n}(K)$, le résultat précédent se transpose à
ce cas: il existe une décomposition $PA=LU$, où $P$ est une matrice de
permutation de taille $m$, $L$ est une matrice triangulaire inférieure de
$\Gl_m(K)$ dont les coefficients diagonaux sont égaux à $1$, et $U$ est une
matrice \emph{échelonnée par lignes} de $\mathcal M_{m,n}(K)$. Il n'y a pas
unicité en général, même si $P$ est fixée.

Rappelons ce qu'est une matrice échelonnée par lignes.
\begin{defi}\label{echelons}
Soit $E=(e_{ij})_{i,j}\in\mathcal M_{m,n}(K)$. On dit que $E$ est
\emph{échelonnée par lignes} s'il existe un entier $r\leq\min(m,n)$ et une
fonction $f\colon [[1,r]]\longrightarrow [[1,n]]$ strictement croissante telle
que les propriétés suivantes sont vérifiées.
\begin{enumerate}
\item Pour tout $i\in[[1,r]]$, $e_{if(i)}\ne0$.
\item Si $j<f(i)$, alors $e_{ij}=0$.
\item Si $i>r$, alors $e_{ij}=0$.
\end{enumerate}
Le rang de $E$ est alors égal à $r$. 

La matrice $E$ est dite \emph{échelonnée réduite par lignes} si de plus
pour tout $i\in[[1,r]]$:
\begin{enumerate}
\item $e_{if(i)}=1$
\item pour tout $k<i$, $e_{kf(i)}=0$. 
\end{enumerate}
\end{defi}

Dans sage, la matrice $U$ donnée par {\tt A.LU()} n'est pas échelonnée par
lignes, mais seulement triangulaire supérieure. Par contre, la commande {\tt
A.echelon\_form()} rend une matrice $E\in\mathcal M_{m,n}(K)$ échelonnée
réduite par lignes telle qu'il existe $G\in\Gl_m(K)$ vérifiant $A=GE$. On
peut souhaiter récupérer la matrice $G$. C'est utile par exemple pour
calculer l'image de $A$. La fonction {\tt extended\_echelon\_form} donne $E$
et $G$, sous la forme concaténée $(E|G)$. 

\Q Essayer la commande {\tt LU} sur
{\tt A=matrix(QQ,[[1,2,3],[3,2,1],[1,1,1]])}. 
On voit sur sa décomposition $LU$ que $A$ n'est pas inversible. En utilisant
cette décomposition, calculer $\im A$, $\ker A$, puis résoudre $AX=B$, où
$B=\hbox{}^t(1,2,3)$. Essayer aussi avec $B=\hbox{}^t(2,2,1)$. Retrouver ces
résultats en utilisant les commandes {\tt column\_space}, {\tt right\_kernel}, et
{\tt solve\_right}. \comment{(Ne pas oublier que {\tt kernel} et {\tt solve} sont à gauche par défaut.)}

\Q Soit
$A=
\begin{pmatrix}
0&1&2&1&1\\
0&1&2&0&2\\
0&2&4&3&1\\
0&-1&-2&3&0
\end{pmatrix}
$.
En utilisant les fonctions citées ci-dessus, Calculer 
$\ker A$ et $\im A$, puis résoudre $AX=B$, où
$B=\hbox{}^t(1,1,1,1)$, puis où $B=\hbox{}^t(1,1,2,0)$.

%%%%%%%%%%%%%%%%%%%%%
%% LU : expériences
%%%%%%%%%%%%%%%%%%%%%
\exo[LU : vérification expérimentale de la complexité]
\Q Quelle est la complexité asymptotique de la factorisation LU, en terme d'opérations dans le corps de base $K$ (en fonction de la dimension $n$ de la matrice).

\Q Vérifiez expérimentalement cette complexité, en prenant des matrices carrées au hasard dans $\mathbb{F}_7$ et en faisant augmenter la dimension (cf TD09).

%%%%%%%%%%%%%%%%%%%%%%
%% Décomposition QR
%%%%%%%%%%%%%%%%%%%%%%
\exo[Décomposition $QR$]
\label{QR}

\begin{theo}
Soit $A\in\Gl_n(\RM)$. Alors il existe une matrice triangulaire supérieure
$R$ dont les coefficients diagonaux sont strictement positifs et une matrice
orthogonale $Q$ telles que $A=QR$. De plus, cette décomposition est unique.
\end{theo}
Cette décomposition permet de ramener la résolution d'une équation $AX=B$ à
la résolution d'une équation triangulaire. En effet, si $A=QR$ est la
décomposition $QR$ de $A$ (supposée inversible), alors l'équation $AX=B$ est
équivalente à l'équation $RX=\hbox{}^tQB$.

Par exemple, on définit la matrice

\noindent{} {\tt A=matrix(ZZ,[[1,2,3],[1,-2,0],[-2,2,1 ]])}

Si on essaie {\tt A.QR()}, ça ne marche pas. Dans l'aide à la décomposition
$QR$, le corps de base utilisé est une clôture algébrique de $\QM$.
Essayons.

\noindent{} {\tt M3Qbar = MatrixSpace(QQbar,3,3); A = M3Qbar(A); A.QR()}

On doit trouver la décomposition $QR$ de $A$ (vérifier que $QR$ est
bien une approximation numérique de $A$).

Comme pour la décomposition $LU$, le théorème précédent se transpose au cas
où $A$ n'est pas inversible, et au cas où $A$ n'est pas carrée. Soit donc
$A\in\mathcal M_{m,n}(\RM)$. Il existe une décomposition $A=QR$, où
$Q\in\mathcal O_m(\RM)$ et où $R$ est une matrice \emph{échelonnée par lignes}
de $\mathcal M_{m,n}(\RM)$. Il n'y a pas unicité en général.

\smallskip

En utilisant la décomposition $QR$, retrouver les résultats déjà obtenus
ci-dessus (grâce à la décomposition $LU$ de $A$), pour
$A =
\begin{pmatrix}
1&2&3\\
3&2&1\\
1&1&1
\end{pmatrix}
$.

\section{Matrices à coefficients dans $\mathbb Z$}

\exo[Forme normale d'Hermite]

\begin{defi}\label{HNF}
Soit $E=(e_{ij})\in\mathcal M_{m,n}(\ZM)$ une matrice échelonnée par ligne de
rang $r$. Pour $i\in[[1,r]]$, on note $f(i)$ le plus petit entier tel que
$e_{if(i)}\ne0$ (c'est la fonction $f$ de la définition~\ref{echelons} du
paragraphe~\ref{LU}). Alors $E$ est dite \emph{échelonnée réduite}
si pour tout $i\in[[1,r]]$
\begin{itemize}
\item $e_{if(i)}>0$,
\item pour tout $k\in[[1,i-1]]$, $0\leq e_{k,f(i)}<e_{i,f(i)}$.
\end{itemize}
\end{defi}

\begin{theo}
Soit $A\in\mathcal M_{m,n}(\ZM)$. Il existe une unique matrice échelonnée
réduite $H$ de $\mathcal M_{m,n}(\ZM)$ et une matrice unimodulaire $U\in\Gl_n(\ZM)$ telles
que $A=UH$. La matrice $H$ s'appelle la forme normale d'Hermite de $A$.
\end{theo}

Cela s'obtient par des opérations sur les lignes, en utilisant la relation de
Bézout sur $\ZM$, et donc l'algorithme d'Euclide étendu (une des briques de base pour ce calcul est ce qu'on a fait dans l'exercice $2$ du TD7).

En sage, pour calculer la forme normale d'Hermite d'une matrice entière $A$, on utilise {\tt A.hermite\_form()}. Si on veut obtenir la matrice unimodulaire $U$ en plus de la forme normale de Hermite $H$, on peut utiliser {\tt A.hermite\_form(transformation = True)} (c'est rappelé dans l'aide).

\subsection*{Applications}

\subsubsection*{Équation diophantienne linéaire}

On veut trouver les solutions entières de l'équation
$$2x_1+3x_2+5x_3=0,$$
c'est-à-dire
$AX=0$, où $A=(2,3,5)$. Ici, la matrice $A$ est échelonnée
par lignes, mais cela ne nous aide pas. Il vaut mieux
l'échelonner par colonnes, en appliquant {\tt hermite\_form}
à la transposée de $A$. On trouve alors une matrice $U$ de
$\Gl_3(\ZM)$ et un entier $a$ tels que
$AU=(a,0,0)$. En écrivant $X=UY$, on est amené à résoudre
$$(1,0,0)Y=0.$$ 
On trouve alors l'ensemble des solutions grâce à l'expression $X=UY$.

Essayez aussi la commande {\tt kernel} (ou {\tt right\_kernel}).

\subsubsection*{Système d'équations diophantiennes linéaires}

Choisir une matrice au hasard $A$ dans $\mathcal M_{3,4}(\ZM)$ et un vecteur
$B$ au hasard dans $\mathcal M_{3,1}(\ZM)$, et résoudre l'équation $AX=B$
dans $\ZM$.

\iffalse
\subsubsection*{Compléter une base}
On rappelle qu'un vecteur $(a_1,\dots,a_n)$ de $\mathbb Z^n$
est primitif si et seulement si $\pgcd(a_1,\dots,a_n)=1$.
\begin{prop}
Un vecteur de $\mathbb Z^n$ peut être
complété en une base de $\mathbb Z^n$ si et seulement si
il est primitif.
\end{prop}

Pour montrer ce résultat, on peut utiliser la forme normale
d'Hermite. Cette forme normale d'Hermite peut aussi servir
pour construire effectivement une telle base.

Par exemple, pour compléter $a=(6,20,15)$ en une base de
$\mathbb Z^3$, on cherche $G\in\hbox{GL}_3(\mathbb Z)$
telle que $AG=(1,0,0)$. Si les $l_i$ sont les lignes
de $G^{-1}$, alors $l_1=a$ et $(l_1,l_2,l_3)$ est une base de
$\mathbb Z^3$.
\fi

\end{document}
