\documentclass[12pt]{amsart}
\usepackage{url, a4, amsmath, amsfonts, amsthm, amssymb, amscd}
\usepackage[noend]{algorithmic}
\usepackage{kbexo}
\course{PIN 401}
\num{2\text{ (complément)}}

\def\B{\mathcal{B}}
\def\M{\mathcal{M}}
\def\Mat{\mathrm{Mat}}

\makeatletter
\renewcommand{\algorithmicrequire}{\textbf{Entrée:}}
\renewcommand{\algorithmicensure}{\textbf{Sortie:}}
\renewcommand{\algorithmiccomment}[1]{\quad\{\emph{#1}\}}

\renewcommand{\algorithmicend}{\textbf{fin}}
\renewcommand{\algorithmicif}{\textbf{si}}
\renewcommand{\algorithmicthen}{\textbf{alors}}
\renewcommand{\algorithmicelse}{\textbf{sinon}}
\renewcommand{\algorithmicelsif}{\algorithmicelse\ \algorithmicif}
\renewcommand{\algorithmicendif}{\algorithmicend\ \algorithmicif}
\renewcommand{\algorithmicfor}{\textbf{pour}}
\renewcommand{\algorithmicforall}{\textbf{pour tout}}
\renewcommand{\algorithmicdo}{\textbf{effectuer}}
\renewcommand{\algorithmicendfor}{\algorithmicend\ \algorithmicfor}
\renewcommand{\algorithmicwhile}{\textbf{tant que}}
\renewcommand{\algorithmicendwhile}{\algorithmicend\ \algorithmicwhile}
\renewcommand{\ALG@name}{Algorithme}
\def\thealgorithm{.}

\begin{document}\exotitle

\bigskip
\noindent Le but de ce document est de montrer à moindre frais comment on
peut formaliser et systématiser les notions et opérations vues en TD sur
des exemples. Il n'est pas question ici de minimiser le nombre
d'opérations dans le corps $K$ ($= \RM$ ou~$\CM$) ou l'erreur numérique.
Si $M$ est une matrice dont la plus grande dimension (lignes ou colonnes)
est $n$, toutes les algorithmes qui suivent utilisent $O(n^3)$ opérations
dans $K$ (de type $\pm,\times,/$). On peut faire mieux si $n$ est grand,
mais en particulier si la matrice $M$ est très
structurée\footnote{Beaucoup de $0$ dans des positions faciles à décrire,
par exemple $M$ diagonale!}.

\section{Opérations sur les colonnes (image)}

\begin{defi} La matrice $m\times n$ ($m$ lignes et $n$ colonnes)
$M = (M_{i,j})$
est \emph{échelonnée en colonnes} s'il existe une application strictement
croissante $f:[1,n]\to [1,m]$ telle que
\begin{itemize}
\item Pour $1 \leq j \leq n$, on a $M_{f(j), j} = 1$
\quad($M_{f(j),j}\neq 0$ nous suffirait),
\item Pour $i < f(j)$, on a $M_{i,j} = 0$,
\item Pour $k > j$, on a $M_{f(j), k} = 0$.
\end{itemize}
Les $M_{f(j),j} = 1$, pour $j = 1,\dots, n$ sont les \emph{pivots} de $M$.
En d'autres termes, à droite (même ligne) et au dessus (même colonne) d'un
pivot, il n'y a que des $0$, et les pivots forment une ligne brisée
décroissante; $f(j)$ donne la ligne du $j$-ème pivot (celui de la $j$-ème
colonne).
\end{defi}
Exemple: ici, $f(1) = 1$, $f(2) = 3$, $f(3) = 5$, $f(4) = 6$.
$$
\begin{pmatrix}
1 &    0    & 0 & 0  \\
\times&  0    & 0 & 0  \\
\times& 1   & 0 & 0  \\
\times& \times& 0 & 0  \\
\times& \times& 1& 0 \\
\times& \times&\times& 1  \\
\times& \times&\times&\times\\
\end{pmatrix}
$$
On note $M_{i,\bullet}$ la $i$-ème ligne et $M_{\bullet,j}$ la $j$-ème colonne de $M$.
\begin{theo} Les colonnes d'une matrice échelonnée en colonnes forment une
famille libre.
\end{theo}
\begin{proof}
Si $\lambda_1 M_{\bullet,1} + \dots \lambda_n M_{\bullet,n} = 0$, alors
la ligne d'indice $f(1)$ dit $\lambda_1 + 0+\dots +0 = 0$, soit
$\lambda_1 = 0$. De proche en proche on prouve que les $\lambda_i$ sont
tous nuls.
\end{proof}

\begin{algorithm}[H]
\caption{Image d'une application linéaire $\phi$}
\begin{algorithmic}[1]
\REQUIRE $M = (M_{i,j}) \in \M_{m \times n}(K)$ la matrice $\Mat(\phi,\B,\B')$.
\ENSURE Une base échelonnée en colonnes de $\im\phi$ (donnée dans la base~$\B'$).
\STATE Poser $j\leftarrow 0$.
\FOR[on traite la ligne $i$]{$i=1, 2, \dots , m$}
  \IF[un pivot sur cette ligne ?]{il existe $p > j$, tel que $M_{i,p}
\neq 0$}
    \STATE Choisir $p$ tel que $M_{i,p}\neq 0$ comme \emph{pivot}. Par
    exemple, $\abs{M_{i,p}}$ minimal.
    \STATE Poser $j \leftarrow j+1$.
    \STATE Échanger les colonnes $M_{\bullet,p}$ et $M_{\bullet,j}$.
    \STATE Diviser la colonne $M_{\bullet,j}$ par $M_{i,j}$.
    \COMMENT{le pivot $M_{i,j}$ est en place, $f(j) = i$}
    \FOR[annuler $M_{i,k}$ en utilisant $M_{i, j}=1$]{$k = j+1, \dots, n $}
      \STATE $M_{\bullet,k}\leftarrow M_{\bullet,k} - M_{i,k} \times M_{\bullet,j}$
    \ENDFOR
  \ENDIF
\ENDFOR
\STATE Retourner les $j$ premières colonnes de $M$. L'image est de
dimension~$j$.
\end{algorithmic}
\end{algorithm}
\noindent Comme $p > j$ lors du choix du pivot, la
colonne $p$ ne contient pas déjà un pivot.

\section{Opérations sur les lignes (noyau)}

\begin{defi} La matrice $m\times n$ ($m$ lignes et $n$ colonnes) $M =
(M_{i,j})$ est \emph{échelonnée en lignes} si sa transposée $(M_{j,i})$
est échelonnée en colonnes.

Autrement dit, s'il existe une application strictement croissante $g:[1,m]\to
[1,n]$ telle que
\begin{itemize}
\item Pour $1 \leq i \leq m$, on a $M_{i, g(i)} = 1$
\quad($M_{i, g(i)}\neq 0$ nous suffirait),
\item Pour $j < g(i)$, on a $M_{i,j} = 0$,
\item Pour $k > i$, on a $M_{k, g(i)} = 0$.
\end{itemize}
Les $M_{i, g(i)} = 1$, pour $i = 1,\dots, m$ sont les \emph{pivots} de $M$.
En d'autres termes, à gauche (même ligne) et en dessous (même colonne) d'un
pivot, il n'y a que des $0$, et les pivots forment une ligne brisée
décroissante; $g(i)$ donne la colonne du $i$-ème pivot (celui de la $i$-ème
ligne).
\end{defi}
Exemple: ici $g(1) = 2$, $g(2) = 3$, $g(3) = 5$.
$$
\begin{pmatrix}
0   & 1  & \times & \times & \times  \\
 0  &   0    & 1    & \times & \times  \\
 0  &   0    & 0      &  0     & 1     \\
\end{pmatrix}
$$

\begin{theo} Les lignes d'une matrice échelonnée en lignes forment une famille
libre.
\end{theo}

\begin{algorithm}[H]
\caption{Noyau d'une application linéaire $\phi$ (version partielle)}
\begin{algorithmic}[1]
\REQUIRE $M = (M_{i,j}) \in \M_{m \times n}(K)$ la matrice $\Mat(\phi,\B,\B')$.
\ENSURE Une matrice échelonnée en lignes qui a le même noyau que $M$.
\STATE Poser $i\leftarrow 0$.
\FOR[on traite la colonne $j$]{$j=1, 2, \dots , m$}
  \IF[un pivot sur cette colonne ?]{il existe $p > i$, tel que $M_{p,j}
    \neq 0$}
    \STATE\COMMENT{Comme $p > i$, la ligne $p$ ne contient pas
                   déjà un pivot}
    \STATE Choisir $p$ tel que $M_{p,j}\neq 0$ comme \emph{pivot}. Par
    exemple, $\abs{M_{p,j}}$ minimal.
    \STATE Poser $i \leftarrow i+1$.
    \STATE Échanger les lignes $M_{p,\bullet}$ et $M_{i,\bullet}$.
    \STATE Diviser la ligne $M_{j,\bullet}$ par $M_{i,j}$.
    \COMMENT{le pivot $M_{i,j}$ est en place, $g(i) = j$}
    \FOR[annuler $M_{k,j}$ en utilisant $M_{i, j}=1$]{$k = i+1, \dots, m $}
      \STATE $M_{k,\bullet}\leftarrow M_{k,\bullet} - M_{k,j} \times M_{i,\bullet}$
    \ENDFOR
  \ENDIF
\ENDFOR
\STATE Retourner les $i$ premières lignes de $M$. Le noyau est de
dimension~$n-i$.
\end{algorithmic}
\end{algorithm}
\noindent Comme $p > j$ lors du choix du pivot, la
ligne $p$ ne contient pas déjà un pivot. Jusqu'ici c'est l'exact
pendant des opérations sur les colonnes utilisées pour calculer l'image.
Si on veut expliciter l'obtention d'une base du noyau, en particulier
distinguer variables liées et paramètres libres, il faut poursuivre:
\begin{algorithm}[H]
\caption{Noyau d'une application linéaire $\phi$}
\begin{algorithmic}[1]
\REQUIRE Une matrice $M$ échelonnée en lignes de même noyau que
$\Mat(\phi,\B,\B')$.
\ENSURE Une base échelonnée en lignes de $\ker\phi$ (donnée dans la base~$\B$).
\FOR{$x = i, i-1,\dots, 2 $}
\FOR[annuler $M_{h,g(x)}$ utilisant $M_{x, g(x)}=1$]{$h = 1,\dots,x-1$}
  \STATE $M_{h,\bullet}\leftarrow M_{h,\bullet} - M_{h,g(x)} \times M_{x,\bullet}$
\ENDFOR
\ENDFOR
\STATE\{\emph{Maintenant les colonnes des pivots ont tous leurs autres
coefficients à $0$.}\}
\STATE Les vecteurs $(a_1,\dots,a_n)$ éléments du noyau vérifient
$$-a_{g(x)} = M_{x, g(x)+1} a_{g(x)+1} + \dots + M_{x, n} a_n,
\quad\text{pour $x = 1,\dots, i$}.
$$
Les $i$ variables $a_{g(1)},\dots, a_{g(i)}$ sont liées, les autres sont
des paramètres libres: le noyau est de dimension $n-i$. Si on veut
afficher explicitement une base (échelonnée en lignes):
\FOR{$y = 1,\dots, n$}
  \IF[pas de pivot en colonne $y$]{$y$ n'est pas de la forme $g(x)$}
    \STATE Afficher le vecteur $A= (a_1,\dots,a_n)$ dont les coordonnées sont
    $$a_j = \begin{cases}
            -1 & \text{si $j = y$}\\
      M_{x,j} & \text{si $j = g(x)$}\\
      0       & \text{sinon}.
    \end{cases}$$
  \ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}
\noindent À la réflexion, mise sous forme échelonnée ligne et colonne
sont essentiellement équivalentes: on passe de l'un à l'autre algorithme
en travaillant sur la transposée de $M$. Il paraît naturel d'éviter de
faire \emph{deux} calculs très analogues si on a besoin de l'image
\emph{et} du noyau. On adapte le premier algorithme (image), qui fait des
opérations élémentaires sur les colonnes\footnote{On pourrait très bien
adapter l'autre, qui fait des opérations élémentaires sur les lignes.}.
L'idée est d'effectuer ces opérations sur $M$, en en gardant la trace sur
une matrice auxiliaire $U$, grâce au principe suivant
\begin{theo} Initialement $U = \id_n$, $M = A\in \M_{m\times n}(K)$.
Si on effectue la \emph{même} suite d'opérations sur les 
\emph{colonnes}
de $M$ et de $U$, alors on a toujours $A U = M$. La matrice $U$ est
toujours inversible.
\end{theo}
\noindent 
L'algorithme correspondant est plus compliqué que noyau/image, et on
va en donner une forme inefficace. Le but est de mettre la matrice $M$
sous une forme facilement utilisable. Pas seulement pour le calcul du
noyau (échelonnée en lignes) ou de l'image (échelonnée en colonnes), pour
lesquels ce qui précède est «optimal».

On s'inspire du calcul de l'image, et on va écrire $MU = (H|0)$, où $H$
est échelonnée en colonnes suivie de colonnes de $0$.
\begin{rem}
Ce n'est pas forcément assez général : pour répondre à une question sur
$M$, il faudra répondre à une question sur $U$, qui n'a pas de forme
particulièrement simple. En particulier, cette forme est adéquate pour le
calcul de noyau et image, et la résolution de systèmes linéaires (en
particulier le calcul de l'inverse quand $M$ est carrée). Elle ne l'est
pas pour le calcul du déterminant.

%On peut rajouter la possibilité d'échanger des lignes de $M$, ce qui
%permet d'imposer que la fonction $f:[1,n]\to[1,m]$ vérifie $f(j) = j$
%pour $j\leq m$, i.e.~la ligne brisée de pivots est ininterrompue, et
%surtout $U$ devient \emph{triangulaire}. On obtiendrait une
%identité de la forme $PMU = (H|0)$, dont on peut facilement déduire le
%déterminant de $M$ (on prouve que $\det P = \pm 1$ et est facile à
%calculer).
\end{rem}

Pour résoudre le système linéaire $MX = Y$, d'inconnue $X$, on l'écrit
$$(MU)U^{-1}X = Y.$$
On résout $(H|0)Z = Y$, d'inconnue $Z$, qui est facile et on retourne $X
= UZ$. C'est plus intéressant que la méthode classique dès que l'on veut
résoudre plusieurs systèmes pour la même matrice $M$, mais en variant le
second membre $Y$. Par exemple pour calculer $M^{-1}$.

\begin{algorithm}
\caption{«Simplification» d'une application linéaire $\phi$
(pour noyau, image, systèmes\dots)}
\begin{algorithmic}[1]
\REQUIRE $M = (M_{i,j}) \in \M_{m \times n}(K)$ la matrice $\Mat(\phi,\B,\B')$.
\ENSURE Une matrice inversible $U$, une matrice échelonnée en colonnes
$H$ telle que $MU = (H|0)$.
\STATE\{\emph{On met $M$ sous forme échelonnée en colonnes. On garde
trace des opérations sur les colonnes dans $U$.
Si initialement $M = A$, on a toujours $AU = M$.}\}
\STATE Poser $j\leftarrow 0$, $U\leftarrow \id_n$.
\FOR[on traite la ligne $i$]{$i=1, 2, \dots , m$}
  \IF[un pivot sur cette ligne ?]{il existe $p > j$, tel que $M_{i,p} \neq 0$}
    \STATE Choisir $p$ tel que $M_{i,p}\neq 0$ comme \emph{pivot}. Par
    exemple, $\abs{M_{i,p}}$ minimal.
    \STATE Poser $j\leftarrow j+1$.
    \STATE Échanger les colonnes $M_{\bullet,p}$ et $M_{\bullet,j}$, puis
           $U_{\bullet,p}$ et $U_{\bullet,j}$.
    \STATE Diviser les colonnes $M_{\bullet,j}$ et $U_{\bullet,j}$
           par $M_{i,j}$
    \COMMENT{le pivot $M_{i,j}$ est en place}
    \FOR[annuler $M_{i,k}$ en utilisant $M_{i, j}=1$]{$k = j+1, \dots, n $}
      \STATE $M_{\bullet,k}\leftarrow M_{\bullet,k} - M_{i,k} \times M_{\bullet,j}$
      \STATE $U_{\bullet,k}\leftarrow U_{\bullet,k} - U_{i,k} \times U_{\bullet,j}$
    \ENDFOR
  \ENDIF
\ENDFOR
\STATE Retourner $U$ et $H\leftarrow$ (les $i$ premières colonnes de
$M$). L'image est de dimension~$i$, donnée par $H$; le noyau est de
dimension $n-i$, donné par les $n-i$ dernières colonnes de $U$.
\end{algorithmic}
\end{algorithm}
\end{document}
