%\chapter{Ensembles, logique}
\chapterimage{monoid}
\chapter{Algèbre générale}


\modeexercice

\section{Monoïdes}



\begin{exercice}[Pourcentages]
  On peut considérer que les pourcentages sont en fait les nombres réels entre 0
  et 1 compris. Est-ce que ces nombres munis de l'addition forment un monoïde?
  Avec la multiplication?
\end{exercice}


\begin{exercice}
  Un monoïde peut-il avoir plusieurs éléments neutres?
\end{exercice}

\begin{exercice}[Have you got the power?]\label{exo::1}

On considère la LCI $\star$ définie sur
$\bbz$ par $a\star b = a - b$



L'écriture $a^3=a\star a\star a$ a-t-elle un sens? Quel est le sens de cette question?
\end{exercice}





\begin{exercice}[Have  you  got  the
  power now?]\label{exo::2}


On considère la LCI $\star$ définie sur
$\bbz$ par $a\star b = \underbrace{a\times a \times \cdots \times a}_{b \text{ facteurs}}$

L'écriture $a^3=a\star a\star a$ a-t-elle un sens?

\end{exercice}


\begin{exercice}[And now?]\label{exo::3}
  On considère la LCI définie sur $\bigl\{A,B,C,D\bigr\}$ par:

  \begin{center}
    \begin{tabularx}{0.5\linewidth}{Y{3}}
      \whline
      $\star$&$A$&$B$&$C$&$D$\\
      \whline
      $A$&$B$&$C$&$D$&$A$\\
      \hline
      $B$&$D$&$A$&$B$&$C$\\
      \hline
      $C$&$A$&$B$&$C$&$D$\\
      \hline
      $D$&$C$&$D$&$A$&$B$\\
      \whline
    \end{tabularx}
  \end{center}

L'écriture $A^3=A\star A\star A$ a-t-elle un sens?

\end{exercice}







\begin{exercice}
  Une définition:

{\itshape Un élément $a$ de E est dit \textbf{régulier à gauche} (ou \textbf{simplifiable
  à gauche}) si, et
seulement si:

$$\bigl(\forall x\bigr)\bigl(\forall y\bigr)\bigl((a\star x = a\star y)\limp (x=y)\bigr)$$

On a une définition similaire de la régularité à droite.

Un élément à la fois régulier à gauche et à droite est dit \textbf{régulier}.

Une loi telle que tout élément soit régulier est dite régulière.}



Un élément inversible est régulier (vérifiez-le). Un élément régulier est-il inversible?

\end{exercice}



\begin{exercice}
  On considère l'opération définie sur $\bbz$ par:
  $$a\top b = a + 2b$$
  Cette opération est-elle une LCI?  Est-elle commutative? Associative? Y a-t-il
  un élément neutre? Y a-t-il
  des éléments simplifiables? Symétrisables? 

Mêmes questions avec la loi définie sur $\bbq$ par $a\dagger b = (a+b)/2$.
\end{exercice}



\begin{exercice}
  On considère l'opération $\nand$ définie sur $\bbn_1=\llbracket 1,+\infty\llbracket$ par:
  $$ a\nand 1 = a,\quad a\nand b = a \times (a \nand (b-1))$$
  Cette opération vous  rappelle-t-elle quelque chose? Est-ce  une LCI? Est-elle
  commutative? Associative? etc.

Cherchez un élément régulier à droite mais pas à gauche.


\end{exercice}


\begin{exercice}
  En termes de magma, monoïde, que pensez-vous de la soustraction des entiers? Du produit cartésien des
  ensembles? De la composition des  relations? De la multiplication d'un vecteur
  du plan par un réel? etc.
\end{exercice}



\begin{exercice}
  Donnez  des  exemples  de  couples
  $\langle E,\star\rangle $ avec $\star$ une application
  définie sur $E\otimes E$ telle que
  $\langle E,\star\rangle $ ne soit pas un magma.
\end{exercice}



\begin{exercice}
  Soit  $A=\bigl\{a_1,a_2,...,a_p\bigr\}$ un  ensemble  de  caractères. On  note
  $A^\star$  l'ensemble  des chaînes  de  caractères  construites à  partir  des
  caractères de A.
  \begin{enumerate}
  \item $A^\star$ muni de la concaténation des chaînes a-t-il 
    une structure de magma associatif? de monoïde?
  \item  Les ensembles
    suivants munis de la
    concaténation sont-ils des magmas associatifs?  Des monoïdes?
    \begin{enumerate}
    \item L'ensemble des chaînes de longueur paire;
    \item L'ensemble des chaînes de longueur impaire;
    \item $\bigl\{(a_1a_2)^n\quad\mid\quad  n\in \bbn\bigr\}$;
    \item $\bigl\{a_1^na_2^n\quad\mid\quad  n\in \bbn\bigr\}$;
    \item L'ensemble  des chaînes ne  contenant que $a_1$ et  $a_2$, ceux-ci
      apparaissant un nombre égal de fois.
    \end{enumerate}
  \end{enumerate}
\end{exercice}


\begin{exercice}
Soit $\bbb_2=\bigl\{0,1\bigr\}$ l'ensemble des  booléens. Est-ce que $\bbb_2$ muni
de NAND est un monoïde? Muni de NOR?
\end{exercice}

\begin{exercice}
  Soit l'opération  $\intercal$ définie  par $x\intercal y=  \sqrt{x^2+y^2}$. Est-ce
  que $\langle \bbr,\intercal\rangle
  $ est un magma associatif?  Un monoïde? Un monoïde simplifiable? Y a-t-il un élément absorbant?
\end{exercice}

\begin{exercice}
Soit une fonction $\FR(E)$ l'ensemble des fonctions de $E$ dans $E$.

On dit que  $f$ est inversible à  gauche s'il existe une fonction  $g$ telle que
$g\circ f= \mathrm{Id}_E$.

Montrez que $f$ inversible à gauche si,  et seulement si, $f$ est injective puis
que $f$ est inversible à droite si, et seulement si, $f$ est surjective.


\end{exercice}










\begin{exercice}
  [Notation polonaise inverse]

La  notation polonaise  inverse  ou  notation postfixée  consiste  à placer  les
opérateurs  \emph{après}  les  opérandes,  en  cela  il  diffère  de  la  notion
infixe. Par exemple:

\begin{center}
{\renewcommand{\arraystretch}{0.8}
\begin{tabular}{|c|c|}
\hline
Notation infixe & Notation postfixe\\\hline
$1+2$& $1$ $2$ $+$\\\hline
$ 10 \div 0.5 $ & $10$  $0.5$ $\div$ \\\hline
$ 2\times 3 $  &  $2$ $3$ $\times$ \\\hline
$ (1+2)\times 3 $   & $1$ $2$ $+$ $3$ $\times$ \\\hline
$ 1+(2\times 3) $   & $1$ $2$ $3$ $\times$ $+$  \\\hline
$ (-2) - 3 $  & $2$  $-_1$ $3$ $-_2$ \\\hline
$ -(2 - 3) $& $2$ $3$ $-_2$ $-_1$ \\\hline

\end{tabular}
}
\end{center}

\textit{Remarques sur la notation postfixe.}
\begin{itemize}
\item Pas besoin de parenthèses
\item Il faut distinguer le $-$ unaire (noté ici $-_1$) du moins binaire (noté ici $-_2$). Le premier transforme un nombre en son opposé (exemple : $-2$) le second calcule la différence entre deux termes (exemple : $1-3$).
\end{itemize}


\begin{enumerate}
\item Convertir les expressions suivantes en notation polonaise inverse.%
\begin{multicols}{2}%
\begin{enumerate}%
\item $1+2+3+4+5+6$
\item $7 + (1+3)\times (2+3) $
\item $ 2\times 3 \times 5 \div 7  $
\item $ 3 + 9\times (5\times (7 + 2) +2)   $
 \end{enumerate}\end{multicols}

\item Convertir en notation usuelle les expressions postfixes suivantes.

\begin{multicols}{2}%
\begin{enumerate}
\item $2$ $3$ $-_1$ $-_2$
\item $1$ $2$ $3$ $+$ $\times$  
\item $1$ $2$ $3$ $+$ $-_1$ $\times$  
\item $7$ $5$ $3$ $2$ $1$ $+$ $\times$ $\div$ $+$
\end{enumerate}\end{multicols}

\end{enumerate}

\end{exercice}










\begin{pyxercice}
  Essayez de  déterminer des valeurs  \og flottantes\fg{}  $a$, $b$ et  $c$ pour
  lesquelles $(a+b)+c \neq a+(b+c)$. Expliquez votre raisonnement. Vérifiez avec
  l'interpréteur Python.
  
\end{pyxercice}




\begin{pyxercice}
  Est-ce que les opérateurs Python
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{and} et \mintinline[fontsize=\small,fontfamily=txtt]{python}{or} 
sont commutatifs?

\end{pyxercice}







\begin{pyxercice}

Explorez le code suivant...


\begin{pythoncode}
  class C() :

    def  __init__(self, chaine = ' ') :
        self.car = chaine

    def __add__(self, other):
        return chr( ord(self.car) + ord(other.car) - 32)

    def __repr__(self) :
        return self.car

class Ens() :

    def __init__(self, elements = set([])) :
        self.elms = elements

    def __add__(self, other) :
        U = Ens()
        U.elms = set.union(self.elms, other.elms)
        return U

    def __repr__(self):
        return str(self.elms)

class Nat() :

    def __init__(self, ent = 0) :
        self.nat = abs(ent)

    def __add__(self, other) :
        if self.nat >= other.nat :
            return Nat(self.nat)
        return Nat(other.nat)

    def __repr__(self):
        return str(self.nat)

class Panier() :

    def __init__(self, articles = set([])) :
        self.contenu = articles

    def __add__(self, other) :
        return Panier(self.contenu | other.contenu)

    def __repr__(self) :
        return str(self.contenu)
\end{pythoncode}


\end{pyxercice}







\begin{pyxercice}[HP15C]
  Créez une calculatrice  qui effectue les calculs  arithmétiques à la
  mode polonaise inversée.

  On  pourra se  contenter d'une  version simplifiée:  on donne  comme
  argument  la chaîne  correspondant  à l'opération  à effectuer  sous
  forme postfixée. La fonction renvoie le résultat de l'opération. Par
  exemple:

  \begin{pythoncode}
In [1]: seq = "2 3 4 + *"

In [2]: npi(seq)
Out[2]: 14
  \end{pythoncode}

On pourra utiliser les fonctions du module \texttt{operator}.

Par exemple, \texttt{operator.add(2,3)} renvoie 5.

On peut alors créer un dictionnaire des opérations:

\begin{pythoncode}
operations = {
    '+':  operator.add, '-':  operator.sub,
    '*':  operator.mul, '/':  operator.truediv,
    '%':  operator.mod, '**': operator.pow,
    '//': operator.floordiv
}
\end{pythoncode}

et  on   obtient  l'opération  d'addition   à  partir  de   la  chaîne
\texttt{'+'}:

\begin{pythoncode}
In [3]: operations['+']
Out[3]: <function _operator.add>
\end{pythoncode}

Par exemple:

\begin{pythoncode}
In [1]: npi("3 2 7 9 - * 3 + 2 / +")
Out[1]: 2.5

In [2]: npi("3 2 7 9 - * 3 + 2 /")
  File "<string>", line unknown
SyntaxError: Expression non valide
\end{pythoncode}

Vous   pouvez    ensuite   proposer   une   calculatrice    plus   \og
interactive\fg{}:

\begin{pythoncode}
In [1]: hp_inter()
->  |
rentrer un nombre ou un opérateur: 1
-> 1 |
rentrer un nombre ou un opérateur: 2
-> 2, 1 |
rentrer un nombre ou un opérateur: 3
-> 3, 2, 1 |
rentrer un nombre ou un opérateur: 4
-> 4, 3, 2, 1 |
rentrer un nombre ou un opérateur: '+'
-> 7, 2, 1 |
rentrer un nombre ou un opérateur: '-'
-> -5, 1 |
rentrer un nombre ou un opérateur: '+'
-> -4 |
rentrer un nombre ou un opérateur: 3
-> 3, -4 |
rentrer un nombre ou un opérateur: '*'
-> -12 |
rentrer un nombre ou un opérateur: 'fin'
\end{pythoncode}



\end{pyxercice}



\begin{pyxercice}
  Définissez                             une                            fonction
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{big(op,    neutre)}   qui
  prend un opérateur associatif et son  neutre et renvoie une fonction qui prend
  une collection 
(\mintinline[fontsize=\small,fontfamily=txtt]{python}{tuple, list, set,...})
et renvoie la réduction de la collection par l'opération:

\mintinline[fontsize=\small,fontfamily=txtt]{python}{neutre op x1 op x2 op...op xn}



\end{pyxercice}




\begin{pyxercice}
  Les  fonctions   \mintinline[fontsize=\small,fontfamily=txtt]{python}{map}  et
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{filter} de Python sont en
  fait              des             cas              particuliers             de
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{reduce}.
Définissez-les                            en                           utilisant
\mintinline[fontsize=\small,fontfamily=txtt]{python}{reduce} au lieu d'itération
ou de récursion.




\end{pyxercice}







\begin{pyxercice}
  Définissez                   une                  version                   de
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{reduce}   qui   omet   le
  troisième argument (le neutre). 

Cette fonction sera utilse pouur travailler sur des magmas associatifs qui n'ont
pas de neutre.

\end{pyxercice}















%%%%%%%%%%


\section*{Groupes}



\begin{exercice}
\begin{enumerate}
\item   $\bbb_2$ muni des opérations suivantes est-il un groupe:

  \begin{multicols}{3}
    \begin{enumerate}
    \item $\land$? \item $\lor$? \item $\oplus$?
    \end{enumerate}
  \end{multicols}

\item Résoudre dans $\bbb_2$ l'équation $a\oplus x = b$.
\end{enumerate}
\end{exercice}

\begin{exercice}
  Soit $\langle G,\star\rangle $ un groupe et $a$ et $b$ deux éléments de $G$.  Exprimez
  l'inverse de $a\star b$ en fonction des inverses de $a$ et de $b$.
\end{exercice}






\begin{exercice}
  Les    tables    ci-dessous    définies   sur    $E=\bigl\{a,b,c\bigr\}$
  définissent-elles des magmas associatifs? des monoïdes?

  \begin{multicols}{2}
    \begin{tabularx}{0.7\linewidth}{Y{2}}
      \whline
      $\star$&$a$&$b$&$c$\\
      \whline
      $a$&$a$&$b$&$c$\\
      \hline
      $b$&$b$&$c$&$a$\\
      \hline
      $c$&$c$&$a$&$b$\\
      \whline
    \end{tabularx}
    
    \begin{tabularx}{0.7\linewidth}{Y{2}}
      \whline
      $\bot$&$a$&$b$&$c$\\
      \whline
      $a$&$a$&$c$&$c$\\
      \hline
      $b$&$b$&$c$&$a$\\
      \hline
      $c$&$c$&$a$&$a$\\
      \whline
    \end{tabularx}
  \end{multicols}
  
  Notons $A=\bigl\{a,b,c\bigr\}$.
  Montrez        que        $\langle
  A,\star\rangle $ a une structure de groupe. Comparer ce groupe
  avec 
  \begin{itemize}
  \item                $\left\langle
      \ofr{\Z}{3\Z},\overline{+}\right\rangle
    $ 
  \item               $\left\langle              \bigl\{1,\mathrm{e}^{\ofr{2{\rm
            i}\pi}{3}},\mathrm{e}^{\ofr{-2{\rm i}\pi}{3}}\bigr\},\times\right\rangle$.
  \end{itemize} 
\end{exercice}






\begin{exercice}[Isomorphisme]
Montrez que $\langle \bbf_2,+\rangle $ et $\langle \ofr{\bbz}{4\bbz}^\star , \cdot\rangle $ sont isomorphes.

Est-ce que $\langle \ofr{\bbz}{4\bbz} , +\rangle $ et $\langle \ofr{\bbz}{5\bbz}^\star , \cdot\rangle $ sont
isomorphes?

Est-ce que $\langle \ofr{\bbz}{4\bbz} , +\rangle $ et $\langle \ofr{\bbz}{8\bbz}^\star , \cdot\rangle $ sont
isomorphes?

Est-ce que $\langle \bbf_2\otimes \bbf_2, +\rangle $ et $\langle \ofr{\bbz}{8\bbz}^\star , \cdot\rangle $ sont
isomorphes?
\end{exercice}




\begin{exercice}[Déplacement à partir du pavé numérique]

À  chaque  touche  du  pavé  numérique,  on  fait  correspondre  un  déplacement
élémentaire d'un point  sur l'écran: 6 pour un déplacement  unitaire à droite, 2
pour un déplacement unitaire vers le bas, etc.

On  note $D$  l'ensemble  de  ces dix  déplacements  et  $D^\star$ l'ensemble  des
séquences de déplacements.

Associer à $D^*$ une loi pour en faire un monoïde. Montrez que c'est un groupe abélien.
  

Que se passe-t-il si  au lieu de déplacements on considère  la trace laissée par
ces déplacements? 
\end{exercice}




\begin{exercice}[Caractérisation d'un sous-groupe]

La programmation, c'est l'efficacité... La définition d'un sous-groupe n'est pas
efficace:  pouvez-vous  en  donner   une  caractérisation  plus  synthétique  en
trouvant des propriétés minimales à vérifier?
  
\end{exercice}







\begin{exercice}
 Est-ce que l'ensemble $\bigl\{x+y \sqrt{2} \mid (x,y)\in \bbq^2\bigr\}$ muni de
 la multiplication des réels a une structure de groupe?
\end{exercice}






\begin{exercice}[Chiffrement par blocs]\label{exo::bloc}

Commençons par une définition:
\setindent{\indentationcours}
\begin{definition}[Cryptosystème (ou système de chiffrement ou chiffre)]
Un  cryptosystème est  un quintuplet
$\langle \PR,\CR,\KR,\ER,\DR\rangle $ tel que:
\begin{itemize}
\item L'ensemble $\PR$ est l'espace des messages en clair (\textit{plaintext} en
      anglais). En général, c'est l'ensemble des chaînes de bits.
\item L'ensemble $\CR$ est l'espace des messages chiffrés (\textit{cyphertext} en
      anglais). En général, c'est aussi l'ensemble des chaînes de bits.
\item L'ensemble $\KR$ est l'espace des clés (\textit{key});
\item $\ER$  est la  famille des fonctions  de chiffrement, qui  vont de
      $\PR$ dans $\CR$;
\item $\DR$  est la  famille des fonctions  de déchiffrement, qui  vont de
      $\CR$ dans $\PR$;
\end{itemize}

Pour chaque élément  $e\in\KR$, il existe un élément  $d\in\KR$ tel que,
pour  tout  message  clair  $m$  de  $\PR$,  il  existe  $D_d\in\DR$  et
$E_e\in\ER$  telles que  $D_d(E_e(m))=m$. Les  fonctions $D_d$  et $E_e$
sont des applications injectives. Il est entendu que $d$ doit
rester secret...

\end{definition}
\setindent{0cm}

\begin{enumerate}
\item On travaille sur des  mots formés des 26 minuscules non accentuées
      de notre alphabet latin et d'une espace qui sont modélisés par les
      entiers de $E=\bigl\{0,1,2,...,26\bigr\}$.

Dans ce  contexte, on  remplace une \og  lettre\fg{} $x$ par  $kx [27]$ avec $k\in E$. Définit-on ainsi un cryptosystème?
\item  Un  cryptosystème  est   un  \textit{chiffrement  par  blocs}  si
      $\PR=\CR=\{0,1\}^n$.   Est-ce  que  le  chiffrement  ROT-13  est  un
      chiffrement par blocs?

\item Pourquoi  les fonctions de chiffrement d'un  chiffrement par blocs
      sont des permutations?
\end{enumerate}

Depuis 2001, le  chiffrement par blocs \og officiel  \fg{} est l'AES qui
opère par blocs de 128 bits.  Une présentation de l'algorithme de chiffrement associé,
\textsc{Rijndael}, et de sa résistance aux attaques est présentée ici :

\href{http://www.cryptis.fr/assets/files/Canteaut-25ans-Cryptis.pdf}{http://www.cryptis.fr/assets/files/Canteaut-25ans-Cryptis.pdf}.

\end{exercice}






\begin{exercice}[Mode ECB]\label{exo::ecb}
  ECB: \textit{Electronic  CodeBook}. C'est le plus  simple...et le plus
  vulnérable des modes de chiffrement par blocs.


Voyons sur  un exemple.  On considère une  chaîne de bits  quelconque que
l'on découpe en  blocs de longueur fixe, par exemple  7 (plus pratique
pour ensuite utiliser  l'ASCII: pourquoi?). On rajoute
éventuellement des zéros en bout de chaîne.

Considérons $m=1001001111011$. On rajoute un 0 en bout de chaîne:

$$m'=1001001\ 1110110 =\beta_1\beta_2$$

avec $\beta_1=1001001$ et $\beta_2=1110110$.


On choisit une clé de chiffrement dans 
$\mathfrak{S}_7$ car $\KR= \mathfrak{S}_7$:
$\pi=
\begin{pmatrix}
  2&0&3&1&5&4&6
\end{pmatrix}
$

Alors $E_{\pi}(\beta_1)=0110001$ et $E_{\pi}(\beta_2)=1101110$.

\tikzstyle{vertex}=[draw,fill=black!15,circle,minimum size=20pt,inner sep=0pt]
\tikzstyle{encrypt}=[draw,fill=black!15,rectangle,minimum        size=20pt,inner
sep=0pt]
\begin{center}
\begin{tikzpicture}
    \newcommand{\n}{2}
    \foreach \nr in {0, ..., \n}{
        \node (m\nr) at (0,{(\n-\nr)*2}) {$m_\nr$};
        \node (c\nr) at (4,{(\n-\nr)*2}) {$c_\nr$};
        \node (E\nr)[encrypt] at (2,{(\n-\nr)*2}) {$E$};
        \node (k\nr) at (2,{(\n-\nr)*2+1}) {$k$};

        \draw[->,very thick] (m\nr) -- (E\nr);
        \draw[->,very thick] (k\nr) -- (E\nr);
        \draw[->,very thick] (E\nr) -- (c\nr);
    }

   \node (mx) at (0,-1) {$\vdots$};
   \node (Ex) at (2,-1) {$\vdots$};
   \node (cx) at (4,-1) {$\vdots$};
\end{tikzpicture}
\end{center}

\begin{enumerate}
\item Que se passe-t-il si un bloc chiffré est mal transmis ou perdu?

\item Quelle est la principale faiblesse du mode ECB?

\item Chiffrez  \og maman\fg{} avec ce cryptosystème  en transformant la
      chaine de lettres en chaînes de bits constituée des codes ASCII de
      ses   caractères.   Le   tableau   ASCII  standard   est-il satisfaisant? Comment y remédier?
\item  Quelle est  la  fonction de  déchiffrement  associée à  l'exemple
      précédent?
\item Déchiffrez $10110111001111$ sachant que la clé de
      chiffrement est $k=
  \begin{pmatrix}
    1&2&0&6&5&4&3
  \end{pmatrix}
$
\item Déchiffrez \og papa\fg{} sachant que c'est le cryptosystème du début qui a été employé.
\end{enumerate}
\end{exercice}













\begin{exercice}[Mode CBC]
  CBC:  \textit{Cipher-Block  Chaining}.  Ce  mode  a  été  inventé  par
  \textsc{Ibm} en  1976. Pour  éviter la faiblesse  de l'ECB,  les blocs
  sont maintenant chaînés: chaque bloc en clair est \og XORé\fg{} ou \og
  OUEXé\fg{} avec le bloc crypté précédent avant d'être crypté lui-même.

Pour le premier bloc, on utilise un \textit{vecteur d'initialisation} public.
Avec   les  notations   habituelles,  on   a   donc  $$c_i=E_k(m_i\oplus
c_{i-1}),\quad c_0 = \ve{v_0}$$

\begin{center}
% thanks to http://tex.stackexchange.com/a/75838/5645
\tikzset{XOR/.style={fill=black!15,draw,minimum size=13pt,circle,append after command={
[shorten >=\pgflinewidth, shorten <=\pgflinewidth,]
(\tikzlastnode.north) edge (\tikzlastnode.south)
(\tikzlastnode.east) edge (\tikzlastnode.west)
}
}
}
\tikzstyle{encrypt}=[draw,fill=black!15,rectangle,minimum size=20pt,inner sep=0pt]
\begin{tikzpicture}
\newcommand{\n}{3}
\foreach \nr in {1, ..., \n}{
\node (M\nr) at (0,{(\n-\nr)*2}) {$m_\nr$};
\node (x\nr)[XOR] at (2,{(\n-\nr)*2}) {};
\node (E\nr)[encrypt] at (4,{(\n-\nr)*2}) {$E$};
\node (C\nr) at (6,{(\n-\nr)*2}) {$c_\nr$};
\node (K\nr) at (4,{(\n-\nr)*2+1}) {$k$};
\draw[->,very thick] (M\nr) -- (x\nr);
\draw[->,very thick] (x\nr) -- (E\nr);
\draw[->,very thick] (E\nr) -- (C\nr);
\draw[->,very thick] (K\nr) -- (E\nr);
}
\foreach \nr in {2, ..., \n}{
\pgfmathtruncatemacro{\tmp}{\nr-1}
\draw[->,very thick] (E\tmp) -- (4, {(\n-\tmp)*2-0.5}) -- (2, {(\n-\nr)*2+1.5}) -- (x\nr);
}
\node (IV) at (2,{\n*2-1}) {$\ve{v_0}$};
\draw[->, very thick] (IV) -- (x1);
\node (Mx) at (0,-1) {$\vdots$};
\node (xx) at (2,-1) {$\vdots$};
\node (Ex) at (4,-1) {$\vdots$};
\node (Cx) at (6,-1) {$\vdots$};
\end{tikzpicture}
\end{center}


\begin{enumerate}
\item Quel est le lien entre OUEX et $\bbf_2$?
\item Cryptez l' exemple traité avec ECB en prenant $\ve{v_0}=1010101$.
\item Faites de même avec \og Maman\fg{}.
\item Donnez  une formule  de déchiffrement. Déchiffrer  le cryptogramme
      $101101110011111$ sachant que la clé est 

$k=\begin{pmatrix}
    1&0&2
  \end{pmatrix}
$ et que $\ve{v_0}=001$.
\item Déchiffrez \og Papa\fg{} sachant  que c'est le cryptosystème de la
      question 2. qui a été employé.
\end{enumerate}


Ce  mode  est efficace  mais  nécessite  l'utilisation  de fonctions  de
chiffrement  et de  déchiffrement différentes  ce qui  peut  ralentir la
procédure.
\end{exercice}


\begin{exercice}[Mode CFB]
  CFB:  \textit{Cipher-FeedBack}. C'est un  mode dérivé  de CFB  qui est
  utilisé  par  OpenPGP,  format  pour  l'échange  sécurisé  de  données
  (paiements sécurisés par exemple)
  largement  utilisé actuellement  mais est  susceptible  d'être attaqué,
  même s'il est très difficile  de mettre en \oe uvre concrètement cette
  attaque:

{\scriptsize
  \href{http://www.cert-ist.com/fra/ressources/Publications\_ArticlesBulletins/Autres/FailledanslechiffrementCFBdOpenPGP/}{http://www.cert-ist.com/fra/ressources/Publications\_ArticlesBulletins/Autres/FailledanslechiffrementCFBdOpenPGP/}
}

Le mode CFB utilise un registre de décalage de taille $r$ inférieure à 
celle de la clé.

On a  besoin d'un vecteur d'initialisation $\ve{v_0}$.  Le message clair
est découpé  en blocs  de longueur $r$.  Ensuite on procède  comme suit,
sachant que  les  $m_j$ sont les blocs en clair de longueur $r$:

\begin{itemize}
\item $t_0=\ve{v_0}$;
\item $s_j=E_k(t_j)$;
\item $g_j$ est  la chaîne constituée des $r$ bits les  plus à gauche de
      $s_j$. Quelle est l'opération arithmétique associée?
\item $c_j=m_j\oplus g_j$;
\item  $t_j=(2^rt_{j-1}+c_{j-1})   \modu  2^n$  (attention!   Il  faut
  travailler en base 2).
\end{itemize}


\begin{center}
% thanks to http://tex.stackexchange.com/a/75838/5645
\tikzset{XOR/.style={fill=black!15,draw,minimum size=13pt,circle,append after command={
[shorten >=\pgflinewidth, shorten <=\pgflinewidth,]
(\tikzlastnode.north) edge (\tikzlastnode.south)
(\tikzlastnode.east) edge (\tikzlastnode.west)
}
}
}
\tikzstyle{encrypt}=[draw,fill=black!15,rectangle,minimum size=20pt,inner sep=0pt]
\begin{tikzpicture}
\newcommand{\n}{3}
\foreach \nr in {1, ..., \n}{
\node (M\nr) at (0,{(\n-\nr)*3}) {$m_\nr$};
\node (x\nr)[XOR] at (2,{(\n-\nr)*3}) {};
\node (E\nr)[encrypt] at (2,{(\n-\nr)*3+1}) {$E$};
\node (K\nr) at (2,{(\n-\nr)*3+2}) {$k$};
\node (C\nr) at (4,{(\n-\nr)*3}) {$c_\nr$};
\draw[->,very thick] (M\nr) -- (x\nr);
\draw[->,very thick] (x\nr) -- (C\nr);
\draw[->,very thick] (K\nr) -- (E\nr);
\draw[->,very thick] (E\nr) -- (x\nr);
}
\foreach \nr in {2, ..., \n}{
\pgfmathtruncatemacro{\tmp}{\nr-1}
\draw[->,very thick] (3, {(\n-\tmp)*3}) -- (3, {(\n-\tmp)*3-0.5}) -- (1, {(\n-\tmp)*3-0.5}) -- (1, {(\n-\nr)*3+1}) -- (E\nr);
}
\node (IV) at (0.5,{\n*3-2}) {$\ve{v_0}$};
\draw[->, very thick] (IV) -- (E1);
\node (Mx) at (0,-1) {$\vdots$};
\node (xx) at (2,-1) {$\vdots$};
\node (Ex) at (4,-1) {$\vdots$};
\end{tikzpicture}
\end{center}



Le déchiffrement fonctionne de manière identique en échangeant les rôles
de $m_j$ et $c_j$ à la quatrième étape: démontrez-le!

\begin{enumerate}
\item Chiffrez \og \textit{ Papa is cool}\fg{} sachant que la clé est $k= 
  \begin{pmatrix}
    3&0&2&1
  \end{pmatrix}
$, que $\ve{v_0}=0101$ et que $r=3$.


\item Déchiffrer  le cryptogramme
      $101101110011111$ sachant que la clé est $k= 
  \begin{pmatrix}
    1&0&2
  \end{pmatrix}
$, que $r=2$ et que $\ve{v_0}=001$.
\end{enumerate}



\end{exercice}










\begin{exercice}[\textsc{Hamilton} et les quaternions]


\parpic{\includegraphics[width=7cm]{hamilton}}
Après avoir travaillé sur les nombres complexes comme nous allons le voir bientôt, Sir
William \textsc{Hamilton} (il a été anobli en 1835) voulut étendre ses travaux à la dimension 3. 
Il n'arrivait cependant pas à  imaginer une multiplication qui puisse satisfaire
des critères intéressants, notamment la conservation des normes.\\
Un  jour qu'il  se promenait  avec son  épouse dans  un parc  dublinois, il  eut
soudain un  éclair qu'il  s'empressa de  graver sur  la pierre  du pont  le plus
proche :

$${\rm i}^2 = {\rm j}^2={\rm k}^2= {\rm ijk} = -1$$

Remplissez alors la table de multiplication suivante:

\begin{center}
  \begin{tabularx}{0.4\linewidth}{Y{3}}
    \whline
    $\times$ & 1 & i & j & k \\
    \whline
    1        &  &  &  &  \\
    \hline
    i        &  &  &  &  \\
    \hline
    j        &  &  &  &   \\
    \hline
    k        &  &  &  &   \\
    \whline
  \end{tabularx}
\end{center}


\textsc{Hamilton} définit alors  un \textit{quaternion} par la  donnée de quatre
réels $a$,  $b$, $c$ et  $d$ car un quaternion  peut s'écrire de  manière unique
comme combinaison des quatre quaternions élémentaires:

$$q = a1 + b{\rm i} + c{\rm j} + d{\rm k}$$

Le nombre  $a$ est  la partie  scalaire et  le triplet  $(b,c,d)$ est  la partie
vectorielle  (c'est \textsc{Hamilton}  qui  a  en effet  introduit  le terme  de
\textit{vecteur} en mathématique).

Quelles propriétés possède ou ne possède pas la multiplication des quaternions?


{\itshape
  Il y a énormément  de choses à dire sur les quaternions  mais nous manquons un
  peu de recul mathématique...

  Point  de vue  informatique, il  faut  cependant noter  qu'ils sont  largement
  utilisés  en  infographie,  en  traitement  du signal  et  dans  tout  domaine
  utilisant des rotations et entraînant de nombreux calculs. 

  En  physique,  ces  calculs  sont traditionnellement  traités  par  du  calcul
  matriciel mais nous verrons bientôt  que celui-ci induit de nombreuses erreurs
  d'arrondis qui peuvent être atténuées en passant par les quaternions.


  Un site  à visiter :  \href{http://www.alcys.com/}{http://www.alcys.com/}. Les
  quaternions  apparaissent  sous  vos   yeux  ébaubis....
}


\end{exercice}












\begin{pyxercice}
  Déterminez une fonction \mintinline[fontsize=\small,fontfamily=txtt]{python}{braguette(v1, v2)}
qui renvoie la liste des couples formés par les éléments de  deux listes pris dans l'ordre.


%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{eclair}
\end{center}
%\end{figure}




Si les listes sont de longueurs différentes, on s'arrête à la plus petite.

\begin{pythoncode}
In [38]: braguette([1, 2, 3, 4],['a', 'b', 'c'])
Out[38]: [(1, 'a'), (2, 'b'), (3, 'c')]  
\end{pythoncode}


Déduisez-en une fonction \mintinline[fontsize=\small,fontfamily=txtt]{python}{prod_scal(v1, v2)}
qui   calcule   le   produit   scalaire   de   deux   listes   avec   un   petit
\mintinline[fontsize=\small,fontfamily=txtt]{python}{reduce}.

\begin{pythoncode}
In [39]: prod_scal([1,2,3],[4,5,6])
Out[39]: 32  
\end{pythoncode}


En   fait,   on  aurait   pu   gagner   du   temps   en  créant   une   fonction
\mintinline[fontsize=\small,fontfamily=txtt]{python}{braguette_avec(xs, ys, op)} 
qui ferme la braguette en effectuant une opération sur chaque dent.

\begin{pythoncode}
In [44]: braguette_avec("abcd", "ABCD", lambda x, y: x + y)
Out[44]: ['aA', 'bB', 'cC', 'dD']  
\end{pythoncode}



Comment                                 un                                simple
\mintinline[fontsize=\small,fontfamily=txtt]{python}{braguette_avec}   va  alors
nous permettre d'implémenter l'algorithme d'Euclide étendu en trois lignes?

Rappel:


\begin{center}
\begin{tabular}{|c||c|c|c||c|l}
\hhline{-----} $k$ & $u_k$ & $v_k$ & $r_k$ & $q_k$ &  \\ 
\hhline{=====} 0 & \Colorbox{blue!50!white}{ 1} & \Colorbox{blue!50!white}{ 0} & \Colorbox{blue!50!white}{ 19} & / & $L_0$ \\ 
\hhline{-----} 1 & \Colorbox{blue!50!white}{ 0} & \Colorbox{blue!50!white}{ 1} &\Colorbox{blue!50!white}{ 15} & \Colorbox{yellow!50!white}{1} & $L_1$ \\ 
\hhline{-----} 2 & 1 & $-1$ & 4 & 3 & $L_2\leftarrow L_0-\Colorbox{yellow!50}{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}



Donnez ensuite une autre version de cet algorithme avec une boucle while:

\begin{pythoncode}
def bezout(a,b) :
    U, V = ????, ????
    while ???? :
        U, V = ????
    return ?
\end{pythoncode}

C'est celle que nous utiliserons pour construire notre classe de calcul modulaire.

\end{pyxercice}
















\begin{pyxercice}[Permutations]
\setindent{\indentationcours}
  \begin{definition}[Permutation]
    Soit  E  un ensemble.  Une  permutation  de  E est  une  application
    bijective  de E  sur  E. On  note  $\mathfrak{S}(E)$ l'ensemble  des
    permutations de E.
  \end{definition}
\setindent{0cm}

Généralement, on  note les permutations  sous forme d'une matrice  où la
première  ligne correspond aux  éléments de  E et  où la  deuxième ligne
correspond aux images des éléments de E.

Par exemple:


$$
π = \begin{pmatrix}
  0&1&2&3&4\\
2&0&1&4&3
\end{pmatrix}
$$



est une permutation de $E=\bigl\{0,1,2,3,4\bigr\}$.


On peut la résumer à la donnée de  $[2,0,1,4,3]$ ou la donnée de la fonction $π$
en extension.





\setindent{\indentationcours}
\begin{definition}
  Soit  $n\in\bbn$,   alors  ${S}_n$  désigne   l'ensemble  des
  permutations de $\bigl\{0,1,2,3,...,n-1\bigr\}$.
\end{definition}





\begin{theoreme}[Groupe des permutations]\label{th::groupe_perm}
  L'ensemble ${S}_n$  muni
  de la loi $\circ$ de composition des applications a une structure de groupe.
\end{theoreme}

\begin{theoreme}[Nombre de permutations]\label{th::nb_perm}
  Le groupe ${S}_n$ est d'ordre $n!$.
\end{theoreme}
\setindent{0cm}

\begin{enumerate}
\item Faites le  lien entre la composition des applications  et le \textit{pipe}
  (\og paillepeu\fg{}) des commande système.
Écrivez $f\circ g(x)$ en notations sytème.

\item Soit par exemple $π' = \begin{pmatrix}
  0&1&2&3&4\\
1&2&3&4&0
\end{pmatrix}$

Déterminez $π\circ π'$, $π'\circ π$, $π\circ π$. 


\item Quelle peut être la réciproque d'une permutation pour la composition?

\item       Voici      quelques       éléments      sur       les      fonctions
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{zip}                   et
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{sorted}:

\begin{pythoncode}
In [39]: sorted([1,6,5,4])
Out[39]: [1, 4, 5, 6]

In [40]: sorted([(1,2),(4,1),(3,2),(2,0)])
Out[40]: [(1, 2), (2, 0), (3, 2), (4, 1)]

In [41]: zip([1,3,2],['a','b','c'])
Out[41]: <zip at 0x7f82a884f488>

In [42]: list( zip([1,3,2],['a','b','c']) )
Out[42]: [(1, 'a'), (3, 'b'), (2, 'c')]

In [43]: sorted( list( zip([1,3,2],['a','b','c']) ) )
Out[43]: [(1, 'a'), (2, 'c'), (3, 'b')] 
\end{pythoncode}

Comment dit-on braguette en anglais?

Alors que dire de:


\begin{pythoncode}
class Perm :

    def __init__(self, images = []) :
        self.images = images

    def __repr__(self) :
        return (' ').join( [str(x) for x in self.images] )

    def __neg__(self) :
        im = self.images
        n = len(im)
        return Perm( map(lambda couple : couple[1], sorted( zip(im, range(n)) ) ) )  
    def __add__(self, other) :
        """ fabrique la composée self o other """ 
        return Perm( ??????? )

    def permute(self,xs) :
        """ si xs = [xs[0], xs[1], xs[2],...], p.permute(xs) = [xs[p(0)], xs[p(1)], xs[p(2)],...] """
        return ??????
\end{pythoncode}

qui permet d'obtenir:

\begin{pythoncode}
In [47]: p = Perm([0,2,3,1])

In [48]: p
Out[48]: 0 2 3 1

In [49]: -p
Out[49]: 0 3 1 2
\end{pythoncode}






\item 

Une \textit{permutation circulaire  gauche} \og décale\fg{} les éléments
d'un nombre fixé  de \og rangs\fg{}. Par exemple,  voici une permutation
circulaire gauche:

$$
\begin{pmatrix}
  0&1&2&3&4\\
  3&4&0&1&2
\end{pmatrix}
$$

Décrire $\pi(k)$ dans le cas d'une permutation circulaire de bits de $i$
rangs vers la gauche.

On définit de même des permutations circulaires droite.

Combien y a-t-il de permutations circulaires dans ${S}_n$?

Écrire                                une                                méthode
\mintinline[fontsize=\small,fontfamily=txtt]{python}{circulaire(self, rangs)}
qui renvoie 
\mintinline[fontsize=\small,fontfamily=txtt]{python}{self} 
permutée de \mintinline[fontsize=\small,fontfamily=txtt]{python}{rangs} rangs
circulairement.

\begin{pythoncode}
def circulaire(self, rangs) :
        """ permutation circulaire de rangs rangs """
        im = self.images
        n = len(im)
        return Perm( ?????? )  
\end{pythoncode}




\end{enumerate}

\end{pyxercice}










\begin{pyxercice}[Mode ECB : la programmation]
Il reste à programmer tout ça...

On aura d'abord besoin de la fonction 
\mintinline[fontsize=\small,fontfamily=txtt]{python}{reduce} de  la bibliothèque
\mintinline[fontsize=\small,fontfamily=txtt]{python}{functools}.

Complétez alors le squelette suivant:

\begin{pythoncode}
def decoupe_en_blocs(n, bs) :
    """découpe une liste en liste de blocs de longueur n"""
    ????????????

def ecb(cle, bs) :
    """renvoie la liste des permutations des blocs contenus dans une liste"""
    ????

def string2bin(s, n) :
    """ transforme un caractère en sa représentation sur n bits sous forme de liste""" 
    ?????

def bin2string(bs) :
    """ transforme une liste de bits en l'entier décimal correspondant"""
    ????

def cats(xs) :
    """concatène une liste de listes ou de chaînes"""
    ????

def code_bloc_string(code_bloc, cle, n_bits, chaine) :
    """applique un chiffrement par bloc sur une chaîne en donnant le nom du
       chiffrement, sa clé et le nb de bits sur lequel les caractères sont codés """
    ?????
\end{pythoncode}


Par exemple:

\begin{pythoncode}
In [5]: bs = [1,0,0,1,0,0,1,1,1,1,0,1,1]

In [6]: decoupe_en_blocs(7, bs)
Out[8]: [[1, 0, 0, 1, 0, 0, 1], [1, 1, 1, 0, 1, 1, 0]]

In [9]: ecb(Perm([2,0,3,1,5,4,6]), bs)
Out[9]: [[0, 1, 1, 0, 0, 0, 1], [1, 1, 0, 1, 1, 1, 0]]

In [10]: string2bin('(', 7)
Out[12]: [0, 1, 0, 1, 0, 0, 0]

In [13]: bin2string([0, 1, 0, 1, 0, 0, 0])
Out[20]: 40

In [21]: cats(['a', 'u', ' ', 's', 'e', 'c', 'o', 'u', 'r', 's'])
Out[21]: 'au secours'

In [22]: cats([[0,1], [2,3]])
Out[22]: [0, 1, 2, 3]

In [23]: code_bloc_string(ecb, Perm([2,0,3,1,5,4,6]), 7, 'Help')
Out[23]: '0+:h'  
\end{pythoncode}
\end{pyxercice}

























%%
%%
%%

\section*{Corps}







\begin{exercice}[C'est fini]
  Soit $E=\bigl\{1,2,3,5,6,10,15,30\bigr\}$.

Pour tout couple $\langle a,b\rangle$ d'éléments de $E$, on note $a\wedge b$ le PGCD de $a$ et $b$ et $a\vee b$
le PPCM de $a$ et $b$. 

Démontrez que $(a\vee b)(a\wedge b) = ab$.
Quelle est la  structure de $\langle
E,\wedge,\vee\rangle $?  De $\langle
E,\vee,\wedge\rangle $?
\end{exercice}




\begin{exercice}[\textsc{Hamilton} et les isomorphismes]
  
Le  mathématicien irlandais  William Rowan  \textsc{Hamilton}  (1805-1865) publie en
1837    \textit{Theory   of    Conjugate    Functions,   or    Algebraic
  Couples}                                                    :
   (\href{http://www.maths.tcd.ie/pub/HistMath/People/Hamilton/PureTime/PureTime.pdf}{http://www.maths.tcd.ie/pub/HistMath/People/Hamilton/PureTime/PureTime.pdf}).


En voici un extrait:


\begin{quote}
  {\itshape\small

\begin{center}
On the Addition, Substraction, Multiplication, and Division, of
Number-Couples, as
combined with each other.
\end{center}

%\nobreak\bigskip
6.
Proceeding to operations upon number-couples, considered in
combination with each other, it is easy now to see the
reasonableness of the following definitions, and even their
necessity, if we would preserve in the simplest way, the analogy
of the theory of couples to the theory of singles:
$$\langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  = \langle b_1 + a_1, b_2 + a_2\rangle ;
   \eqno ( 52.)$$
$$\langle b_1, b_2\rangle  - \langle a_1, a_2\rangle  = \langle b_1 - a_1, b_2 - a_2\rangle ;
   \eqno (53.)$$
$$\langle b_1, b_2\rangle  \langle a_1, a_2\rangle 
    = \langle b_1, b_2\rangle  \cdot \langle a_1, a_2\rangle 
    = \langle b_1 a_1 - b_2 a_2, b_2 a_1 + b_1 a_2\rangle ;
   \eqno (54.)$$
$${\langle b_1, b_2\rangle  \over \langle a_1, a_2\rangle }
    = \left\langle 
         {b_1 a_1 + b_2 a_2 \over a_1^2 + a_2^2}, \,
         {b_2 a_1 - b_1 a_2 \over a_1^2 + a_2^2}
      \right\rangle .
   \eqno (55.)$$
Were these definitions even altogether arbitrary, they would at
least not contradict each other, nor the earlier principles of
Algebra, and it would be possible to draw legitimate conclusions,
by rigorous mathematical reasoning, from premises thus
arbitrarily assumed: but the persons who have read with attention
the foregoing remarks of this theory, and have compared them with
the Preliminary Essay, will see that these definitions are really
{\it not arbitrarily chosen}, and that though others might have
been assumed, no others would be equally proper.

With these definitions, addition and subtraction of
number-couples are mutually inverse operations, and so are
multiplication and division; and we have the relations,
$$\langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  = \langle a_1, a_2\rangle  + \langle b_1, b_2\rangle ,
   \eqno (56.)$$
$$\langle b_1, b_2\rangle  \cdot \langle a_1, a_2\rangle  = \langle a_1, a_2\rangle  \cdot \langle b_1, b_2\rangle ,
   \eqno (57.)$$
$$\langle b_1, b_2\rangle  ( \langle a_1', a_2'\rangle  + \langle a_1, a_2\rangle  )
   =  \langle b_1, b_2\rangle  \langle a_1', a_2'\rangle  + \langle b_1, b_2\rangle  \langle a_1, a_2\rangle :
   \eqno (58.)$$
we may, therefore, extend to number-couples all those results
respecting numbers, which have been deduced from principles
corresponding to these last relations.  For example,



$( \langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  ) \cdot
  ( \langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  )
   =  \langle b_1, b_2\rangle  \langle b_1, b_2\rangle 
    + 2 \langle b_1, b_2\rangle  \langle a_1, a_2\rangle \\
    + \langle a_1, a_2\rangle  \langle a_1, a_2\rangle ,
   \hfill (59.)$


in which


$$2 \langle b_1, b_2\rangle  \langle a_1, a_2\rangle 
   =  \langle 2, 0\rangle  \langle b_1, b_2\rangle  \langle a_1, a_2\rangle 
   =  \langle b_1, b_2\rangle  \langle a_1, a_2\rangle  + \langle b_1, b_2\rangle  \langle a_1, a_2\rangle ;
   \eqno (60.)$$
for, in general, we may {\it mix the signs of numbers with those
of number-couples}, if we consider every single number~$a$ as
equivalent to a pure primary number-couple,
$$a = \langle a, 0\rangle .
   \eqno (61.) $$
When the pure primary couple $\langle 1, 0\rangle $ is thus considered as
equivalent to the number~$1$, it may be called, for shortness,
the {\it primary unit\/}; and the pure secondary couple $\langle 0, 1\rangle $
may be called in like manner the {\it secondary unit}.

We may also agree to write, by analogy to notations already
explained,


\begin{eqnarray*}
  \langle 0, 0\rangle  + \langle a_1, a_2\rangle  &=& + \langle a_1, a_2\rangle ,\\
\langle 0, 0\rangle  - \langle a_1, a_2\rangle  &=& - \langle a_1, a_2\rangle ;
   \quad (62.)\\
\end{eqnarray*}


and then $+ \langle a_1, a_2\rangle $ will be another symbol for the
number-couple $\langle a_1, a_2\rangle $ itself, and $- \langle a_1, a_2\rangle $ will be a
symbol for the {\it opposite number-couple\/} $\langle - a_1, - a_2\rangle $.
The {\it reciprocal\/} of a number-couple $\langle a_1, a_2\rangle $ is this
other number-couple,
$${1 \over \langle a_1, a_2\rangle }
   =  {\langle 1, 0\rangle  \over \langle a_1, a_2\rangle }
   =  \left\langle 
         {a_1 \over a_1^2 + a_2^2},
         {- a_2 \over a_1^2 + a_2^2}
      \right\rangle 
   =  {\langle a_1, - a_2\rangle  \over a_1^2 + a_2^2}.
   \eqno (63.)$$
It need scarcely be mentioned that the insertion of the sign of
coincidence~$=$ between any two number-couples implies that those
two couples coincide, number with number, primary with primary,
and secondary with secondary; so that {\it an equation between
number-couples is equivalent to a couple of equations between
numbers}.

}
\end{quote}


Vous ferez  de ce texte  un commentaire composé puis  détaillerez l'isomorphisme
entre $\bbr^2$ et $\bbc$ évoqué en cours. 




\end{exercice}




\begin{pyxercice}[Rationnels - Relations d'équivalences]
Qu'est-ce qu'un  rationnel? \textit{Ratio}  est un mot  latin, qui  désignait un
 calcul  mais  qui   a  donné  en  français  le  mot   \textit{raison}.  Le  mot
 \textit{ratio} est passé en anglais pour désigner un indice en comptabilité: le
 rapport entre deux quantités de même nature.
 Ce mot a été importé de l'anglais de spécialité par les financiers.

 En mathématique, un \textit{nombre rationnel} est \og \textbf{construit}\fg{} à partir d'un couple d'entiers
 relatifs, le deuxième étant non nul.  
 Le premier est appelé \textit{numérateur}, le second \textit{dénominateur}.
 
 Oui  mais  comment  s'effectue  cette  \og construction\fg{}?  On  a  une  idée
 intuitive  de  la réponse:  on  veut  qu'un \textit{ratio}nnel  représente  une
 proportion. Par exemple, si  Daniel a 5 billes bleues parmi ses  8 billes et si
 Fabienne a 10 billes  bleues parmi ses 16 billes, les deux  enfants ont la même
 proportion  de billes  bleues.  On  voudrait alors  que  cette proportion  soit
 désignée par le même nombre rationnel.

On voudrait donc  mettre en \textit{relation} tous les  couples $\langle$ nombre
de billes bleues, nombre total de  billes $\rangle$ qui \og représentent\fg{} la
même proportion de billes bleues.

On va donc modéliser cela en considérant la relation:

$$                 \Big(\forall                  \langle                 a,b\rangle{}
\in\bbz\otimes(\bbz\setminus\left\{0\right\})\Big)\Big(\forall    \langle    c,d\rangle{}
\in\bbz\otimes(\bbz\setminus\left\{0\right\})\Big)\Big(        \langle        a,b\rangle
\,\mathcal{R}\,\langle c,d\rangle \lequiv ad=bc\Big) $$


Deux couples  en relation vont  donc représenter des  fractions \textit{égales}:
c'est une \textit{relation d'équivalence} car elle est:
\begin{itemize}
\item réflexive: $∀x.x\mathcal{R}x$
\item symétrique: $∀x.∀y.x\mathcal{R}y ⟹ y\mathcal{R}x$
\item transitive: $∀x.∀y.∀z.x\mathcal{R}y ∧ y\mathcal{R}z⟹ x\mathcal{R}z$
\end{itemize}

On va alors pouvoir définir cette égalité dans une classe Python.

Une proportion est alors une classe modulo cette relation d'équivalence.


 On désigne par $\bbq$ l'ensemble quotient de $\bbz\otimes (\bbz\setminus\{0\})$
 modulo $\RR$.

 Cette notation a été
 introduite par  le mathématicien  italien Guiseppe  \textsc{Peano} en  1895 car
 c'est l'initiale du mot italien \og \textit{quoziente}\fg{}.

 $$ \bbq = \ofr{\bbz\otimes (\bbz\setminus\{0\})}{\RR} =
 \bigl\{\big[\langle n, d\rangle\big]_\RR\ |\ \langle n, d\rangle \in \bbz\otimes
 (\bbz\setminus\{0\}) \bigr\}$$

Un nombre rationnel est donc une classe d'équivalence, c'est-à-dire un ensemble!!!

Pour  définir une  nouvelle  égalité sur  Python, il  faut  vérifier qu'on  peut
définir une relation d'équivalence.


\begin{pythoncode}
class Ratio():

    def __init__(self, num, den) :
        assert den != 0, "Rationnel non défini ! (dénominateur nul)"
        self.num = num
        self.den = den

    def __eq__(self, other) :
        return self.num * other.den == self.den * other.num  
\end{pythoncode}


On             peut            alors             utiliser            l'opérateur
\verb+==+   pour   comparer   des
rationnels:

\begin{pythoncode}
In [5]: r1 = Ratio(1,3)
In [6]: r2 = Ratio(4,12)
In [7]: r1 == r2
Out[7]: True
In [8]: r3 = Ratio(2,0)
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-8-73704c7d78e0> in <module>()
----> 1 r3 = Ratio(2,0)
~/PROG/PYTHON/IntroAlg/monoides.py in __init__(self, num, den)
AssertionError: Rationnel non défini ! (dénominateur nul)  
\end{pythoncode}


On peut rajouter  une petite méthode pour représenter les  rationnels de manière
sympathique:

\begin{pythoncode}
     def __repr__(self) :
        return str(self.num) + '/' + str(self.den) 
\end{pythoncode}

Par exemple:

\begin{pythoncode}
In [13]: Ratio(2,4)
Out[13]: 2/4  
\end{pythoncode}


Mais on peut faire mieux pour avoir le représentant irréductible: comment?

\begin{pythoncode}
In [17]: Ratio(3,6)
Out[17]: 1/2  
\end{pythoncode}




Définissez de même les opérations usuelles sur les corps:

\begin{pythoncode}
    def __add__(self, other) :

    def __neg__(self) :

    def __sub__(self, other) :

    def __mul__(self, other) :

    def __div__(self, other) :  
\end{pythoncode}


On            rajoutera            une            méthode            mystérieuse
\mintinline[fontsize=\small,fontfamily=txtt]{python}{__hash__(self)}         qui
permettra de  faire par  exemple des ensembles  de rationnels.  Vous comprendrez
pourquoi en seconde année dans le cours d'algo avancée.


\begin{pythoncode}
def __hash__(self) :
        return hash(self.num)^hash(self.den)
\end{pythoncode}




Imaginez ensuite une classe\texttt{ Complex} pour les nombres complexes.
  
\end{pyxercice}



\begin{pyxercice}[Calcul modulaire]

Créez une classe Modulo afin de calculer dans $\ofr{\bbz}{n\bbz}$. 

\begin{multicols}{2}
\begin{pythoncode}
In [140]: Modulo(6,3)
Out[140]: 3%6

In [141]: Modulo(6,3) + Modulo(6,26)
Out[141]: 5%6

In [142]: Modulo(6,3) * Modulo(6,26)
Out[142]: 0%6

In [143]: Modulo(6,3).est_inversible()
Out[143]: False

In [144]: Modulo(6,5).est_inversible()
Out[144]: True

In [145]: Modulo(6,13) == Modulo(6,25)
Out[145]: True  
\end{pythoncode}
\end{multicols}


  
\end{pyxercice}





\begin{pyxercice}
  Récupérez           sur             Madoc             le             fichier
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{plotting.py} 

Créez dans le même répertoire un fichier
\mintinline[fontsize=\small,fontfamily=txtt]{python}{complex.py}:

\begin{pythoncode}
from plotting import plot

S = {2+2j, 3+2j, 1.75+1j, 2+0.9j, 2.25+0.83j, 2.5+0.79j, 2.75+0.83j, 3+0.9j, 3.25+1j}  
\end{pythoncode}

Puis lancez \mintinline[fontsize=\small,fontfamily=txtt]{python}{plot(S)} 

Il s'agit ensuite de faire tourner S, de translater S, de réduire ou agrandir S,
de combiner les transformations sur une seule figure: comment?




%\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{smile}
\end{center}
%\end{figure}



\end{pyxercice}




\begin{pyxercice}[Corps]
Nous  allons avoir  besoin  de  plusieurs coprs  pour  nos  expériences sur  les
vecteurs.


%\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{frankenstein}
\end{center}
%\end{figure}


Vous allez créer  (en reprenant le travail déjà fait  auparanvant), une classe \verb+R+
des réels,  une classe  \verb+Cplx+ des complexes,  une classe  \verb+Ratio+ des
rationnels, une classe \verb+Mod+ des entiers modulo un entier qui auront toutes le
squelette suivant:

\begin{multicols}{2}
\begin{pythoncode}
class X:
    def __init__(self,val) :

    def __hash__(self) :
        return hash(val)

    def zero(self) :
        """le neutre de l'addition"""

    def un(self) :
        """le neutre de la multiplication"""

    def __eq__(self, other) :

    def __str__(self) :

    def __repr__(self) :

    def __add__(self, other) :

    def __mul__(self, other) :

    def __neg__(self) :

    def __sub__(self, other) :

    def __truediv__(self, other) :

    def inv(self) :

\end{pythoncode}
\end{multicols}


\end{pyxercice}



\chapterimage{robin}

\chapter{Algèbre linéaire}



%%%%%%%%%%%%%%%%%%

\section{Vecteurs}


\begin{exercice}[Sous-espace vectoriel engendré par une famille de vecteurs]
  Combien   y  a-t-il   de  vecteurs   dans  $\Vect(\langle   1,1\rangle,\langle
  0,1\rangle)$ considéré comme $\bbf_2$-espace vectoriel? comme $\bbr$-espace vectoriel?
\end{exercice}

\begin{exercice}[Famille génératrice]
On travaille dans le $\bbf_2$-espace vectoriel $\bbf^5_2$.
Quels  sont  tous  les  vecteurs  de  $\Vect(\langle  1,1,1,0,0  \rangle,\langle
0,1,1,1,0 \rangle, \langle 0,0,1,1,1 \rangle )$?

\setindent{\indentationcours}
\begin{definition}[Famille génératrice]
Soit $\VR$ un ensemble de  vecteurs. Soit $(v_0,v_1,v_2,...,v_n)$ une famille de
vecteurs   telle  que   $\VR=\Vect(v_0,v_1,v_2,...,v_n)$   alors   on  dit   que
$(v_0,v_1,v_2,...,v_n)$ est une \textbf{famille génératrice} de $\VR$.
\end{definition}

\setindent{0cm}

Comment traduire alors le résultat initial en terme de famille génératrice?



\end{exercice}


\begin{exercice}[Famille génératrice de $\bbr^3$]
Comment  démontrer  que $(\langle  3,0,0  \rangle,  \langle 0,0,1  \rangle,
\langle 0,2,0  \rangle )$ est une  famille génératrice de $\bbr^3$?  Pourquoi le
problème est différent du cas d'un $\bbf_2$-espace vectoriel?
\end{exercice}




\begin{exercice}[Les canons]
  Montrez que $\bbk^n$ a une structure de $\bbk-$espace vectoriel.

Comment  organiseriez-vous,   de  manière   très  informelle,  une   classe  \og
$\bbk-EV$ \fg{}?

Il sera utile, surtout pour des informaticiens, de garder cette image en tête.
\end{exercice}



\begin{exercice}
On travaille dans $\bbk^3$ considéré comme $\bbk$-espace vectoriel muni des lois canoniques.

Résolvez dans $\bbr^3$ puis dans $\bbf_2^3$ l'équation:

$$\langle  2,-3,4\rangle =  x\langle 1,1,1\rangle  + y\langle  1,1,0\rangle +  z
\langle 1,0,0\rangle $$ 
\end{exercice}


\begin{exercice}[RVB/CJMN]
  Comment  modéliseriez-vous  les  systèmes  RVB   et  CJMN  en  terme  d'espace
  vectoriel?

  Comment passer en niveau de gris ? En codage 24 bits ?
\end{exercice}


\begin{exercice}[Espaces vectoriels pour les nuls]

Avec les notations usuelles, que pensez-vous des égalités suivantes:

\begin{enumerate}
\item $0_+ \cdot \mathbf{u} =\mathbf{0}$
\item $λ\cdot \mathbf{0}=\mathbf{0}$
\item $(λ\cdot \mathbf{u} = \mathbf{0})\limp (λ=0 \lor \mathbf{u}=\mathbf{0})$
\end{enumerate}

  
\end{exercice}


\begin{exercice}
  Soit  $(E,+_E,\cdot)$  un  $(\bbk,+_\bbk,×_\bbk)$-espace  vectoriel. Est-ce  que  vous  pouvez
  imaginer un moyen \og économique\fg{} d'assurer qu'un sous-ensemble F de E ait
  une structure d'espace vectoriel avec les mêmes lois?
\end{exercice}


\begin{exercice}[R-espaces vectoriels?]
  Déterminez si les ensembles  suivants munis des opérations indiquées
  ont  une  structure de  $\bbr$-espace  vectoriel.  N'hésitez  pas à  voir  ces
  exercices comme des problèmes d'instances de classes.
  \begin{enumerate}
  \item   Soit  $V=\bigl\{\langle   a,b,c,0\rangle  \mid   \langle  a,
    b,c\rangle  \in \bbr^3\bigr\}$  muni de  l'addition canonique  des
    quadruplets et du produit canonique d'un quadruplet par un réel.
  \item Soit  $V=\bigl\{\langle   a,b,c,2\rangle  \mid   \langle  a,
    b,c\rangle  \in \bbr^3\bigr\}$  muni de  l'addition canonique  des
    quadruplets et du produit canonique d'un quadruplet par un réel.
  \item On munit $V=\bbr^\star_+$ de  l'addition définie par $a\oplus b=a\times
    b$ et  $\bbr$ opère  sur le groupe  $\langle V,\oplus\rangle$
    par  le   produit  externe  défini  par   $λ\otimes  \mathbf{x}  =
    \mathbf{x}^λ$.
  \item        $V=\bigl\{\langle       a,b,c\rangle\mid        \langle
    a,b,c\rangle\in\bbr^3 \land  a\cdot b\cdot  c =0\bigr\}$  avec les
    opérations canoniques.
\item $V$ est l'ensemble des fonctions dérivables sur $\bbr$.
\item $V$ est l'ensemble des suites arithmétiques réelles.
  \end{enumerate}
\end{exercice}


\begin{exercice}[K-espaces vectoriels?]
Les exemples suivants permettent-ils de définir des $\bbk$-espaces vectoriels?
  \begin{enumerate}
  \item $\bbk=\bbc$, l'ensemble des  nombres complexes, $V=\bbc$
    muni de l'addition habituelle des complexes, et le produit externe
    est défini par:
$$
 (\star)\ \colon \begin{array}{rll} \bbc\otimes \bbc& \to & \bbc\\
   \langle λ,\mathbf{z}\rangle& \mapsto & λ^2\cdot \mathbf{z}
 \end{array}
 $$

\item Soit $\bbk$ un corps quelconque et $V=\bbk^2$ muni de l'addition
  canonique des couples. On définit le produit externe ainsi:

$$
 (\star)\ \colon \begin{array}{rll} \bbk\otimes \bbk^2& \to & \bbk^2\\
   \big\langle λ,\langle x,y\rangle\big\rangle& \mapsto & \langle λ x,0\rangle
 \end{array}
 $$

\item $\bbk=\bbq$ et $V=\bbr$ munis des opérations canoniques.

\item L'ensemble des vecteurs de $\bbf_2^5$ qui ont un nombre pair de 1.

\item L'ensemble des vecteurs de $\bbf_2^5$ qui ont un nombre impair de 1.



  \end{enumerate}
\end{exercice}


\begin{exercice}
Soit $V$ un espace vectoriel muni de tout ce qu'il faut.

Soit  $\langle \mathbf{u_i}\rangle_{0  \leqslant i  \leqslant p}$  une
famille  de  vecteurs  de $V$.  Montrez  que  $\sev{\mathbf{u_0}\cdots
  \mathbf{u_p}}$ a une structure d'espace vectoriel.

Voilà pourquoi on appellera maintenant  $\sev{\mathbf{u_0}\cdots
  \mathbf{u_p}}$  le \textbf{sous-espace  vectoriel  engendré} par  la
famille $\langle \mathbf{u_i}\rangle_{0 \leqslant i \leqslant p}$.

On dit  que $\langle \mathbf{u_i}\rangle_{0 \leqslant  i \leqslant p}$
est une \textbf{famille génératrice} de  $\sev{\mathbf{u_0}\cdots
  \mathbf{u_p}}$.
\end{exercice}





  \begin{exercice}
Voici des messages de 7 bits considérés comme des vecteurs de $\bbf_2^7$:

$$e_1=1100000,\ e_2=0110000,\ e_3=0011000,\ e_4=0001100,\ e_5=0000110,\ e_6=0000011$$

Est-ce que  les vecteurs suivants  peuvent être des combinaisons  linéaires des
$e_i$:

$u=0010010$? $v=0100010$?

  \end{exercice}


  \begin{exercice}
    Trouvez un vecteur de $\bbf^4_2$ satisfaisant les conditions suivantes:
$1100\odot x=1,\ 1010\odot x =1, 1111\odot x = 1$ avec $\odot$ le produit scalaire.
  \end{exercice}





 \begin{exercice}
     On travaille dans l'ev $\mathbb{R}^{2}$ :
\begin{enumerate}
\item $u=\langle  6,-9\rangle  $\ et $v=\langle  -10,15\rangle  .$\ Donner des CL
de la famille $\langle u\rangle ,$\ de la famille $\langle u,v\rangle .$

Pensez  à un  pauvre compilateur:  comment décider  si des  espaces sont  égaux?
Comparer tous les éléments? Avoir une approche plus formelle? Comment?

Il pourrait être utile par exemple, comme pour les rationnels, d'avoir une forme
\textit{normalisée} des vecteurs pour mieux les comparer: des idées?

\item Que représente $\sev{\mathcal{F}} $\ avec $%
\mathcal{F}=\langle  u,v\rangle  $ ?

\item Démontrer que $w=\langle  2,-3\rangle  \in \sev{\mathcal{F}}  .$

\item $u$\ et $v$\ sont-ils colinéaires ?

%\item $\mathcal{F}$\ est-elle libre ou liée ?

\item Démontrer que $\sev{\FR}  =\sev{\langle  w\rangle}  .$

\item Démontrer que $\langle  1,2\rangle  \notin \sev{\mathcal{F}}.$

% \item $t=\langle  1,2\rangle  ,$\ et $\mathcal{F}^{\prime }=\langle  w,t\rangle  $%
% \ ; démontrer que ${\rm Vect}\langle  \mathcal{F}^{\prime }\rangle  =%
% \mathbb{R}^{2}.$
\end{enumerate}

   \end{exercice}



   \begin{exercice}
      On note $H=\left\{ \langle  x,y,z\rangle  \in \mathbb{R}^{3}\mid
x+2y+3z=0\right\} ,$\ démontrer que $H$\ est un sev de $\mathbb{R}^{3}$
en déterminant $u$\ et $v,$\ deux vecteurs de $\mathbb{R}^{3},$\ de
sorte que $H=\sev{\langle  u,v\rangle}$.
On note $w=(1,2,3)$. Est-ce que $w\in H$?
   \end{exercice}

  \begin{exercice}
    \begin{enumerate}
    \item Démontrer que $H=\left\{ \langle  x,y,z\rangle  \in \mathbb{R}^{3}\mid
        x-z=0\right\} $ est un sev de $\mathbb{R}^{3}$.
    \item Démontrer que $H=\left\{ \langle  x,y,z\rangle  \in \mathbb{R}^{3}\mid
        x=0\right\} $ est un sev de $\mathbb{R}^{3}$.
    \item   $H=\left\{   \langle   x,y,z\rangle    \in   \mathbb{R}^{3}\mid
          ax+by+cz=0\right\} $ o\`{u} $a$, $b$ et $c$ sont des réels
          fixés.  
          Démontrer que $H$ est un sev de $\mathbb{R}^{3}$.  
    \end{enumerate}
  \end{exercice}

% \begin{exercice}[ A bit of game]
  
% \end{exercice}

 \begin{exercice}
    On travaille dans $\mathbb{R}^{3}$ et on note $u=\langle  1,2,2\rangle 
    $ et $v=\langle -2,1,2\rangle $. 


Déterminer des réels $a$, $b$
    et                   $c$                  pour                   que
    $\sev{\langle   u,v\rangle} =\left\{  \langle   x,y,z\rangle   \in
    \mathbb{R}^{3}\mid ax+by+cz=0\right\}$. 
  \end{exercice}



\begin{exercice}[Des dessins de dés]\label{exo::des}
On voudrait dessiner ce dé:
\drawdie{8}


Pour cela, on dispose de 6 dés un peu spéciaux:

\drawdie{1}
\drawdie{2}
\drawdie{3}
\drawdie{4}
\drawdie{5}
\drawdie{6}


On peut les additionner selon la  règle suivante: on superpose les dés
et un  point apparaît  si, et seulement  si, un et  un seul  point est
présent par position.

En fait, le  jeu est constitué de  petites lumières. Quand on appuie  sur une de
ces lumières, cela change l'état (allumé  ou éteint) des lumières voisines. Quel
lien y a-t-il entre la situation réelle et la modélisation proposée?

Par exemple, 1\drawdie{1} + 1\drawdie{2}=\fancydie{0}{0}{1}{1}{0}{0}

Quel  est le  rapport avec  notre cours?  Dessinez le  dé demandé.  Et
celui-ci \fancydie{0}{1}{0}{0}{1}{0}? Et celui-là \fancydie{1}{0}{0}{0}{0}{0}?

Pour aller plus loin, aller jouer au \textit{Lights Out} : \href{http://www.jaapsch.net/puzzles/lights.htm}{http://www.jaapsch.net/puzzles/lights.htm}


Pourra-t-on  résoudre  toutes  les  énigmes? Est-ce  qu'il  est  vraiment  utile
d'appuyer sur certaines touches?

\end{exercice}

%
%%%%%%%%%%%% PYXERCICES
%



  \begin{pyxercice}[Recherches d'amphi]
    Finissez de  répondre aux problèmes  posés en amphi...En  particulier, créez
    les classes de vecteurs (à l'aide de listes puis à l'aide de dictionnaires).
  \end{pyxercice}


  \begin{pyxercice}[Dés]
    Comment jouer aux dés de la \vref{exo::des} avec Python et des vecteurs?
  \end{pyxercice}





\begin{pyxercice}[Famille génératrice canonique]
 Travaillons dans un espace vectoriel de type $\bbk^n$, par exemple $\bbk^3$.

Prenons n'importe quel  vecteur de $\bbk^3$ et notons-le  $\langle x,y,z \rangle
$.

Il est assez évident d'écrire que:

$$\langle x,y,z \rangle = x \langle 1,0,0 \rangle + y \langle 0,1,0 \rangle + z \langle 0,0,1 \rangle 
$$

On dit  que $\langle 1,0,0 \rangle$,  $\langle 0,1,0 \rangle$ et  $\langle 0,0,1
\rangle$ sont les générateurs canoniques de $\bbr^3$.


Écrivez                   alors                   une                   fonction
\mintinline[fontsize=\small,fontfamily=txtt]{python}{canonique(dim, un, zero)} 
qui, étant donné le nombre de composantes des vecteurs, l'unité et le zéro du corps, retourne la liste des
générateurs canoniques  en utilisant la classe  de vecteurs définis à  partir de
séquences.

\begin{pythoncode}
In [94]: canonique1(5, Mod(1,2))
Out[94]: 
[[1%2, 0%2, 0%2, 0%2, 0%2],
 [0%2, 1%2, 0%2, 0%2, 0%2],
 [0%2, 0%2, 1%2, 0%2, 0%2],
 [0%2, 0%2, 0%2, 1%2, 0%2],
 [0%2, 0%2, 0%2, 0%2, 1%2]]
\end{pythoncode}

Faites  de  même  avec  les  vecteurs   définis    à  l'aide  de
dictionnaires:

\begin{pythoncode}
In [97]:  canonique2({'pou', 'chou', 'caillou', 'genou', 'hibou'}, Ratio(1,1))
Out[97]: 
[Vecteur{'hibou': 1, 'genou': 0, 'pou': 0, 'chou': 0, 'caillou': 0},
 Vecteur{'hibou': 0, 'genou': 1, 'pou': 0, 'chou': 0, 'caillou': 0},
 Vecteur{'hibou': 0, 'genou': 0, 'pou': 1, 'chou': 0, 'caillou': 0},
 Vecteur{'hibou': 0, 'genou': 0, 'pou': 0, 'chou': 1, 'caillou': 0},
 Vecteur{'hibou': 0, 'genou': 0, 'pou': 0, 'chou': 0, 'caillou': 1}]
\end{pythoncode}

\end{pyxercice}


\begin{pyxercice}[Vecteurs fonctions]

Voici une troisième modélisation des  vecteurs: maintenant que vous êtes chauds,
vous pouvez compléter cette classe sans autre commentaire...

\begin{pythoncode}
class V :
    def __init__(self, dim, fct ) :
        self.F = fct
        self.D = dim
        self.T = tuple(fct(i) for i in range(dim))

    def __hash__(self) :
        return hash(self.T)

    def __getitem__(self, i) :
        return ??????

    def __str__(self) :
        return str(self.T)

    def __repr__(self) :
        return ??????

    def __len__(self) :
        return ???????

    def __add__(self, other) :
        assert ??????????
        return ??????????

    def __mul__(self, k) : 
        return ?????????

    def dot(self, other) :
        assert ????????
        return ????????

    def __eq__(self, other):
        return ????????
\end{pythoncode}





  
\end{pyxercice}


\begin{pyxercice}[Sommes]
Créez                                une                                fonction
\mintinline[fontsize=\small,fontfamily=txtt]{python}{select(veclist, k)} 
qui renvoi la  liste des vecteurs de la liste  \verb+veclist+ dont la composante
\verb+k+ est nulle.

Par exemple:

\begin{pythoncode}
In [99]: select(vs, 'chou')
Out[99]: 
[Vecteur{'hibou': 1%2, 'genou': 0%2, 'pou': 0%2, 'chou': 0%2, 'caillou': 0%2},
 Vecteur{'hibou': 0%2, 'genou': 1%2, 'pou': 0%2, 'chou': 0%2, 'caillou': 0%2},
 Vecteur{'hibou': 0%2, 'genou': 0%2, 'pou': 1%2, 'chou': 0%2, 'caillou': 0%2},
 Vecteur{'hibou': 0%2, 'genou': 0%2, 'pou': 0%2, 'chou': 0%2, 'caillou': 1%2}]
\end{pythoncode}


Créez ensuite une fonction qui renvoie la somme d'une liste de vecteurs:

\begin{pythoncode}
In [100]: somme(vs)
Out[100]: Vecteur{'hibou': 1%2, 'genou': 1%2, 'pou': 1%2, 'chou': 1%2, 'caillou': 1%2}
\end{pythoncode}


Et enfin la fonction \mintinline[fontsize=\small,fontfamily=txtt]{python}{som_select(veclist, k)} 
qui effectue la somme des vecteurs de \verb+veclist+ dont la composante $k$ est nulle.

\begin{pythoncode}
In [101]: som_select(vs, 'chou')
Out[101]: Vecteur{'hibou': 1%2, 'genou': 1%2, 'pou': 1%2, 'chou': 0%2, 'caillou': 1%2}
\end{pythoncode}



\end{pyxercice}


\begin{pyxercice}[Combinaisons de $\bbf_2$-vecteurs]
Construisez                             une                             fonction
\mintinline[fontsize=\small,fontfamily=txtt]{python}{F2_vect(vectlist)} qui
renvoie  la  liste  de  toutes   les  combinaisons  linéaires  des  vecteurs  de
\verb+vectlist+ sur $\bbf_2$.

\begin{pythoncode}
In [109]: vs = canonique2({'pou', 'chou', 'caillou'},Mod(1,2))

In [110]: F2_vect(vs)
Out[110]: 
[Vecteur{'pou': 0%2, 'chou': 0%2, 'caillou': 0%2},
 Vecteur{'pou': 1%2, 'chou': 0%2, 'caillou': 0%2},
 Vecteur{'pou': 0%2, 'chou': 1%2, 'caillou': 0%2},
 Vecteur{'pou': 1%2, 'chou': 1%2, 'caillou': 0%2},
 Vecteur{'pou': 0%2, 'chou': 0%2, 'caillou': 1%2},
 Vecteur{'pou': 1%2, 'chou': 0%2, 'caillou': 1%2},
 Vecteur{'pou': 0%2, 'chou': 1%2, 'caillou': 1%2},
 Vecteur{'pou': 1%2, 'chou': 1%2, 'caillou': 1%2}]
\end{pythoncode}


\end{pyxercice}








  \begin{pyxercice}[Politique américaine]



%\begin{figure}
\begin{center}
  \includegraphics[height=8cm]{smith}
\end{center}
%\end{figure}



    Le  Sénat américain  est composé  de  deux sénateurs  par  état (il  y a  50
    états...). Vous allez  récupérer sur Madoc les statistiques sur  46 votes du
    109\eme  congrès (2006).  Un 1  signifie  un \og  Yea\fg{}, un  $-1$ un  \og
    Nay\fg{}   et  un   0  une   abstention.  Il   manque  les   votes  de   Jon
    \textsc{Corzine}, ssénateur du New-Jersey qui a été victime d'un accident de
    voiture cette année-là (cela fait une exception à gérer :-) ).

    On                  utilisera                 les                  fonctions
    \mintinline[fontsize=\small,fontfamily=txtt]{python}{open, read, split} pour
    récupérer les données.

    \begin{enumerate}
    \item Créez un dictionnaire \texttt{vs} de type \mintinline{python}{{Nom : liste des votes}} et
      un autre, \texttt{os}, de type \mintinline{python}{Nom : [Parti, État]}.

      Par exemple:

\begin{pythoncode}
In [18]: os['Obama']
Out[18]: ['D', 'IL']

In [20]: vs['Obama']
Out[20]: [1, -1, 1, 1, 1, -1, -1,...]
\end{pythoncode}

On              pourra             utiliser              la             fonction
\mintinline[fontsize=\small,fontfamily=txtt]{python}{int} et des définitions par compréhension.


\item Comment utiliser le produit scalaire pour mesurer l'accord ou le désaccord
  entre deux sénateurs?

\item                   Écrivez                   une                   fonction
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{compare(sen1, sen2)} 
qui  mesure le  degré  d'accord  de deux  sénateurs. Par exemple:

\begin{pythoncode}
In [21]: compare('Obama', 'McCain')
Out[21]: 16
\end{pythoncode}

\item                   Écrivez                   une                   fonction
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{senat_parti(parti)}  qui
  renvoie l'ensemble  des noms des sénateurs  d'un parti donné. Créez  aussi une
  fonction qui  renvoie le  nom des  sénateurs par  état, le  nom des  états par
  parti.

\item Écrivez une fonction \mintinline[fontsize=\small,fontfamily=txtt]{python}{compare_sen_etat(etat)} 
qui mesure la cohérence des votes des deux sénateurs d'un état donné.

\begin{pythoncode}
In [23]: compare_etat('WA')
Out[23]: (39, 'WA', ('Cantwell', 'Murray'))  
\end{pythoncode}

Classez les états dans l'ordre croissant des cohérences.


\item                    Créez                   une                    fonction
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{plus_eloigne(sen, ens)} 
qui renvoie le nom et la mesure de l'écart du sénateur d'un ensemble donné le plus en désaccord avec
un sénateur donné.

\begin{pythoncode}
In [33]: plus_eloigne('Obama',senat_parti('D'))
Out[33]: (22, 'Nelson2')

In [34]: plus_eloigne('Obama',senat_parti('R'))
Out[34]: (7, 'Sununu')
\end{pythoncode}

Faites de même avec le plus en accord.


\item  Quel est  le parti  le plus  \og cohérent\fg{}?  Comment le  déterminer à
  l'aide d'une fonction calculant une moyenne de cohérence.

Par  souci d'efficacité,  on  pourra se  souvenir que  le  produit scalaire  est
distributif sur l'addition des vecteurs.

\item Écrivez une fonction \mintinline[fontsize=\small,fontfamily=txtt]{python}{moins_d_accord(ens)}
qui renvoie le couple de sénateurs les moins d'accord d'un ensemble donné:

\begin{pythoncode}
In [50]: moins_d_accord(senateurs)
Out[50]: (('Feingold', 'Inhofe'), -3)
\end{pythoncode}

Combien de  calculs et de  comparaisons sont effectués? Pensez-vous  pouvoir être
plus efficace?



\item Qui est le sénateur le plus Républicain? L'État le plus Démocrate? Classez
  les sénateurs/États selon ces critères.


\item                    Ouvrez                    le                    fichier
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{ONU_vote.txt} et
étudiez-le d'une manière similaire à ce qui vient d'être fait.


    \end{enumerate}




  \end{pyxercice}


\vfill

\eject

\section{La matrice}



%\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{matrix}
\end{center}
%\end{figure}


\subsection{Un peu d'histoire}



\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{sylvester}
\caption{J.\bsc{Sylvester (1814-1897)}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.8cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}

Vers 160 avant le petit Jésus, parut en Chine le
 Fang  Tcheng %\begin{CJK}{UTF8}{song}  方程 \end{CJK}  ^J (\textit{fang tcheng})
 ou, si vous préférez, \og la disposition rectangulaire\fg{}
 qui désigne en mandarin actuel \og équation mathématique\fg{}. C'est le
 huitième des \textit{Neuf chapitres  sur l'art mathématique}. Dès cette
 époque,  les   chinois  regroupaient  les   coefficients  des  systèmes
 d'équations  linéaires dans  un tableau  rectangulaire  et transformait
 celui-ci pas à  pas pour le résoudre. Cette  méthode sera reprise vingt
 siècles  plus  tard par  les  Allemands  Carl Friedrich  \textsc{Gauss}
 (1777 - 1855) et
 Wilhelm \textsc{Jordan} (1842 - 1899)(à ne pas confondre avec le mathématicien
 français Camille \textsc{Jordan}) et  c'est elle que nous programmerons
 en Python.


Le terme \og matrice\fg{} pour  désigner ces tableaux a été introduit en
1850 par James \textsc{Sylvester} en 1850. Son ami Arthur \textsc{Cayley} (1821
- 1855) introduisit  le produit de matrices et  la notion d'inverse cinq
        années plus tard. Le terme  \og matrice\fg{} est dérivé du latin
        \textit{mater} qui signifie \og mère\fg{}...

\setindent{0cm}


\subsection{Qu'est-ce que c'est?}

\subsubsection{Vecteur}

Nous  appellerons \textit{vecteur}  une liste  d'éléments  d'un ensemble
$\bba$. Cet  ensemble  $\bba$  est   muni  de  deux  opérations,  $\boxplus$  et
$\boxdot$, qui lui confèrent une structure d'\textbf{anneau} (le plus souvent commutatif):

\begin{itemize}
\item $(\bba,\boxplus)$ a une structure de groupe commutatif;
\item $(\bba,\boxdot)$ a une structure de monoïde;
\item $\boxdot$ est distributive sur $\boxplus$.
\end{itemize}

On désigne souvent  par $0_{\bba}$ l'élément neutre de  $\boxplus$ et par
$1_{\bba}$ l'élément neutre de $\boxdot$.

$(\bba,\boxdot)$ n'étant pas forcément  un groupe, tout le monde n'admet
pas forcément un inverse par $\boxdot$. 

\setindent{\indentationcours}
\begin{recherche}
 Quels sont les éléments inversibles de $(\bbz,\cdot)$?
\end{recherche}
\setindent{0cm}

On notera $\bba^p$ l'ensemble des vecteurs à coefficients dans $\bba$ de
\textit{taille} $p$.

Notons  $u=[a_1,a_2,...,a_p]$ et  $v=[b_1,b_2,...,b_p]$  de vecteurs  de
même taille. On peut alors en faire la \textit{somme}:


$$u\boxplus v=[a_1\boxplus b_1,a_2\boxplus b_2,...,a_n\boxplus b_n]$$

On peut multiplier un  vecteur par un \textit{scalaire}, c'est-à-dire un
élément de $\bba$:

$$k u =[k\boxdot a_1,k \boxdot a_2,...,k\boxdot a_p]$$

On notera en particulier $-u = (-1_{\bba})u$.

On peut multiplier deux vecteurs composante par composante:

$$u\boxdot v = [a_1\boxdot b_1,a_2 \boxdot b_2,...,a_p\boxdot b_p]$$




\subsubsection{Matrice}

Une  matrice à  $n$ lignes  et $p$  colonnes est  un tableau  d'éléments
appartenant à un ensemble $\bba$.
On note alors $\bba^{n\times p}$ l'ensemble des matrices de $n$
lignes et $p$ colonnes à coefficients dans $\bba$. 


$$
\bordermatrix{
  &        &        &        &  j     &        &        \cr
  & a_{1,1} & a_{1,2} & \cdots & a_{1,j} & \cdots & a_{1,p} \cr
  & \vdots & \vdots &        & \vdots &        &  \vdots \cr
i & a_{i,1} & a_{i,2} & \cdots & a_{i,j} & \cdots & a_{i,p} \cr
  & \vdots & \vdots &        & \vdots &        &  \vdots \cr
  & a_{n,1} & a_{n,2} & \cdots & a_{n,j} & \cdots & a_{n,p} \cr
}
$$


On  note  souvent $a_{ij}$  le  coefficients  $a_{i,j}$  et $M_{ij}$  le
coefficient de M situé sur la ligne $i$ et la colonne $j$.

En fait, une matrice
est un vecteur dont les  coefficients sont eux-mêmes des vecteurs ce qui
facilitera notre tâche en programmation.

\subsection{Matrices particulières}
\begin{itemize}
\item On peut définir des \textbf{ matrices par blocs}:

\begin{center}
\begin{tikzpicture}[>=latex]

\tikzset{node style ge/.style={minimum size=0.7cm}}

% les noms
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = (,%
             right delimiter = )] at (0,0)
{%
 a_{11} & a_{12}  & a_{13}  \\ 
  a_{21} &a_{22}& a_{23} \\ 
  a_{31}& a_{32}  & a_{33}  \\ 
}; 

% les blocs 
\draw[orange,rounded corners=0.2mm] (A-2-2.north west)
rectangle (A-3-3.south east);

\draw[blue,rounded corners=0.2mm] (A-1-1.north west)
rectangle (A-1-1.south east);


 \end{tikzpicture} 
\end{center}

pourra s'écrire:

\newcommand{\temp}[1]{\multicolumn{1}{|c}{#1}}

$$
\left(
\begin{array}{cc}
A &\temp{B} \\ \hline
C &\temp{D}
\end{array}\right)
$$

avec $A\in\bba^{1×1}$, $B\in\bba^{1×2}$, $C\in\bba^{2×1}$ et  $D\in\bba^{2×2}$

\item  Les \textbf{matrices  diagonales}: $(a_{ij}=0)$  pour $i\neq  j$. On  les
  notera:

$$
A= {\rm diag} \left[a_{11},a_{22},...,a_{mm}\right] 
$$

Avec $A\in\bba^{n × p}$ et $m=\min(n,p)$.


\item Les \textbf{matrices tridiagonales} telles que $a_{ij}=0$ pour $|i-j|>1$.

\item Les \textbf{matrices triangulaires supérieures} telles que $a_{ij}=0$ pour
  $i>j$.

\item Les \textbf{matrices triangulaires inférieures} telles que $a_{ij}=0$ pour
  $i<j$.

\item Les \textbf{matrices de Hessenberg supérieures} telles que $a_{ij}=0$ pour
  $i>j+1$.

\item Les \textbf{matrices de Hessenberg inférieures} telles que $a_{ij}=0$ pour
  $j>i+1$.

\item Une \textbf{matrice colonne} est une matrice de $\bba^{n ×1}$.

\item Une \textbf{matrice ligne} est une matrice de $\bba^{1 × n}$.


\item Les \textbf{matrices Attila} sont les matrices remplies de 1.

\item Les \textbf{matrices nulles} sont les matrices remplies de 0.

\item Algorithmiquement parlant, il peut être  intéressant de traiter à part les
  matrices  contenant proportionnellement  beaucoup  de 0:  on  les appelle  les
  \textbf{matrices creuses}.

\end{itemize}


Donnez des exemples de matrices de chacun de ces types.

\subsection{Opérations sur les matrices}

\subsubsection{Égalité}

Deux  matrices sont  égales si,  et seulement  si, elles  ont  les mêmes
dimensions et des coefficients égaux.


\subsubsection{Opération terme à terme}

Notons $(S_{ij})_{\substack{1  \leqslant i  \leqslant n\\ 1  \leqslant j
\leqslant p}}$ la somme terme à terme des deux matrices $(A_{ij})_{\substack{1 \leqslant i \leqslant n\\ 1 \leqslant j
\leqslant p}}$ et $(B_{ij})_{\substack{1  \leqslant i  \leqslant n\\ 1  \leqslant j
\leqslant p}}$ alors chaque coefficient de S est obtenu par: 
$$S_{ij} = A_{ij}\boxplus N_{ij}$$

On peut  définir de la  même manière un  produit terme à terme  qu'il ne
faudra pas confondre avec le produit de matrices ou le produit par un scalaire...

\subsubsection{Multiplication par un scalaire}

Soit $k\in \bba$ et $M\in  \bba^{n\times p}$ alors la matrice $P=kM$ est
définie par:

$$P_{ij} = k\boxdot M_{ij}$$

\subsubsection{Produit de matrices}


Un petit rappel...

Notons $(p_{ij})_{\substack{1 \leqslant i \leqslant n\\ 1 \leqslant j \leqslant p}}$ 
le produit des deux matrices $(a_{ij})_{\substack{1 \leqslant i \leqslant n\\ 1 \leqslant j \leqslant m}}$ 
et $(b_{ij})_{\substack{1 \leqslant i \leqslant m\\ 1 \leqslant j \leqslant p}}$ 

alors $$p_{ij}=\displaystyle\boxsum_{k=1}^{m}a_{ik}\boxdot b_{kj}$$

\renewcommand\myunit{0.9cm}

% \begin{center}
% \begin{tikzpicture}[>=latex]
% % unit

% % the styles
% \tikzset{node style sp/.style={draw,circle,minimum size=\myunit}}  
% \tikzset{node style ge/.style={circle,minimum size=\myunit}}
% \tikzset{arrow style mul/.style={draw,sloped,midway,fill=white}}
% \tikzset{arrow style plus/.style={midway,sloped,fill=white}}
% % defintion of matrices
% \matrix (A) [matrix of math nodes,%
%              nodes = {node style ge},%
%              left delimiter  = (,%
%              right delimiter = )] at (0,0)
% {%
%   a_{11} & a_{12}  & a_{13}  \\ 
%   \node[node style sp] {a_{21}};& \node[node style sp] {a_{22}};& \node[node style sp] {a_{23}}; \\ 
%   a_{31}& a_{32} & a_{33} \\ 
%    a_{41}& a_{42}  & a_{43}  \\ 
% }; 
% \node [draw,below] at (A.south) { $A$ : \textcolor{red}{$4$ lignes} $3$ colonnes};
% \matrix (B) [matrix of math nodes,%
%              nodes = {node style ge},%
%              left delimiter  = (,%
%              right delimiter =)] at (5*\myunit,5*\myunit)
% {% 
%   b_{11} & \node[node style sp] {b_{12}};& b_{13} & b_{14} & b_{15}\\ 
%   b_{21} & \node[node style sp] {b_{22}}; & b_{23}& b_{24} & b_{25} \\ 
%   b_{31} & \node[node style sp] {b_{32}}; & b_{33} & b_{34} & b_{35} \\ 
% };
% \node [draw,above] at (B.north) { $B$ : $3$ lignes \textcolor{red}{$5$ colonnes}}; 
% % matrice résultat
% \matrix (C) [matrix of math nodes,%
%              nodes = {node style ge},%
%              left delimiter  = (,%
%              right delimiter = )] at (5*\myunit,0)
% {% 
%   p_{11} & p_{12} & p_{13} & p_{14} & p_{15}\\ 
%   p_{21}&  \node[node style sp,red] {p_{22}};& p_{23} & p_{24} & p_{25}\\ 
%   p_{31}& p_{32} & p_{33} & p_{34} & p_{35}\\ 
%   p_{41}&  p_{42} &  p_{43} & p_{44} & p_{45}\\
% }; 
% \node [draw,below] at (C.south) {$ P=A\times B$ : \textcolor{red}{$4$ lignes}  \textcolor{red}{$5$ colonnes}};
% % arrows
% \draw[blue] (A-2-1.north) -- (C-2-2.north);
% \draw[blue] (A-2-1.south) -- (C-2-2.south);
% \draw[blue] (B-1-2.west)  -- (C-2-2.west);
% \draw[blue] (B-1-2.east)  -- (C-2-2.east);
%  \draw[<->,red](A-2-1) to[in=180,out=90] (B-1-2);%
%        node[arrow style mul] (x) {$a_{21}\times b_{12}$};
%  \draw[<->,red](A-2-2) to[in=180,out=90](B-2-2);%
%        node[arrow style mul] (y) {$a_{22}\times b_{22}$};
%  \draw[<->,red](A-2-3) to[in=180,out=90](B-3-2);%
%        node[arrow style mul] (z) {$a_{23}\times b_{32}$};
%  \draw[red,->] (x) to node[arrow style plus] {${\Large +}$} (y)%
%                    to node[arrow style plus] {${\Large +}$} (z);
%                    to (C-3-3.north west);
%  \draw[->,red,decorate,decoration=zigzag] (z) -- (C-2-2.north west);
% \end{tikzpicture} 
% \end{center}
\tikzset{
    node style sp/.style={draw,circle,minimum size=\myunit},
    node style ge/.style={circle,minimum size=\myunit},
    arrow style mul/.style={draw,sloped,midway,fill=white},
    arrow style plus/.style={midway,sloped,fill=white},
}

\begin{center}
\begin{tikzpicture}[>=latex]
% les matrices
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = (,%
             right delimiter = )] at (0,0)
{%
  a_{11} & a_{12} & \ldots & a_{1p}  \\
  \node (A-2-1) [node style sp] {a_{21}};%
         & \node (A-2-2) [node style sp] {a_{22}};%
                  & \ldots%
                           & \node (A-2-4)[node style sp] {a_{2p}}; \\
  \vdots & \vdots & \ddots & \vdots  \\
  a_{n1} & a_{n2} & \ldots & a_{np}  \\
};


\matrix (B) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = (,%
             right delimiter =)] at (6*\myunit,6*\myunit)
{%
  b_{11} & \node (B-1-2) [node style sp] {b_{12}};%
                  & \ldots & b_{1q}  \\
  b_{21} & \node (B-2-2) [node style sp] {b_{22}};%
                  & \ldots & b_{2q}  \\
  \vdots & \vdots & \ddots & \vdots  \\
  b_{p1} & \node (B-4-2) [node style sp] {b_{p2}};%
                  & \ldots & b_{pq}  \\
};

% matrice rÃƒÂ©sultat
\matrix (C) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = (,%
             right delimiter = )] at (6*\myunit,0)
{%
  c_{11} & c_{12} & \ldots & c_{1q} \\
  c_{21} & \node (C-2-2) [node style sp,red] {c_{22}};%
                  & \ldots & c_{2q} \\
  \vdots & \vdots & \ddots & \vdots \\
  c_{n1} & c_{n2} & \ldots & c_{nq} \\
};
% les fleches
\draw[blue] (A-2-1.north) -- (C-2-2.north);
\draw[blue] (A-2-1.south) -- (C-2-2.south);
\draw[blue] (B-1-2.west)  -- (C-2-2.west);
\draw[blue] (B-1-2.east)  -- (C-2-2.east);
\draw[<->,red](A-2-1) to[in=180,out=90]
	node[arrow style mul] (x) {$a_{21}\times b_{12}$} (B-1-2);
\draw[<->,red](A-2-2) to[in=180,out=90]
	node[arrow style mul] (y) {$a_{22}\times b_{22}$} (B-2-2);
\draw[<->,red](A-2-4) to[in=180,out=90]
	node[arrow style mul] (z) {$a_{2p}\times b_{p2}$} (B-4-2);
\draw[red,->] (x) to node[arrow style plus] {$+$} (y)%
                  to node[arrow style plus] {$+\raisebox{.5ex}{\ldots}+$} (z)%
                  to (C-2-2.north west);


\node [draw,below=10pt] at (A.south) 
    { $A$ : \textcolor{red}{$n$ lignes} $p$ colonnes};
\node [draw,above=10pt] at (B.north) 
    { $B$ : $p$ lignes \textcolor{red}{$q$ colonnes}};
\node [draw,below=10pt] at (C.south) 
    {$ C=A\times B$ : \textcolor{red}{$n$ lignes}  \textcolor{red}{$q$ colonnes}};

\end{tikzpicture}
\end{center}
Nous  mettrons au  point des  fonctions nous  permettant de  calculer le
produit de deux matrices.



\setindent{\indentationcours}

\begin{recherche}
  Montrez que $(\bba^{n\times n},+,\times)$ est un anneau. Est-il commutatif? 

On notera $\bbi_n$ l'élément neutre de $(\bba^{n\times n},\times)$: quelle est sa tête?
\end{recherche}

\begin{recherche}
Est-ce qu'on ne pourrait pas parler de produit matriciel en utilisant le produit scalaire?...
\end{recherche}
\setindent{0cm}


\subsubsection{Transposée d'une matrice}


Soit $M\in \bba^{n\times p}$. Sa transposée est la matrice $T$ de $\bba^{p\times n}$ définie par 

$$T_{ij}=A_{ji}$$

On note le plus souvent $T= \tr A$.




En pratique, on échange lignes et colonnes.
\setindent{\indentationcours}
\begin{recherche}
  Démontrez que $\tr (A\times B) = \tr B \times \tr A$.
\end{recherche}


\begin{definition}
  Une matrice telle que $\tr A = A$ est dite \textbf{symétrique}.

Une matrice telles que $\tr A = -A$ est dite \textbf{antisymétrique}
\end{definition}
\setindent{0cm}
\subsection{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}$.

\setindent{\indentationcours}
\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}
\setindent{0cm}



\begin{exercice}
  L'ensemble des matrices à coefficients dans un corps $\bbk$ de la forme:

$$
\begin{pmatrix}
  a & a+b\\
  a+b & b
\end{pmatrix}
$$

muni de  l'addition matricielle ainsi que  de la multiplication par  un scalaire
est-il un espace vectoriel?


Même question avec les matrices de la forme $\begin{pmatrix}
  a & 0_\bbk\\
  1_\bbk & b
\end{pmatrix}$ et celles de la forme  $\begin{pmatrix}
   0_\bbk & a\\
   b & 0_\bbk
\end{pmatrix}$
\end{exercice}


















\begin{exercice}
On considère les matrices suivantes à coefficients réels : 
\begin{equation*}
A=\left( 
\begin{array}{rrr}
1 & 2 & 0 \\ 
2 & -1 & 2 \\ 
0 & 1 & 3%
\end{array}%
\right) ,B=\left( 
\begin{array}{rr}
2 & 0 \\ 
1 & 5 \\ 
-1 & -3%
\end{array}%
\right) ,C=\left( 
\begin{array}{r}
4 \\ 
5 \\ 
6%
\end{array}%
\right)
\end{equation*}%
\begin{equation*}
D=\left( 
\begin{array}{rrr}
1 & 2 & 3%
\end{array}%
\right) ,E=\left( 
\begin{array}{rrrr}
1 & 2 & 4 & -3 \\ 
1 & -2 & 0 & 5 \\ 
0 & 3 & 1 & 6%
\end{array}%
\right) ,F=\left( 
\begin{array}{rr}
7 & 0 \\ 
5 & -6 \\ 
-3 & 0 \\ 
-1 & 1%
\end{array}%
\right) ,G=\left( 
\begin{array}{rrr}
1 & 2 & -1 \\ 
-1 & 0 & 1 \\ 
1 & -1 & 1%
\end{array}%
\right)
\end{equation*}%
\vspace{0.5cm}
\end{exercice}

\begin{enumerate}
\item Calculer : $A-2G,$\ $3A+2G,$\ $^{t}A,$\ $^{t}G.$

\item Calculer $B\times A,A\times B,E\times F,D\times C,C\times
D,A^{2},A\times G,G\times A.$
\end{enumerate}




\begin{exercice}
  Soit $A=
  \begin{pmatrix}
    1&0&0\\
    0&0&1\\
    1&1&0\\
  \end{pmatrix}
$ et $B=
\begin{pmatrix}
  0&1&1\\
  1&0&0\\
  0&1&0\\
\end{pmatrix}
$ deux matrices booléennes. Calculez $A\times B$, $B\times A$, $A^2$.
\end{exercice}



\begin{exercice}[Puissances de matrices]

\begin{enumerate}

\item
 Soit $\ds A=\frac{1}{3}\bmat
0&-2&-2\\
2&0&-1\\
2&1&0 \emat $.



\begin{enumerate}
\item
Calculer $A^2,A^3$ et $A^4$.
\item Montrez que $\{A,A^2,A^3,A^4\}$ est un groupe pour le produit matriciel de $\mathfrak{M}_3(\bbr)$.
%\item Que peut-on dire de ce groupe ?
\end{enumerate}


\item
Pour chacune des matrices $A$ suivantes, calculer $A^n$ pour tout $n\in\bbn$. \been
\item $\bmat 1&a\\ 0&1\emat$ avec $a\in\bbr$.
\item La matrice $J_p$ de $\mathfrak{M}_p(\bbr)$ dont tous les
coefficients sont égaux à 1. \end{enumerate} \end{enumerate}



\end{exercice}

\begin{exercice}[Matrices et relations]

Considérons par exemple la relation $\RR$ définie par son dictionnaire d'association:


\begin{center}
             \begin{tabularx}{0.15\textwidth}{Y{0}}
	     \whline
             De & Vers\\
\whline
 a & $\gamma$\\
\hline
b & $\beta$,$\delta$\\
\hline
c & $\gamma$\\
\hline
d& $\delta$\\

             \whline
             \end{tabularx}
             \end{center}

Donnez sa représentation matricielle. 


Donnez la représentation matricielle d'une relation incluse dans $\bbr$.




À votre  avis, pourquoi le nom  \og transposée\fg{} a-t-il été  bien choisi pour
désigner la relation réciproque?



Donnez la représentation matricielle de se
transposée. Généralisez.

Quelle est la représentation matricielle de la négation de $\RR$?



Soit la relation $\RR'$:


\begin{center}
             \begin{tabularx}{0.15\textwidth}{Y{0}}
	     \whline
             De & Vers\\
\whline
 a & $α,\gamma$\\
\hline
b & $α,\beta,δ$\\
\hline
c & $β,δ$\\
\hline
d& $α,β,γ$\\

             \whline
             \end{tabularx}
             \end{center}

Quelle est la représentation matricielle de $\RR\cap \RR'$? De $\RR\cup\RR'$?


Quelle est le rapport entre composition de relations et calcul matriciel?

Quelle est la représentation matricielle de $\RR \circ \tr \RR' $?





\end{exercice}




\begin{exercice}
\begin{enumerate}
\item   Donner la représentation  matricielle des relations suivantes définies
  sur $\bigl\{1,2,3,4\bigr\}$:
  \begin{enumerate}
  \item $\bigl\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\bigr\}$;
  \item $ \bigl\{(1,1),(1,4),(2,2),(3,3),(4,1)\bigr\}$;
  \item                                                                 $
    \bigl\{(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),$

        $(3,4),(4,1),(4,2),(4,3)\bigr\}$;
   \item $ \bigl\{(2,4),(3,1),(3,2),(3,4)\bigr\}$
  \end{enumerate}
\item  Quelles sont, parmi  ces relations,  celles qui  sont réflexives?
  irrefléxives?  symétriques? antisymétriques?  transitives?  Donner des
  algorithmes qui répondent à ces  questions en prenant les relations en
  arguments et en effectuant des calculs sur les matrices.
\end{enumerate}
\end{exercice}







\begin{exercice}
  Soit $\ER=\bigl\{1,2,3,4,5\bigr\}$ et $\RR$ une relation sur $\ER$ qui
  contient  les  couples $(1,3)$,  $(2,4)$,  $(3,1)$, $(3,5)$,  $(4,3)$,
  $(5,1)$, $(5,2)$ et $(5,4)$. Déterminez:

  \begin{multicols}{3}
    \begin{enumerate}
    \item $\RR^2$ \item $\RR^3$ \item $\RR^4$
    \item $\RR^5$ \item $\RR^6$ 
    \end{enumerate}
  \end{multicols}
Utilisez  le calcul  matriciel.

\end{exercice}









\begin{exercice}
$A$ et $B$ sont deux matrices carrées d'ordre $n,$ développer


\begin{multicols}{2}
\begin{enumerate}
\item $\left( A+B\right) ^{2}$

\item $\left( A+B\right) ^{3}$
\end{enumerate}
\end{multicols}

\end{exercice}

\begin{exercice}
$A=\left( 
\begin{array}{rrr}
1 & 1 & 1 \\ 
0 & 1 & 1 \\ 
0 & 0 & 1%
\end{array}%
\right) ,$ calculer $A^{n}.$
\end{exercice}

\begin{exercice}
$A\in \bba^{3\times 2}$, peut-on trouver une matrice $B$ de sorte que $%
A\times B=B\times A$ ?
\end{exercice}






\begin{exercice}
$A=(a_{ij})\in \bbr^{n\times n}$. Expliciter la matrice $A$ dans
les cas suivants :
\end{exercice}

\begin{enumerate}
\item $a_{ij}=i+j$\ si $i>j$\ et $a_{ij}=0$\ sinon.

\item $a_{ij}=j$\ si $i\leq j$\ et $a_{ij}=i$\ si $i>j.$

\item $a_{ij}=\left\vert i-j-1\right\vert $
\end{enumerate}




\begin{exercice}
$A=\left( a_{i,j}\right) \in \bba^{n\times n}$ et $B=^{t}A\times A.$
\end{exercice}

\begin{enumerate}
\item Démontrer que $B$\ est symétrique.

\item $B=\left( b_{i,j}\right) ,$\ calculer $b_{i,j}$\ en fonction des $%
a_{k,l}.$
\end{enumerate}

\begin{exercice}
$A=(a_{i,j})$ est une matrice carrée d'ordre $n$ à coefficients r%
éels. $D=(d_{i,j})$ est une matrice carrée diagonale d'ordre $n$ 
à coefficients réels ayant ses éléments diagonaux tous
distincts. Démontrer : 
\begin{equation*}
A\times D=D\times A\limp A\text{ est diagonale.}
\end{equation*}
\end{exercice}

\begin{exercice}
$A=(a_{ij})\in \bbr^{n\times n},$ on appelle trace de $A$ la
somme de ses éléments diagonaux que l'on note tr($A)$ ce nombre : $%
\func{tr}(A)=\sum\limits_{i=1}^{n}a_{ii}.$ Démontrer : 
\begin{equation*}
A=(a_{ij})\in \bbr^{n\times n}\text{ et }B=(a_{ij})\in \bbr^{n\times n}
\limp \func{tr}(A\times B)=\func{tr}(B\times A)
\end{equation*}
\end{exercice}

\begin{exercice}
$A=(a_{ij})\in \bbr^{n\times n},$ calculer la trace de $%
^{t}A\times A.$
\end{exercice}

\begin{exercice}
$A=\left( 
\begin{array}{rrr}
0 & 1 & -1 \\ 
-3 & 4 & -3 \\ 
-1 & 1 & 0%
\end{array}%
\right) \vspace{0.5cm}$
\end{exercice}

\begin{enumerate}
\item Calculer $A^{2}.$

\item Calculer $A^{2}-3A+2I_{3}.$

\item En déduire que $A$\ est inversible et déterminer $A^{-1}.$
\end{enumerate}

\begin{exercice}
  \begin{itemize}\item[a)]                                                  Soit
    $U=\begin{pmatrix}0&0&5\\1&0&2\\0&1&0\end{pmatrix}$.   Exprimer   de   façon
    simple la matrice $U^3$ comme combinaison linéaire de $U^2$, $U$ et $I_3$. En déduire que $U$ est inversible et donner $U^{-1}$.
\item[b)] Soit $U=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}$. Déterminer $(a,b)\in\R^2$ tel que $(U-aI_3)(U-bI_3)=O_3$. En déduire que $U$ est inversible et donner $U^{-1}$.

\end{itemize}
\end{exercice}








\begin{exercice}[Espace vectoriel de matrices]
  
Nous désignerons  par $E_{ij}$ la  matrice carrée de  $\bbr^{2\times 2}$
dont tous  les coefficients  sont nuls sauf  le coefficient  $(i,j)$ qui
vaut $1$.
Par exemple, $E_{12}=\left(
\begin{smallmatrix}
  0&1\\
  0&0\\
\end{smallmatrix}\right)
$ dans $\bbr^{2\times 2}$.

Dans  toute la  suite de  l'exercice, $E$  désignera le  $\bbr$-espace vectoriel
$\bbr^2=\bigl\{(x,y)\mid x\in\bbr ∧ y \in \bbr\bigr\}$ muni des lois usuelles.

\begin{enumerate}
\item Démontrez que $E={\rm Vect}(E_{11},E_{12},E_{21},E_{22})$.
\item Démontrez que la famille de vecteurs ${\mathcal F}=(E_{11},E_{12},E_{21},E_{22})$ est
  libre. Qu'en déduisez-vous sur cette famille?
\item On note $S=\left\{
    \begin{pmatrix}
      a&c\\
      c&b
    \end{pmatrix}\mid (a,b,c)\in\bbr^3
\right\}$. Démontrez que $\mathcal C=(E_{11},E_{22},E_{12}+E_{21})$ est une base de S.

\item On note $φ$ la fonction de $\bbr^3$ dans $S$ définie par:

$$φ(x,y,z)=
\begin{pmatrix}
  x&z\\
  z&y
\end{pmatrix}
$$

Démontrez que $φ\in{\mathcal L}(\bbr^3,S)$,  ensemble des applications linéaires
de $\bbr^3$ dans $S$.

\item \textit{Question  bonus}: déterminez ${\rm mat}_{\mathcal  B,\mathcal C}φ$
  avec ${\mathcal B}=\bigl\{(1,0,0),(0,1,0),(0,0,1)\bigr\}$.




\end{enumerate}



\end{exercice}







\begin{exercice}
  Soit la matrice $A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$.
\begin{itemize}
\item[a)] Déterminer $A^n$ pour tout $n\in\mathbb{N}$.
\item[b)] On considère les deux suites $(u_n)_{n\in\mathbb{N}}$ et
$(v_n)_{n\in\mathbb{N}}$ définies par la donnée de $u_0$ et $v_0$ et
les relations de récurrence
\[\left\{\begin{array}{ccc}u_{n+1}&=&u_n-v_n\\
v_{n+1}&=&-u_n+v_n
\end{array}\right.\]
\begin{itemize}
\item[(i)] On pose $W_n=\begin{pmatrix}u_n\\v_n\end{pmatrix}$. Etablir
une relation entre $W_{n+1}$, $A$ et $W_n$.
\item[(ii)] En déduire une expression de $u_n$ et $v_n$ en fonction de $u_0$, $v_0$ et
$n$ pour tout $n\in\mathbb{N}$.
\end{itemize}
\end{itemize}
\end{exercice}







\begin{exercice}[Dynamique des populations]
  Dans une île vendéenne, on trouve des tyrannosaures (prédateurs) et des pintades
  (proies). On  note les populations de  tyrannosaures et de pintades  après $k$
  années par $T_k$ et $P_k$. Un  biologiste a avancé que les populations varient
  d'année en année selon le modèle suivant:

$$
\begin{cases}
T_k=0,6T_{k-1}+0,3P_{k-1}\\
P_k=-0,5T_{k-1}+1,4P_{k-1}
\end{cases}
$$


Soit $M_k=
\begin{pmatrix}
  T_k\\P_k
\end{pmatrix}
$ la matrice des populations de tyrannosaures et de pintades après $k$ années et $M_0=
\begin{pmatrix}
  10\\30
\end{pmatrix}
$ la matrice de la population initiale.

On note $A=
\frac{1}{10}
\begin{pmatrix}
6&3\\
-5&14
\end{pmatrix}
$

\begin{enumerate}
\item Quelle est la population initiale des tyrannosaures?
\item Justifiez le fait que $a_{1,0}<0$ et $a_{1,1}>0$.
\item Exprimez la matrice des populations  après $k$ années en fonction de celle
  des populations de l'année précédente.
\item Exprimez la matrice des populations  après $k$ années en fonction de celle
  des populations initiales.
\item Quelle sera la population de tyrannosaures après 3 ans?
\item Proposez  une résolution de la  question précédente à l'aide  de la classe
  \mintinline{python}{Mat} introduite dans l'exercice précédent.

\end{enumerate}
\end{exercice}





\begin{exercice}
Dans une ferme du bocage vendéen, un fermier élève des pintades.

Les pintades se reproduisent selon le schéma suivant:

$$p_{n+2}=p_{n+1}+p_n$$

avec $p_n$ le nombre de pintades au bout de $n$ mois sachant que $p_0=p_1=1$.

On veut connaître le nombre de pintades au bout de 1111 mois.

\begin{enumerate}
\item Estimez  le nombre  d'opérations arithmétiques élémentaires  pour calculer
  $p_{1111}$.
Combien de temps  cela prendra-t-il au fermier d'effectuer le  calcul sur son PC
équipé d'un processeur I5 de 60 GFLOPs?
\item Comment le calcul matriciel peut sauver le fermier?
\end{enumerate}
\end{exercice}






\begin{exercice}
Dans toute la suite $U$ désigne une suite de 4 bits qui peut être
représentée par la matrice 
\begin{equation*}
U=\left( 
\begin{array}{llll}
x_{1} & x_{2} & x_{3} & x_{4}%
\end{array}%
\right)
\end{equation*}%
et la transposée de $U$ est notée $X$ : 
\begin{equation*}
^{t}U=X=\left( 
\begin{array}{l}
x_{1} \\ 
x_{2} \\ 
x_{3} \\ 
x_{4}%
\end{array}%
\right)
\end{equation*}%
et il est bien entendu que les éléments $x_{i}$ sont considér%
és comme des éléments du corps $\mathbb{F}_{2}$ en ce sens que $%
1+1=0.$ Pour améliorer la sécurité de la transmission des cha%
\^{\i}nes de 4 bits on décide de transformer le message $U$ en 
\begin{equation*}
V=U\times B
\end{equation*}%
où $B$ est une matrice (judicieusement choisie) à coefficients dans $%
\mathbb{F}_{2}$ ou, si l'on préfère, on transforme le message $X$
en $Y=A\times X$
\end{exercice}

\begin{enumerate}
\item Quelle relation existe-t-il entre $Y$\ et $V$\ ? Entre $A$\ et $B$\ ?

\item Si on veut que $V=\left( 
\begin{array}{lllll}
x_{1} & x_{2} & x_{3} & x_{4} & x_{2}%
\end{array}%
\right) ,$\ donner la matrice $B.$

\item Si on veut que $Y=\left( 
\begin{array}{c}
x_{1} \\ 
x_{1}+x_{2} \\ 
x_{3} \\ 
x_{1+}x_{4} \\ 
x_{2} \\ 
x_{3}%
\end{array}%
\right) ,$\ donnner la matrice $A.$

\item On veut rajouter au message\ $U$\ un bit de parité\ paire (pour
un bit de parité impaire, ce qui suit est impossible), décrire alors 
$V$\ et donner alors $B$\ ?

\item On veut que $V=\left( 
\begin{array}{llllllll}
x_{4} & x_{3} & x_{2} & x_{1} & x_{1} & x_{2} & x_{3} & x_{4}%
\end{array}%
\right) ,$\ déterminer $B.$

\item Quelqu'un décide de choisir 
\begin{equation*}
B=\left( 
\begin{array}{llllll}
1 & 1 & 1 & 1 & 1 & 1 \\ 
0 & 1 & 0 & 1 & 0 & 1 \\ 
1 & 0 & 1 & 0 & 1 & 0 \\ 
1 & 1 & 0 & 0 & 1 & 1%
\end{array}%
\right)
\end{equation*}

\begin{enumerate}
\item Calculer les images des éléments suivants : 
\begin{equation*}
\begin{tabular}{|c|c|}
\hline
$U$ & $V$ \\ \hline
$1111$ & \hspace{1in} \\ \hline
1100 &  \\ \hline
0011 &  \\ \hline
0110 &  \\ \hline
0101 &  \\ \hline
0010 &  \\ \hline
1010 &  \\ \hline
0100 &  \\ \hline
\end{tabular}%
\ 
\end{equation*}

\item Qelle remarque faites-vous sur le choix de $B$\ ?

\item Donner une matrice $B^{^{\prime }}$\ ayant la même taille que $B$\
et qui ne possède pas à coup s\^{u}r le défaut précédent.

\item Donner une matrice $B^{\prime \prime }$\ ayant la même taille que $%
B$\ et ayant le défaut (même pire\ si vous le voulez) de $B.$
\end{enumerate}
\end{enumerate}




\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{pmatrix}
    \sin(t)&\cos(t)\\-\cos(t)&\sin(t)
  \end{pmatrix}
$ est-elle orthogonale pour tout $t\in\bbr$?

\item Déterminez la troisième ligne de la matrice orthogonale:
  $\begin{pmatrix}
    1/3&2/3&2/3\\2/3&-2/3&1/3\\ & &
  \end{pmatrix}$
  \end{enumerate}
\end{exercice}






\begin{exercice}[Calculs complexes]
On note i le  nombre de carré $-1$. On note ${\rm e}^{{\rm  i}t}=\cos t + {\rm i}
\sin t$. On note $C=\bigl\{{\rm e}^{{\rm i}t} \mid t \in \bbr\bigr\}$
  \begin{enumerate}
  \item Démontrez que $C$ muni de  la multiplication des nombres complexes a une
    structure de groupe.
  \item On  considère deux réels  $t$ et $t'$. Calculez  la partie réelle  et la
    partie imaginaire de ${\rm e}^{{\rm i}t}×{\rm e}^{{\rm i}t'}$.
    Déduisez-en que $$\cos(t+t')=\cos  t\cos t' - \sin t\sin  t'$$. Déterminez une
    formule similaire pour $\sin(t + t')$.
  \item On considère la matrice $A=
    \begin{pmatrix}
      \cos t & -\sin t\\
      \sin t & \cos t
    \end{pmatrix}
$.

Calculez $A^2$ et $A^3$.

\item Donnez  une forme  simple donnant  $A^k$ pour tout  entier naturel  $k$ et
  démontrez votre résultat.

\item Calculez $A×\tr A$ en donnant la forme la plus simple possible.
\item \textit{Question bonus}: on note $R=\left\{ \begin{pmatrix}
      \cos t & -\sin t\\
      \sin t & \cos t
    \end{pmatrix} \mid t\in \bbr\right\}$.

Démontrez que $R$ muni de la multiplication matricielle a une structure de groupe.

\item Lien avec les rotations?

  \end{enumerate}
  
\end{exercice}





















\begin{pyxercice}[La Matrice]
 

\subsection{Fabriquons nos outils}

\begin{quote}
 \textbf{ Matrice} — du mot latin \textit{matrix} (matricis), lui-même dérivé de\textit{ mater}, qui signifie « mère » — un élément qui fournit un appui ou une structure, et qui sert à entourer, à reproduire ou à construire.
\end{quote}








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



\setindent{\indentationcours}\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}\setindent{0cm}



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}


\setindent{\indentationcours}\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}\setindent{0cm}




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


\setindent{\indentationcours}\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}\setindent{0cm}


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


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

\end{recherche}\setindent{0cm}


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


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



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




\setindent{\indentationcours}\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}\setindent{0cm}


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}





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




\end{pyxercice}


\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 étudié  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}$.


\setindent{\indentationcours}\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}\setindent{0cm}

\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}
\begin{center}
  \includegraphics[height=4cm]{kronecker}
\end{center}

% \includegraphics[width=3.1cm]{kronecker}
%\caption{Leoplod \bsc{Kronecker} \\ (1823-1891)}
%\end{figure}
%\end{minipage}
%\end{flushleft}
%\setindent{\indentationcours}
%\vspace{-4.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:

\setindent{0cm}

$$\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}}$$

\setindent{\indentationcours}\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}\setindent{0cm}


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

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

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

\end{theoreme}
\setindent{0cm}



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.


\setindent{\indentationcours}
\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}
\setindent{0cm}


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*}

\setindent{\indentationcours}
\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}
\setindent{0cm}


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 

\vspace{1cm}

\begin{equation*}
A=\left( 
\begin{array}{rrrr}
2 & 5 & -2 & 3 \\ 
3 & 6 & 3 & 6 \\ 
1 & 2 & -1 & 2%
\end{array}%
\right)
\end{equation*}%

\vspace{1cm}


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.

\setindent{\indentationcours}
\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}
\setindent{0cm}

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}
\setindent{\indentationcours}
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*}%

\setindent{0cm}


$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 (qui ne comporte  que des additions de
  vecteurs ou des multiplication par un scalaire) 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}


\subsection{Exercices}


\begin{exercice}
Déterminer les $\ell$-réduites échelonnées ($\ell$ré) des
matrices suivantes et donner leur rang :
\end{exercice}

\begin{multicols}{2}
\begin{enumerate}
\item $A=\left( 
\begin{array}{rrrr}
1 & 2 & 0 & 1 \\ 
-1 & 2 & 1 & 1 \\ 
3 & 1 & 0 & -2%
\end{array}%
\right) $

\item $A=\left( 
\begin{array}{rrrrrr}
1 & 1 & 2 & 2 & 2 & 2 \\ 
1 & 0 & 0 & -1 & 0 & 1 \\ 
0 & 0 & 1 & 1 & 1 & 0 \\ 
2 & 1 & -1 & 0 & -1 & 2%
\end{array}%
\right) $

\item $\left( 
\begin{array}{ccc}
1 & 2 & 3 \\ 
4 & 5 & 6 \\ 
7 & 8 & 9%
\end{array}%
\right) $

\item $\left( 
\begin{array}{ccc}
1 & 2 & 3 \\ 
4 & 5 & 6 \\ 
5 & 5 & 10%
\end{array}%
\right) $
\end{enumerate}
\end{multicols}


\begin{exercice}
Les matrices suivantes sont-elles inversibles ? On cherchera, pour chacune
d'elles, l'inverse par la méthode de Gauss.
\end{exercice}


\begin{multicols}{2}
\begin{enumerate}
\item $A=\left( 
\begin{array}{rrr}
0 & 1 & 1 \\ 
1 & 0 & 1 \\ 
1 & 1 & 0%
\end{array}%
\right) $

\item $B=\left( 
\begin{array}{rrr}
1 & 0 & -1 \\ 
0 & 2 & 2 \\ 
-1 & 1 & 4%
\end{array}%
\right) $

\item $C=\left( 
\begin{array}{rrr}
1 & 2 & -1 \\ 
-1 & -1 & 2 \\ 
2 & 1 & 1%
\end{array}%
\right) $

\item $D=\left( 
\begin{array}{rrr}
1 & 2 & 3 \\ 
4 & 5 & 6 \\ 
7 & 8 & 9%
\end{array}%
\right) $
\end{enumerate}
\end{multicols}

\begin{exercice}
Soit $D=\lceil d_{1,1},d_{2,2},\ldots ,d_{n,n}\rfloor $ une matrice
diagonale, démontrer que $D$ est inversible si, et seulement si,  $\prod%
\limits_{i=1}^{n}d_{i,i}\neq 0.$
\end{exercice}



\begin{exercice}
  Inverser les matrices suivantes:
$$\begin{array}{llll}
A=\begin{pmatrix}
1&2\\2&5
\end{pmatrix}&
B=\begin{pmatrix}
1&1&1\\1&0&2\\
2&1&3
\end{pmatrix}&
C=\begin{pmatrix}
i&2&-3\\0&i&2\\0&0&i
\end{pmatrix}&
D=\begin{pmatrix}
2&2&3\\1&-1&0\\-1&2&1
\end{pmatrix}
\end{array}$$
\end{exercice}





\begin{exercice}
Ecrire matriciellement de deux façons les systèmes suivants :
\end{exercice}


\begin{multicols}{3}
\begin{enumerate}
\item $\left\{ 
\begin{array}{c}
x-2y+3z=2 \\ 
2x-5y-4z=-1 \\ 
4y-3z=8%
\end{array}%
\right. $

\item $\left\{ 
\begin{array}{c}
3x-z=6 \\ 
5y-4z=-3 \\ 
4x-3y=7%
\end{array}%
\right. $

\item $\left\{ 
\begin{array}{c}
5x+2y+3z=2 \\ 
2x-5y-6z=-2 \\ 
4y-3z=8 \\ 
4x+3y+2z=0%
\end{array}%
\right. $
\end{enumerate}
\end{multicols}



\begin{exercice}
Résoudre le système : 
\begin{equation*}
\left\{ 
\begin{array}{c}
x-2y+z=a \\ 
2x-3y-2z=b \\ 
x-y+z=c%
\end{array}%
\right.
\end{equation*}%
obligatoirement par la méthode  \textsc{Gauss-Jordan}   où $x,y$ et $z$ sont les
inconnues. En déduire que la matrice $A=\left( 
\begin{array}{rrr}
1 & -2 & 1 \\ 
2 & -3 & -2 \\ 
1 & -1 & 1%
\end{array}%
\right) $ est inversible et donner son inverse.
\end{exercice}

\begin{exercice}
Résoudre les systèmes suivants par la méthode de  \textsc{Gauss-Jordan}   :
\end{exercice}

\begin{multicols}{3}

\begin{enumerate}
\item $\left\{ 
\begin{array}{c}
x+2y+3z=1 \\ 
4x+5y+6z=2 \\ 
7x+8y+9z=3%
\end{array}%
\right. $

\item $\left\{ 
\begin{array}{c}
x+2y+3z=1 \\ 
4x+5y+6z=2 \\ 
5x+7y+9z=3%
\end{array}%
\right. $

\item $\left\{ 
\begin{array}{c}
x+2y+3z+4t=1 \\ 
4x+5y+6z+2t=2 \\ 
7x+8y+9z-t=3%
\end{array}%
\right. $

\item $\left\{ 
\begin{array}{c}
x+y+z=1 \\ 
x-y-2z=3 \\ 
2x+3y+5z=0 \\ 
4x+3y+4z=4%
\end{array}%
\right. $

\item $\left\{ 
\begin{array}{c}
x+y+z=1 \\ 
x-y-2z=3 \\ 
2x+3y+5z=0 \\ 
4x+3y+4z=1%
\end{array}%
\right. $

\item $\left\{ 
\begin{array}{c}
x+y+z=1 \\ 
x-y-2z=3 \\ 
2x-z=4 \\ 
3x+y=5%
\end{array}%
\right. $
\end{enumerate}
\end{multicols}

\begin{exercice}
  Déterminer le rang des systèmes linéaires d'inconnues réelles suivants, en fonction du paramètre $m\in\R$. On donnera l'ensemble des solutions.
$$ \begin{array}{lll}
a)\left\{\begin{array}{c}mx+y+z=m\\
x+my+z=m\\
x+y+mz=m
\end{array}\right.&
b)\left\{\begin{array}{c}(m+1)x+my=2m\\
mx+(m+1)y=1
\end{array}\right.&
c)\left\{\begin{array}{c}x-my+m^2z=2m\\
mx-m^2y+mz=2m\\
mx+y-m^2z=1-m
\end{array}\right.
\end{array}
$$
\end{exercice}








\begin{exercice}
Soit $\mathcal{B}=\left( i,j\right) $\ une base du plan ou $\mathcal{B}%
=\left( i,j,k\right) $\ une base de l'espace$,$\ nous savons que tout
vecteur se décompose de façon unique dans la base $\mathcal{B}.$\
Nous fixons un point $O$\ appelé origine$,$\ pour tout point $M$\ de
notre plan ou espace, le vecteur $\overrightarrow{OM}$\ se décompose de
façon unique dans la base $\mathcal{B}$\ et nous obtenons les coordonn%
ées du vecteur $\overrightarrow{OM}$\ qui correspondent au coordonné%
es du point $M$\ dans le repère $\mathcal{R}=\left( O,i,j\right) $\ ou $%
\mathcal{R}=\left( O,i,j,k\right) .$%


%schéma

Ces coordonnées se notent, respectivement, par%
\begin{equation*}
M\left( 
\begin{array}{c}
x \\ 
y%
\end{array}%
\right) _{\mathcal{R}}\text{ , }M\left( 
\begin{array}{c}
x \\ 
y \\ 
z%
\end{array}%
\right) _{\mathcal{R}}
\end{equation*}%
Un changement de repère peut concerner un changement d'origine ou un
changement de base ou les deux. Soit donc le repère $\mathcal{R}=\left(
O,i,j,j\right) $\ avec $\mathcal{B}=\left( i,j,k\right) $\ la base associ%
ée et $\mathcal{R}^{\prime }=\left( O^{\prime },i^{\prime },j^{\prime
},k^{\prime }\right) $\ un autre repère avec $\mathcal{B}^{\prime
}=\left( i^{\prime },j^{\prime },k^{\prime }\right) $\ la base associée.
Nous notons%
\begin{equation*}
M\left( 
\begin{array}{c}
x \\ 
y \\ 
z%
\end{array}%
\right) _{\mathcal{R}},M\left( 
\begin{array}{c}
x^{\prime } \\ 
y^{\prime } \\ 
z^{\prime }%
\end{array}%
\right) _{\mathcal{R}^{\prime }},O^{\prime }\left( 
\begin{array}{c}
\alpha \\ 
\beta \\ 
\gamma%
\end{array}%
\right) _{\mathcal{R}}\text{ et }M\left( 
\begin{array}{c}
x_{1} \\ 
y_{1} \\ 
z_{1}%
\end{array}%
\right) _{\mathcal{R}_{1}=\left( O,i^{\prime },j^{\prime },k^{\prime
}\right) }
\end{equation*}%
et $P=\left( p_{i,j}\right) $\ la matrice de passage de $\mathcal{B}$\ à 
$\mathcal{B}^{\prime },$\ c'est-à-dire la matrice des coordonnées
des vecteurs de $\mathcal{B}^{\prime }$\ dans la base $\mathcal{B}.$
\end{exercice}

\begin{enumerate}
\item Quelle sont les coordonnées de $O$ dans le repère $\mathcal{R}$
?

\item Démontrer que $P$\ est inversible en cherchant les coordonnées
des vecteurs de $\mathcal{B}$\ dans la base $\mathcal{B}^{\prime }.$

\item On note $X=\left( 
\begin{array}{c}
x \\ 
y \\ 
z%
\end{array}%
\right) ,X^{\prime }=\left( 
\begin{array}{c}
x^{\prime } \\ 
y^{\prime } \\ 
z^{\prime }%
\end{array}%
\right) ,X_{1}=\left( 
\begin{array}{c}
x_{1} \\ 
y_{1} \\ 
z_{1}%
\end{array}%
\right) .$\ Démontrer que $X_{1}=P\times X.$

\item Déterminer $X^{\prime }$\ en fonction de $X$\ et de $P.$
\end{enumerate}














\begin{exercice}
  Soit $A=
  \begin{pmatrix}
    10&7&8&7\\
    7&5&6&5\\
    8&6&10&9\\
    7&5&9&10
  \end{pmatrix}$, $B_1=
  \begin{pmatrix}
    32 \\ 23 \\ 33 \\ 31
  \end{pmatrix}
$ et $B_2=
\begin{pmatrix}
  32,1\\22,9\\33,1\\30,9
\end{pmatrix}
$

Résolvez les systèmes $A\times X= B_1$ et $A\times X= B_2$: commentaires?

\end{exercice}



\begin{exercice}
  Soit $A=
  \begin{pmatrix}
    10^{-16} & 1\\
    1 & 1
  \end{pmatrix}
$ et $B=
\begin{pmatrix}
  1 \\ 2
\end{pmatrix}
$.  Supposons  que les  nombres  flottants  soient représentés  avec  10
chiffres  significatifs.  Résolvez  le  système   $A\times  X  =  B$  en
choisissant $10^{-16}$  comme premier  pivot. Recommencez  en commençant
par permuter les deux lignes puis en prenant 1 comme pivot.

Généralisez en  remplaçant $10^{-16}$ par un  nombre strictement positif
quelconque $\varepsilon$: des commentaires?


\end{exercice}












\begin{pyxercice}






\subsection{Back to code: 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}



\setindent{\indentationcours}\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}\setindent{0cm}



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


\setindent{\indentationcours}\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}\setindent{0cm}


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:


\setindent{\indentationcours}\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}\setindent{0cm}



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}



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

\end{recherche}\setindent{0cm}

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

\setindent{\indentationcours}\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}\setindent{0cm}

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}




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

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


\end{recherche}\setindent{0cm}


\setindent{\indentationcours}\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}\setindent{0cm}










\end{pyxercice}




%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "PolyMD2_15"
%%% End: 
