\chapterimage{matrix}
\chaptertext{}
\setcounter{chapter}{2}
\maple
\chapter{Autour du calcul matriciel}

\section{Étude de quelques algorithmes}

\subsection{Fabriquons nos outils}


\subsubsection{Les primitives}

Les matrices seront crées comme
une liste de listes représentant les lignes.



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

\begin{lstlisting}[caption={}]
> m := [[1,2],[3,4],[5,6]]:
\end{lstlisting}

On obtiendra alors $m_{i,j}$ en entrant \lstinline+m[i][j]+.


Pour avoir  un affichage convivial, on crée  une procédure convertissant
la liste en tableau (type \lstinline+array+):

\begin{lstlisting}
> affiche:=proc(T)
    print(convert(T,array))
  end:
\end{lstlisting}

On obtient l'affichage de le matrice en entrant \lstinline+affiche(m)+.

On aura également besoin de deux primitives \lstinline+Lignes+ et 
\lstinline+Cols+  qui \og  compterons\fg{}  le nombre  de  lignes et  de
colonnes de la matrice:


\begin{lstlisting}
> Lignes := proc(M)
    RETURN(nops(M))
  end:
 
> Cols := proc(M)
    RETURN(nops(M[1]))
  end:
\end{lstlisting}

On aura souvent besoin de créer une matrice nulle d'une certaine taille:


\begin{lstlisting}
> nulle := proc(lignes,colonnes)
    RETURN([[0 $ colonnes] $ lignes])
  end:
\end{lstlisting}

Notez bien l'ordre d'appel de \lstinline+colonnes+ et  \lstinline+lignes+. 



\subsubsection{Transposée d'une matrice}

Déterminez une procédure \lstinline+transpose := proc(M)+ qui renvoie la
transposée d'une matrice M.



\subsubsection{Unité}

Déterminer  une  procédure  \lstinline+Id  := proc(n)+  qui  renvoie  la
matrice unité d'ordre $n$.

\subsection{Pivot de \bsc{Gauss}}

\subsubsection{Opérations élémentaires}


Créer  tout  d'abord  une  procédure \lstinline+GJ(M)  :=  proc(M)+  qui
fabrique une  matrice  où  se
juxtaposent la matrice initiale
et la matrice identité. 

Par exemple, $
M=
\begin{bmatrix}
1 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 0
\end{bmatrix}
$ est complétée en:

$$T=
\begin{bmatrix}
1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 1
\end{bmatrix}
$$

On montre  ensuite qu'en effectuant  des combinaisons sur les  lignes ou
des permutations  de lignes,  si on arrive  à obtenir la  matrice unité
dans la partie  gauche du tableau alors M est  inversible et son inverse
est la partie droite du tableau.


On commence par créer une procédure 
\lstinline+mult_ligne := proc(k,M,j)+ qui  
effectue la transformation $L_j\leftarrow k\times L_j$.


\begin{lstlisting}[caption={}]
> mult_ligne := proc(k,M,i)
  local A,j;
  A := M;
  for j from 1 to Cols(M) do
    A[i][j] := k*M[i][j]
  od:
  RETURN(A)
  end:
\end{lstlisting}


Selon le même modèle, créer une procédure 
\lstinline+comb_lignes := proc(ki,kj,M,i,j)+
 qui effectue la transformation $L_j\leftarrow
k_i\times L_i + k_j\times L_j$.

Créer aussi  une procédure \lstinline+swap :=  proc(M,i,j)+ qui effectue
l'échange de lignes $L_i\leftrightarrow L_j$.


On peut  alors effectuer  une succession d'opérations  élémentaires pour
vérifier si M et inversible et obtenir alors son inverse:

\begin{lstlisting}
> T := GJ(M): affiche(T);
\end{lstlisting}

$$
\textcolor{blue}
{
\begin{bmatrix}
1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 1
\end{bmatrix}
}
$$


\begin{lstlisting}[caption={}]
> T := comb_lignes(-1,1,T,1,3): affiche(T);
\end{lstlisting}

$$
\textcolor{blue}
{
\begin{bmatrix}
1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & -1 & -1 & 0 & 1
\end{bmatrix}
}
$$

On continue ainsi jusqu'à obtenir:

$$
\textcolor{blue}{
\begin {bmatrix} 
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{bmatrix}
}
$$

Il reste à extraire la partie  gauche du tableau en créant une procédure
\lstinline+JG  :=  proc(T)+. On  se  souviendra que  \lstinline+L[k..m]+
renvoie la sous-liste de L contenant les éléments de \lstinline+L[k]+ jusque 
\lstinline+L[m]+. 

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

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

Analyser le programme suivant:

 \begin{lstlisting}[caption={}]
> inv_gauss := proc(M)
    local S,NoLigne,NoCol,E,k,pivot;
    if Cols(M) <>  Lignes(M) then
       RETURN(`La matrice doit être carrée`)
    fi;
    S := GJ(M);
    for NoCol from 1 to Lignes(M) do
       NoLigne := NoCol;
       while (S[NoLigne][NoCol] = 0) do
         if (NoLigne = Lignes(M)) then
            RETURN(`Matrice non inversible`)
         fi;
         NoLigne := NoLigne + 1;
       od;
       S := swap(S,NoLigne,NoCol);
       pivot := S[NoCol][NoCol];
       S := mult_ligne(1/pivot,S,NoCol);
       E := {seq(k,k=1..Lignes(T))} minus {NoCol};
       for k in E do
          S := comb_lignes(-S[k][NoCol],1,S,NoCol,k);
       od;
     od;
     RETURN(JG(S))
  end: 
 \end{lstlisting}


\subsection{Généralisation}


Afin de résoudre  des systèmes linéaires, il ne faut  pas se limiter aux
matrices inversibles ni même aux matrices carrées.

On va essayer d'écrire la matrice originale sous forme \og triangulaire
supérieure \fg{}  en généralisant  cette configuration aux  matrices \og
rectangulaires\fg{}.

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. 

Il  faudra donc  faire  attention maintenant  à utiliser  le
minimum entre le nombre de lignes et le nombre de colonnes de la matrice.

\begin{lstlisting}[caption={}]
> A:=[[4,1,-2,8,1],[5,-13,7,6,1],[-1,9,-11,9,1],[2,-8,12,-3,1]]:
> affiche(A);
\end{lstlisting}

$$
\textcolor{blue}{
\begin {bmatrix} 
                     4& 1& -2& 8& 1\\
                      5& -13& 7& 6& 1\\
                     -1& 9& -11& 9& 1\\
                      2& -8& 12& -3& 1
\end{bmatrix}
}
$$

\begin{lstlisting}[caption={}]
> affiche(tri_gauss(A));
\end{lstlisting}
$$
\textcolor{blue}{
\begin {bmatrix} 
 4& 1& -2& 8& 1\\
 0& -57 &38& -16& -1\\
 0& 0& 1216& -1916& -248\\
 0& 0& 0& -1924320 &-594624
\end{bmatrix}
}
$$


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


 Déterminer une fonction \lstinline+image := proc(M)+ qui retourne une base de
  l'image puis une fonction \lstinline+rang := proc(M)+ qui renvoie le rang de
  la matrice M.




\subsubsection{Calcul du déterminant}



On  utilise \lstinline+tri_gauss+  sur  une matrice  carrée: on  obtient
ainsi une matrice  triangulaire. 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.

\subsubsection{Polynôme caractéristique et valeurs propres}


Déduisez-en une procédure \lstinline+polycar  := proc(M)+ qui renvoie le
polynôme caractéristique de M.

On pourra introduire \lstinline+idx := proc(n,x)+, 
une  variante  de  \lstinline+id(n)+,   qui  renvoie  $xI_n$,  puis  une
procédure \lstinline+Ex := proc(M,x)+ qui renvoie la matrice $M-xI_n$.


\begin{lstlisting}[caption={}]
> B := [[1,1,0],[-1,-1,0],[1,-1,0]]:
> affiche(Ex(B,x))
\end{lstlisting}

$$
\textcolor{blue}{
\begin {bmatrix} 
-x+1 &1&0\\
-1&-x-1&0\\
1&-1&-x
\end{bmatrix}
}
$$

\begin{lstlisting}[caption={}]
> polycar(B);
\end{lstlisting}

$$\textcolor{blue}{ -x^3}$$


Comment   déterminer  à   l'aide   de  Maple   si   cette  matrice   est
diagonalisable?

Déterminer un test \lstinline+est_diagonalisable := proc(M)+ qui renvoie
vrai ou faux.

\section{Maple à Centrale}

\begin{exercice}[Centrale,  2010]

    Si $n≥2$, on note $\vc =\nuple{\vc e}$ la base canonique de $ℝ^n$.

    Soit $f_n∈\mcal{L}(ℝ^n)$ tel que\enskip
    $f_n(\vc e_i) = \vc e_{i+1}$ si $i∈\llbracket1, n-1\rrbracket$
    et $f_n(\vc e_n) = \vc e_1$.
    \begin{enumerate}
        \item Écrire une procédure permettant d'obtenir la matrice $A_n$ de
            $f_n$ dans la base $\vc e$.
        \item Dans cette question, $n=6$.
            \begin{enumerate}
                \item Calculer le polynôme caractéristique de $A_6$.
                    Factoriser ce polynôme sur $ℝ[X]$.

                    On écrit $χ=\prod\limits_{1≤k≤p} R_k$
                    où les $R_k$ sont irréductibles dans $ℝ[X]$.
                \item Déterminer $\ker R_k(f_6)$ pour $k∈\llbracket1, p\rrbracket$.
                    Montrer que $ℝ^6=\ker R_1(f_6)⊕⋯⊕\ker R_p(f_6)$.
                \item Donner la matrice de $f_6$ dans une base adaptée à cette
                    décomposition.
            \end{enumerate}
        \item Si $n \geqslant 2$, calculer le polynôme caractéristique $χ$ de $A_n$. Le
            factoriser sur $ℝ[X]$.
    \end{enumerate}
  \end{exercice}
  


Voyons   quelques   commandes   utiles   issues   de   la   bibliothèque
\lstinline+LinearAlgebra+:

  \begin{lstlisting}[caption={}]
with(LinearAlgebra);
# a)
A := proc(n);
    M := Matrix(n);
    for i to n-1 do
        M[i+1, i] := 1;
        end do;
    M[1, n] := 1;
    return M
    end proc;

M := A(6);
I6 := IdentityMatrix(6);
latex(M);

# b)
#    i)
chi := CharacteristicPolynomial(M, x);
chi := factor(chi);
R := op(chi);

#    ii)
# Détermination des sev Ker(Rk(f))
F1 := NullSpace(M - I6);
F2 := NullSpace(M + I6);
F3 := NullSpace(M^2 + M + I6);
F4 := NullSpace(M^2 - M + I6);

P := <F1[1]|F2[1]|F3[1]|F3[2]|F4[1]|F4[2]>;
# Trois manières de vérifier que P est inversible :
Determinant(P);
NullSpace(P);
ColumnSpace(P);

#    iii)
# Matrice de f_6 dans un base adaptée :
P^(-1).M.P;

# c)
for n from 2 to 10 do
    CharacteristicPolynomial(A(n), x),\
    factor(CharacteristicPolynomial(A(n), x));
    end do;
    \end{lstlisting}



\begin{exercice}[Centrale,  2010]

    \begin{enumerate}
        \item
            Démontrer que, si deux endomorphismes $u$ et $v$ d'un espace vectoriel $E$ commutent, alors, les sous-espaces
            propres de $u$ et l'image de $u$ sont stables par $v$.

            Dans les deux cas suivants :
            \[
            A = \left( \begin{array}{cccc}
                {20} & {12} & { - 4} & {12}  \\
                { - 4} & { - 3} & 9 & { - 5}  \\
                { - 4} & 1 & 5 & { - 5}  \\
                { - 8} & { - 10} & 6 & { - 2}  \\
            \end{array} \right)
            \quad \text{ et } \quad
            A = \left( \begin{array}{cccc}
                { - 12} & { - 16} & { - 8} & { - 4}  \\
                4 & {13} & 1 & { - 1}  \\
                4 & 5 & 9 & { - 1}  \\
                8 & {10} & 2 & 6  \\
            \end{array} \right)
            \]

        \item
            Préciser les matrices qui commutent avec $A$ (structure, dimension, base éventuelle).

        \item
            Etudier dans ${\mathcal{M}}_4 (\mathbb{R})$, puis dans ${\mathcal{M}}_4 (\mathbb{C})$, l'équation
            \[
            X^2  = A
            \]
            (nombre de solutions, un exemple de solution quand il y en a, somme et produit des solutions quand elles sont en nombre fini).
    \end{enumerate}
  \end{exercice}
  


\begin{lstlisting}[caption={}]
with(LinearAlgebra):
# a)
A := <<20|12|-4|12>, <-4|-3|9|-5>, <-4|1|5|-5>, <-8|-10|6|-2>>;
(vpA, P) := Eigenvectors(A);
P^(-1).A.P;

B := <<-12|-16|-8|-4>, <4|13|1|-1>, <4|5|9|-1>, <8|10|2|6>>;
(vpB, Q) := Eigenvectors(B);
Q^(-1).B.Q;

# c)
Determinant(A);
Determinant(B);
  \end{lstlisting}




\vfill
\eject



\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}
def codage(message,cle):
    L = code(message);
    clair = transpose(matmod(list2mat(L,3),27));
    return decode(mat2list(transpose(matmod(mprod(cle,clair),27))))
  \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: "PolyMapleMPstar"
%%% End: 
