\modenormal

\chapterimage{lena_couleur}
\chaptertext{%{\small 
Aujourd'hui,  des  mathématiques  concrètes  vont  nous  permettre  de
réduire,   agrandir,   assombrir,  éclaircir,   compresser,   bruiter,
quantifier,... une photo. Pour cela,  il existe des méthodes provenant
de  la théorie  du signal  et des  mathématiques continues.  Nous nous
pencherons plutôt sur  des méthodes plus légères  basées sur l'algèbre
linéaire  et l'analyse  matricielle.   Une image  sera  pour nous  une
matrice  carrée de  taille $2^9$  à coefficients  dans $\llbracket  0,
2^9-1\rrbracket$.  Cela manque de charme?  C'est sans compter sur Lena
qui depuis quarante ans rend les maths sexy (la population hantant les
laboratoires  mathématiques   et  surtout  informatiques   est  plutôt
masculine ...).

Nous   étudierons  pour   cela   la  \og   Décomposition  en   Valeurs
Singulières\fg{} qui apparaît de nos jours comme un couteau suisse des
problèmes linéaires:  en traitement  de l'image et  de tout  signal en
général, en  reconnaissance des formes, en  robotique, en statistique,
en  étude  du  langage  naturel,  en  géologie,  en  météorologie,  en
dynamique des structures, en....

Dans  quel domaine  travaille-t-on alors:  algèbre linéaire,  analyse,
probabilités, topologie, informatique...? %  Un peu de tout cela et d'autres choses
% encore: cela s'appelle la mathématique.%}
}


\chapter{Dessine-moi une matrice...}





\section{Lena}

\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{kahan}
\caption{W. \bsc{Kahan (né en 1933)}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.35cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}


Nous  allons travailler  avec  des  images qui  sont  des matrices  de
niveaux de gris.  Notre belle amie Léna sera représentée par une matrice
carrée de  taille $2^9$ ce qui  permet de reproduire Léna  à l'aide de
$2^{18}=262\,144$  pixels. Léna  prend alors  beaucoup de  place. Nous
allons tenter de  compresser la pauvre Léna sans pour  cela qu'elle ne
perde sa qualité  graphique. Une des méthodes les  plus abordables est
d'utiliser la décomposition d'une matrice en valeurs singulières.

C'est   un    sujet   extrêmement   riche   qui    a   de   nombreuses
applications.  L'algorithme que  nous  utiliserons (mais  que nous  ne
détaillerons pas) a été mis au point par deux très éminents chercheurs en 1965
(Gene   \textsc{Golub},   états-unien   et   William   \textsc{Kahan},
canadien, père de la norme  IEEE-754). Il s'agit donc de mathématiques
assez récentes, au moins en comparaison avec votre programme...


La petite histoire  dit que des chercheurs  américains de l'University
of Southern California étaient pressés de trouver une image de taille
$2^{18}$ pixels pour leur conférence.  Passe alors un de leurs
collègues avec, en bon informaticien, le dernier Playboy sous le bras.
Ils décidèrent alors 
d'utiliser le poster central de la Playmate comme support...

 La photo originale est ici:
 \href{http://www.lenna.org/full/len\_full.html}{http://www.lenna.org/full/len\_full.html}
 mais nous n'utiliserons  que la partie scannée par  les chercheurs, de
 taille $5.12 \mathrm{in}\times 5.12 \mathrm{in}$...




\section{La SVD}

\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{eckart}
\caption{C. \bsc{Eckart (1902-1973)}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-6.35cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}


\subsection{Le théorème}

Un théorème démontré officiellement en 1936 par Carl \textsc{Eckart}
et Gale \textsc{Young} affirme alors que toute matrice rectangulaire A se
décompose sous la forme:

$$A = U \times S \times \tr V$$

avec U et  V des matrices orthogonales et S  une matrice nulle partout
sauf sur sa diagonale principale  qui contient les valeurs singulières
de A  rangées dans  l'ordre décroissant. \textsc{Sylvester}  s'y était
déjà  intéressé pour  des matrices  carrées  réelles en  1889 mais  ce
résultat a semblé n'intéresser personne pendant des années. 


Le court article de \textsc{Eckart} et \textsc{Young} est disponible à
l'adresse suivante: 

{\small
\href{http://projecteuclid.org/DPubS?service=UI\&version=1.0\&verb=Display\&handle=euclid.bams/1183501633}{http://projecteuclid.org/DPubS?service=UI\&version=1.0\&verb=Display\&handle=euclid.bams/1183501633}.
}
Ce qui est  remarquable, c'est que n'importe quelle  matrice admet une
telle  décomposition, alors  que la  décomposition en  valeurs propres
(la  diagonalisation d'une  matrice) n'est  pas toujours  possible. Et
quand  on  dit n'importe  quelle  matrice,  on  ne rigole  pas:  toute
matrice, même rectangulaire. C'est vraiment très puissant et à la fois
simple mais cette décomposition  n'a trouvé d'applications importantes
qu'assez récemment (ce  qui veut dire après 1899 à  l'échelle de votre
programme de prépa...) ce qui explique peut-être qu'on en parle si peu
en premier cycle.


Cependant,  la   décomposition  en  éléments  singuliers   utilise  la
décomposition en éléments propres.



Notons $r$ le rang  de A et $U_i$ et $V_i$ les  vecteurs colonnes de U
et V. La décomposition s'écrit:


$$A=
\begin{pmatrix}
  U_1&U_2&\cdots &U_r&\cdots & U_m
\end{pmatrix}
\times
\begin{pmatrix}
  \sigma_1& & & &\\
    &\ddots & & & \\
   & &\sigma_r & &\\
   & & &\ddots &\\
   & & & & 0
\end{pmatrix}
\times
\begin{pmatrix}
  \tr V_1\\
  \vdots\\
  \tr V_r\\
  \vdots\\
  \tr V_n
\end{pmatrix}
$$

ou formulé autrement:



\begin{eqnarray*}
A  &=&  \sigma_1\cdot  U_1\times  \tr  V_1+\sigma_2\cdot  U_2\times  \tr
V_2+\cdots+\sigma_r\cdot  U_r\times \tr  V_r+0\cdot U_{r+1}\times  \tr
V_{r+1}+\cdots\\
&=&\sigma_1\cdot  U_1\times  \tr  V_1+\sigma_2\cdot  U_2\times  \tr
V_2+\cdots+\sigma_r\cdot  U_r\times \tr  V_r
\end{eqnarray*}


Il  faut ensuite  se souvenir  que  les $\sigma_i$  sont classés  dans
l'ordre  décroissant ce  qui va  avoir des  applications importantes  en
informatique.


\subsection{Interprétation géométrique}


Comment interpréter géométriquement ce résultat? Considérez une sphère
de rayon 1:  que devient-elle transformée par A, i.e.  par $U \times S
\times \tr V$? Faites un petit dessin en dimension 2.
Que vaut $\Vert A\Vert_2 =\displaystyle \max_{\Vert x\Vert =1}\Vert Ax\Vert_2$?

Afin de répondre, un peu de vocabulaire d'abord.  On a $AV_i=\sigma_i U_i$: on dit alors
que $U_i$ est un vecteur singulier  à gauche pour la valeur singulière
$\sigma_i$.

De même $\tr A U_i =\sigma_i V_i$  et $V_i$ est un vecteur singulier à
droite  pour la  valeur singulière  $\sigma_i$. Les  bases $(u_i)$  et
$(V_i)$ sont orthonormées: si l'on exprime la matrice de l'application
linéaire  associée   à  A  dans   ces  bases,  que   pouvez-vous  dire
géométriquement?




\subsection{Un exemple simple}


On suppose  que la SVD d'une  matrice A de taille  $m\times n$ s'écrit
$U\times S \times \tr V$.

\begin{enumerate}
\item  Quelles sont  les  dimensions de  U et  V?  Que pensez-vous  de
  $A\times \tr A$?  Que représentent les
  colonnes de U pour $A\times \tr A$?. Et les colonnes de V pour $\tr A\times A$.
\item Calculez (à la main...) la SVD de $A=
  \begin{pmatrix}
    2&-2\\
    1&1
  \end{pmatrix}
$.

\item Shoot again avec $
  \begin{pmatrix}
    3&1&1\\
    -1&3&1
  \end{pmatrix}
$
\end{enumerate}


Quels liens existent entre la SVD et la recherche des éléments propres
d'une  matrice?  Avec le  théorème  spectral?  Vaut-il mieux  utiliser
$A\times \tr A$ ou $\tr A\times A$?


\subsection{Approximation de rang minimum d'une matrice}


Dans  de  nombreux  domaines,  on  doit  travailler  avec  de  grosses
matrices. Il est alors très important de déterminer une matrice $\widetilde{A_s}$ de
même taille qu'une matrice A mais de rang $s$ inférieur au rang $r$ de
A et qui minimise
l'erreur commise pour  une certaine norme (qui est le  plus souvent la
norme de  \textsc{Frobenius}, i.e.  la racine carrée  de la  somme des
carrés des  coefficients). Le théorème  d'\textsc{Eckart-Young} permet
alors de dire que:

$$\min_{{\rm   rg}(X)\leqslant  s}\Vert   A-X\Vert_F=\Vert
A-\widetilde{A_s}\Vert_F= \sqrt{\sum_{j=s+1}^r \sigma_j^2(A)}$$


avec $\widetilde{A_s}=\sigma_1\cdot  U_1\times  \tr  V_1+\sigma_2\cdot  U_2\times  \tr
V_2+\cdots+\sigma_s\cdot  U_s\times \tr  V_s$:  on  considère que  les
éléments diagonaux de A sont  nuls en-dessous d'un certain seuil. Nous
allons l'illustrer informatiquement  à défaut de le  démonter. On voit
tout de  suite des conséquences  pratiques, que nous  allons également
illustrer informatiquement dans le cas de la compression des images.



\section{Manipulation d'images}

\subsection{Quelques fonctions Python}

Python contient une  matrice carrée de taille 512 contenant  les niveaux de gris
représentant Lena. Il suffit de cherger les bonnes bibliothèques:
\pythonc

\begin{pythoncode}
from pylab import *
from scipy import misc

l = misc.lena()
imshow(l,cmap=cm.gray)
\end{pythoncode}

Lena est bien une matrice:


\begin{pythoncode}
In [8]: type(l)
Out[8]: numpy.ndarray

In [9]: shape(l)
Out[9]: (512, 512)
\end{pythoncode}

On peut préférer travailler sur une photo de format jpg (qui sera à l’envers) ou
png (qui  sera à l’endroit).  Python la transforme  en matrice avec  la fonction
imread.  La matrice  obtenue est  en  RVB :  chaque coefficient  est un  vecteur
(R,V,B). On la convertit  en niveau de gris par exemple  en calculant la moyenne
des trois couleurs.

On récupère d'abord une image:

\begin{pythoncode}
In [4]: from urllib.request import urlretrieve

In [5]: urlretrieve('http://download.tuxfamily.org/tehessinmath/les_images/marty.png','marty.png')
Out[5]: ('marty.png', <http.client.HTTPMessage at 0x7f3aeeb5fa20>)
\end{pythoncode}

et on la transforme en matrice:

\begin{pythoncode}
tm = imread('marty.png')

def rvb_to_gray(m):
    r = len(m)
    c = len(m[0])
    return(array([[m[i,j][0] for j in range(c)] for i in range(r)]))

marty = rvb_to_gray(tm)
\end{pythoncode}


\subsection{Manipulations basiques}

Comment obtenir les images suivantes:

\begin{multicols}{2}
  \begin{center}
  \includegraphics[height=3cm]{lena_miroir}
\end{center}
\begin{center}
  \includegraphics[height=3cm]{lena_retourne}
\end{center}
\end{multicols}

Sachant que l'échelle de gris est celle-ci:


%\begin{figure}
\begin{center}
  \includegraphics[width=0.8\linewidth]{grayscale}
\end{center}
%\end{figure}

comment obtenir les images suivantes:

\begin{multicols}{3}
   \begin{center}
  \includegraphics[height=4cm]{lena_foncee}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_claire}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_neg}
\end{center}

\end{multicols}


\subsection{Gagner de la place}


Une matrice de taille $2^9$ contient $2^{18}$ entiers codés entre 0 et
$2^8-1$ ce  qui prend pas mal  de place en mémoire.  Peut-on être plus
économique sans pour cela diminuer la qualité esthétique de la photo?

\subsubsection{Résolution}

La première idée est de prendre  de plus gros pixels, c'est-à-dire une
matrice plus petite: on extrait par exemple régulièrement un pixel sur
$k$ (en choisissant $k$ parmi une puissance de 2 inférieure à $2^9$).

Comment obtenir par exemple ces images?

\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{lena_64}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_128}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_256}
\end{center}
%\end{figure}
\end{multicols}



\subsubsection{Quantification}

On peut également  réduire le nombre de niveaux de  gris en regroupant
par exemple tous les niveaux entre 0 et 63 en un seul niveau 0, puis 64
à 127 en 64, 128 à 191 en 128, 192 à 256 en 192.

Par exemple, avec 4, 8 puis 16 niveaux:





\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{lena_q4}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_q8}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_q16}
\end{center}
%\end{figure}
\end{multicols}







\subsubsection{Compression et SVD}

Tout  langage  orienté  calcul  comprend  des  fonctions  liées  à  la
décomposition en éléments simples.  

Python a  sa fonction  \lstinline+linalg.svd(mat)+ qui renvoie la décomposition en
valeurs singulières sous la forme du triplet U, S et V.


En  vous  inspirant  des   commentaires  faits  dans  les  paragraphes
précédents sur la SVD, expliquez comment cette décomposition permet de
compresser une image. Quantifiez également le niveau de compression.

Voici trois niveaux de compression:


\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{lena_svd10}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_svd25}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_svd50}
\end{center}
%\end{figure}
\end{multicols}



\subsection{Enlever le bruit}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{shannon}
\caption{C.E. \bsc{Shannon (1916-2001)}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-2.9cm}
\begin{minipage}[t]{\linewidth}

La transmission  d'informations a toujours posé  des problèmes: voleurs
de grands  chemins, poteaux télégraphiques sciés,  attaques d'indiens,
etc.

Claude    Elwood    \textsc{Shannon}    (1916    -    2001)    est    un
mathématicien-inventeur-jongleur américain qui,  suite à son article \og
\textit{A mathematical theory of communications}\fg{} paru en 1948, est
considéré comme le fondateur de la
\textit{théorie  de  l'information}  qui  est  bien sûr  une  des  bases
de...l'\textit{informatique}.
\end{minipage}

L'idée est d'étudier et de quantifier l'\og information\fg{} émise et
reçue:  quelle est la  compression maximale  de données  digitales? Quel
débit choisir pour transmettre un message dans un canal \og bruité\fg{}?
Quel est le niveau de sûreté d'un chiffrement?...

La  théorie de  l'information  de \textsc{Shannon}  est  fondée sur  des
modèles probabilistes:  leur étude  est donc un  préalable à  l'étude de
problèmes   de  réseaux,   d'intelligence   artificielle,  de   systèmes
complexes. 

Par   exemple,   dans   le   schéma  de   communication   présenté   par
\textsc{Shannon}, la  source et le destinataire  d'une information étant
séparés, des perturbations peuvent créer une différence entre le message
émis et le message reçu.   Ces perturbations (bruit de fond thermique ou
accoustique, erreurs d'écriture ou de lecture, etc.) sont de nature
\textit{aléatoire}:  il n'est  pas possible  de prévoir  leur  effet. De
plus, le message  source est par nature \textit{imprévisible} du  point de vue du
destinataire (sinon, à quoi bon le transmettre). 

\textsc{Shannon}  a  également  emprunté   à  la  physique  la  notion
d'entropie   pour   mesurer   le  désordre   de   cette   transmission
d'information, cette même notion d'entropie  qui a inspiré notre héros
national, Cédric \textsc{Villani}... 


Mais revenons à Lena. Nous allons simuler une Lena bruitée:

\begin{pythoncode}
from random import *
def ber(p):
    if random() < p:
        return 1
    else:
        return 0
    
def bruit(m,p):
    r = len(m)
    c = len(m[0]) 
    return(array([[(m[i,j] + randint(0,255)*ber(p))%256 for j in range(c)] for i in range(r)]))
\end{pythoncode}


Il existe de nombreuses méthodes, certaines très élaborées, permettant
de minimiser  ce bruit. Une des  plus simples est de  remplacer chaque
pixel par la  moyenne de lui-même et de ses  8 autres voisins directs,
voire aussi ses  24 voisins directs et indirect, voire  plus, ou de la
médiane de  ces séries  de \og  cercles\fg{} concentriques  de pixels,
comme on  le voit  sur cette figure  (extraite du  site \texttt{Images
  des mathématiques}):



%\begin{figure}
\begin{center}
  \includegraphics[height=2.25cm]{mean_pix}
\end{center}
%\end{figure}

Créez  des fonctions    qui feront  le  boulot. Vous  utiliserez
\texttt{mean} et \texttt{median} pour obtenir par exemple:





\setindent{1cm}
\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=3.8cm]{lena_bruit}
\end{center}
\begin{center}
  \includegraphics[height=3.8cm]{lena_mean}
\end{center}
\begin{center}
  \includegraphics[height=3.8cm]{lena_median}
\end{center}
%\end{figure}
\end{multicols}
\setindent{\indentationcours}

où l'on  trouve de gauche à  droite l'image bruitée originale  puis sa
correction par moyenne sur 25 pixels et par médiane sur 9 pixels.


\subsection{Détection de bords}


Pour  sélectionner  des objets  sur  une  image,  on peut  essayer  de
détecter leurs bords, i.e. des  zones de brusque changement de niveaux
de gris.

On  remplace alors  un pixel  par une  mesure des  écarts des  voisins
immédiats donnée par exemple par:

$$\sqrt{ \left(m_{i,j+1}-m_{i,j-1}\right)^2+ \left(m_{i+1,j}-m_{i-1,j}\right)^2
}$$

On obtient alors au choix:


\begin{multicols}{2}
%\begin{figure}
\begin{center}
  \includegraphics[height=4.5cm]{lena_contour}
\end{center}

\begin{center}
  \includegraphics[height=4.5cm]{lena_contour_blanc}
\end{center}
%\end{figure}
\end{multicols}




\section{Chiffrement de Hill}



Nous  allons  à présent  utiliser  nos  outils  de calcul  matriciel  en
cryptographie. En  1929, Lester \textsc{Hill} (1891 - 1961) proposa une
méthode  de chiffrement  par blocs  de lettres  en travaillant  avec des
matrices à  coefficients dans $\bbz/26\bbz$  (combien y a-t-il  de lettres
dans notre alphabet?).  Par la suite nous noterons $\bbz_{n}$ l'ensemble
$\bbz/n\bbz$. Cela a ouvert le domaine de la cryptographie algébrique et
de   nos  jours,   c'est   l'\textsc{Aes}  (\textit{Advanced   Encrypting
  Standard}),  né  en  2000,  qui  assure la  majorité  de  la  sécurité
informatique.


Nous allons explorer cette
méthode en travaillant sur tous les caractères affichables en ASCII.

\subsubsection{Codage}\label{code_ascii}



Chaque caractère est  associé à un codage binaire, en général
sur 8 bits (un octet) ce qui donne $2^8=256$ caractères possibles.

En fait,  un américain a mis au  point en 1961 l'ASCII  (on prononce \og
aski\fg{})   pour   \og   American   Standard   Code   for   Information
Interchange\fg{}  qui  codait 128  caractères  sur  7  bits ce  qui  est
suffisant pour les américains qui n'ont pas de lettres accentuées.

Il  a ensuite  fallu étendre  ce code  pour les  langues  comportant des
caractères  spéciaux  et là,  les  normes  diffèrent,  ce qui  crée  des
problèmes de compatibilité.

Depuis quelques années, le codage  \emph{Unicode} tente de remédier à ce
problème  en codant  tous  les caractères  existants. %  C'est le  standard
% utilisé sur les systèmes Linux par exemple.

La plupart des langages de programmation, et bien sûr \py, ont une commande qui associe le
code  ASCII  (éventuellement étendu)  à  un  caractère.  On pourra  donc
l'utiliser pour résoudre notre problème. Il s'agit de  la
commande \lstinline+ord(caratère)+ qui  renvoie le code ASCII\index{ASCII} du
caractère \lstinline+caractère+.



\begin{table}[h!]
\begin{center}
{\scriptsize
\begin{tabularx}{0.99\linewidth}{Il*{19}{|Z}I}
\whline
Caractère&  & ! & " & \# & \$ & \% & \& & ' & (  & ) & * & + & , & - & . & / & 0 & 1 & 2 \\
\hline
Code & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\
\hline
\end{tabularx}

\begin{tabularx}{0.99\linewidth}{Il*{19}{|Z}I}
\hline
Caractère&3 & 4 & 5 & 6 & 7 & 8 & 9 & : & ; & < & = & > & ? & @ & A & B & C & D & E \\
\hline
Code &51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 & 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69\\
\hline
\end{tabularx}



\begin{tabularx}{0.99\linewidth}{Il*{19}{|Z}I}
\hline
Caractère&F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X \\
\hline
Code &70 & 71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 & 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88\\
\hline
\end{tabularx}





\begin{tabularx}{0.99\linewidth}{Il*{19}{|Z}I}
\hline
Caractère& Y & Z & [ & \verb+ \ + & ] & \verb+ ^ + & \verb+ _ + & \verb+ ` + & a & b & c & d & e & f & g & h & i & j & k \\
\hline
Code & 89 & 90 & 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 & 101 & 102 & 103 & 104 & 105 & 106 & 107 \\
\hline
\end{tabularx}



\begin{tabularx}{0.99\linewidth}{Il*{19}{|Z}I}

\hline
Caractère& l & m & n & o & p & q & r & s & t & u & v & w & x & y & z & \{ & | & \} & \verb+~+ \\
\hline
Code & 108 & 109 & 110 & 111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & 120 & 121 & 122 & 123 & 124 & 125 & 126\\
\whline
\end{tabularx}
}
\caption{Table des caractères ASCII affichables}
\end{center}
\end{table}



Par exemple:

\begin{pythoncode}
>>> ord('@')
64
\end{pythoncode}

Mais   attention!  Cela   ne  fonctionne   par  pour   les   chaînes  de
caractères\index{chaîne de caractères}:

\begin{pythoncode}
>>> ord('AB')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: ord() expected a character, but string of length 2 found
\end{pythoncode}

Il faudra donc considérer les caractères d'une chaîne un par un:


\begin{pythoncode}
def ascii(chaine):
    return [ord(c)-ord((' ')) for c in chaine]
\end{pythoncode}

Le \lstinline+-ord((' ')+ permet d'obtenir des caractères codés entre 0 et
95.

\begin{pythoncode}
>>> ascii("3h de retard !!#@!")
[19, 72, 0, 68, 69, 0, 82, 69, 84, 65, 82, 68, 0, 1, 1, 3, 32, 1]
\end{pythoncode}




Tant  qu'on y  est,  créons une  fonction  \lstinline+deascii+ qui  effectuera
l'opération inverse.  On utilisera alors  la commande \Com{chr}
qui renvoie le caractère associé à un code ASCII.  On utilise
\Com{join} pour concaténer plus vite des chaînes.


\begin{pythoncode}
def deascii(chaine):
    return ''.join(chr(x + ord((' '))) for x in chaine)
\end{pythoncode}

Par exemple:

\begin{pythoncode}
>>> deascii([19, 72, 0, 68, 69, 0, 82, 69, 84, 65, 82, 68, 0, 1, 1, 3, 32, 1])
'3h de retard !!#@!'
\end{pythoncode}


Choisissons à présent un message à coder, assez long:

\begin{center}
Arghh !! Ce 1000 pattes aurait 314 pattes ??
\end{center}


\begin{pythoncode}
>>> m = "Arghh !! Ce 1000 pattes aurait 314 pattes ??"
\end{pythoncode}

Le  principe consiste  alors  à  regrouper les  nombres  par paquets  de
longueur constante $p$ et donc à construire à partir de la liste \lstinline+L+ une
matrice de $p$ (lignes ou colonnes?) complétée éventuellement de zéros.

Nous allons  pour cela  créer une fonction  \lstinline+to_Hill(liste,p)+ qui
transforme une liste  en une matrice de $p$ (lignes  ou colonnes?) en complétant
par des zéros si nécessaire:

\begin{pythoncode}[Python3]
def to_Hill(m,p):
  ???
\end{pythoncode}



Le message  en clair devient une matrice.  Choisissons par exemple
un 3-chiffrement de Hill; la matrice \lstinline+clair+ aura donc 3 lignes:


\begin{pythoncode}[Python3]
>>> clair = to_Hill(m,3)
>>> clair
 33  72   1  35  17  16  65  69  65  65   0  20  65  69  31
 82  72   1  69  16   0  84  83  85  73  19   0  84  83  31
 71   0   0   0  16  80  84   0  82  84  17  80  84   0   0
\end{pythoncode}


Il faut  choisir à présent une  clé de chiffrement: ce  sera une matrice
carrée de taille  3, à coefficients dans $\bbz_{95}$  et inversible dans
$\bbz_{95}$.
Nous allons vérifier que la matrice $
\left(\begin{smallmatrix}
1&23&29\\
0&31&1\\
47&3&1
\end{smallmatrix}\right)
$ convient.

Nous voudrions utiliser \lstinline{inverse}
mais on y effectue une division réelle ce qui n'est pas autorisée
dans $\bbz_{95}$.  Nous allons donc un  peu transformer \lstinline{inverse}
pour donner la méthode d'inversion des nombres comme argument.  Seule la dernière ligne de
\lstinline{diago_triangle} change en fait: 



\begin{pythoncode}[matrice.py]
    def diago_triangle(self,inv):
        .
        .
        .
            T = T.mult_ligne(inv(T[k,r-1]),k)
        return T

\end{pythoncode}


puis:

\begin{pythoncode}[matrice.py]
def inverse(self,inv):
    return self.cat_carre_droite().triangle().diago_triangle(inv).extrait_carre_droite()
\end{pythoncode}


Oui mais quel est l'inverse d'un nombre dans $\bbz_{95}$?

C'est un problème d'arithmétique qui  se résout à l'aide de l'algorithme
d'Euclide étendu:



Petit rappel sur cet algorithme qui permet de prouver le théorème de
Bézout et d'obtenir des coefficients vérifiant $au+bv=a\wedge b$~:
\index{\textsc{Bézout} (coefficients de)}
\begin{center}
\begin{tabular}{|c||c|c|c||c|}
\hline $k$ & $u_k$ & $v_k$ & $r_k$ & $q_k$ \\ 
\hhline{=====} 0 & 1 & 0 &$r_0=a$& /  \\ 
\hline 1 & 0 & 1 &$r_1=b$& $q_1$  \\
\hline 2 & $u_0-u_1q_1$ & $v_0-v_1q_1$ &$r_2=r_0-r_1q_1$& $q_2$  \\ 
\hline 3 & $u_1-u_2q_2$ & $v_1-v_2q_2$ & $r_3=r_1-r_2q_2$&$q_3$  \\ 
\hline $\vdots$ &  &  & $\vdots$ & $\vdots$ \\ 
\hline $p-1$ &  &  & $r_{p-1}=a\wedge b$ & $q_{p-1}$ \\ 
\hline $p$ &  &  &   $r_p=0$ &\\
\hline 
\end{tabular} 
\end{center}

La démonstration de l'algorithme découle de la relation:

\begin{center}
\begin{tabular}{ccccc}
 & \fcolorbox{black!90}{black!20}{$u_k$} & {\Large{\textbf{$-$}}} &  &    \\
 & & & &  \\ 
{\Large\bfseries  (   }  &  \fcolorbox{black!90}{black!20}{$u_{k+1}$}  &
{\Large $\mathbf\times$ } & \fcolorbox{black}{black!40}{$q_{k+1}$} &
{\Large\bfseries )} \\
 & & & &  \\ 
{\Large{\textbf{$=$}}} & \fbox{$u_{k+2}$} &  &  &    \\ 
\end{tabular} 
\end{center}


et de la relation similaire pour les $v_k$ et les $r_k$.


Par exemple, pour 19 et 15~:



\begin{center}
\begin{tabular}{|c||c|c|c||c|l}
\hhline{-----} $k$ & $u_k$ & $v_k$ & $r_k$ & $q_k$ &  \\ 
\hhline{=====} 0 & \fcolorbox{black!90}{black!20}{ 1} & \fcolorbox{black!90}{black!20}{ 0} & \fcolorbox{black!90}{black!20}{ 19} & / & $L_0$ \\ 
\hhline{-----} 1 & \fcolorbox{black!90}{black!20}{ 0} & \fcolorbox{black!90}{black!20}{ 1} & \fcolorbox{black!90}{black!20}{ 15} & \fcolorbox{black}{black!40}{1} & $L_1$ \\ 
\hhline{-----} 2 & 1 & $-1$ & 4 & 3 & $L_2\leftarrow L_0-\fcolorbox{black}{black!40}{1}\times L_1$ \\ 
\hhline{-----} 3 & $-3$ & 4 & 3 & 1 & $L_3\leftarrow L_1-3\times L_2$ \\ 
\hhline{-----} 4 & 4 & $-5$ & 1 & 3 & $L_4\leftarrow L_2-1\times L_3$ \\ 
\hhline{-----} 5 &  &  & 0 &  & $L_5\leftarrow L_3-3\times L_4$ \\ 
\hhline{-----} 
\end{tabular} 
\end{center}

C'est-à-dire $4\times 19-5\times 15=1$ et  $19\wedge 15=1$.

En  version récursive, on  peut procéder  en deux  étapes en  suivant la
méthode rappelée ci-dessus:


\begin{pythoncode}[Python3]
def aee(u,v,r,U,V,R):
    if R == 0: return [u,v,r]
    else:
        q = r // R
        return ???

def AEE(a,b): 
    return aee(1,0,a,0,1,b)
\end{pythoncode}


Soit $\dot{a}$ la classe de l'entier $a$ modulo $n$.
Démontrons que $\dot{a}$ est inversible dans $\bbz_n$ si et
seulement si $a$ et $n$ sont premiers entre eux:



$\dot{a}\times\dot{b}=\dot{1}\Leftrightarrow ab\equiv 1[n]\Leftrightarrow  \exists k\in\bbz \ 
ab=1+kn\Leftrightarrow \exists k\in\bbz \ ba-kn=1 \Leftrightarrow a\wedge n=1$, la dernière équivalence 
étant obtenue grâce au théorème de Bézout.

Comme 11 et 13 sont premiers, chaque élément non nul de $\bbz_{11}$ et $\bbz_{13}$ 
est inversible. Mais par 
exemple 6 n'est pas premier avec 9, donc $\dot{6}$ n'est pas inversible dans 
$\bbz_9$,  c'est pourquoi  la résolution  de l'équation  $6x\equiv b[9]$
pose problème.


Nous allons  donc utiliser la fonction  \verb+AEE+ créée précédemment
 pour déterminer l'inverse d'un nombre dans
$\bbz_{n}$:\label{inv_modulaire}


\begin{pythoncode}[Python3]
def inv_mod(p,n):
    B = AEE(p,n)
    assert B[2] == 1, str(p) + ' non iversible modulo ' + str(n)
    return ???
\end{pythoncode}





On peut alors obtenir directement l'inverse de la matrice \lstinline+cle+:



\begin{pythoncode}[python3]
>>> cle = list2mat([[1,23,29],[0,31,1],[47,3,1]])
>>> inv_cle = cle.inverse(lambda x: inv_mod(x, 95))
>>> inv_cle
-1.82136E+09 -4.16311E+09  5.69826E+10
       23312      -675552         -496
      -30597        22638          651
\end{pythoncode}

Oups!  Il  serait  plus  lisible   d'obtenir  les  représentants  canoniques  de
$\bbz_{95}$. Il suffit  donc de calculer le reste de  chaque coefficient dans la
division par 95 donc d'appliquer la fonction \lstinline{lambda coeff : coeff % 95}.

Comme ce genre d'action est standard, on créer une méthode \lstinline{map} dans notre classe
\lstinline{Mat}   (on  parle   alors  de   \textit{foncteur}  en   programmation
fonctionnelle qui rejoint la notion homonyme en théorie des catégories).

\begin{pythoncode}[matrice.py]
    def map(self,f):
        return Mat(self.D, lambda i,j: f(self.F(i,j)))
\end{pythoncode}


Alors:

\begin{pythoncode}[Python3]
>>> inv_cle = cle.inverse(lambda x: inv_mod(x, 95)).map(lambda coeff : coeff % 95)
>>> inv_cle
 18  14  34
 37  88  74
 88  28  81
\end{pythoncode}

On vérifie:

\begin{pythoncode}[Python3]
>>> (cle * inv_cle).map(lambda coeff : coeff % 95)
 1  0  0
 0  1  0
 0  0  1
\end{pythoncode}


Nous  pouvons multiplier  \lstinline+cle+ par  \lstinline+clair+ pour  coder notre
message. Pour le  décoder, il suffira de multiplier  le message codé par
\lstinline+inv_cle+.

La   matrice  \lstinline+cle+$\times$\lstinline+clair+  est   une  matrice   de  3
lignes. Il  faudra la  transformer ensuite en  liste pour  lui appliquer
\lstinline+decode+. On utilise la fonction  \Com{iter} définie dans notre classe
\lstinline{Mat}.



\begin{pythoncode}[python3]
>>> crypte = deascii(iter((cle * clair).map(lambda n : n % 95)))

>>> crypte
"sP_2Ou8?R'QOyE(Xph_<bn(h<Yc cAkDj\\pf_<bn(ho+>"
\end{pythoncode}

Si on le compare au message initial:

\lstinline{"Arghh !! Ce 1000 pattes aurait 314 pattes ??"}

on remarque  que le premier \og pattes\fg{}  est codé par  \lstinline{h_<be(} alors que le  second est
codé par \lstinline{pf_<bn}: ce n'est donc pas un codage lettre par lettre et il est donc
apparemment plus compliqué que le chiffrement de César.



\subsubsection{Décodage}



Celui  qui  reçoit ce  message  (l'éternel  Bob...)  possède la  clé  de
décodage qui est \lstinline+inv_cle+.


\begin{pythoncode}[Python3]
>>> decrypte = deascii(???)
>>> decrypte
'Arghh !! Ce 1000 pattes aurait 314 pattes ?? '
\end{pythoncode}

Ça marche! On remarque les deux espaces (neutres) rajoutés à la fin pour obtenir
une chaîne de longueur un multiple de 3.

% \subsubsection{Casser le chiffrement de \textsc{Hill}}

% \subsubsection{Exercices}


\section{Codes correcteurs d'erreurs linéaires}

Un très rapide tour d'horizon...Vous utiliserez la classe Mat pour illustrer les
notions suivantes...


\subsection{Quelques rappels}

On  veut transmettre  $2^r$ messages  distincts: on  les code  sur $r$  bits. On
rajoute des bits de contrôle pour vérifier que le message a été bien transmis.

Le message tient donc en fait sur $n$ bits.

Si une transformation linéaire permet de  passer du code initial de $\bbf_2^r$ au
code émis de $\bbf_2^n$, on dit que le code est linéaire.

\begin{exercice}
Par exemple, on veut transmettre des mots de 1 bit. On émet le message en le
triplant (1 est émis en 111). Le code est-il linéaire? Quelle est sa matrice $G$ de codage?
\end{exercice}


Notons $G$ la matrice du code linéaire. 

\begin{exercice}
  Il doit y avoir au moins autant de  mots codés que de mots au départ: comment
  cela se traduit-il quant au rang de $G$?
\end{exercice}


Notons $C$ la matrice de contrôle telle  que $C\cdot m_r=0$ si, et seulement si,
$m_r$ (le message reçu) est un mot de code (qui a donc été transmis sans erreur).


\begin{exercice}
  Que dire du rang de C?
\end{exercice}


On notera \textit{syndrome} la fonction associée à $s$.

On appellera matrice de décodage la  matrice $D$ telle que $x=Dy \Leftrightarrow
y = Gx$.

Par la  méthode de  la $\ell$-réduite échelonnée  de \textsc{Gau\ss  -Jordan} on
peut  déterminer $D$  et $C$:  suivez  les explications  de votre  chargé de  TD
préféré...

\begin{exercice}
  Que donne $R\times (G|m_r)$?
\end{exercice}

Notons $ε$ l'erreur commise que le message codé émis $m_c$. Alors $m_c=m_r+ε$.

\begin{exercice}
  Montrez que $s(m_r)=s(ε)$ et que l'on peut répartir les vecteurs de $\bbf_2^n$
  selon des classes d'équivalences par syndromes.

Montrez que si $u$ est un  message reçu quelconque, ${\rm classe}(u)=u+\CR$ avec
$\CR$ l'ensemble des mots codés.
\end{exercice}

Un  code  de  \textsc{Hamming}  est  un  code  tel  que  tous  les  vecteurs  de
$\bbf_2^{n-r}$, sauf le vecteur nul, apparaissent dans C.


\subsection{Exemples}

\begin{exercice}
  Déterminez une matrice de contrôle du code défini par la matrice génératrice:


$$G=
\left(
\begin{smallmatrix}
  1&0&0&1\\
  1&1&1&1\\
  0&1&1&0\\
  1&0&0&0\\
  0&1&0&0\\
  0&0&1&0\\
  0&0&0&1\\
\end{smallmatrix}
\right)
$$

Après contrôle d'erreur, décodez les  messages reçus suivants: 0111101, 0100110,
1010010.

Quel est le défaut de ce code?


\end{exercice}



\begin{exercice}
  Même style de questions avec:


$$
G=\left(
\begin{smallmatrix}
  1&1&0&1\\
  1&0&1&1&\\
  1&0&0&0\\
  0&1&1&1\\
  0&1&0&0\\
  0&0&1&0\\
  0&0&0&1\\
\end{smallmatrix}
\right)
$$
On reçoit 1010110, 1100110, 0100001, 0010001.
Quelle est la nature du code? Quelle est la matrice de décodage $D$?




\end{exercice}




\begin{exercice}
  Même style de questions avec:


$$
G=
\left(
\begin{smallmatrix}
1&0&0&0\\
0&1&0&0\\
1&0&1&0\\
1&1&0&1\\
0&1&1&0\\
0&0&1&1\\
0&0&0&1\\
\end{smallmatrix}
\right)
$$
On reçoit 1100101.
Quelle est la nature du code? Quelle est la matrice de décodage $D$?




\end{exercice}


\begin{exercice}
  Si $p$ est la  probabilité d'erreur sur un bit et si les  erreurs par bit sont
  indépendantes, exprimez la  probabilité en fnctin de $p$  qu'un message erroné
  devienne   un  mot   différent   du  mot   émis  lorsque   le   code  est   de
  \textsc{Hamming}.  Donnez  une valeur  approchée  pour  $p=0,1$. (On  rappelle
  que 
le code de \textsc{Hamming} ne corrige que les erreurs de poids 1).
\end{exercice}

\section{Construisons nos outils}




\subsubsection{Création d'une classe \og Matrice\fg{}}


Dans cette section,  nous créerons nos matrices en donnant  leur dimension et la
fonction  définissant leurs  coefficients en  fonction de  leurs indices...comme
nous l'avons fait en Haskell...sauf que c'est moins joli et mois contrôlable...

\begin{pythoncode}
class Mat:
    """ une matrice sous la forme Mat([nb lignes, nb cols], fonction(i,j))"""

    def __init__(self, dim, f):
        self.F = f   # fonction (i,j) -> coeff en position i,j
        self.D = dim # liste [nb de lignes, nb de cols]
\end{pythoncode}




Par exemple,
$\left(\begin{smallmatrix}
 1&2\\3&4\\5&6
\end{smallmatrix}\right)$
sera cre\'ee avec:

\begin{pythoncode}
>>> M = Mat([3,2],lambda i,j : 2*i + (j + 1))
\end{pythoncode}






On a quand même l'habitude de rentrer  une matrice comme une liste de lignes. On
va  donc créer  une fonction  qui permet  de convertir  une liste  de lignes  en
matrice:

\begin{pythoncode}
def list2mat(mat):
    r,c = len(mat),len(mat[0])
    return Mat([r,c], lambda i,j : mat[i][j])
\end{pythoncode}


La matrice précédente aurait donc pu être définie par:

\begin{pythoncode}
>>> M = list2mat([[1,2],[3,4],[5,6]])
\end{pythoncode}




\begin{pythoncode}
>>> M.D # dimension de la matrice
[3, 2]
>>> M.F(0,1) # coefficient à la position 0,1
2
\end{pythoncode}



\begin{recherche}

Écrivez une  fonction qui  renvoie une  matrice nulle de  taille $n×m$  puis une
autre qui renvoie la matrice identité de taille $n$.

  
  

\end{recherche}



Nous  rajoutons  quelques  méthodes  habituellement  définies  pour  les  objets
structurés de ce type:

\begin{pythoncode}
   def __getitem__(self,cle):
        """ permet d'obtenir Mij avec M[i,j] """
        return self.F(*cle)
        
    def __iter__(self):
        """ pour itérer sur la liste des coefficients donnés par colonnes """ 
        [r,c] = self.D
        for j in range(c):
            for i in range(r):
                yield self.F(i,j)
\end{pythoncode}


L'emploi  du  mot-clé   \texttt{yield}  au  lieu  de  \texttt{return}   permet  de  ne
\textit{retourner} \lstinline{self.F(i,j)}  que lorsque cela est  demandé. Ainsi
la liste de tous les coefficients  n'est pas créée en entier systématiquement ce
qui économise la mémoire.

Nous pouvons ainsi créer une méthode qui va permettre un joli affichage:

\begin{pythoncode}
    def __str__(self):
        """ joli affichage d'une matrice"""
        [r,c],f = self.D, self.F
        lmax = len(str(max(iter(self)))) + 1
        s = '\n'.join( (' '.join('{0:>.{l}G}'.format(f(i,j),l=lmax) for j in range(c))) for i in range(r))
        return s

    def __repr__(self):
        """ représentation dans le REPL"""
        return str(self)
\end{pythoncode}

La   méthode    \texttt{join}   est    à   employer   systématiquement    pour   la
concaténation des chaînes de  caractères: elle est beaucoup
plus efficace que son pendant sous forme de  boucle..


\begin{pythoncode}
>>> M
1 2
3 4
5 6
\end{pythoncode}


\begin{recherche}
  Créez deux fonctions qui créent un  itérateur respectivement sur les lignes et
  sur les colonnes.

Par exemple  laliste des coefficients  de la première  colonne de M  sera donnée
par:

\begin{pythoncode}
>>> [i for i in M.col(0)]
[1, 3, 5]
\end{pythoncode}

\end{recherche}




\subsubsection{Transposée d'une matrice}


 La  transposée d'une
matrice $(M_{ij})_{\substack{1 \leqslant i \leqslant n \\ 1 \leqslant j \leqslant m}}$
est égale à la matrice $(M_{ji})_{\substack{1 \leqslant i \leqslant n \\ 1
  \leqslant j \leqslant m}}$.
Attention aux indices et aux nombre de lignes et de colonnes!
\label{transpose}


\begin{recherche}
  Créez une fonction qui renvoie la transposée d'une matrice donnée en argument.

\begin{pythoncode}
>>> M.transpose() 
1 3 5
2 4 6
\end{pythoncode}
\end{recherche}


\subsubsection{Somme de matrices}


On voudrait créer une méthode qui  prend comme  arguments deux  matrices et
renvoie leur  somme. Il faudra  vérifier que les matrices  à additionner
sont de  bonnes tailles: on  utilisera la  fonction \texttt{assert} qui  est suivie
d'une condition à vérifier et d'un message à affichher en cas de problème.

Pour pouvoir utiliser le symbole \lstinline{+}  par la suite, on va nommer notre
méthode \lstinline{__add__}:

\begin{pythoncode}
    def __add__(self,other):
        """ somme de deux matrices : utilisation du symbole +"""
        assert self.D == other.D, "tailles incompatibles"
        return Mat(self.D, lambda i,j : self.F(i,j) + other.F(i,j))
\end{pythoncode}




Par exemple, avec la matrice M précédemment introduite:


\begin{pythoncode}
>>> M + M
  2   4
  6   8
 10  12
\end{pythoncode}


\begin{recherche}
  On définit de même \lstinline{__neg__} pour l'opposé et \lstinline{__sub__} pour
la soustraction: faites-le!

\end{recherche}


\subsubsection{Produit par un scalaire}


On voudrait obtenir la matrice $k\cdot  M$ à partir d'une matrice $M$ et
d'un scalaire $k$.


\begin{pythoncode}
>>> A = Mat([2,3], lambda i,j : 3*i + j)
>>> A
 0  1  2
 3  4  5
>>> A.prod_par_scal(5)
  0   5  10
 15  20  25
\end{pythoncode}


\begin{recherche}
  Écrivez une implémentation de la méthode \lstinline{prod_par_scal}
\end{recherche}



\subsubsection{Produit de matrices}


Soit $A=(a_{ij})_{\substack{1 \leqslant i \leqslant n \\ 1 \leqslant i
    \leqslant m}}$ et $B=(b_{ij})_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant i
    \leqslant p}}$.
Alors $A\times B=C$ avec $C=(c_{ij})_{\substack{1 \leqslant i \leqslant n \\ 1 \leqslant i
    \leqslant p}}$ et \[\forall (i,j)\in\bbn^*_n\times \bbn^*_p,\quad c_{ij}=\sum_{k=1}^ma_{ik} b_{kj}\]


C'est l'algorithme habituel trois boucles imbriquées).

Nous allons l'abstraire d'un petit niveau: chaque coefficient $c_ij$ est en fait
égal au produit scalaire de la ligne $i$ de A et de la colonne $j$ de B.

Commençons donc par  construire une fonction qui calcule le  produit scalaire de
deux itérables.


Pour cela, nous allons utiliser une fonction extrêmement importante qui vient du
monde de la programmation fonctionelle: \texttt{map}.


\lstinline{map(fonc, iterable(s))} renvoie un itérateur de type \lstinline{map} mais où
chaque  élément sera  remplacé  par son  image  par la  fonction  (si c'est  une
fonction de  une variable) ou  par l'image combinée  des itérables si  c'est une
fonction de plusieurs variables.

Par exemple:

\begin{pythoncode}
>>> map(lambda x: x*x, [1,2,3,4])
<map at 0x7fe8307f2ef0>
>>> [i for i in m]
[1 4 9 16]
\end{pythoncode}

arghhh : l'objet crée est de type \lstinline{map} et on a son adresse mais on ne
sait pas ce qu'il y a dedans...

\begin{pythoncode}
>>> m = map(lambda x: x*x, [1,2,3,4])
>>> [i for i in m]
[1 4 9 16]
\end{pythoncode}

Mais atention! m a maintenant été \og consommé\fg{}. Si on en redemande:

\begin{pythoncode}
>>> [i for i in m]
[]
\end{pythoncode}


Si on veut en garder une trace on peut utiliser par exemple \texttt{list}:

\begin{pythoncode}
>>> m = map(lambda x: x*x, [1,2,3,4])
>>> l = list(m)
>>> l
[1 4 9 16]
\end{pythoncode}


Avec une fonction de deux variables et deux itérables:

\begin{pythoncode}
>>> m = map(lambda x, y: x + y, [1,2,3,4], [-1,-2,-3,-4])
>>> list(m)
[0, 0, 0, 0]
\end{pythoncode}


On peut  aller plus  vite en  utilisant les  opérateurs arithmétiques  écrits en
notation préfixée dans la bibliothèque \texttt{operator}:

\begin{pythoncode}
from operator import mul
>>> m = map(mul, [1,2,3,4], [-1,-2,-3,-4])
>>> list(m)
[-1, -4, -9, -16]
\end{pythoncode}



Pour  notre produit  scalaire, nous  utilisons également  la classique  fonction
\texttt{sum}.




\begin{recherche}
Créez une fonction \Colorbox{blue!10}{\lstinline{prod_scal}}.

Utilisez \lstinline{prod_scal}  pour écrire en  une ligne la matrice  produit de
deux matrices données en arguments.

Vous créerez ainsi une méthode \lstinline{prod_mat(self,other)} en ajoutant à la
ligne précédente une ligne vérifiant que les formats sont corrects.
\end{recherche}


Pour utiliser  le symbole \lstinline{*}  pour le  produit d'une matrice  par une
autre  matrice  ou   un  scalaire,  on  crée  dans  notre   classe  une  méthode
\lstinline{__mul__}. On utilisera la fonction  \texttt{type} qui teste le type d'un
objet.


\begin{pythoncode}
  def __mul__(self,other):
        """ produit d'une matrice par un scalaire ou une matrice : utilisation du symbole *"""
        if Mat == type(other):
            return self.prod_mat(other)
        else:
            return self.prod_par_scal(other)
\end{pythoncode}



\subsubsection{Comparaison de plusieurs produits matriciels}

Notre  produit  n'est pas  si  mal:  il s'écrit  très  simplement  et est  assez
efficace. Comparons-le avec d'autres implémentations.


\paragraph*{Avec les outils standards de Python}

D'abord une  implémentation classique  en introduisant une  liste Python  et des
matrices du  type \lstinline{array} de  \texttt{numpy}. On travaillera  par exemple
avec des  tableaux d'entiers  (l'argument \texttt{dtype}\lstinline{  = int})  et on
utilisera les commandes \texttt{shape} et \texttt{zeros} de \lstinline{numpy}.


\begin{pythoncode}
import numpy as np

def pymatmatprod(A, B):
    '''
    Multiplication matricielle avec les outils Python usuels
    '''
    ra, ca = A.shape
    rb, cb = B.shape
    assert ca == rb, "Tailles incompatibles"
    C = np.zeros((ra, cb),dtype = int)
    for i in range(ra):
        Ai,Ci = A[i],C[i]
        for j in range(cb):
            for k in range(ca):
                Ci[j] += Ai[k] * B[k, j]
    return C
\end{pythoncode}



\paragraph*{Avec Cython}

\texttt{Cython}  (\href{http://cython.org/}{http://cython.org/})   est  un  langage
dont la  syntaxe est très proche  de celle de  Python mais c'est un  langage qui
permet  de  générer   des  exécutables  compilés  et  d'utiliser   un  style  de
programmation proche du C. Cela permet d'optimiser grandement Python.

Le          logiciel           de          calcul           formel          Sage
{\href{http://www.sagemath.org/}{http://www.sagemath.org/}}
est principalement écrit en Cython pour gagner en efficacité.

Voyons  un  exemple en  \oe  uvre.  L'usage conjoint  de  Python  et Cython  est
grandement facilité par le travail dans l'environnement iPython.


\begin{pythoncode}
In [1]: %load_ext cythonmagic

In [2]: 
%%cython
cimport cython
import numpy as np
cimport numpy as np

cdef long[:, :] matprodC( long[:, :]  A, long[:, :]  B):
    '''
    multiplication matricielle via cython et les array de numpy
    '''
    cdef: 
        int i, j, k
        int ra = A.shape[0]
        int ca = A.shape[1]
        int rb = B.shape[0]
        int cb = B.shape[1]
        long [:, :] C
        long [:] Ai, Ci
    
    assert ca == rb, 'Tailles non compatibles'

    C = np.zeros((ra, cb),dtype=int)
    for i in range(ra):
        Ai,Ci = A[i],C[i]
        for j in range(cb):
            for k in range(ca):
                Ci[j] = Ci[j] + Ai[k] * B[k, j]
    return C

def matprod(long [:, :]  A, B):
    return matprodC(A, B)
\end{pythoncode}


On  remarque qu'écrire  en Cython  revient un  peu à  écrire en  Python mais  en
déclarant des variables comme en C.

iPython permet  également de  comparer facilement  les temps  de calcul  avec la
commande magique 
\lstinline{%timeit}.

On commence par  créer une matrice de  taille $200×200$ puis on  va demander son
coefficient [100,100]:

\begin{pythoncode}
In [3]: A = np.ones((200,200),dtype = int)
\end{pythoncode}


On compare alors le produit via Python, Cython et la multiplication de \lstinline{numpy}:


\begin{pythoncode}
In [4]: %timeit matprod(A,A)[100,100]
100 loops, best of 3: 16.3 ms per loop

In [5]: %timeit pymatmatprod(A,A)[100][100]
1 loops, best of 3: 8.35 s per loop

In [6]: %timeit np.dot(A,A)[100,100]
100 loops, best of 3: 8.94 ms per loop
\end{pythoncode} 



Notre fonction en Cython est 500 fois plus rapide!!!
Elle est très légèrement plus lente que le produit de \lstinline{numpy}.

Et notre implémentation personnelle avec la classe \lstinline{Mat}?

\begin{pythoncode}
In [7]: A = Mat([200,200],lambda i,j:1)

In [8]: %timeit (A*A)[100,100]
10000 loops, best of 3: 79.6 μs per loop
\end{pythoncode}


Trop fort! Nous battons tout le monde à plate couture! Nous sommes 100 fois plus
rapides que \lstinline{numpy}!!!

...et nous avons bien le bon résultat:

\begin{pythoncode}
In [9]: (A*A)[100,100]
Out[9]: 200
\end{pythoncode}


Bon, ça va pour un seul produit.  Pour calculer une puissance 200, ce sera moins
magique...




\subsubsection{Puissances d'une matrice}



Par exemple, avec $J=
\left(\begin{smallmatrix}
  1&1\\1&1
\end{smallmatrix}\right)
$:

\begin{pythoncode}
>>> J = Mat([2,2], lambda i,j : 1)
>>> J ** 5
 16  16
 16  16
\end{pythoncode}

En effet,  $J^n=2^{n-1}J$ est un  résultat classique. On    utilise un  algorithme d'exponentiation
rapide.  Par exemple,  en voici  une version  récursive rapide  à écrire  qui se
nomme \lstinline{__pow__} afin d'utiliser le symbole \lstinline{**}:


\begin{pythoncode}
    def __pow__(self,n):
        r = self.D[0]
        if n == 0:
            return unite(r)
        def pui(m,k,acc):
            if k == 0:
                return acc
            return pui((m*m),k//2,acc if k % 2 == 0 else (m*acc))
        return pui(self,n,unite(r))  
\end{pythoncode}





\begin{recherche}
Déterminez une version impérative de la méthode précédente.
\end{recherche}


\section{Rappels sur l'inversion des matrices}





\subsubsection{Matrice carrée inversible}


Soit  $M\in  \bba^{n\times n}$.  M  est  inversible  (régulière) si,  et
seulement si, il existe une matrice N dans $\bba^{n\times n}$ telle que: 
 

$$M\times N = N \times M = \bbi_n$$

On note alors $N=M^{-1}$. 

On remarque (n'est-ce pas) que, d'après cette définition, $(M^{-1})^{-1}=M$.


Lorsque nous  aurons étudier  les déterminants, nous  pourrons démontrer
que  si A  et  B sont  deux  matrices carrées  de  taille $n$  vérifiant
$A\times B=\bbi_n$, alors elles sont régulières et $A=B^{-1}$.


\begin{recherche}
Si   A  et  B  sont  régulières   et  de  taille  $n$,
  alors comment calculer  $(A\times B)^{-1}$ à partir des  inverses de A
  te B?
\end{recherche}

\subsubsection{Opérations sur les lignes}



\paragraph{Matrices élémentaires}

Nous désignerons  par $E_n^{ij}$ la  matrice carrée de  $\bba^{n\times n}$
dont tous  les coefficients  sont nuls sauf  le coefficient  $(i,j)$ qui
vaut $1_{\bba}$.
Par exemple, $E_3^{12}=\left(
\begin{smallmatrix}
  0&1&0\\
  0&0&0\\
  0&0&0\\
\end{smallmatrix}\right)
$ dans $\bbz^{3\times 3}$.




\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3.1cm]{kronecker}
\caption{Leoplod \bsc{Kronecker} \\ (1823-1891)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.3cm}

Leopold \textsc{Kronecker} est un mathématicien prussien né dans l'actuelle
Pologne. On lui doit la célèbre citation: \og \textit{Die ganzen Zahlen
hat der liebe Gott gemacht, alles andere ist Menschenwerk}\fg{}.


En son honneur, on a donné son nom à la fonction suivante:
$$\delta\colon\begin{array}{rll} \bbn\times\bbn  &\to & \bigl\{0;1\bigr\}
\\ (i,j) & \mapsto & 1 \text{ si } i=j, \ 0 \text{ sinon}\end{array}$$


On condense  souvent la notation en  $\delta_{ij}$ et on  parle alors de
\textbf{symbole de \textsc{Kronecker}}. Par exemple, la matrice identité
peut être définie par:

$$\bbi_n=(\delta_{ij})_{\substack{1  \leqslant i  \leqslant n\\ 1  \leqslant j
\leqslant n}}$$

\begin{recherche}
  Étudiez le  produit $E_n^{ij}\times E_n^{\ell k}$ et  exprimez-le à l'aide
  du symbole de \textsc{Kronecker}.

Simplifiez ensuite  le produit $(\bbi_n+\lambda E_n^{ij})\times(\bbi_n-\lambda E_n^{ij})$:
qu'en concluez-vous?
\end{recherche}


\paragraph{Transvections de lignes}

On s'intéresse à la fonction:


$$T^{ij}_\lambda \colon\begin{array}{rll}\bba^{n\times p} &\to &\bba^{n\times p}
\\ M & \mapsto & (\bbi_n+\lambda E_n^{ij})\times M \end{array}$$


Calculez par exemple l'image par $T_\lambda ^{23}$ de $\left(
\begin{smallmatrix}
  a_1&b_1&c_1&d_1\\
  a_2&b_2&c_2&d_2\\
  a_3&b_3&c_3&d_3\\
\end{smallmatrix}\right)$

Ainsi, $T_\lambda ^{ij}(M)$ permet d'obtenir  la matrice construite à partir de
M en remplaçant la ligne $i$ par elle-même plus $\lambda $ fois la ligne $j$.

On   note  plus   commodément  cette   transformation   $L_i  \leftarrow
L_i\boxplus (\lambda \boxdot L_j)$.

Vous  aurez  bien  noté  que $(\bbi_n+\lambda  E_n^{ij})^{-1}  =  \bbi_n-\lambda
E_n^{ij}$.


\paragraph{Dilatations de lignes}

On  veut effectuer  l'opération  $L_i\leftarrow \lambda \boxdot  L_i$. On  note
$$\Delta_n^{i,\lambda }= \bbi_n+(\lambda \boxplus (-1_{\bba}))E_n^{ii}$$

Calculez par exemple le produit de $\Delta_3^{2,\lambda}$ par $\left(
\begin{smallmatrix}
  a_1&b_1&c_1&d_1\\
  a_2&b_2&c_2&d_2\\
  a_3&b_3&c_3&d_3\\
\end{smallmatrix}\right)$


Le produit par $\Delta_n^{i,\lambda }$ est une dilatation de ligne.


\paragraph{Échange de lignes}


On    considère   la    matrice   $S^{ij}_n=\Delta_n^{j,-1_{\bba}}\times
(\bbi_n+E_n^{ij})\times (\bbi_n-E_n^{ji})\times (\bbi_n+E_n^{ij})$.

Développez ce produit. Que vaut  le produit de $S_3^{23}$ par $\left(
\begin{smallmatrix}
  a_1&b_1&c_1&d_1\\
  a_2&b_2&c_2&d_2\\
  a_3&b_3&c_3&d_3\\
\end{smallmatrix}\right)$?

On note cette opération $L_i\leftrightarrow L_j$.


\paragraph{Opérations sur les lignes}


De manière  plus générale, une fonction $\varphi$  de $\bba^{n\times p}$
dans  lui-même est  une \textbf{opération  sur les  lignes} si  c'est la
composée finie de transvections et de dilatations de lignes.

L'image d'une matrice par $\varphi$ est donc le produit à gauche par des
matrices de transvections ou de dilatations:

$$\varphi : M\mapsto ( F_k \times F_{k-1}\cdots \times F_1)\times M$$

avec chaque  $F_i$ inversible. La fonction $\varphi$  est donc elle-même
totale bijective et sa réciproque est: 


$$\varphi^{-1}  :  N\mapsto (  F_1^{-1}  \times F_{2}^{-1}\cdots  \times
F_k^{-1})\times N$$


On en déduit en particulier que  l'inverse de $\varphi \left( \bbi_{n}\right) $ existe et
que c'est $\varphi ^{-1}\left( \bbi_{n}\right) .$


\paragraph{Lien avec les matrices régulières}

Voici  un théorème  important qui  nous  sera très  utile pour  calculer
l'inverse d'une matrice régulière. 


\begin{theoreme}
$\varphi $ étant une opération élémentaire sur les lignes,%

$$
M\text{ inversible}\lequiv \varphi (M)\text{ inversible}
$$

\end{theoreme}



En effet nous savons que $\varphi (M)=\varphi (\bbi_n)\times M.$ Si $M$ est
inversible, $\varphi (M)$ s'exprime comme le produit de deux matrices
inversibles et elle est donc inversible. Supposons maintenant $\varphi (M)$
inversible, comme $\varphi (\bbi_n)$ est inversible on obtient : 
$$
\varphi (\bbi_n)^{-1}\times \varphi (M)=\varphi (\bbi_n)^{-1}\times \left(
\varphi (\bbi_n)\times M\right)
$$%
qui se transforme en 
$$
\varphi (\bbi_n)^{-1}\times \varphi (M)=\left( \varphi (\bbi_n)^{-1}\times
\varphi (\bbi_n)\right) \times M=\bbi_n\times M
$$%
et en définitive 
$$
M=\varphi (\bbi_n)^{-1}\times \varphi (M)=\varphi ^{-1}(\bbi_n)\times \varphi
(M)
$$%
$M$ s'exprimant comme le produit de deux matrices inversibles est inversible.

\begin{theoreme}
Si $\varphi _{1},\varphi _{2},....,\varphi _{k}$ est une suite d'opé%
rations sur les lignes de $M$ qui transforme $M$ en $\bbi_n$ alors $M$ est
inversible et 
$$
M^{-1}=\varphi _{k}(\bbi_n)\times \varphi _{k-1}(\bbi_n)\times ....\times
\varphi _{1}(\bbi_n)=\varphi _{k}\circ \varphi _{k-1}\circ ...\circ \varphi
_{1}(\bbi_n)
$$
\end{theoreme}

En effet, si nous avons $\varphi _{k}\circ \varphi _{k-1}\circ ...\circ
\varphi _{1}(M)=\bbi_n$ alors%
$$
\varphi _{k}\circ \varphi _{k-1}\circ ...\circ \varphi _{1}(M)=\bbi_n=\left(
\varphi _{k}(\bbi_n)\times \varphi _{k-1}(\bbi_n)\times ....\times \varphi
_{1}(\bbi_n)\right) \times M
$$%
Nous avons trouvé une matrice carrée qui multipliant $M$ donne $%
\bbi_n,$ c'est son inverse.

Le théorème précédent nous indique une méthode pour
trouver l'inverse de $M$ (s'il  existe), nous allons étudier plus en
détail cette technique et nous démontrerons plus loin que s'il est
impossible de transformer $M$ en $\bbi_n$ en utilisant les opérations 
élémentaires sur les lignes, alors $M$ n'est pas inversible.


\subsection{Rang d'une matrice}




Dans  tout   ce  qui  suit  nous  allons   utiliser  les  opérations
élémentaires sur les lignes d'une matrice et on travaille dans
$\bba^{n\times p}$.

\subsubsection{Matrices ligne-équivalentes}

Nous dirons que deux matrices $M$ et $N$ sont \textbf{ligne-équivalentes}
si, et seulement si, il existe une suite finie $\left( \varphi _{i}\right)
_{i\in \mathbb{N}_{k}}$ d'opérations élémentaires sur les lignes
de sorte que 

$$N=\varphi _{k}\circ \varphi _{k-1}\circ ...\circ \varphi_{1}(M)$$

 Nous écrirons alors $M\overset{\ell}{\equiv }N.$ La relation $%
\overset{\ell}{\equiv }$ est manifestement une relation d'équivalence
sur $\bba^{n\times p}$, on démontre sans peine que%
\begin{equation*}
\begin{array}{l}
M\overset{\ell}{\equiv }M \\ 
M\overset{\ell}{\equiv }N\limp N\overset{\ell}{\equiv }M \\ 
\left( M\overset{\ell}{\equiv }N\text{ et }N\overset{\ell}{\equiv }C\right)
\limp M\overset{\ell}{\equiv }C%
\end{array}%
\end{equation*}%
Nous savons que $\varphi _{k}\circ \varphi _{k-1}\circ ...\circ \varphi
_{1}(M)=\varphi _{k}\circ \varphi _{k-1}\circ ...\circ \varphi
_{1}(\bbi_n )\times M,$ par conséquent nous aurons $M\overset{\ell}{\equiv 
}N$ s'il existe une matrice $R$ inversible vérifiant 
\begin{equation*}
N=R\times M
\end{equation*}%
$R$ étant le résultat du produit de matrices du type $\varphi
(\bbi_n ).$ Pour obtenir cette matrice $R$ il suffit d'appliquer
successivement en parallèle les opérations élémentaires qui
transforment $M$ en $N$ sur $\bbi_n .$ Pour cela on utilise un tableau où
l'on juxtapose $M$ et $\bbi_n ,$ $M$ étant la partie gauche et $\bbi_n $ la
partie droite de ce tableau. Toute opération élémentaire sur les
lignes effectuée sur la partie gauche est simultanément effectué%
e sur la partie droite.

\begin{equation*}
\begin{tabular}{|c|c|c|c|}
\hline
opérations\textbf{\ }$\varphi $ & Partie gauche & Partie droite & 
Remarques \\ \hline
& $M$ & $\bbi_n $ & initialisation du tableau \\ \hline
$\varphi _{1}$ & $M_{1}$ & $R_{1}$ & $M_{1}=\varphi _{1}(M),$ $R_{1}=\varphi
_{1}(\bbi_n )$ \\ \hline
$\varphi _{2}$ & $M_{2}$ & $R_{2}$ & $M_{2}=\varphi _{2}(M_{1}),$ $%
R_{2}=\varphi _{2}(R_{1})$ \\ \hline
$\vdots $ & $\vdots $ & $\vdots $ & $\vdots $ \\ \hline
$\varphi _{i}$ & $M_{i}$ & $R_{i}$ & $M_{i}=R_{i}\times M$ \\ \hline
$\vdots $ & $\vdots $ & $\vdots $ & $\vdots $ \\ \hline
$\varphi _{k}$ & $N$ & $R$ & $N=R\times M$ \\ \hline
\end{tabular}%
\end{equation*}

\subsubsection{L réduite échelonnée}

La matrice $M=\left( m_{ij}\right) \in \bba^{n\times p}(\mathbb{K)}$ est
dite \textbf{$\bm \ell$-réduite} ($\bm \ell$ pour \og ligne\fg{}) si, et seulement si, elle satisfait aux
conditions suivantes :

\begin{enumerate}
\item Toutes les lignes nulles (une ligne est nulle si elle ne comporte que
des zéros) sont au-dessous des lignes non nulles.

\item Dans chaque ligne non nulle le premier élément non nul est $ 1_{\bba}$
(on lit une ligne de la gauche vers la droite), ce $ 1_{\bba}$ est appelé\textbf{ pivot} ou 
élément pivot. La colonne où se trouve ce $ 1_{\bba}$ est appelée
colonne pivot et c'est le seul élément non nul de cette colonne.

\item Si, \textbf{de plus}, les pivots apparaissent en ordre croissant par
numéro de ligne \textbf{et} numéro de colonne, on dit que $M$ est 
\textbf{$\bm \ell$-réduite échelonnée }(en abrégé $\ell$ré ou LR%
é).
\end{enumerate}

\begin{equation*}
\begin{array}{cc}
\begin{tabular}{l|}
1 \\ \hline
\end{tabular}
&  \\ 
& 
\begin{tabular}{|l}
\hline
Zone du prochain pivot%
\end{tabular}%
\end{array}%
\end{equation*}%
\vspace{0.3cm}

Donnons quelques exemples de matrices entières: 
\begin{eqnarray*}
&&\left( 
\begin{array}{cccc}
0 & 
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& 2 & 0 \\ 
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& 0 & 3 & -1 \\ 
0 & 0 & 0 & 0%
\end{array}%
\right) \text{ est $ \ell$-réduite non échelonnée} \\
&&\left( 
\begin{array}{ccc}
0 & 
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& 0 \\ 
0 & 2 & 0 \\ 
0 & 0 & 
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}%
\end{array}%
\right) \text{ n'est pas $ \ell$-réduite} \\
&&\left( 
\begin{array}{ccc}
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& -2 & 0 \\ 
0 & 0 & 
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
\\ 
0 & 0 & 0 \\ 
0 & 0 & 0%
\end{array}%
\right) \text{ est $ \ell$-réduite échelonnée}
\end{eqnarray*}

\begin{theoreme}
Pour toute matrice $M\in \bba^{n\times p}$, il existe une unique matrice $ \ell$-r%
éduite   échelonnée  $N~\in~\bba^{n\times   p}$   telle  que
$M\overset{\ell}{\equiv }N,$ $N$ est appelée la $ \ell$-réduite échelonnée de $%
M$ que l'on peut noter par $N=\ell\text{ré}\left( M\right) .$
\end{theoreme}

La démonstration de ce théorème se fait par récurrence sur $%
n $ et elle est un peu difficile.

Le \textbf{rang} de $M$, noté $\limfunc{rang}(M)$, est le nombre de
lignes non nulles de sa $ \ell$-réduite échelonnée, c'est donc aussi
le nombre de pivots da sa $\ell$ré. $M$ est dite de plein rang si son rang
est égal à son nombre de lignes.

Nous énoncons les évidences (conséquences directes de la dé%
finition) :

\begin{enumerate}
\item Si $M\in \bba^{n\times p}$ le rang de $M$ est inférieur ou é%
gal à $n$ \textbf{et }à\textbf{\ }$p.$

\item Si $M\in \bba^{n\times n}$ et si $\limfunc{rang}(M)=n$ alors sa $ \ell$-ré%
duite échelonnée est $\bbi_n $ et nous avons précédemment d%
émontré que dans ce cas $M$ est inversible.

\item Deux matrices ligne-équivalentes ont la même $ \ell$-réduite 
échelonnée et ont donc même rang.

\item Si $M^{\prime }$ est une matrice extraite de $M,$ on a $\limfunc{rang}%
\left( M^{\prime }\right) \leq \limfunc{rang}\left( M\right) .$
\end{enumerate}











\subsection{Algorithme Fang-Tcheng}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{jordan}
\caption{Wilhelm \bsc{Jordan} \\ (1842-1899)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.3cm}

Notre eurocentrisme préfère nommer cet algorithme \textsc{Gauss-Jordan}...

Nous allons le présenter sur un exemple. Soit à chercher la $\ell$-ré%
duite échelonnée de la matrice 
\begin{equation*}
A=\left( 
\begin{array}{rrrr}
2 & 5 & -2 & 3 \\ 
3 & 6 & 3 & 6 \\ 
1 & 2 & -1 & 2%
\end{array}%
\right)
\end{equation*}%
Nous allons faire appara\^{\i}tre les pivots ordonnés par numéro de
ligne et numéro de colonne, cela veut dire que si un pivot (qui sera
toujours égal à 1) est obtenu à la ligne $i$ et colonne $j,$ le
pivot suivant sera au moins\ en ligne $i+1$ et en colonne $j+1$ et on
s'imposera de trouver la solution minimale en numéro de ligne et numé%
ro de colonne.

\begin{itemize}
\item \textbf{Première étape.} On repère l'élément de la
première colonne qui est le plus grand en valeur absolue (il peut y
avoir plusieurs choix). Si le résultat est nul (la première colonne
ne contient que des zéros), la première colonne ne peut être une
colonne pivot et on passe à la colonne suivante. Ici c'est 3 qui se
trouve sur la deuxième ligne première colonne. On permute alors la
première ligne avec la deuxième ligne et on obtient%
\begin{equation*}
A_{1}=\left( 
\begin{array}{rrrr}
3 & 6 & 3 & 6 \\ 
2 & 5 & -2 & 3 \\ 
1 & 2 & -1 & 2%
\end{array}%
\right)
\end{equation*}%
On divise tous les éléments de la première ligne par 3 : 
\begin{equation*}
A_{2}=\left( 
\begin{array}{rrrr}
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& 2 & 1 & 2 \\ 
2 & 5 & -2 & 3 \\ 
1 & 2 & -1 & 2%
\end{array}%
\right)
\end{equation*}%
On fait appara\^{\i}tre ensuite des zéros sous le premier 1 de la premi%
ère colonne en utilisant les opérations $L_{2}\leftarrow
L_{2}-2L_{1} $ et $L_{3}\leftarrow L_{3}-1L_{1}$ : 
\begin{equation*}
A_{3}=\left( 
\begin{array}{rrrr}
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& 2 & 1 & 2 \\ 
0 & 1 & -4 & -1 \\ 
0 & 0 & -2 & 0%
\end{array}%
\right)
\end{equation*}%
La première colonne est une colonne pivot et elle ne devra pas être
modifiée par la suite.

\item \textbf{Deuxième étape.} On repère dans la deuxième
colonne (en fait la colonne qui suit la dernière colonne pivot obtenue), 
à partir de la deu\-xième ligne (en fait à partir du numéro
de ligne qui suit le numéro de la ligne qui a donné le dernier
pivot), le plus grand élément en valeur absolue (si on obtient zé%
ro on passe à la colonne suivante, etc$\cdots ).$ Ici on obtient 1 qui
se trouve sur la deuxième ligne et deuxième colonne et il n'y a pas
de permutation de lignes à faire. Maintenant il faut faire appara\^{\i}%
tre des zéros dans la colonne pivot en ligne 1 et en ligne 3. On utilise
les opérations $L_{1}\leftarrow L_{1}-2L_{2}$ et $L_{3}\leftarrow
L_{3}-0L_{2}$ (qui ne sert à rien) ; on obtient : 
\begin{equation*}
A_{4}=\left( 
\begin{array}{rrrr}
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& 0 & 9 & 4 \\ 
0 & 
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& -4 & -1 \\ 
0 & 0 & -2 & 0%
\end{array}%
\right)
\end{equation*}%
La deuxième colonne est une colonne pivot, elle ne devra pas être
mo\-difiée dans la suite.

\item \textbf{Troisième étape. }On repère dans la colonne qui
suit la dernière colonne pivot obtenue et à partir de la ligne qui
suit la ligne qui a donné le dernier pivot le plus grand élément
en valeur asolue. Ici c'est -2 qui se trouve sur la troisième ligne et
troisième colonne, la troisième colonne est alors la troisième
colonne pivot. Il n'y a pas de permutation de lignes à faire, nous
n'avons qu'à faire appara\^{\i}tre un 1 à la place de -2 puis faire
appara\^{\i}tre des zéros dans la colonne pivot en conservant é%
videmment le pivot 1. Appliquons à $A_{4}$ l'opération $%
L_{3}\leftarrow -\frac{1}{2}L_{3}$%
\begin{equation*}
A_{5}=\left( 
\begin{array}{rrrr}
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& 0 & 9 & 4 \\ 
0 & 
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& -4 & -1 \\ 
0 & 0 & 1 & 0%
\end{array}%
\right)
\end{equation*}%
puis appliquons $L_{1}\leftarrow L_{1}-9L_{3}$ et $L_{2}\leftarrow
L_{2}+4L_{3}$%
\begin{equation*}
A_{6}=\left( 
\begin{array}{rrrr}
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& 0 & 0 & 4 \\ 
0 & 
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& 0 & -1 \\ 
0 & 0 & 
\begin{tabular}{|l|}
\hline
1 \\ \hline
\end{tabular}
& 0%
\end{array}%
\right)
\end{equation*}%
Nous venons d'obtenir la $\ell$-réduite échelonnée de $A,$ $A$ est de
rang 3.
\end{itemize}


Nous avons utilisé, ici, la méthode dite du pivot partiel en
cherchant dans chaque colonne le plus grand élément en valeur
absolue. Si nous avions choisi de prendre le premier élément rencontr%
é non nul, en vertu de l'unicité de la $\ell$-réduite échelonn%
ée, nous aurions obtenu le même résultat final. Il est conseill%
é, en programmation, d'utiliser la méthode dite pivot partiel pour 
éviter une trop grande propagation des erreurs lors des divisions par
des petits nombres. Si on fait les calculs à la main il vaut mieux se
contenter de choisir, tant que c'est possible, des nombres sympathiques.


\begin{theoreme}
$A$ est une matrice carrée d'ordre $n$ inversible si, et seulement si,
le rang de $A$ est égal à $n.$
\end{theoreme}

Nous avons en fait déjà démontré une partie de ce théor%
ème mais, vu son importance, nous allons reprendre ce qui a été
dit. Supposons donc que le rang de $A$ est égal à $n,$ dans ces
conditions la $\ell$-réduite échelonnée de $A$ est $\bbi_n ,$ cela
signifie que $A\overset{\ell}{\equiv }\bbi_n $ et donc qu'il existe $A^{\prime
}$ vérifiant $A^{\prime }\times A=\bbi_n ,$ $A^{\prime }$ est l'inverse de 
$A.$ Supposons maintenant que la rang de $A$ est strictement inférieur 
à $n,$ il est alors s\^{u}r que la dernière ligne de la $\ell$-ré%
duite échelonnée de $A$ est une ligne nulle. Notons $B$ cette $\ell$-r%
éduite échelonnée, nous savons que $A$ inversible équivaut 
à écrire que $B$ est inversible puisque $A\overset{\ell}{\equiv }B.$
Supposons $B$ inversible, il existe alors $B^{\prime }$ vérifiant $%
B\times B^{\prime }=\bbi_n $ or cette égalité est impossible car la
dernière ligne de $B$ étant nulle, la dernière ligne du produit $%
B\times B^{\prime }$ sera aussi nulle et donc distincte de la dernière
ligne de $\bbi_n .$ Nous venons de démontrer%
\begin{equation*}
\text{rg}\left( A\right) <n\limp A\text{ non inversible}
\end{equation*}%
et donc $A$ inversible $\limp \text{rg}\left( A\right) =n$.

\textbf{Pratique : }pour rechercher la matrice inverse de $A$, si elle
existe, on applique simultanément sur $\bbi_n $ les opérations faites
pour déterminer la $\ell$-réduite échelonnée de $A.$ Pour cela on
considère le tableau 
\begin{equation*}
\left[ A\left\vert \bbi_n \right. \right]
\end{equation*}%
on applique l'algorithme Fang Tcheng %\begin{CJK}{UTF8}{song}  方程 \end{CJK} ^J à $A,$ la partie gauche du
tableau, et chaque opération faite sur la partie gauche est reproduite
sur la partie droite. Si la $\ell$-réduite de $A$ est la matrice $\bbi_n $ (le r%
ésultat de la partie gauche est $\bbi_n )$ alors $A$ est inversible et sa
matrice inverse est donnée par la partie droite. Si la partie gauche ne
donne pas $\bbi_n ,$ $A$ n'est pas inversible, son rang est strictement inf%
érieur à $n.$


\subsection{Résolution de systèmes}




\subsubsection{Généralités}

\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{cramer}
\caption{Gabriel \bsc{Cramer} \\ (1704-1752)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.5cm}

On appelle \textbf{système de }$n$\textbf{\ équations linéaires 
à }$p$\textbf{\ inconnues} dans $\mathbb{A}$  tout système de la forme : 
\begin{equation*}
(S):\left\{ 
\begin{array}{c}
\sum\limits_{j=1}^{p}a_{i,j}x_{j}=b_{i} \\ 
i\in \left\{ 1,2,\cdots ,n\right\} \\ 
a_{i,j}\text{ et }b_{i}\in \mathbb{K}%
\end{array}%
\right.
\end{equation*}%
Soit aussi%
\begin{equation*}
(S):\left\{ 
\begin{array}{c}
a_{1,1}x_{1}+a_{1,2}x_{2}+\cdots +a_{1,p}x_{p}=b_{1} \\ 
\vdots \\ 
a_{n,1}x_{1}+a_{n,2}x_{2}+\cdots +a_{n,p}x_{p}=b_{p}%
\end{array}%
\right. \vspace{0.2cm}
\end{equation*}%
$x_{1},x_{2},\cdots ,x_{p}$ sont les $p$ inconnues, les $a_{i,j}$ sont appel%
és les coefficients du système $(S)$ et les $b_{i}$ sont appelés
les seconds membres (ce sont aussi des coefficients du système $(S)).$

Notons $A=(a_{i,j})\in \bba^{n\times p}$ ($A$ est appelée
la matrice du système).

$X=\left( 
\begin{array}{c}
x_{1} \\ 
x_{2} \\ 
\vdots \\ 
x_{p}%
\end{array}
\right) $ est la matrice colonne des inconnues et $B=\left( 
\begin{array}{c}
b_{1} \\ 
b_{2} \\ 
\vdots \\ 
b_{n}%
\end{array}
\right) $ est la matrice colonne des seconds membres, le système $(S)$ s'%
écrit matriciellement : 
\begin{equation*}
\left( 
\begin{array}{cccccc}
a_{1,1} & a_{1,2} & . & . & . & a_{1,p} \\ 
a_{2,1} & a_{2,2} & . & . & . & a_{2,p} \\ 
. & . & . & . & . & . \\ 
. & . & . & . & . & . \\ 
a_{n,1} & a_{n,2} & . & . & . & a_{n,p}%
\end{array}
\right) \times \left( 
\begin{array}{c}
x_{1} \\ 
x_{2} \\ 
\vdots \\ 
x_{p}%
\end{array}
\right) =\left( 
\begin{array}{c}
b_{1} \\ 
b_{2} \\ 
\vdots \\ 
b_{n}%
\end{array}
\right)
\end{equation*}
soit aussi 
\begin{equation*}
A\times X=B\text{ ou }^{t}X\times ^{t}A=^{t}B
\end{equation*}

Résoudre le système $(S)$ c'est chercher tous les $p$-uplets $%
(x_{1},x_{2},\cdots ,x_{p})$ de $\mathbb{A}^{p}$ qui vérifient simultan%
ément les $n$ équations. C'est aussi chercher toutes les matrices $%
X=\left( 
\begin{array}{c}
x_{1} \\ 
x_{2} \\ 
\vdots \\ 
x_{p}%
\end{array}%
\right) \in \bba^{p\times 1}$ vérifiant l'égalité
matricielle $A\times X=B.$ C'est pourquoi, dans ce qui suit, nous serons
souvent amenés à confondre le $p$-uplet $(x_{1},x_{2},\cdots ,x_{p})$
avec la matrice colonne $\left( 
\begin{array}{c}
x_{1} \\ 
x_{2} \\ 
\vdots \\ 
x_{p}%
\end{array}%
\right) .$ Attention, en informatique et plus particulièrement en ré%
seaux, le $p$-uplet $(x,x_{2},\cdots ,x_{p})$ est aussi noté
matriciellement par 
\begin{equation*}
\left( 
\begin{array}{llll}
x_{1} & x_{2} & \cdots & x_{p}%
\end{array}%
\right)
\end{equation*}%
qui n'est autre que la transposée de $X.$

Le système est dit\textbf{\ homogène} si, et seulement si, tous les
seconds membres (les coefficients $b_{i}$) sont nuls. Dans ce cas le syst%
ème admet forcément au moins une solution : la solution nulle ou
solution banale qui est le $p$-uplet 
\begin{equation*}
(0,0,\cdots ,0)\in \mathbb{A}^{p}
\end{equation*}%
ou bien la matrice nulle $0_{p,1}$ si on note matriciellement cette solution.

Le système $A\times X=B$ est dit \textbf{régulier} ou de \textbf{%
Cramer} si, et seulement si, il a autant d'équations que d'inconnues et
si $A$ est inversible (le système ayant autant d'équations que
d'inconnues on a $n=p$ et $A$ est une matrice carrée$).$ $A$ étant
inversible, $A^{-1}$ existe et 
\begin{eqnarray*}
A\times X &=&B\text{ se transforme en} \\
A^{-1}\times (A\times X) &=&A^{-1}\times B,\text{ c'est-à-dire} \\
X &=&A^{-1}\times B
\end{eqnarray*}%
Le système admet donc au moins une solution qui est $A^{-1}\times B.$
Nous allons prouver qu'il n'y en a pas d'autre. Pour cela supposons
l'existence d'une autre solution $X^{\prime },$ nous avons alors simultan%
ément 
\begin{equation*}
A\times X=B\text{ et }A\times X^{\prime }=B
\end{equation*}%
En retranchant membre à membre on obtient : 
\begin{equation*}
A\times (X-X^{\prime })=0_{n,1}
\end{equation*}%
Multiplions maintenant les deux membres par $A^{-1}$%
\begin{eqnarray*}
A^{-1}\times \left( A\times (X-X^{\prime })\right) &=&A^{-1}\times
0_{n,1}=0_{n,1} \\
(A^{-1}\times A)\times (X-X^{\prime }) &=&0_{n,1} \\
\bbi_n \times (X-X^{\prime }) &=&0_{n,1}=X-X^{\prime }\text{ et pour finir} \\
X &=&X^{\prime }
\end{eqnarray*}%
Nous retiendrons que si le système $A\times X=B$ est tel que $A$ est
inversible (il est nécessaire que $A$ soit carrée et donc que le syst%
ème possède autant d'équations que d'inconnues) alors il admet
une unique solution qui est 
\begin{equation*}
X=A^{-1}\times B
\end{equation*}

\subsubsection{Systèmes équivalents et résolution}

Deux systèmes linéaires $(S)$ et $(S^{\prime })$ sont \textbf{é%
quivalents }si, et seulement si, ils possèdent le même ensemble
solution.

Nous allons définir trois opérations élémentaires :

\begin{enumerate}
\item Multiplication d'une équation par un scalaire (un élément
de $\mathbb{A)}$ non nul. Si $E_{i}$ est la $i\eme$ équation,
le résultat de la multiplication de $E_{i}$ par $\alpha \in \mathbb{A}$
est noté $\alpha E_{i}$ et nous écrirons $E_{i}\leftarrow \alpha
E_{i}.$%
\begin{eqnarray*}
E_{i} &:&\sum\limits_{j=1}^{p}a_{i,j}x_{j}=b_{i} \\
\alpha E_{i} &:&\sum\limits_{j=1}^{p}\alpha a_{i,j}x_{j}=\alpha b_{i}
\end{eqnarray*}%
Pour retrouver l'équation initiale il suffit de multiplier l'é%
quation obtenue par $\frac{1}{\alpha }$ et par conséquent le système
obtenu par cette opération est équi\-valent au système initial.

\item Permutation de deux équations, nous noterons $E_{i}%
\longleftrightarrow E_{j}$ l'opération qui consiste à permuter l'%
équation numéro $i$ avec l'équation numéro $j.$ Pour
retrouver le système initial il suffit d'appliquer de nouveau cette op%
ération, cela nous permet d'affirmer que cette opération transforme
un système en un système équivalent.

\item Ajout à une équation une autre équation multipliée par
un scalaire : si on ajoute à l'équation $E_{i}$ l'équation $%
E_{h\neq i}$ multipliée par $\beta $ nous noterons $E_{i}\leftarrow
E_{i}+\beta E_{h}$%
\begin{equation*}
\left\{ 
\begin{array}{l}
E_{i}:\sum\limits_{j=1}^{p}a_{i,j}x_{j}=b_{i} \\ 
E_{h}:\sum\limits_{j=1}^{p}a_{h,j}x_{j}=b_{h} \\ 
E_{i}\leftarrow E_{i}+\beta E_{h}:\sum\limits_{j=1}^{p}(a_{i,j}+\beta
a_{h,j})x_{j}=b_{i}+\beta b_{h}%
\end{array}%
\right.
\end{equation*}%
Pour retrouver l'équation de départ il suffit d'appliquer au ré%
sultat l'opéra\-tion $E_{i}\leftarrow E_{i}-\beta E_{h}$ et cette opé%
ration, comme les précédentes, transforme un système en un syst%
ème équivalent.
\end{enumerate}

Nous allons maintenant passer à la résolution : nous pouvons é%
crire le système 

$
(S):\left\{ 
\begin{array}{c}
\sum\limits_{j=1}^{p}a_{i,j}x_{j}=b_{i} \\ 
i\in \left\{ 1,2,\cdots ,n\right\} \\ 
a_{i,j}\text{ et }b_{i}\in \mathbb{A}%
\end{array}%
\right.
$
sous la forme 
$\left[ A\mid B\right]$

où $A$ est la matrice du système et $B$ la matrice colonne des
seconds membres. Nous notons $T$ cette matrice (ou ce tableau), le nombre de
lignes de $T$ est égal au nombre de lignes de $A$ soit aussi le nombre d'%
équations de $\left( S\right) ,$ le nombre de colonnes de $T$ est é%
gal au nombre de colonnes de $A+1$ soit aussi le nombre d'inconnues $+1.$
Les opérations élémentaires sur les équations sont alors des
opérations élémentaires sur les lignes de ce tableau, les opé%
rations se faisant simultanément sur la partie gauche et sur la partie
droite, c'est-à-dire sur le tableau $T.$ Appliquons à ce tableau
l'algorithme de Gauss-Jordan pour obtenir la $ \ell$-réduite échelonné%
e de $A$ (on ne cherchera pas pour le moment à faire appara\^{\i}tre un
pivot dans la dernière colonne du tableau) et notons $R$ cette $ \ell$-ré%
duite échelonnée. Nous notons le résultat 
\begin{equation*}
T^{\prime }=\left[ R\mid H\right] ,R=\ell\text{ré}\left( A\right)
\end{equation*}%
Le système est alors devenu $R\times X=H.$ Comme on a $A\overset{\ell}{%
\equiv }R$ et $B\overset{\ell}{\equiv }H$, il existe $P$ (rappel, $P$ est
inversible) telle que 
$$R =P\times A \qquad
H =P\times B
$$
Si nous notons $U$ une solution du système ($S)$, $U$ vérifie 
\begin{equation*}
A\times U=B
\end{equation*}%
et en multipliant les deux membres à gauhe par $P$ on obtient 
\begin{eqnarray*}
P\times A\times U &=&P\times B\text{ soit} \\
R\times U &=&H
\end{eqnarray*}%
De même toute solution de $R\times X=H$ est solution de $A\times X=B,$
en effet notons de même $U$ une solution de $R\times X=H$, on a 
\begin{eqnarray*}
R\times U &=&H\text{ donc} \\
P\times A\times U &=&P\times B
\end{eqnarray*}%
et en multipliant les deux membres à gauche par $P^{-1}$ on obtient 
\begin{equation*}
A\times U=B
\end{equation*}%
On a bien prouvé que les deux systèmes $A\times X=B$ et $R\times X=H$
sont équivalents. Il nous reste à résoudre le système $%
R\times X=H.$

Continuons, si besoin, le calcul de la $ \ell$-réduite échelonnée de $%
T $ et notons $T^{\prime \prime }$ le résultat :%
\begin{equation*}
T^{\prime }=\left[ R\mid H\right] ,T^{^{\prime \prime }}=\left[ R\mid
H^{\prime }\right]
\end{equation*}%
Si on arrive à faire appara\^{\i}tre un pivot dans la dernière
colonne, les opérations sur les lignes ne modifieront pas la partie
gauche car la partie gauche de cette ligne pivot est constituée de zé%
ros.

\begin{itemize}
\item Si le système est homogène (tous les seconds membres sont
nuls) on a forcément $T^{\prime }=T^{\prime \prime }$ et le système
admet, rappelons-le, au moins la solution nulle.

\item Si le rang de $T$ est supérieur au rang de $R$ (c'est donc que le
rang de $T$ est d$^{\text{'}}$une unité supérieure au rang de $A,$
on ne peut créer qu'un seul nouveau pivot au maximum) cela signifie
qu'il y a plus de lignes nulles dans $R$ que dans $T^{\prime \prime }$ et
par conséquent que le système $R\times X=H^{\prime }$ contient l'%
équation du type 
\begin{equation*}
0x_{1}+0x_{2}+\cdots +0x_{p}=1
\end{equation*}%
ou que le système $R\times X=H$ contient au moins une équation du
type%
\begin{equation*}
0x_{1}+0x_{2}+\cdots +0x_{p}=h\text{ avec }h\neq 0
\end{equation*}%
ce qui est impossible et le système n'admet pas de solution.

\item Si $\limfunc{rang}(T)=\limfunc{rang}(R)=r,$ c'est que $T^{\prime
}=T^{^{\prime \prime }}$ et la résolution de $A\times X=B$ équivaut 
à la résolution des $r$ équations non nulles de $R\times X=H.$
Deux cas peuvent se présenter :

\begin{enumerate}
\item $r=p,$ le système à résoudre est alors de la forme : 
\begin{equation*}
\left\{ 
\begin{array}{ccccc}
x_{1} &  &  &  & =h_{1} \\ 
& x_{2} &  &  & =h_{2} \\ 
&  & \vdots &  & \vdots \\ 
&  &  & x_{p} & =h_{p}%
\end{array}%
\right.
\end{equation*}%
et il est résolu, il y a unicité de la solution.

\item $r<p.$ Nous appelons inconnues pivots ou inconnues principales $\left(
IP\right) $ les $r$ inconnues $x_{j_{1}},x_{j_{2}},\cdots ,x_{j_{r}}$
correspondant aux $r$ colonnes pivots $j_{1},j_{2},\cdots ,j_{r}$ de $R.$
Les $p-r$ autres inconnues sont appelées inconnues non principales $%
\left( INP\right) ,$ certains les appellent aussi des inconnues ou des
variables libres ou encore des paramètres. Pour résoudre le systè%
me la métho\-de consiste à faire passer dans les seconds membres\
les inconnues non principales, le système devient alors un sytème de
Cramer résolu dont les solutions dépendent des $p-r$ inconnues non
principales (ces inconnues non principales sont, à ce stade, considér%
ées comme des paramètres), \textbf{il y a donc une infinité de
solutions }; si l'on désire une solution particulière, il suffit de
donner des valeurs arbitraires aux inconnues non principales. 
\begin{equation*}
\left\{ 
\begin{array}{ccccc}
x_{j_{1}} &  &  &  & =h_{j_{1}}+e_{j_{1}} \\ 
& x_{j_{2}} &  &  & =h_{j_{2}}+e_{j_{2}} \\ 
&  & \vdots &  & \vdots \\ 
&  &  & x_{j_{r}} & =h_{j_{r}}+e_{j_{r}}%
\end{array}%
\right.
\end{equation*}%
où les $e_{j_{i}}$ sont des expressions linéaires des $\left(
p-r\right) $ $INP.$
\end{enumerate}
\end{itemize}

Il faut remarquer que si l'on modifie l'ordre d'écriture des inconnues
nous n'obtiendrons pas forcément les mêmes inconnues principales et
non principales mais l'ensemble solution sera évidemment le même.









% \section{Vade-mecum}




% \begin{itemize}
% \item Vous devez savoir ce qu'est un groupe, $E$ a une structure de groupe
% ssi on a défini dans $E$ une loi de composition interne = une opération (le plus
% souvent cette opération est notée $+$) qui a \og de 
% bonnes propriétés\fg{} (voir le cours).

% \item $H$ est un sous groupe de $E$ ssi $H\subseteq E$ et $H\neq \varnothing 
% $ et si $H$ est stable pour l'opération de groupe $+$. Qu'est-ce que
% cela signifie ? Tout simplement que si on fait des additions ou des
% soustractions dans $H,$ on \og reste\fg{} ou on \og ne sort pas\fg{} de $H$, il suffit de
% retenir ce résultat ! Donc, par exemple, si $x\notin H$ on a forcément $x-x=0_{E}\in H.$

% \item $E$ est un espace vectoriel sur $\mathbb{R}$ (par exemple mais ce peut 
% \^{e}tre un autre corps, pour les codes détecteurs et correcteurs
% d'erreurs on utilse le corps $\mathbb{F}_{2}$) ssi on a défini 2 opérations dans
% $E$:
%  une addition \og interne\fg{} qui fait que $E$ est un groupe
% commutatif et  une multiplication  par un  scalaire = un  nombre (ici  un nombre
% réel) qui a de \og bonnes\fg{} propriétés.

% \item Si $E$ est un e.v. sur $\mathbb{R},$ que signifie \og $H$ est un sous
% espace vectoriel ? Tout simplement que $H\subseteq E$ et $H\neq \varnothing $
% et que $H$ est stable pour les opérations de l'espace vectoriel. Si on
% fait des calculs dans $H,$ on reste dans $H,$ il suffit de retenir ce résultat!
%  Par exemple, si $H$ est un sev de $E,$ et si $u\in H$ on doit avoir 
% $u-u=0_{E}\in H$ ou encore $0.u=0_{E}\in H.$

% \item Si $E$ est un e.v. sur $\mathbb{R},$ il est d'usage d'appeler les éléments
%   de $E$ des vecteurs, $0_{E}=$ \og le zéro de $E$\fg{} i.e. le vecteur
% nul.

% \item Faire des calculs dans un e.v. c'est \og faire des combinaisons linéaires\fg{} = CL.

% \item Une CL de vecteurs c'est un calcul o\`{u} interviennent ces vecteurs.

% \item Une famille de vecteurs = une suite de vecteurs = une liste ordonnée de vecteurs

% \item Si $\mathcal{F}=\left( u,v,w\right) $ est une famille de vecteurs de $%
% E,$ 
% \begin{eqnarray*}
% 2u-3v+0w &=&2u-3v \\
% 0u+0v+1w &=&w
% \end{eqnarray*}%
% sont des CL des vecteurs de $\mathcal{F}.$

% \item On note $\func{Vect}\left( \mathcal{F}\right) $ l'ensemble des CL des
% vecteurs de $\mathcal{F}.$ Donc si $z\in \func{Vect}\left( u,v,w\right) ,$
% cela signifie que $z$ peut s'écrire comme une CL des vecteurs de $%
% \mathcal{F}.$

% \item $\func{Vect}\left( \mathcal{F}\right) $ est un sev (évident).

% \item Dire que $\mathcal{F}$ est génératice de $E,$ c'est dire que $%
% E=\func{Vect}\left( \mathcal{F}\right) ,$ c'est donc dire que tout vecteur
% de $E$ peut s'écrire comme une CL des vecteurs de $\mathcal{F}.$

% \item Considérons la famille de $k$ vecteurs $\mathcal{F}=\left(
% u_{1},u_{2},...,u_{k}\right) $ et considérons l'équation 
% \[
% \alpha _{1}u_{1}+\alpha _{2}u_{2}+...+\alpha _{k}u_{k}=0=0_{E}
% \]%
% o\`{u} les $\alpha _{i}$ sont les inconnues réelles. Il est clair que
% cette équation a pour solution%
% \[
% \alpha _{1}=\alpha _{2}=...=\alpha _{k}=0=0_{\mathbb{R}}
% \]

% \begin{itemize}
% \item Si c'est la seule solution on dit que la famille $\mathcal{F}$ est
% libre ou que les vecteurs de $\mathcal{F}$ sont linéairement indépendants.

% \item Si ce n'est pas la seule solution, on dit que la famille $\mathcal{F}$
% est liée ou que les vecteurs de $\mathcal{F}$ sont linéairement dépendants.

% \item Donc une famille qui n'est pas libre est liée et une famille qui
% n'est pas liée est libre, \og libre\fg{} est le contraire logique de \og liée\fg{}.
% \end{itemize}

% \item $\mathcal{F}=\left( u\right) $ est libre ssi $u\neq 0_{E}$ ($u$ est
% différent du vecteur nul)

% \item Si $\mathcal{F=}\left( u,v\right) $ est liée on dit que $u$ et $v$
% sont colinéaires : l'un peut s'écrire comme une CL de l'autre.

% \item Une famille qui comporte le vecteur nul est forcément liée.

% \item $\mathcal{F}$ est liée ssi l'un des vecteurs de $\mathcal{F}$ peut
% s'écrire comme une CL des autres.

% \item Une  base de  $E$ est une  famille libre et  génératrice, on  démontre que
%   toutes les bases  d'un espace vectoriel ont le m\^{e}me  nombre d'éléments, ce
%   nombre s'appelle la dimension de l'e.v. 

% \item Soit $\mathcal{B=}\left( e_{1},e_{2},...,e_{n}\right) $ une base de $E$
% et $u$ un vecteur quelconque de  $E$ ; $\mathcal{B}$ étant génératrice, $u$ peut
% s'écrire comme une CL des vecteurs de $\mathcal{B}$ et
% comme $\mathcal{B}$ est libre on démontre que cette écriture est
% unique : il existe donc $n$ réels $x_{1},...,x_{n}$ vérifiant%
% \[
% u=x_{1}e_{1}+...+x_{n}e_{n}
% \]%
% ces réels sont uniques, on dit que l'on a décomposé $u$ dans la
% base $\mathcal{B}$ et ces réels sont les coordonnées de $u$ dans la
% base $\mathcal{B},$ notation :%
% \[
% u\left(
% \begin{smallmatrix}
% x_{1} \\ 
% x_{2} \\ 
% \vdots  \\ 
% x_{n}%
% \end{smallmatrix}%
% \right) _{\mathcal{B}}
% \]%
% pour exprimer que $u=\sum\limits_{i=1}^{n}x_{i}e_{i}$ et on dit que $\left( 
% \begin{smallmatrix}
% x_{1} \\ 
% x_{2} \\ 
% \vdots  \\ 
% x_{n}%
% \end{smallmatrix}%
% \right) $ est la matrice des coordonnées de $x$ dans la base $\mathcal{B}%
% .$

% \item $\mathbb{R}^{n}$ est un e.v. sur $\mathbb{R}$ avec les opérations
% \og addition de 2 $n$-uplets et multiplication d'un $n$-uplet par un réel\fg{}.

% \item Soit $x=\left( x_{1},x_{2},\ldots ,x_{n}\right) $ un vecteur
% quelconque de $\mathbb{R}^{n},$ $x$ peut s'écrire 
% \[
% x=x_{1}\left( 1,0,\ldots ,0\right) +x_{2}\left( 0,1,0,\cdots ,0\right)
% +\cdots +x_{n}\left( 0,0,\cdots ,0,1\right) 
% \]%
% Nous notons  $e_{i}$ le $n$-uplet  de $\mathbb{R}^{n}$  qui a tous  ses éléments
% nuls sauf le $i^{\grave{e}me}$ qui est égal à 1: 
% \begin{eqnarray*}
% e_{1} &=&\left( 1,0,0,\cdots ,0,0\right)  \\
% e_{2} &=&\left( 0,1,0,\cdots ,0,0\right)  \\
% &&\vdots  \\
% e_{n} &=&\left( 0,0,0,\cdots ,0,1\right) 
% \end{eqnarray*}%
% la famille $\mathcal{B=}\left( e_{1},e_{2},...,e_{n}\right) $ est une base
% de $\mathbb{R}^{n},$ la dimension de $\mathbb{R}^{n}$ est donc égale 
% à $n.$

% \item $\left\{ 0_{E}\right\} $ est un sev de $E,$ sa dimension est égale 
% à 0 (convention).

% \item Dans $\mathbb{R}^{n}$ toute famille libre de $n$ vecteurs est gén%
% ératrice et est donc une base.

% \item Dans $\mathbb{R}^{n}$ toute famille génératrice de $n$
% vecteurs est libre et est donc une base.

% \item On appelle \textbf{matrice d'une famille} dans une base, la matrice
% des  coordonnées des  vecteurs  de cette  famille dans  la  base considérée;  on
% juxtapose les coordonnées des vecteurs de la famille dans la
% base et le  résultat est la matrice  de la famille dans la  base. Considérons la
% famille de $p$ vecteurs de $\mathbb{K}^{n}$ : 
% \[
% \mathcal{F}=\left( u_{1},u_{2},\ldots ,u_{p}\right) 
% \]%
% Notons les coordonnées de $u_{j}$ dans la base $\mathcal{B}$ par 
% \[
% u_{j}\left( 
% \begin{smallmatrix}
% a_{1,j} \\ 
% a_{2,j} \\ 
% \vdots  \\ 
% a_{n,j}%
% \end{smallmatrix}%
% \right) _{\mathcal{B}}
% \]%
% et la matice de $\mathcal{F}$ dans la base $\mathcal{B}$ est 
% \[
% A=\limfunc{Mat}\nolimits_{\mathcal{B}}\left( \mathcal{F}\right) =\left(
% a_{i,j}\right) \in \mathcal{M}_{n,p}\left( \mathbb{R}\right) 
% \]%
% $A$ est aussi qualifiée de \textbf{matrice génératrice} de $%
% \limfunc{Vect}\left( \mathcal{F}\right) $ dans la base $\mathcal{B}$ et les
% colonnes de $A$ sont appelées des vecteurs colonnes.

% \item Le rang d'une famille $\mathcal{F}$ est le rang de sa matrice dans une
% base, on note%
% \[
% \limfunc{rang}\left( \mathcal{F}\right) =\limfunc{rang}\left( \limfunc{Mat}%
% \nolimits_{\mathcal{B}}\left( \mathcal{F}\right) \right) 
% \]

% \item Le rang d'une famille $\mathcal{F}$ est la taille des familles libres
% maximales que l'on peut extraire de $\mathcal{F},$ ces familles libres
% maximales étant des bases de $\func{Vect}\left( \mathcal{F}\right) .$

% \item Si $\mathcal{F}$ est une famille de $p$ vecteurs de $\mathbb{K}^{n}$
% alors 
% \[
% \limfunc{Vect}\left( \mathcal{F}\right) =\mathbb{K}^{n}\Leftrightarrow 
% \limfunc{rang}\left( \mathcal{F}\right) =n
% \]

% \item Voici le problème : $\mathcal{B}=\left( e_{1},e_{2},\cdots
% ,e_{n}\right) $ et $\mathcal{B}^{\prime }=\left( e_{1}^{\prime
% },e_{2}^{\prime },\cdots ,e_{n}^{\prime }\right) $ sont deux bases de $%
% \mathbb{K}^{n},$ on connaît les coordonnées d'un vecteur $x$ dans $%
% \mathcal{B}$ ainsi que les coordonnées des vecteurs de $\mathcal{B}%
% ^{\prime }$ dans la base $\mathcal{B}$ et on cherche les coordonnées de $%
% x$ dans la base $\mathcal{B}^{\prime }.$ Pour résoudre ce problème
% nous allons utiliser les notations suivantes :

% \item $X=\left( 
% \begin{smallmatrix}
% x_{1} \\ 
% x_{2} \\ 
% \vdots \\ 
% x_{n}%
% \end{smallmatrix}
% \right) $ est la matrice colonne des coordonnées de $x$ dans la base $%
% \mathcal{B}.$

% \item $X^{\prime }=\left( 
% \begin{smallmatrix}
% x_{1}^{\prime } \\ 
% x_{2}^{\prime } \\ 
% \vdots \\ 
% x_{n}^{\prime }%
% \end{smallmatrix}
% \right) $ est la matrice colonne des coordonnées de $x$ dans la base $%
% \mathcal{B}^{\prime }.$

% \item $P=(p_{i,j})\in \mathcal{M}_{n}(\mathbb{K})$ est la matrice de la
% famille $\mathcal{B}^{\prime }$ dans la base $\mathcal{B},$ $P=\limfunc{Mat}%
% _{\mathcal{B}}(\mathcal{B}^{\prime }).$ Cela signifie que la $j^{i\grave{e}%
% me}$ colonne de $P$ nous donne les coordonnées de $e_{j}^{\prime }$ dans 
% $\mathcal{B},$ $P$ est appelée la \textbf{matrice de passage} de $%
% \mathcal{B}$ à $\mathcal{B}^{\prime }.$ Par hypothèse nous avons : 
% \[
% \left\{ 
% \begin{array}{c}
% x=\sum\limits_{i=1}^{n}x_{i}e_{i} \\ 
% x=\sum\limits_{j=1}^{n}x_{j}^{\prime }e_{j}^{\prime } \\ 
% e_{j}^{\prime }=\sum\limits_{i=1}^{n}p_{ij}e_{i}%
% \end{array}%
% \right. 
% \]%
% on en déduit que 
% \[
% x=\sum\limits_{j=1}^{n}x_{j}^{\prime }e_{j}^{\prime
% }=\sum\limits_{j=1}^{n}x_{j}^{\prime }\left(
% \sum\limits_{i=1}^{n}p_{ij}e_{i}\right) =\sum\limits_{i=1}^{n}\left(
% \sum\limits_{j=1}^{n}p_{ij}x_{j}^{\prime }\right) e_{i}
% \]%
% or nous savons que la décomposition d'un vecteur dans une base est
% unique et, par conséquent, 
% \[
% \left\{ 
% \begin{array}{c}
% \sum\limits_{j=1}^{n}p_{ij}x_{j}^{\prime }=x_{i} \\ 
% i\in \mathbb{N}_{n}%
% \end{array}%
% \right. 
% \]%
% les coordonnées de $x$ dans $\mathcal{B}^{\prime }$ sont donc les
% solutions du système linéaire précédent qui s'écrit
% matriciellement : 
% \[
% P\times X^{\prime }=X
% \]%
% Ce système est forcément un système de Cramer, il a autant d'%
% équations que d'incon\-nues et il possède un unique $n$-uplet
% solution puisque nous sommes s\^{u}rs de l'existence et de l'unicité des 
% $x_{j}^{\prime }.$ $P$ est donc de rang $n$ et est inversible (on en é%
% tait s\^{u}r, $P$ est de rang $n$ puisque $\mathcal{B}^{\prime }$ est
% libre), la solution $X^{\prime }$ cherchée est alors donnée par 
% \[
% X^{\prime }=P^{-1}\times X
% \]%
% Ce résultat est à retenir.

% \item Si $P$ est la matrice de passage de $\mathcal{B}$ à $\mathcal{B}%
% ^{\prime }$ alors $P^{-1}$ est la matrice de passage de $\mathcal{B}^{\prime
% }$ à $\mathcal{B}.$

% \item Soit $\mathcal{F}$ une famille de $p$ vecteurs et $A=\limfunc{Mat}_{%
% \mathcal{B}}\left( \mathcal{F}\right) $, de ce qui précède on dé%
% duit%
% \[
% A^{\prime }=\limfunc{Mat}\nolimits_{\mathcal{B}^{\prime }}\left( \mathcal{F}%
% \right) =P^{-1}\times A
% \]%
% puisque si on note $X$ une colonne de $A,$ c'est-à-dire la matrice des
% coordonnées d'un vecteur de $\mathcal{F}$ dans $\mathcal{B},$ la colonne
% correspondante de $A^{\prime }$ est $P^{-1}\times X.$ Comme le rang de $%
% A^{\prime }$ est égal au rang de $A,$ il est alors prouvé que le
% rang d'une famille ne dépend pas de la base choisie.

% \item $E$ et $F$ sont deux espaces vectoriels sur le m\^{e}me corps $\mathbb{%
% R}$ (nous utiliserons les m\^{e}mes notations pour les lois de $E$ et les
% lois de $F)$ et $f$ est une application de $E$ dans $F.$ On dit que $f$ est
% une \textbf{application linéaire} de $E$ dans $F$ si, et seulement si, 
% \[
% \left\{ 
% \begin{array}{l}
% \forall (u_{1},u_{2})\in E\times E,f(u_{1}+u_{2})=f(u_{1})+f(u_{2}) \\ 
% \forall (\alpha ,u)\in \mathbb{K\times }E,f(\alpha u)=\alpha f(u)%
% \end{array}%
% \right. 
% \]%
% En fran\c{c}ais courant cela signifie que l'image de toute CL de vecteurs de 
% $E$ est égale à la CL des images de ces vecteurs.

% \item L'ensemble des applications linéaires de $E$ dans $F$ est noté 
% $\mathcal{L}(E,F),$ c'est un espace vectoriel sur $\mathbb{K}$ avec les op%
% érations suivantes : 
% \begin{eqnarray*}
% (f,g) &\in &\mathcal{L}(E,F)^{2},\left\{ 
% \begin{array}{ll}
% f+g\text{ :} & E\longrightarrow F \\ 
% & x\longmapsto f(x)+g(x)%
% \end{array}%
% \right.  \\
% (\alpha ,f) &\in &\mathbb{K\times }\mathcal{L}(E,F),\left\{ 
% \begin{array}{ll}
% \alpha f\text{ :} & E\longrightarrow F \\ 
% & x\longmapsto \alpha f(x)%
% \end{array}%
% \right. 
% \end{eqnarray*}

% \item $f(x+0_{E})=f(x)=f(x)+f(0_{E})$ et par conséquent $f(0_{E})=0_{F}.$
% Une autre démonstration utilise : $f(0x)=f(0_{E})=0f(x)=0_{F}.$

% \item $f(-x)=f\left( (-1)x\right) =(-1)f(x)=-f(x).$

% \item Si $f\in (E,F)$ et $g\in \mathcal{L}(F,G)$ alors $g\circ f\in \mathcal{%
% L}(E,G),$ c'est très simple à démontrer, on prouve que $g\circ f$
% vérifie bien les deux propriétés attendues.

% \item Si $f$ est bijective on dit que $f$ est un \textbf{isomorphisme} (en
% fait un isomorphisme d'espaces vectoriels) de $E$ sur $F.$

% \item Si $E=F$ on dit que $f$ est un \textbf{endomorphisme} de $E.$ On note $%
% \mathcal{L}(E)$ l'ensemble des endomorphismes de $E$ au lieu de $\mathcal{L}%
% (E,E).$

% \item Un endomorphisme bijectif est appelé un \textbf{automorphisme}.

% \item Endomorphismes de $\mathbb{R}^{n}:$

% \begin{itemize}
% \item Dans ce qui suit $\mathcal{B}=\left( e_{1},e_{2},\cdots ,e_{n}\right) $
% est une base de $E=\mathbb{R}^{n}$ et $f$ est un endomorphisme de $E.$

% \item L'image par $f$ d'un sev est un sev.

% \item $f\left( E\right) =\func{Im}\left( f\right) $ est un sev de $E.$

% \item $\ker (f)=\left\{ x\in E\mid f(x)=0_{E}\right\} $ est un sev de $E.$

% \item La matrice de $f$ dans la base $\mathcal{B}=\left( e_{1},e_{2},\cdots
% ,e_{n}\right) $ n'est autre que la matrice de la famille $\left(
% f(e_{1}),f(e_{2}),\cdots ,f(e_{n})\right) $ dans la base $\mathcal{B}.$ Si
% nous notons $A$ cette matrice, $A$ est une matrice carrée d'ordre $n$ et
% si $A=\left( a_{i,j}\right) $ nous avons 
% \[
% f(e_{j})\left( 
% \begin{smallmatrix}
% a_{1j} \\ 
% a_{2j} \\ 
% \vdots  \\ 
% a_{nj}%
% \end{smallmatrix}%
% \right) _{\mathcal{B}}
% \]%
% ce qui équivaut à écrire 
% \[
% f(e_{j})=\sum_{i=1}^{n}a_{ij}e_{i}
% \]%
% et%
% \[
% \begin{array}{c}
% \left\{ 
% \begin{array}{ll}
% f\text{ :} & E\longrightarrow E \\ 
% & x\longmapsto y=f(x)%
% \end{array}%
% \right.  \\ 
% A=\limfunc{Mat}(f,\mathcal{B},\mathcal{B})=\limfunc{Mat}_{\mathcal{B}}\left(
% f\right)  \\ 
% Y=A\times X%
% \end{array}%
% \vspace{0.2cm}
% \]

% \item Le rang de $f$ est le rang de la famille $\left(
% f(e_{1}),f(e_{2}),\cdots ,f(e_{n})\right) ,$ c'est-à-dire la dimension
% de $\limfunc{Vect}\left( f(e_{1}),f(e_{2}),\cdots ,f(e_{n})\right) =\func{Im}%
% (f),$ mais c'est aussi le rang de la matrice $A.$

% \item Théorème du rang : $\dim \left( \func{Im}(f)\right) +\dim
% \left( \ker (f)\right) =\dim (E)=n.$ En conséquence

% \begin{itemize}
% \item Si $f$ est injective alors $\ker (f)=\left\{ 0_{E}\right\} $ et $\dim
% \left( \func{Im}(f)\right) =n$ ce qui prouve que $f$ est surjective.

% \item Si $f$ est injective $\left( f(e_{1}),f(e_{2}),\cdots ,f(e_{n})\right) 
% $ est une base de $\func{Im}(f)$ et $\func{Im}(f)=E.$

% \item Si $f$ est surjective alors $\func{Im}(f)=E$ et par conséquent $%
% \dim \left( \ker (f)\right) =0$ qui se traduit par $\ker (f)=\left\{
% 0_{E}\right\} $ et $f$ est injective.

% \item Si $\left( f(e_{1}),f(e_{2}),\cdots ,f(e_{n})\right) $ est une base de 
% $E,$ $f$ est surjective.

% \item Si $A$ est de rang $n,$ cela équivaut à écrire que $A$ est
% inversible, et donc $f$ est surjective.

% \item Nous venons de démontrer que les affirmations suivantes sont é%
% quivalentes

% \begin{itemize}
% \item $f$ est injective.

% \item $\ker (f)=\left\{ 0_{E}\right\} .$

% \item $f$ est surjective.

% \item L'image d'une base de $E$ par $f$ est une base de $E.$

% \item $f$ est bijective.

% \item $A$ est inversible.
% \end{itemize}
% \end{itemize}

% \item Si $f$ est bijective, la matrice de $f^{-1}$ dans la base $\mathcal{B}$
% est $A^{-1}$ 
% \[
% Y=A\times X\Leftrightarrow X=A^{-1}\times Y
% \]

% \item Si nous cherchons $A^{\prime }$ la matrice de $f$ dans la base $%
% \mathcal{B}^{\prime }$ en connaissant $P$ la matrice de passage de la base $%
% \mathcal{B}$ à la base $\mathcal{B}^{\prime }.$ Nous savons que si $X$ d%
% ésigne la matrice des coordonnées de $x$ dans $\mathcal{B}$ et $Y$
% la matrice colonne des coordonnées de $y=f(x)$ dans $\mathcal{B}$ alors 
% \[
% Y=A\times X
% \]%
% En notant $X^{\prime }$ la matrice de $x$ et $Y^{\prime }$ la matrice de $y$
% dans la base $\mathcal{B}^{\prime }$ nous avons 
% \[
% Y^{\prime }=A^{\prime }\times X^{\prime }
% \]%
% En utilisant $X=P\times X^{\prime }$ et $Y=P\times Y^{\prime }$ nous
% obtenons l'égalité 
% \[
% P\times Y^{\prime }=A\times P\times X^{\prime }
% \]%
% et comme $P$ est inversible 
% \[
% Y^{\prime }=P^{-1}\times A\times P\times X
% \]%
% ce qui nous donne 
% \[
% A^{\prime }=P^{-1}\times A\times P
% \]%
% Un moyen mnémotechnique pour utiliser rapidement et sans effort ce ré%
% sultat est le suivant%
% \[
% \begin{array}{ccc}
% E_{\mathcal{B}} & \overset{f}{\underset{A}{\longrightarrow }} & E_{\mathcal{B%
% }} \\ 
% P\downarrow \uparrow P^{-1} & \text{ } & P^{-1}\uparrow \downarrow P \\ 
% E_{\mathcal{B}^{\prime }} & \overset{f}{\underset{A^{\prime }}{%
% \longrightarrow }} & E_{\mathcal{B}^{\prime }}%
% \end{array}%
% \]%
% Ce diagramme se lisant : $A^{\prime }=P^{-1}\times A\times P$ ou encore $%
% A=P\times A^{\prime }\times P^{-1}.$

% \item Valeurs propres et diagonalisation : on se propose de chercher s'il
% existe des sev $U$ de sorte que la restriction de $f$ à $U$ soit une
% homothétie (si $u\in U,$ $f\left( u\right) =\lambda u).$

% \begin{itemize}
% \item $\lambda \in \mathbb{R}$ est une valeur propre (vap) de $f$ ssi il
% existe au moins un vecteur non nul vérifiant $f\left( u\right) =\lambda
% u.$

% \item si $\lambda $ est une vap de $f$ alors $E_{\lambda }=\left\{ u\in
% E\mid f\left( u\right) =\lambda u\right\} $ est un sev de $E,$ c'est le sous
% espace propre (sep) associé à la valeur propre $\lambda .$

% \item L'ensemble des valeurs propres de $f$ est appelé le spectre de $f.$

% \item La dimension d'un sep est forcément $\geq 1.$

% \item Si $f$ n'est pas injective ce qui équivaut à dire que $\ker
% \left( f\right) $ n'est pas réduit à $\left\{ 0_{E}\right\} $ alors $%
% 0$ est valeur propre et $E_{\lambda =0}=\ker \left( f\right) .$

% \item La juxtaposition des bases des différents sep est une famille
% libre. Si cette famille est une base, on dit que cette base est une base de
% vecteurs propres et la matrice de $f$ dans cette base est diagonale, on dit
% que l'on a diagonalisé $f.$
% \end{itemize}
% \end{itemize}
% \end{itemize}
























\section{Back to code}




\subsection{Inverse     d'une    matrice     par    la     méthode    de
  \textsc{Gauss-Jordan}}



\subsubsection{Opérations élémentaires}




Pour       effectuer       une       combinaison      linéaire       des
lignes\index{matrice!opérations  élémentaires},  on  va
créer une fonction:

 \lstinline+comb_ligne(ki,kj,M,i,j)+

 qui renverra la matrice construite à partir de M en remplaçant la
ligne $L_j$ par $k_j\times L_j+k_i\times L_i$.



\begin{pythoncode}
    def comb_lignes(self,ki,kj,i,j):
        """Li <- ki*Li + kj * Lj"""
        f = self.F
        g = lambda r,c : ki*f(i,c) + kj*f(j,c) if r == i else f(r,c)
        return Mat(self.D,g)
\end{pythoncode}



\begin{recherche}
  
On crée également une fonction \lstinline+mult_ligne(k,M,j):+
 qui renverra la matrice construite à partir de M en remplaçant la
ligne $L_j$ par $k\times L_j$.

\end{recherche}



\subsubsection{Calcul de l'inverse étape par étape}


On  commence  par créer une  fonction  qui  renvoie  une  matrice  où  se
juxtaposent la matrice initiale
et la matrice identité:

Créons une matrice:


\begin{pythoncode}
>>> M = list2mat([[1,0,1],[0,1,1],[1,1,0]])
\end{pythoncode}


$$
M=
\begin{pmatrix}
1 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 0
\end{pmatrix}
$$




Complétons-la par la matrice identité de même taille:

\begin{pythoncode}
>>> T = M.cat_carre_droite()
>>> T
 1  0  1  1  0  0
 0  1  1  0  1  0
 1  1  0  0  0  1
\end{pythoncode}


\begin{recherche}
  Complétez...

\begin{pythoncode}
    def cat_carre_droite(self):
        """
        Colle l'identité à droite pour la méthode de GJ

        """
        ???
\end{pythoncode}

\end{recherche}


On effectue $L_3\leftarrow L_3-L_1$:


\begin{pythoncode}
>>> T = T.comb_lignes(1,-1,2,0)
>>> T
 1  0  1  1  0  0
 0  1  1  0  1  0
 0  1 -1 -1  0  1
\end{pythoncode}


puis $L_3\leftarrow L_3-L_2$:



\begin{pythoncode}
>>> T = T.comb_lignes(1,-1,2,1)
>>> T
 1  0  1  1  0  0
 0  1  1  0  1  0
 0  0 -2 -1 -1  1
\end{pythoncode}




puis $L_3\leftarrow \frac{1}{2}L_3$:

\begin{pythoncode}
>>> T = T.mult_ligne(-0.5,2)
>>> T
 1  0  1  1   0   0
 0  1  1  0   1   0
 0  0  1  0.5 0.5 -0.5
\end{pythoncode}




On effectue $L_1\leftarrow L_1-L_3$:


\begin{pythoncode}
>>> T = T = T.comb_lignes(1,-1,1,2)
>>> T
 1  0  1  1   0   0
 0  1  0 -0.5 0.5 0.5
 0  0  1  0.5 0.5 -0.5
\end{pythoncode}




et enfin $L_2\leftarrow L_2-L_3$:

\begin{pythoncode}
>>> T = T.comb_lignes(1,-1,0,2)
>>> T
   1    0    0  0.5 -0.5  0.5
   0    1    0 -0.5  0.5  0.5
  -0   -0    1  0.5  0.5 -0.5
\end{pythoncode}




Il ne  reste plus  qu'à extraire  la moitié droite  du tableau  qui sera
l'inverse cherchée à l'aide d'une petite fonction:


\begin{recherche}
  Complétez...


\begin{pythoncode}
  def extrait_carre_droite(self):
        """
        Extrait le carré de droite d'un tableau de GJ

        """
        ???
\end{pythoncode}

\end{recherche}



alors:


\begin{pythoncode}
>>> iM = T.extrait_carre_droite()
>>> iM
 0.5 -0.5  0.5
-0.5  0.5  0.5
 0.5  0.5 -0.5
\end{pythoncode}



On vérifie que c'est bien la matrice inverse de $M$:



\begin{pythoncode}
>>> iM * M
   1    0    0
   0    1    0
   0    0    1
\end{pythoncode}


\subsubsection{Réduction sous-diagonale d'une matrice}

On  pourrait  calculer  l'inverse  d'une  matrice  en  généralisant  la  méthode
précédente mais cela s'avèrerait beaucoup trop gourmand en temps. 

Nous allons  dans un  premier temps  trigonaliser la  matrice en  effectuant des
opérations élémentaires.

Pour éviter de  faire trop de transformations, nous allons  petit à petit réduire
la taille de la matrice à trigonaliser  en ne considérant que le carré inférieur
droit situé sous le pivot courant et mémoriser chaque ligne obtenue dans
une matrice.



Cela  permet  également  de   généraliser  l'emploi  de  la  méthode  de
\textsc{Gauss} à des matrices non carrées pour la résolution de systèmes
par  exemple. Il  faut donc  faire  attention maintenant  à utiliser  le
minimum entre le nombre de lignes et le nombre de colonnes de la matrice.

On place des \og mouchards\fg{} pour comprendre l'évolution du code.

\begin{pythoncode}
    def triangle(self):
        """ renvoie la triangulation d'une matrice de haut en bas """
        [r,c] = self.D
        m     = min(r,c)
        S     = self
        T     = zeros(r,c)
        while m > 0:
            NoLigne = 0
            while S[NoLigne, 0] == 0 and (NoLigne < m - 1):
                    NoLigne += 1
            if S[NoLigne, 0] != 0:
                pivot = S[NoLigne,0]
                for k in range(1,m):
                    if S[k,0] != 0:
                        S = S.comb_lignes(pivot, -S[k,0],k,0)
                        print("pivot = "+str(pivot))
                        print("S dans for :")
                        print(S)
            T = T.remplace_ligned(r - m,S.F)
            print("Évolution de T :")
            print(T)
            S = S.dswap(NoLigne)
            m -= 1
        return T
\end{pythoncode}

Par exemple:

\begin{pythoncode}
In [1]: M
Out[1]: 
 1  2  3
 4  5  6
 7  8  8

In [2]: M.triangle()
pivot = 1
S dans for :
 1  2  3
 0 -3 -6
 7  8  8
pivot = 1
S dans for :
 1  2  3
 0 -3 -6
 0 -6 -13
Évolution de T :
 1  2  3
 0  0  0
 0  0  0
pivot = -3
S dans for :
-3 -6
 0  3
Évolution de T :
 1  2  3
 0 -3 -6
 0  0  0
Évolution de T :
 1  2  3
 0 -3 -6
 0  0  3
\end{pythoncode}


Nous avons besoin de deux fonctions intermédiaires, une remplissant le tableau T
et l'autre réduisant S.



\begin{pythoncode}
      def decoupe(self,i):
        """
        Fonction interne à triangle qui retire la 1ère ligne et la 1ère colonne

        """
        [lig, col], f = self.D, self.F
        return Mat([lig-1,col-1],lambda r,c : f(r+1,c+1))

    def remplace_ligned(self,i,g):
        """
        Fonction interne à triangle qui remplace dans la ligne i
        les coefficients à partir de la colonne i par ceux du tableau S
        """
        [lig, col], f = self.D, self.F
        h = lambda r,c: g(r-i,c-i) if r == i and c >= i else  f(r,c)
        return Mat([lig,col],h)
\end{pythoncode}



\begin{recherche}
   Déterminez une fonction qui calcule rapidement le rang d'une matrice.

\end{recherche}

\subsubsection{Calcul du déterminant}


On triangularise la matrice et le déterminant est égal au produit des
éléments diagonaux  à un détail  près: il ne  faut pas oublier  de tenir
compte de la parité du nombre d'échanges de lignes ainsi
que des multiplications des lignes modifiées par combinaisons.

\begin{recherche}
  Créez une fonction qui calcule le déterminant:

\begin{pythoncode}
       def det(self):
        """ renvoie le déterminant de self par Gauss-Jordan """
       ????
\end{pythoncode}


\end{recherche}

C'est assez  efficace pour du Python  basique: 555 ms pour  un déterminant d'une
matrice de taille 200.

\begin{pythoncode}
In [1]: M = unite(200)
In [2]: %timeit M.det()
1 loops, best of 3: 555 ms per loop
\end{pythoncode}


\subsubsection{Calcul de l'inverse d'une matrice}


La  trigonalisation est  assez rapide  du fait  de la  réduction progressive  de
S. L'idée  est alors de  trigonaliser de bas  en haut puis  de haut en  bas pour
arriver à  une matrice diagonale ce  qui sera plus efficace  qu'un traitement de
tout le tableau en continu. 

On peut utiliser la fonction \lstinline{det} qui  est rapide et permet de ne pas
prendre trop de précautions ensuite sachant que la matrice est inversible.

\begin{pythoncode}
def inverse(self):
    return self.cat_carre_droite().triangle().diago_triangle().extrait_carre_droite()
\end{pythoncode}


Le  tout  est de  construire  cette  méthode \lstinline{diago_triangle}  qui  va
trigonaliser le triangle en le parcourant de bas en haut.


On  transforme  légèrement les  fonctions  intermédiaires  précedentes pour  les
adapter au nouveau parcours:


\begin{pythoncode}
    def decoupe_bas(self):
        """
        Fonction interne à diago_triangle qui retire la dernière ligne et la
        colonne de même numéro de S

        """
        [lig, col], f = self.D, self.F
        #g = lambda r,c: f(lig-1,c) if r == lig else f(i,c) if r == lig-1 else f(r,c)
        g = lambda r,c: f(r,c) if c < lig - 1 else f(r,c+1)
        return Mat([lig-1,col-1],lambda r,c : g(r,c))

    def remplace_ligneg(self,i,g):
        """
        Fonction interne à diago_triangle qui remplace dans la ligne i
        les coefficients à partir de la colonne i par ceux du tableau S
        """
        [lig, col], f = self.D, self.F
        h = lambda r,c: g(r,c - (lig - 1) + i) if r == i and c >= i else  f(r,c)
        return Mat([lig,col],h)
\end{pythoncode}




\begin{recherche}
  Construisez \Colorbox{blue!10}{\lstinline{diago_triangle}}

\begin{pythoncode}
   def diago_triangle(self):
      ????
\end{pythoncode}


\end{recherche}


\begin{recherche}
    On considère la matrice $$A=
  \begin{pmatrix}
    10^{-20}& 0      &  1 \\
    1      & 10^{20} &  1 \\
    0      & 1      & -1 \\
  \end{pmatrix}
$$ Quel est son rang? Quel est son déterminant? Utilisez les fonctions précédentes puis du papier et un crayon...

\end{recherche}


\section{Manipulation d'images}

Dans cette section, des mathématiques concrètes vont nous permettre de
réduire,   agrandir,   assombrir,  éclaircir,   compresser,   bruiter,
quantifier,... une photo. Pour cela,  il existe des méthodes provenant
de  la théorie  du signal  et des  mathématiques continues.  Nous nous
pencherons plutôt sur  des méthodes plus légères  basées sur l'algèbre
linéaire  et l'analyse  matricielle.   Une image  sera  pour nous  une
matrice  carrée de  taille $2^9$  à coefficients  dans $\llbracket  0,
2^9-1\rrbracket$.  Cela manque de charme?  C'est sans compter sur Lena
qui depuis quarante ans rend les maths sexy (la population hantant les
laboratoires  mathématiques   et  surtout  informatiques   est  plutôt
masculine ...).

Nous   étudierons  pour   cela   la  \og   Décomposition  en   Valeurs
Singulières\fg{} qui apparaît de nos jours comme un couteau suisse des
problèmes linéaires:  en traitement  de l'image et  de tout  signal en
général, en  reconnaissance des formes, en  robotique, en statistique,
en  étude  du  langage  naturel,  en  géologie,  en  météorologie,  en
dynamique des structures, etc.

Dans  quel domaine  travaille-t-on alors:  algèbre linéaire,  analyse,
probabilités, topologie,...?  Un  peu de tout cela  et d'autres choses
encore: cela s'appelle...la mathématique.


\subsection{Lena}


Nous  allons travailler  avec  des  images qui  sont  des matrices  de
niveaux de gris.  Notre belle amie Léna sera représentée par une matrice
carrée de  taille $2^9$ ce qui  permet de reproduire Léna  à l'aide de
$2^{18}=262\,144$  pixels. Léna  prend alors  beaucoup de  place. Nous
allons tenter de  compresser la pauvre Léna sans pour  cela qu'elle ne
perde sa qualité  graphique. Une des méthodes les  plus abordables est
d'utiliser la décomposition d'une matrice en valeurs singulières.

C'est   un    sujet   extrêmement   riche   qui    a   de   nombreuses
applications.  L'algorithme que  nous  utiliserons (mais  que nous  ne
détaillerons pas) a été mis au point par deux très éminents chercheurs en 1965
(Gene   \textsc{Golub},   états-unien   et   William   \textsc{Kahan},
canadien, père de la norme  IEEE-754). Il s'agit donc de mathématiques
assez récentes, au moins en comparaison avec votre programme...


La petite histoire  dit que des chercheurs  américains de l'University
of Southern California étaient pressés de trouver une image de taille
$2^{18}$ pixels pour leur conférence.  Passe alors un de leurs
collègues avec, en bon informaticien, le dernier Playboy sous le bras.
Ils décidèrent alors 
d'utiliser le poster central de la Playmate comme support...

 La photo originale est ici:
 \href{http://www.lenna.org/full/len\_full.html}{http://www.lenna.org/full/len\_full.html}
 mais nous n'utiliserons  que la partie scannée par  les chercheurs, de
 taille $5.12 \mathrm{in}\times 5.12 \mathrm{in}$...

\subsection{Environnement de travail}

Nous  travaillerons  dans  Pylab  avec   l'option  \texttt{pylab}  qui  charge  les
bibliothèques nécessaires à la manipulation  d'images (en fait, pylab charge les
bibliothèques  pour  se retrouver  dans  un  environnement  proche de  celui  de
logiciels comme MatLab ou Scilab).

\begin{bashcode}
$ ipython --pylab
\end{bashcode}

%$

Les images sont alors sous forme d'\texttt{array} de la bibliothèque \textt{numpy}.

Nous allons créer  quelques outils pour continuer à travailler  malgré tout avec
notre classe \lstinline{Mat}.

\begin{pythoncode}
def array2mat(tab):
    """ convertit un array de numpy en objet de type Mat"""
    dim = list(tab.shape)
    return Mat(dim,  lambda i,j : tab[i,j])

def mat2array(mat):
    """ convertir un objet de type Mat en array de numpy """
    return np.fromfunction(mat.F,tuple(mat.D),dtype = int)

def montre(mat):
    """ permet de visualiser les images dans un terminal """
    return imshow(mat2array(mat), cmap = cm.gray)
\end{pythoncode}


Python contient un tableau carré de taille 512 contenant les niveaux de gris
représentant Lena. Il suffit de cherger les bonnes bibliothèques:

\begin{pythoncode}
from scipy import misc

# lena sous forme d'un objet de type Mat
matlena = array2mat(misc.lena())
\end{pythoncode}

Lena est bien un carré de $512×512 $ pixels:


\begin{pythoncode}
In [9]: matlena.D
Out[9]: [512, 512]
\end{pythoncode}


On peut voir Lena:


\begin{pythoncode}
In [3]: montre(matlena)
Out[3]: <matplotlib.image.AxesImage at 0x7f06c6d0c7b8>
\end{pythoncode}

et on obtient:

 \begin{center}
  \includegraphics[height=4cm]{lena_normale}
\end{center}

On peut préférer travailler sur une photo de format jpg (qui sera à l’envers) ou
png (qui  sera à l’endroit).  Python la transforme  en matrice avec  la fonction
imread.  La matrice  obtenue est  en  RVB :  chaque coefficient  est un  vecteur
(R,V,B). On la convertit  en niveau de gris par exemple  en calculant la moyenne
des trois couleurs.

On récupère d'abord une image:

\begin{pythoncode}
In [4]: from urllib.request import urlretrieve

In [5]: urlretrieve('addresse de la photo en ligne','photo.png')
Out[5]: ('photo.png', <http.client.HTTPMessage at 0x7f3aeeb5fa20>)
\end{pythoncode}

et on la transforme en matrice:

\begin{pythoncode}
lena_face_couleur = imread('lena_face.jpeg')

def rvb_to_gray(m):
    r = len(m)
    c = len(m[0])
    return(np.array([[m[i,j][0] for j in range(c)] for i in range(r)]))

lena_face_array = rvb_to_gray(lena_face_couleur)

lena_face = array2mat(lena_face_array)
\end{pythoncode}

En exclusivité mondiale, voici Lena de face:

\begin{pythoncode}
In [3]: montre(lena_face)
Out[3]: <matplotlib.image.AxesImage at 0x7f6d8c68cc88>
\end{pythoncode}

et on obtient:

 \begin{center}
  \includegraphics[height=4cm]{lena_face}
\end{center}




\subsection{Manipulations basiques}



Comment obtenir  les deux images de  gauche sachant que l'image  originale est à
droite: 

\begin{multicols}{2}
  \begin{center}
  \includegraphics[height=4cm]{lena_face_miroir}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_face_retourne}
\end{center}
\end{multicols}



Sachant que l'échelle de gris varie entre 0 et 255,
comment obtenir les images suivantes:

\begin{multicols}{2}
   \begin{center}
  \includegraphics[height=4cm]{lena_face_foncee}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_face_claire}
\end{center}

\end{multicols}




On peut modifier le contraste en \og mappant \fg{} par une fonction
croissant  plus  rapidement ou  plus  lentement  que  la fonction  identité  sur
[0 ;255] vers [0 ;255].  


Comment obtenir l'image en négatif de Lena?

\begin{center}
  \includegraphics[height=4cm]{lena_face_neg}
\end{center}



\subsection{Résolution}

Une matrice de taille $2^9$ contient $2^{18}$ entiers codés entre 0 et
$2^8-1$ ce  qui prend pas mal  de place en mémoire.  Peut-on être plus
économique sans pour cela diminuer la qualité esthétique de la photo?


La première idée est de prendre  de plus gros pixels, c'est-à-dire une
matrice plus petite: on extrait par exemple régulièrement un pixel sur
$k$ (en choisissant $k$ parmi une puissance de 2 inférieure à $2^9$).

Comment obtenir par exemple ces images?

\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{lena_face_64}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_face_128}
\end{center}
\vspace{-0.5cm}
\begin{center}
  \includegraphics[height=4cm]{lena_face_256}
\end{center}
%\end{figure}
\end{multicols}




\subsection{Quantification}

On peut également  réduire le nombre de niveaux de  gris en regroupant
par exemple tous les niveaux entre 0 et 63 en un seul niveau 0, puis 64
à 127 en 64, 128 à 191 en 128, 192 à 256 en 192.

Par exemple, avec 4, 8 puis 16 niveaux:





\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{lena_face_q4}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_face_q8}
\end{center}
\vspace{-0.5cm}
\begin{center}
  \includegraphics[height=4cm]{lena_face_q16}
\end{center}
%\end{figure}
\end{multicols}


Pour cela, on divise chaque coefficient de la matrice par une puissance de 2.

Mais une division d'un nombre par une puissance de 2 revient à faire un décalage de la
chaîne de bits représentant ce nombre vers la droite
 Ce décalage vers la droite est effectué en Python par l'opérateur
\lstinline{>>}\index[xcom]{decalage!gauche@\lstinline{>>}}.  L'image  précedente
peut donc être obtenue par ???


\subsection{Enlever le bruit}




La transmission  d'informations a toujours posé  des problèmes: voleurs
de grands  chemins, poteaux télégraphiques sciés,  attaques d'indiens,
etc.

Claude    Elwood    \textsc{Shannon}    (1916    -    2001)    est    un
mathématicien-inventeur-jongleur américain qui,  suite à son article \og
\textit{A mathematical theory of communications}\fg{} paru en 1948, est
considéré comme le fondateur de la
\textit{théorie  de  l'information}  qui  est  bien sûr  une  des  bases
de... l'\textit{informatique}.


L'idée est d'étudier et de quantifier l'\og information\fg{} émise et
reçue:  quelle est la  compression maximale  de données  digitales? Quel
débit choisir pour transmettre un message dans un canal \og bruité\fg{}?
Quel est le niveau de sûreté d'un chiffrement?...

La  théorie de  l'information  de \textsc{Shannon}  est  fondée sur  des
modèles probabilistes:  leur étude  est donc un  préalable à  l'étude de
problèmes   de  réseaux,   d'intelligence   artificielle,  de   systèmes
complexes. 

Par   exemple,   dans   le   schéma  de   communication   présenté   par
\textsc{Shannon}, la  source et le destinataire  d'une information étant
séparés, des perturbations peuvent créer une différence entre le message
émis et le message reçu.   Ces perturbations (bruit de fond thermique ou
accoustique, erreurs d'écriture ou de lecture, etc.) sont de nature
\textit{aléatoire}:  il n'est  pas possible  de prévoir  leur  effet. De
plus, le message  source est par nature \textit{imprévisible} du  point de vue du
destinataire (sinon, à quoi bon le transmettre). 

\textsc{Shannon}  a  également  emprunté   à  la  physique  la  notion
d'entropie   pour   mesurer   le  désordre   de   cette   transmission
d'information, cette même notion d'entropie  qui a inspiré notre héros
national, Cédric \textsc{Villani}... 


Mais revenons  à Lena.  Nous allons  simuler une Lena  bruitée. Pour  cela, nous
allons ajouter  ajouter des pixels  aléatoirement selon  une loi de  Bernoulli de
paramètre $p$.


\begin{pythoncode}
from random import randint

def ber(p):
    return 1 if random() < p else 0

def rand_image(dim,p):
    return Mat(dim, lambda i,j : randint(0,255)*ber(p))
    
def bruit(mat,p):
     return (mat + rand_image(mat.D,p)).map(lambda x : x % 256)
\end{pythoncode}


Par exemple, voici Lena bruitée à 0.1:


\begin{center}
  \includegraphics[height=5cm]{lena_face_bruit01}
\end{center}

Il existe de nombreuses méthodes, certaines très élaborées, permettant
de minimiser ce bruit. Une des plus simples est de remplacer chaque
pixel par la moyenne de lui-même et de ses 8 autres voisins directs,
voire aussi ses 24 voisins directs et indirect, voire plus, ou de la
médiane de ces séries de « cercles » concentriques de pixels.



Voici les  résultats avec  respectivement la  moyenne sur des  9 pixels  puis 25
pixels et à doite la médiane de carrés de 9 pixels. La médiane est plus efficace
que la moyenne!

\begin{multicols}{2}
%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{lena_face_mean}
\end{center}
% \begin{center}
%   \includegraphics[height=5cm]{lena_mean25}
% \end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_face_median}
\end{center}
%\end{figure}
\end{multicols}



Do it!!



\subsection{Compression par SVD}

On en a déjà parlé.


Le problème est d’obtenir cette décomposition. Python
heureusement s’en charge grâce à la fonction \lstinline+linalg.svd(mat)+ qui renvoie la décomposition en
valeurs singulières sous la forme de trois \og array\fg{} de \lstinline{numpy} $U$, $S$ et $\transp V$.

Par  souci  d'efficacité,  nous  travaillerons   ici  uniquement  avec  les  \og
array\fg{} de \lstinline{numpy}.


Voici les trois niveaux de compression 10, 50 et 100:


\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{lena_face_svd10}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_face_svd50}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_face_svd100}
\end{center}
%\end{figure}
\end{multicols}


obtenus par:

\begin{pythoncode}
In [144]: imshow(c_svd(lena_face_array,100),cmap = cm.gray)
\end{pythoncode}


On peut observer la décroissance extrêmement rapide des valeurs singulières:

\begin{pythoncode}
In [1]: U,s,tV = linalg.svd(misc.lena())

In [2]: x = np.arange(len(s))

In [3]: plot(x[:10],s[:10])

In [4]: plot(x[10:50],s[10:50])

In [5]: plot(x[50:],s[50:])
\end{pythoncode}


\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{svd_0_10}
\end{center}
\begin{center}
  \includegraphics[height=5cm]{svd_10_50}
\end{center}
\begin{center}
  \includegraphics[height=5cm]{svd_50_512}
\end{center}
%\end{figure}
\end{multicols}


On peut également faire une petite animation des images compressées:

\begin{pythoncode}
def anim(im,n):
    for k in range(n):
        plt.imsave("lena_face_svd" + str(1000 + k), c_svd(lena_face_array,k), cmap = cm.gray)
\end{pythoncode}

Puis ensuite dans un terminal:

\begin{bashcode}
$ apngasm anim_lena_face.png lena_face_svd*.png 1 5
\end{bashcode}

Il   faut  installer   au  préalable   le  petit   logiciel  \lstinline{apngasm}
(disponible        dans       les        dépôts        Linux       ou        sur
\href{http://sourceforge.net/projects/apngasm/}{http://sourceforge.net/projects/apngasm/}).

On obtient l'image animée suivante:

\href{http://download.tuxfamily.org/tehessinmath/les\_images/anim\_lena\_face.png}{http://download.tuxfamily.org/tehessinmath/les\_images/anim\_lena\_face.png}

\begin{recherche}[Détection des bords]\label{ch03::exo::bords}
Pour  sélectionner  des objets  sur  une  image,  on peut  essayer  de
détecter leurs bords, i.e. des  zones de brusque changement de niveaux
de gris.

On  remplace alors  un pixel  par une  mesure des  écarts des  voisins
immédiats donnée par exemple par:

$$\sqrt{ \left(m_{i,j+1}-m_{i,j-1}\right)^2+ \left(m_{i+1,j}-m_{i-1,j}\right)^2
}$$


Écrivez une fonction qui trace le contour défini ci-dessus.


  
\end{recherche}




%%% Local Variables: 
%%% TeX-master: "PolyIPT2015_16"
%%% End: 
