%Last modified: <matrices_info2.tex modifié par  Guillaume Connan le vendredi 2 décembre 2011 à 22h 52min 10s>
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\chapterimage{matrix}
\chaptertext{Où l'on découvre la richesse d'un algorithme pourtant si simple...}
%\setcounter{chapter}{1}


%\modeexercice % entre en mode exercice
\chapter{Matrices, déterminants et Python}


\section{Calcul matriciel avec Python}


\subsection{Les boucles for}

Lorsque l'on souhaite répéter un bloc d'instructions un nombre déterminé de fois,
on peut utiliser un \emph{compteur actif}, \cad une variable qui compte le
nombre de répétitions et conditionne la sortie de la boucle \verb?while?. C'est
le cas de l'exemple suivant où l'on définit une fonction qui prend en argument
un entier \verb?n? et affiche \verb?n? fois le même message.

\begin{multicols}{2}
\begin{pythoncode}[Python3]
def f(n):
    i = 0 # on initialise le compteur i
    while i < n:
        print('Je me répète {} fois.'
              ' (i={})'.format(n, i))
        i += 1 # on incrémente i
f(5)
\end{pythoncode}
\begin{sortie}
Je me répète 5 fois. (i=0)
Je me répète 5 fois. (i=1)
Je me répète 5 fois. (i=2)
Je me répète 5 fois. (i=3)
Je me répète 5 fois. (i=4)
\end{sortie}
\end{multicols}

Pour effectuer une telle répétition, on dispose d'une structure de répétition nous
économisant d'une part l'initialisation du compteur (\verb?i = 0?), et
d'autre part son incrémentation (\verb?i += 1?) : c'est la structure
introduite par le mot-clé \Com{for} :

\begin{multicols}{2}
\begin{pythoncode}[Python3]
def f(n):
    for i in range(n):
        print('Je me répète {} fois.'
              ' (i={})'.format(n, i))
f(5)
\end{pythoncode}
\begin{sortie}
Je me répète 5 fois. (i=0)
Je me répète 5 fois. (i=1)
Je me répète 5 fois. (i=2)
Je me répète 5 fois. (i=3)
Je me répète 5 fois. (i=4)
\end{sortie}
\end{multicols}

\index{itérateur}
Nous voyons apparaître ici pour la première fois la fonction \Com{range}.
Cette fonction crée un \emph{itérateur}, \cad en quelque sorte un
distributeur d'entiers consécutifs. Au lieu de créer et garder en mémoire une
liste d'entiers, cette fonction génère les entiers au fur et à mesure
des besoins, toujours dans un souci d'optimisation de la mémoire.


\begin{remarque}
Plus précisément, un itérateur est un objet possédant une méthode
\verb?__iter()__? qui renvoie les éléments d'une collection un par un et qui
provoque une exception du type \verb?StopIteration? lorsqu'il n'y a plus
d'éléments.
\end{remarque}

Avec un argument, \verb?range(n)? renvoie un itérateur parcourant l'intervalle
$\llbracket 0,n-1\rrbracket$ ; avec deux arguments, \verb?range(n, p)? parcourt l'intervalle
$\llbracket n, p-1\rrbracket$ ; enfin employée avec trois arguments, \verb?range(n, p, k)? parcourt l'intervalle
$\llbracket n, p-1\rrbracket$ avec un pas égal à $k$.

Signalons que la fonction \verb?range? peut servir à créer des listes d'entiers,
moyennant une conversion de type opérée par la fonction \verb?list?. Examinons
quelques exemples.

\begin{multicols}{2}
\begin{pythoncode}[Python3]
>>> list(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(range(1, 11))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> list(range(0, 30, 5))
[0, 5, 10, 15, 20, 25]
>>> list(range(0, 10, 3))
[0, 3, 6, 9]
>>> list(range(0, -6, -1))
[0, -1, -2, -3, -4, -5]
\end{pythoncode}
\begin{pythoncode}[Python3]
>>> list(range(0)), list(range(1, 0))
[] []
\end{pythoncode}
\begin{pythoncode}[Python3]
>>> list(range(9, 0, -1))
[9, 8, 7, 6, 5, 4, 3, 2, 1]
\end{pythoncode}
\end{multicols}

Autre point important, on peut aussi utiliser comme itérateur dans une boucle
\verb?for? une liste ou une chaîne de caractère.

\begin{remarque}
Plus généralement, le mot-clé \verb?for? peut être utilisé avec
n'importe quel objet \emph{itérable} ; un objet itérable étant un objet
possédant soit une méthode \verb?__iter__()? soit une méthode
\verb?__getitem__()?.
\end{remarque}

\begin{pythoncode}[Python3]
for i in [10, 'a', 1.414]:
    print(i, end=' -> ')
for i in 'mot':
    print(i, end=' -> ')
\end{pythoncode}
\begin{sortie}
10 -> a -> 1.414 -> m -> o -> t ->
\end{sortie}

Pour créer des listes, \py fournit une facilité syntaxique particulièrement
agréable, à savoir les listes (définies) par compréhension
(en anglais, \emph{list-comprehensions}).
Elles permettent de générer des listes d'une manière très concise, sans avoir à
utiliser de boucles.


La syntaxe pour définir une liste par compréhension est proche de celle utilisée
en mathématiques pour définir un ensemble par compréhension :

\begin{center}
\begin{tikzpicture}[every text node part/.style={font=\Large}]
    \matrix [nodes={anchor=base}, column sep=2mm]
    {
    \node {$\{$}; & \node (a) {$f($};   &[-4mm]  \node (b) {$x$}; &[-4mm]
    \node {$)$};  & \node (c) {$\mid$}; & \node (d) {$x$}; &
    \node (e) {$\in $};  & \node (f) {$E$};    & \node {$\}$};
    \\[7mm]
    \node {\verb?[?};  & \node (aa) {\verb?f(?};    & \node (bb) {\verb?x?}; &
    \node {\verb?)?};  & \node (cc) {\verb?for?};   & \node (dd) {\verb?x?}; &
    \node (ee) {\verb?in?}; & \node (ff) {\verb?liste?}; & \node {\verb?]?};
    \\
    };
    \draw [-latex, grisTresFonce, thin] (a) -- (aa);
    \draw [-latex, grisTresFonce, thin] (b) -- (bb);
    \draw [-latex, grisTresFonce, thin] (c) -- (cc);
    \draw [-latex, grisTresFonce, thin] (d) -- (dd);
    \draw [-latex, grisTresFonce, thin] (e) -- (ee);
    \draw [-latex, grisTresFonce, thin] (f) -- (ff);
\end{tikzpicture}
\end{center}


Voici
quelques exemples :

\begin{pythoncode}[Python3]
>>> liste = [2, 4, 6, 8, 10]
>>> [3*x for x in liste]
[6, 12, 18, 24, 30]
>>> [[x, x**3] for x in liste]
[[2, 8], [4, 64], [6, 216], [8, 512], [10, 1000]]
>>> [3*x for x in liste if x > 5] # on filtre avec une condition
[18, 24, 30]
>>> [3*x for x in liste if x**2 < 50] # idem
[6, 12, 18]
>>> liste2 = list(range(3))
>>> [x*y for x in liste for y in liste2]
[0, 2, 4, 0, 4, 8, 0, 6, 12, 0, 8, 16, 0, 10, 20]
\end{pythoncode}

Voici par exemple, un moyen efficace d'obtenir la liste des années bissextiles dans un
intervalle donné :

\begin{pythoncode}[Python3]
>>> bissextile = [b for b in range(2000, 2100)
...               if (b % 4 ==0 and b % 100 != 0) or (b % 400 == 0)]
\end{pythoncode}

Pour concaténer les éléments d'une liste de listes, on peut imbriquer deux
boucles \verb?for? dans la définition d'une liste par compréhension :

\begin{pythoncode}[Python3]
>>> xll = [[1, 2, 3], [4, 5], [6, 7, 8]]
>>> [x for xl in xll for x in xl]
[1, 2, 3, 4, 5, 6, 7, 8]
\end{pythoncode}

Pour obtenir les diviseurs d'un entier $n$, on peut également utiliser une liste
par compréhension :

\begin{pythoncode}[Python3]
>>> n = 100; [d for d in range(1, n+1) if n % d == 0]  # les diviseurs de 100
[1, 2, 4, 5, 10, 20, 25, 50, 100]
\end{pythoncode}




\subsection{Fabriquons nos outils}


Dans cette section, nous créerons nos matrices comme
une liste de listes représentant les lignes.


Par exemple, 
$\begin{pmatrix}
 1&2\\3&4\\5&6
\end{pmatrix}$
sera cre\'ee avec:

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


Pour obtenir  le terme $M_{i,j}$  situé sur la  ligne $i$ et  la colonne
$j$, on entrera \lstinline+M[i][j]+.

\begin{NB}
Attention! \py commence à compter à partir de 0. Ainsi le premier élément d'une
liste est indexé par 0.
\end{NB}


\begin{pythoncode}[python3]
>>> M[0]
[1, 2]
>>> M[0][1]
2
\end{pythoncode}

La commande \lstinline+len+ (comme  \textit{length}) renvoie la longueur d'une
liste.  On obtient donc 
le nombre  de lignes de la  matrice avec \lstinline+len(M)+ et  son nombre de
colonnes avec \lstinline+len(M[0])+.  Comme nous utiliserons souvent ces
nombres,  on  va  créer  deux  fonctions pour  rendre  la  lecture  des
programmes plus évidente:


\begin{pythoncode}[python3]
def lignes(M):
    return range(len(M))

def cols(M):
    return range(len(M[0]))
\end{pythoncode}





\begin{exercice}[Transposée d'une matrice]
  
 Nous vous rappelons  que la  transposée d'une
matrice $(M_{ij})_{{1 \leqslant i \leqslant n }\atop {1 \leqslant j \leqslant m}}$
est  égale  à la  matrice  $(M_{ji})_{{1 \leqslant  i  \leqslant  n} \atop  {1
  \leqslant j \leqslant m}}$.

Définissez une fonction \lstinline+transpose(M)+ qui  
renvoie la transposée de la matrice M.

Attention aux indices et aux nombre de lignes et de colonnes!

\end{exercice}


\begin{exercice}[Somme de matrices]
  
On voudrait créer une procédure \lstinline+msom(A,B)+   
qui  prend comme  arguments deux  matrices et
renvoie leur  somme. Il faudra  vérifier que les matrices  à additionner
sont de bonnes tailles.

\end{exercice}


\begin{NB}
Pour la gestion des erreurs (de taille par exemple), on va créer
une \textit{classe d'exception}.  On la crée la  plus générale possible pour l'utiliser dans
d'autres domaines.


\begin{pythoncode}[python3]\label{except}
class ExceptionMatrice(Exception):
    def __init__(self,raison):
        self.raison = raison
    
    def __str__(self):
        return self.raison
\end{pythoncode}

On l'invoquera avec la commande \lstinline+raise+. Ici:

\begin{pythoncode}[python3]
if len(A[0])!=len(B): 
    raise ExceptionMatrice("Problème de taille")
\end{pythoncode}



\end{NB}




\begin{exercice}[Produit par un scalaire]
  
On voudrait obtenir la matrice $k\cdot  M$ à partir d'une matrice $M$ et
d'un scalaire $k$.
Créer une fonction \lstinline+mprod_scal(M,k)+ qui agira ainsi:

\begin{pythoncode}[python3]
>>> A=[[2,4],[6,8],[10,12]]
>>> mprod_scal(A,0.5)
[[1.0, 2.0], [3.0, 4.0], [5.0, 6.0]]
\end{pythoncode}

\end{exercice}

Je  ne vous  fais pas  l'injure de  vous rappeler  comment  effectuer le
produit de deux matrices...Bon, seulement la formule:

Soit  $A=(a_{ij})_{{1 \leqslant  i  \leqslant n}  \atop  {1 \leqslant  i
    \leqslant m}}$ et $B=(b_{ij})_{{1 \leqslant  i  \leqslant m}  \atop  {1 \leqslant  i
    \leqslant p}}$.
Alors $A\times B=C$ avec $C=(c_{ij})_{{1 \leqslant  i  \leqslant n}  \atop  {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}\]

\begin{exercice}[Produit de matrices]
Créer une fonction \lstinline+mprod(A,B)+ qui renvoie le produit de deux
matrices A et  B en utilisant trois boucles  \textit{pour} imbriquées et
sans oublier les tests de taille. Vous testerez par exemple avec $A=
\begin{pmatrix}
  1&2\\3&4\\5&6
\end{pmatrix}$ et $B=
\begin{pmatrix}
  1&1&1\\2&2&2
\end{pmatrix}$. Essayer $A\times B$ et $B\times A$. Essayer ensuite avec
deux matrices carrées.



\medskip

\textit{Variante}: créer une fonction \lstinline+som_liste(L)+ qui 
calcule la somme  des éléments d'une liste d'entiers  et l'utiliser pour
créer  une  fonction \lstinline+mprod2(A,B)+  sans  utiliser de  matrice
temporaire mais en  fabriquant la liste produit en  place avec une liste
par compréhension.

\medskip

\textit{Variante bis}: on peu aussi gagner un peu de temps en créant des
variables  pour  stocker \lstinline+A[i]+  et  \lstinline+C[i]+  dans la  première
version, du style \lstinline+Ai,Ci = A[i],C[i]+. L'affectation se faisant  par pointeurs, les listes A  et C vont évoluer
avec \lstinline+Ai+ et \lstinline+Ci+.

\medskip

\textit{Variante ter}: On gagnerait  encore du temps  en faisant de  même avec B.  Il suffirait
d'utiliser  la  transposée  de   B:  \lstinline+tB  =  transpose(B)+  et
\lstinline+tBj = tB[j]+.   


\end{exercice}


\begin{NB}
  On   peut   comparer   les   temps  d'exécution   avec   la   fonction
  \lstinline+clock+ du module \lstinline+time+:

\begin{pythoncode}[python3]
    from time import clock
    A=[[1 for k in range(200)] for k in range(200)]
    debut1 = clock()
    mprod(A,A)
    fin1 = clock()
    debut2 = clock()
    mprod2(A,A)
    fin2 = clock()
    debut3 = clock()
    mprod1bis(A,A)
    fin3 = clock()
    print (fin1 - debut1 , fin2 - debut2, fin3-debut3)
\end{pythoncode}
   


\end{NB}




\begin{exercice}[Matrice identité]
Créer une fonction  qui fabrique  la matrice  identité
d'ordre $n$ selon le modèle utilisé.

Par exemple, $I_3$ sera obtenue ainsi:

\begin{pythoncode}[python3]
>>> unite(3)
[[1, 0, 0], [0, 1, 0], [0, 0, 1]]
\end{pythoncode}
\end{exercice}



\begin{exercice}[Puissances d'une matrice]
Créer une fonction \lstinline+mpuis(A,n)+  qui calcule $A^n$. Donner une
version récursive puis une version itérative.


Par exemple, avec $J=
\begin{pmatrix}
  1&1\\1&1
\end{pmatrix}
$:

\begin{pythoncode}[python3]
>>> J=[[1,1],[1,1]]
>>> mpuis(J,5)
[[16, 16], [16, 16]]
\end{pythoncode}

Démontrer alors par récurrence que $J^n=2^{n-1}J$.

\end{exercice}




\begin{exercice}[Trace d'une matrice]
Créer une fonction \lstinline+trace(M)+ qui calcule la trace d'une matrice.

Par exemple, on peut calculer la trace de $J^5$:


\begin{pythoncode}[python3]
>>> trace(mpuis(J,5))
32
\end{pythoncode}

\end{exercice}



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




\begin{exercice}[Opérations élémentaires]
  
Pour       effectuer       une       combinaison      linéaire       des
lignes,  on  va
créer une fonction:
\begin{center}
  \lstinline+add_ligne_scal(k,M,i,j)+
\end{center}
 

 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$.


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$.

On   pensera   à   utiliser   la   copie   \og   en   profondeur   \fg{}
\lstinline+deepcopy+ du module \lstinline+copy+. 


\end{exercice}



\begin{exercice}[Calcul de l'inverse étape par étape]
On commence par créer une fonction \lstinline+GJ(M)+ 
qui  crée  une  matrice  où  se
juxtaposent la matrice initiale
et la matrice identité.

Par exemple, avec $
M=
\begin{pmatrix}
1 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 0
\end{pmatrix}
$ on obtient $T=
\begin{pmatrix}
1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 1
\end{pmatrix}
$
  

Pour  avoir une  meilleure  \og  vision\fg{} de  la  matrice, on  pourra
utiliser une fonction \lstinline+affiche+:


\begin{pythoncode}[python3]
def affiche(M):
    for i in lignes(M):
        print M[i]
\end{pythoncode}



\begin{pythoncode}[python3]
>>> M = [[1,0,1],[0,1,1],[1,1,0]]
>>> T = GJ(M)
>>> affiche(T)
[1, 0, 1, 1, 0, 0]
[0, 1, 1, 0, 1, 0] 
[1, 1, 0, 0, 0, 1]
\end{pythoncode}

Effectuer pas à pas les transformations. À la fin, on devrait obtenir:


$$T=
\begin{pmatrix}
  1 & 0 & 0 & 1/2 & -1/2 & 1/2 \\
0 & 1 & 0 & -1/2 & 1/2 & 1/2 \\
0 & 0 & 1 & 1/2 & 1/2 & -1/2
\end{pmatrix}
$$



Il ne  reste plus  qu'à extraire  la moitié droite  du tableau  qui sera
l'inverse cherchée à l'aide d'une petite fonction \lstinline+JG(T)+.

On rappelle  la syntaxe  de manipulation des  listes: \lstinline+L[1:4],L[1:], L[:]+, etc.


Alors:


\begin{pythoncode}[python3]
>>> IM = JG(T)
>>> affiche(IM)
[0.5, -0.5, 0.5]
[-0.5, 0.5, 0.5]
[0.5, 0.5, -0.5]
>>> affiche(mprod(IM,M))
[1.0, 0.0, 0.0]
[0.0, 1.0, 0.0]
[0.0, 0.0, 1.0]
\end{pythoncode}






\end{exercice}
















\subsubsection{Calcul direct de l'inverse par la méthode de \textsc{Gauss-Jordan}}





Si  la  matrice est  inversible,  alors,  en  effectuant des  opérations
élémentaires sur  les lignes, on peut  se ramener à  la matrice identité
dans la partie gauche du tableau et on obtient son inverse dans la partie droite.


Pour y arriver, l'idée est de balayer le tableau par colonne.

Étant donné  une colonne, on cherche un  élément non nul. S'il  n'y en a
pas,  la matrice  n'est pas  inversible et  le système  n'admet  pas une
unique solution; sinon,
on permute éventuellement  deux lignes pour placer l'élément  non nul de
la colonne  $k$ sur la ligne  $k$ et on  divise tous les éléments  de la
ligne par le nouveau $a_{kk}$ pour obtenir 1.

Il reste ensuite à remplacer chaque ligne (autre que $L_k$) dont l'élément de la colonne
$k$ est non nul par $L_i-a_{ik}\times L_k$.

\begin{exercice}
Créer une fonction \lstinline+inv_gauss(M)+ qui renvoie, si elle existe,
la matrice inverse de M.

On créera d'abord une  fonction \lstinline+swap(L,i,j)+ qui échange deux
lignes.

Analyser ensuite le programme suivant:

\begin{pythoncode}[python3]
def inv_gauss(T):
    if lignes(M) != cols(M):
    raise ExceptionMatrice("La matrice doit être carrée")
    S = GJ(T)
    for NoColonne in lignes(T):
        NoLigne = NoColonne
        while S[NoLigne][NoColonne] == 0:
            if NoLigne == len(T) - 1:
                raise ExceptionMatrice("Matrice non inversible")
            NoLigne += 1
        S = swap(S,NoLigne,NoColonne)
        S = mult_ligne(float(1)/float(S[NoColonne][NoColonne]),S,NoColonne)
        E = set([k for k in lignes(T)]) - set([NoColonne])
        for k in E:
            S = comb_ligne(-S[k][NoColonne],1,S,NoColonne,k)
    return JG(S)
\end{pythoncode}

\end{exercice}


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

\begin{exercice}
 
On s'inspire de la fonction précédente, mais au lieu de travailler sur toutes
les lignes, on ne transforme que les lignes en-dessous du pivot. 

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 obtiendra ainsi une matrice triangulaire.
L'intérêt est aussi que tous les calculs s'effectuent dans l'anneau de départ
car il n'y a plus de divisions.

\end{exercice}



\subsubsection{Base de l'image - Rang d'une matrice}


On écrit  les vecteurs engendrant  l'image de l'endomorphisme  en ligne:
bref, on
transpose la matrice.
En effet, ce sera plus simple d'étudier la matrice
par lignes car il s'agit des sous-listes de la liste représentant la matrice.
Suite à la réduction de \lstinline+tri_gauss+ on ne garde que les lignes
non nulles: la famille obtenue est une base de l'image.


\begin{exercice}
  Déterminer  une fonction  \lstinline+Im(M)+ qui  retourne une  base de
  l'image puis  une fonction \lstinline+rang(M)+ qui renvoie  le rang de
  la matrice M.
\end{exercice}
\vfill

\eject

\section{Déterminants}


\subsection{Propriétés des déterminants}

Dans la  suite, $A=(a_{ij})$, $B=(b_{ij})$ sont des  matrices carrées de
taille $n$, $\lambda$ est un scalaire. $L_i$ est une ligne quelconque de A.

\begin{propriete}
Soient $i$ et $j$ deux entiers compris entre 1 et $n$.

$$\det A= \displaystyle\sum_{k=1}^{n}a_{1k}\Delta_{1k}=\displaystyle\sum_{k=1}^{n}a_{ik}\Delta_{ik}=\displaystyle\sum_{k=1}^{n}a_{kj}\Delta_{kj}$$
\end{propriete}

On admettra cette propriété. \og Traduisez-la\fg{} par une phrase en bon
français.

Appliquez-la pour calculer de tête le déterminant de la matrice suivante:

$$M=
\begin{bmatrix}
  1&17&32&49\\
  0&5&0&3\\
  0&39&2&-49\\
  0&7&0&1
\end{bmatrix}
$$


\begin{propriete}
Le  déterminant  d'une matrice  triangulaire  est  égal  au produit  des
éléments de sa diagonale principale.
\end{propriete}


Sans utiliser cette propriété, calculez de tête le déterminant de la matrice suivante:

$$M=
\begin{bmatrix}
2&32&45&87&987\\
0&-1&568&-542&712\\
0&0&5&741&-12\\
0&0&0&1&-789\\
0&0&0&0&-10
\end{bmatrix}
$$

Prouvez cette propriété dans le cas général.


\begin{propriete}\label{prop::swap}
Si la matrice B résulte de  l'échange de deux lignes ou de deux colonnes
d'une matrice A alors $\det B=-\det A$
\end{propriete}

On admettra cette propriété.


Calculez de tête le déterminant de la matrice suivante:

$$M=
\begin{bmatrix}
45&32&2&987&87\\
568&-1&0&712&-542\\
5&0&0&-12&741\\
0&0&0&-789&1\\
0&0&0&-10&0
\end{bmatrix}
$$

\begin{propriete}
  $$\det \left(\transp{A}\right)=\det A$$
\end{propriete}

Démontrez cette propriété. 

\begin{propriete}
Le déterminant d'une matrice comportant  une ligne (ou une colonne) de 0
est nul.
\end{propriete}

Démontrez cette propriété.


\begin{propriete}
Soit B  la matrice  obtenue à partir  de A en  effectuant $L_i\leftarrow
\lambda L_i$, alors $\det B = \det A$.
\end{propriete}

Démontrez cette propriété.


\begin{propriete}
$$\det (\lambda A) = \lambda^n\det A$$
\end{propriete}

Démontrez cette propriété.

Si A  est une matrice carrée d'ordre  5 dont le déterminant  vaut 4, que
vaut $\det(-2A)$?

Démontrez    que   le    déterminant   d'une    matrice   antisymétrique
(i.e. $\transp{A}=-A$) d'ordre 37 est nul.

\begin{propriete}
Le  déterminant  d'une  matrice  comportant deux  lignes  (ou  colonnes)
identiques est nul.
\end{propriete}


Démontrez cette propriété en utilisant la propriété\vref{prop::swap}.


\begin{propriete}
Le déterminant d'une matrice qui comporte deux lignes (ou colonnes) dont
l'une est multiple de l'autre est nul.
\end{propriete}

Démontrez cette propriété.




\begin{propriete}
Soit B  la matrice  obtenue à partir  de A en  effectuant $L_i\leftarrow
\lambda L_i+\lambda L_j$, alors $\det B = \det A$.
\end{propriete}


Démontrez cette  propriété. Utilisez-la pour calculer  le déterminant de
la matrice suivante:

$$M=
\begin{bmatrix}
 1&3&2&-1\\
 -1&-2&2&6\\
 2&4&-3&2\\
 -2&-7&4&1
\end{bmatrix}
$$

Estimez le  nombre d'opérations nécessaires pour effectuer  le calcul du
déterminant  d'une matrice  de  taille $n$  en  utilisant uniquement  la
définition.

Faites de même lorsqu'on utilise l'algorithme de \textsc{Gauss}.

Il y a quelques jours, un ordinateur japonais de la firme Fujitsu a établi un nouveau record
de  vitesse  de  calcul  de  10  pétaflops,  soit  $10^{16}$  opérations
mathématiques à virgule flottante par seconde.
L ordinateur utilisé  compte quelque  $\numprint{88 000}$ processeurs  enchâssés dans
864 serveurs; chacun des processeurs dispose de 8 c\oe urs d exécution. 

Combien de temps  lui faudra-t-il environ pour effectuer  le calcul d'un
déterminant de taille 30 à l'aide de la définition? Avec l'algorithme de
\textsc{Gauss}?

\vfill\eject
Analysez le programme Python suivant:

\begin{lstlisting}[caption={}]
def mystere(T):
    if lignes(M) != cols(M):
        raise ExceptionMatrice("La matrice doit être carrée")
    S = T
    i = 1
    for NoColonne in lignes(T):
        NoLigne = NoColonne
        while (S[NoLigne][NoColonne]==0) and (NoLigne<len(T)-1) :
            NoLigne+=1
        swap(S,NoLigne,NoColonne)
        i *= -1
        for k in range(NoLigne+1,len(T)):
            S = comb_ligne(-S[k][NoColonne],S[NoColonne][NoColonne],S,NoColonne,k)
            i *= -S[NoColonne][NoColonne]
    d = 1
    for k in lignes(S):
           d *= S[k][k]
    return(d/i)
\end{lstlisting}




\begin{propriete}
$$\det(A\times B)=\det(A)\cdot\det(B)$$
\end{propriete}

On admettra cette définition.

Soit A  une matrice inversible.  Calculez $\det(A^{-1})$ en  fonction de
$\det(A)$.


\begin{definition}
Une matrice dont le déterminant est nul est dite \textbf{singulière}.
\end{definition}


Une matrice singulière peut-elle être inversible?


La matrice suivante est-elle inversible?

$$
M=
\begin{bmatrix}
x^2&xy&xz\\
x+2&y+2&z+2\\
3&3&3
\end{bmatrix}
$$

\subsection{Quelques exercices}


\begin{exercice}
Les déterminants  peuvent servir à calculer certaines  surfaces. On peut
montrer par  exemple que  l'aire du triangle  dont les sommets  sont les
points $A(x_1,y_1)$,  $B(x_2,y_2)$ et $C(x_3,y_3)$ est égal  à la valeur
absolue de $$
\frac{1}{2}\begin{vmatrix}
  x_1&y_1&1\\
  x_2&y_2&1\\
  x_3&y_3&1
\end{vmatrix}
$$

Quelle  est l'aire  du triangle  dont les  sommets ont  pour coordonnées
(2,3), (1,1) et (5,-1)? (3,4),  (2,1) et (4,7)? Qu'en concluez-vous dans
ce dernier cas?
\end{exercice}

\begin{exercice}
 Soit $A=
 \begin{bmatrix}
   1&2\\
   0&0
 \end{bmatrix}
$ et $B=
\begin{bmatrix}
  0&0\\
  3&4
\end{bmatrix}
$

Calculez $\det(A)$, $\det(B)$ et $\det(A+B)$. Conclusion?
\end{exercice}

%\vfill\eject

\begin{exercice}
  Résolvez les équations suivantes dans $\bbr$:
  \begin{multicols}{2}
    \begin{enumerate}
    \item $
      \begin{vmatrix}
        3&x\\
        x+2&1-x
      \end{vmatrix}=-3
$
\item $
  \begin{vmatrix}
    x-2&3\\
    x&x+1
  \end{vmatrix}=3
$
    \end{enumerate}
    
  \end{multicols}
\end{exercice}



\begin{exercice}
Pour  quelles   valeurs  de   $x$  les  matrices   suivantes  sont-elles
singulières?
\begin{multicols}{2}
  \begin{enumerate}
  \item $M_1=
    \begin{bmatrix}
      1&x-1\\
      x&3x
    \end{bmatrix}
$
\item $M_2=
  \begin{bmatrix}
    2x&x+1\\
    x-2&3x
  \end{bmatrix}
$
\item $M_3=
  \begin{bmatrix}
    1&x&x\\
    1&2&3\\
    x&x&1
  \end{bmatrix}
$
\item $M_4=
  \begin{bmatrix}
    1&x&x^2\\
    1&1&1\\
    1&3&9
  \end{bmatrix}
$
  \end{enumerate}
  
\end{multicols}
\end{exercice}



\begin{exercice}
  $A_{ij}=
  \begin{cases}
    2\text{ si } i \leqslant j\\
0 \text{ si } i>j
  \end{cases}
$. Calculer $\det(A)$. 
Faites de même si  $A_{ij}=
  \begin{cases}
    i\text{ si } i = j\\
0 \text{ si } i\neq j
  \end{cases}
$.
\end{exercice}

\begin{exercice}
  Soit $M=
  \begin{bmatrix}
    a&d&g\\b&e&h\\ c&f&i
  \end{bmatrix}
$ et $\det(M)=-4$. Calculez le déterminant des matrices suivantes:

\begin{multicols}{2}

$A=
\begin{bmatrix}
  a&b&c\\d&e&f\\g&h&i
\end{bmatrix}
$

$
B=\begin{bmatrix}
  g&a&d\\h&b&e\\i&c&f
\end{bmatrix}
$

$
C=\begin{bmatrix}
  3a&d&-g\\3b&e&-h\\3c&f&-i
\end{bmatrix}
$

$
D=\begin{bmatrix}
a&d&g\\4b+3a&4e+3d&4h+3g\\c&f&i
\end{bmatrix}
$
  
\end{multicols}
\end{exercice}



\begin{exercice}
  Soient  A,   B  et  P  trois   matrices  de  même   ordre  telles  que
  $B=P^{-1}AP$. Calculez le déterminant de B en fonction de celui de A.
\end{exercice}

\begin{exercice}
  Une  matrice est  dite \textbf{orthogonale}  si, et  seulement  si, sa
  transposée est égale à son inverse.

  \begin{enumerate}
  \item La matrice $I_n$ est-elle orthogonale?
\item La matrice $A=
  \begin{bmatrix}
    \sin(t)&\cos(t)\\-\cos(t)&\sin(t)
  \end{bmatrix}
$ est-elle orthogonale pour tout $t\in\bbr$?
\item  Montrez que  le déterminant  d'une matrice  orthogonale est  1 ou
  $-1$.
\item Déterminez la troisième ligne de la matrice orthogonale:
  $\begin{bmatrix}
    1/3&2/3&2/3\\2/3&-2/3&1/3\\ & &
  \end{bmatrix}$
  \end{enumerate}
\end{exercice}



\section{Chiffrement de \textsc{Hill}}


On   travaille  avec   l'alphabet   $\bigl\{@,A,B,C,D,...,Z\bigr\}$,  le
caractère @ symbolisant l'espace.

On fait correspondre à  chaque lettre un élément de $\ofr{\bbz}{27\bbz}$
soit respectivement $\bigl\{0,1,2,3,4,...,26\bigr\}$.

Le chiffrement  proposé par Lester  \textsc{Hill} en 1929  s'effectue en
plusieurs étapes:

\begin{enumerate}
\item    on     choisit    une    matrice     K    de    $\mathfrak{M}_n
  \left(\ofr{\bbz}{27\bbz}\right)$   inversible:  c'est  notre   clé  de
  chiffrement.
\item on  regroupe chaque  bloc de $n$  lettres consécutives  du message
  clair M en blocs d
\end{enumerate}


Nous  allons   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$.

Nous allons explorer cette
méthode  en rajoutant  un vingt-septième  caractère qui  représentera un
espace entre les lettres.

\subsection{Codage}

On  considère  les  vingt-six  lettres  de  l'alphabet  plus  une  espace
représenté  par le  caractère \lstinline+@+.  La première  étape  est de
passer d'un caractère 
à un  nombre appartenant à  $\bbz_{27}$.


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 du
caractère \lstinline+caractère+.


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.



Définissez  une fonction  \lstinline+code(chaîne)+ qui  transformera une
chaîne en la liste des \og numéros\fg{} des caractères qui la compose, A
portant le numéro 1, Z le numéro 26 et @ le numéro 0.

Par exemple:

\begin{lstlisting}
>>> code('COUCOU@MAMAN')
[3, 15, 21, 3, 15, 21, 0, 13, 1, 13, 1, 14]
\end{lstlisting}



Tant que vous y êtes, créez une fonction \lstinline+decode+ qui effectuera
l'opération inverse.  


Par exemple:

\begin{lstlisting}
>>> decode([3, 15, 21, 3, 15, 21, 0, 13, 1, 13, 1, 14])
'COUCOU@MAMAN'
\end{lstlisting}


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

\begin{center}
Je ne suis pas un numéro, je suis un homme libre!
\end{center}


Mettons tout en majuscules, enlevons la ponctuation et les accents et codons:


\begin{lstlisting}
>>> L = code('JE@NE@SUIS@PAS@UN@NUMERO@JE@SUIS@UN@HOMME@LIBRE')
\end{lstlisting}

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 complétée éventuellement de zéros où les codes des
caractères seront rentrés colonne par colonne.

 
Nous allons  pour cela  créer une fonction  \lstinline+list2mat(liste,p)+ qui
transforme  une  liste  en  une   matrice  de  $p$  colonnes  puis  nous
utiliserons    la    fonction    \lstinline+transpose(matrice)+    créée
précédemment.


Attention! Nous devons travailler modulo 27. Créez donc une
fonction  \lstinline+matmod+ qui  transforme les  coefficients d'une
matrice modulo un nombre choisi.


Bref, le message  en clair devient une matrice.  Choisissons par exemple
un  3-chiffrement  de  Hill.  


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

 Écrivez une fonction
\lstinline+diag_gauss+ qui ressemble à \lstinline+tri_gauss+ vue précédemment.

Comme nous ne  vivons pas complètement à Disneyland,  tous les pivots ne
sont pas égaux à 1... 


Il  reste à
étudier le pivot  13. On cherche à résoudre  dans $\bbz_{27}$ l'équation
$13x=1$: cela signifie qu'on recherche l'inverse de 13 dans $\bbz_{27}$.





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+,   après   transposition.    Créez   donc   la   fonction
\lstinline+mat2list+ qui transforme  une matrice en une liste  en mettant ses
lignes \og bout à bout\fg{}.



On obtient donc enfin le message crypté à transmettre: 
\begin{center}

\lstinline+'LQVPQNDUGNPENPAEZ@RYUTFEULHYJXVPLEZ@OJOOQPQKETQF'+.
\end{center}




Si on le compare au message initial:

\lstinline+JE@NE@SUIS@PAS@UN@NUMERO@JE@SUIS@UN@HOMME@LIBRE+

on remarque  que le premier E  est codé par  Q alors que le  dernier est
codé par F: ce n'est donc pas un codage lettre par lettre et il est donc
apparemment plus compliqué que le chiffrement de César.


Nous pouvons résumer tout le codage en une seule opération:

\begin{lstlisting}
codage(message,cle):
    L = code(message)
    clair = transpose(matmod(list2mat(L,3),27))
    return decode(mat2list(transpose(matmod(mprod(cle,clair),27))))
end:
  \end{lstlisting}

\begin{lstlisting}
>>> codage('JE@NE@SUIS@PAS@UN@NUMERO@JE@SUIS@UN@HOMME@LIBRE',cle)
'LQVPQNDUGNPENPAEZ@RYUTFEULHYJXVPLEZ@OJOOQPQKETQF'
\end{lstlisting}


\subsection{Décodage}

Celui  qui  reçoit ce  message  possède la  clé  de
décodage qui est \lstinline+inv_cle+.

Les étapes  sont à peu près les  mêmes que pour le  codage. Proposez une
fonction \lstinline+decodage(message_crypte,inv_cle)+   
qui retournera le message décodé à partir du message crypté reçu.


%%% Local Variables: 
%%% TeX-master: "poly_graphes_11.tex"
%%% End: 
