%Last modified: <matrix_info2.tex modifié par  Guillaume CONNAN le lundi 7 janvier 2013 à 00h 50min 03s>
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\chapterimage{matrix}

\chaptertext{Le calcul  matriciel est  très utilisé en  réseaux, théorie
des graphes, en infographie, en structures de données, etc.  Bref, c'est
une nouvelle notion indispensable à bien maîtriser par tous les informaticien(ne)s...
}

\chapter{Calcul matriciel}

\section{La matrice}

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

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


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

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


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


Sur CAML, on créera un type \texttt{anneau} :


\begin{lstlisting}[caption={}]
type 'a anneau =
  {zero      : 'a;
   un        : 'a;
   som       : 'a -> 'a -> 'a;
   prod      : 'a -> 'a -> 'a;
   sous      : 'a -> 'a -> 'a;
   div       : 'a -> 'a -> 'a;
   to_string : 'a -> string;
   egal      : 'a -> 'a -> bool;
   ordre     : 'a -> 'a -> bool;
  };;
\end{lstlisting}

Par exemple, l'anneau $(\bbr,+,\cdot)$ sera représenté par:


\begin{lstlisting}[caption={}]
let reel =
  {zero      = 0.;
   un        = 1.;
   som       = ( +. );
   prod      = ( *. );
   sous      = ( -. );
   to_string = string_of_float;
   div       = ( /. );
   egal      = (=);
   ordre     = (>=);
  };;
\end{lstlisting}




\begin{recherche}
 Définissez de la même manière l' anneau $(\bbz,+,\cdot)$  sur CAML.
\end{recherche}


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


Sur  CAML, on  utilisera à  bon  escient les  fonctions \texttt{map}  et
\texttt{mapi}. Voici ce que dit la documentation:


\begin{lstlisting}[caption={}]
val map : ('a -> 'b) -> 'a list -> 'b list
     List.map f [a1; ...; an] applies function f to a1, ..., an, and builds the list [f a1; ...; f an] with the results returned by f. Not tail-recursive.

val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
     Same as List.map, but the function is applied to the index of the element as first argument (counting from 0), and the element itself as second argument. Not tail-recursive.
\end{lstlisting}


\begin{recherche}
Que font alors les fonctions suivantes:

\begin{lstlisting}[caption={}]
let map_vec = fun op vec ->
  map (fun x -> op x) vec;;

let vecs_op = fun op v1 v2 ->
    mapi ( fun i x -> op (nth v1 i) x ) v2;;
\end{lstlisting}

sachant que \texttt{nth} est défini par:


\begin{lstlisting}[caption={}]
val nth : 'a list -> int -> 'a

    Return the n-th element of the given list. The first element (head of the list) is at position 0. Raise Failure "nth" if the list is too short. Raise Invalid_argument "List.nth" if n is negative.
\end{lstlisting}

\end{recherche}



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


\begin{recherche}
...que vous inspire:

  \begin{lstlisting}[caption={}]
let mats_op = fun op m1 m2 ->
  vecs_op (vecs_op op) m1 m2;;

let rec make_vec long x =
  match long with
  |0 -> []
  |_ -> x::(make_vec (long-1) x);;

let rec make_mat row col x =
  match row with
  |0 -> []
  |_ -> (make_vec col x)::(make_mat (row -1) col x);;
  \end{lstlisting}
\end{recherche}


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

Nous  mettrons au  point des  fonctions nous  permettant de  calculer le
produit de deux matrices:




\begin{lstlisting}[caption={}]
# let a = [[1;2;3];[4;5;6]];;
val a : int list list = [[1; 2; 3]; [4; 5; 6]]
# printm entier a;;
 |     1      2      3  | 
 |     4      5      6  | 

# let b = [[0;10;20;30];[-10;0;10;20];[-20;-10;0;10]];;
val b : int list list =
  [[0; 10; 20; 30]; [-10; 0; 10; 20]; [-20; -10; 0; 10]]
# printm entier b;;
 |     0     10     20     30  | 
 |   -10      0     10     20  | 
 |   -20    -10      0     10  | 

# printm entier (prod_mat entier a b);;
 |   -80    -20     40    100  | 
 |  -170    -20    130    280  | 
\end{lstlisting}


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






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

\begin{lstlisting}[caption={}]
# printm entier a;;
 |     1      2      3  | 
 |     4      5      6  | 
- : unit = ()
# printm entier (transpose a);;
 |     1      4  | 
 |     2      5  | 
 |     3      6  | 
- : unit = ()
\end{lstlisting}


En pratique, on échange lignes et colonnes.

\begin{recherche}
  Démontrez que $\tr (A\times B) = \tr A \times \tr B$.
\end{recherche}




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


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

\subsection{Opérations sur les lignes}



\subsubsection{Matrices élémentaires}

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




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

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


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


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

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

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

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


\begin{lstlisting}[caption={}]
# printm entier (elem entier 2 3 4);;
 |     0      0      0      0  | 
 |     0      0      0      0  | 
 |     0      0      0      1  | 
 |     0      0      0      0  | 
\end{lstlisting}

\subsubsection{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}$.

\begin{lstlisting}[caption={}]
# printm entier (transvec entier 0 3 (-2) (unite entier 4));;
 |     1      0      0     -2  | 
 |     0      1      0      0  | 
 |     0      0      1      0  | 
 |     0      0      0      1  | 
\end{lstlisting}


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

\begin{lstlisting}[caption={}]
# printm entier (dilat entier 1 7 (attila entier (3,4)));;
 |     1      1      1      1  | 
 |     7      7      7      7  | 
 |     1      1      1      1  | 
\end{lstlisting}



\subsubsection{É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$.

\begin{lstlisting}[caption={}]
# printm entier (swap entier 0 1 [[11;12;13];[21;22;23];[31;32;33]]);;
 |    21     22     23  | 
 |    11     12     13  | 
 |    31     32     33  | 
\end{lstlisting}


\subsubsection{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) .$


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

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


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

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

\end{theoreme}



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

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

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

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


\section{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}$.

\subsection{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*}

\subsection{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é lré ou LR%
é).
\end{enumerate}

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

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

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

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

Le \textbf{rang} de $M$, noté $\limfunc{rang}(M)$, est le nombre de
lignes non nulles de sa $ \ell$-réduite échelonnée, c'est donc aussi
le nombre de pivots da sa lré. $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}











\section{Algorithme Fang-Tcheng}


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

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

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

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

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

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



\begin{lstlisting}[caption={}]
# printm entier ( lre entier [[2;5;-2;3];[3;6;3;6];[1;2;-1;2]]);;
 |     1      0      0      4  | 
 |     0      1      0     -1  | 
 |     0      0      1      0  | 
\end{lstlisting}


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


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

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

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

\section{Déterminant d'une matrice carrée}


\subsection{Déterminant d'une matrice de taille 2}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{leibniz2}
\caption{Godfried W. \bsc{Leibniz} \\ (1646-1716)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-6.2cm}




En fait, vous savez depuis la Seconde que deux vecteurs du plan de coordonnées
$(a,b)$  et  $(a',b')$  sont  colinéaires  si, et  seulement  si,  leurs
coordonnées sont proportionnelles. Il  existe donc un réel $\lambda$ tel
que $a=\lambda a'$ et $b=\lambda b'$ et alors 

$$ab'-a'b=\lambda ab-\lambda ab=0$$

On appelle  déterminant de  la matrice $A=\begin{pmatrix}  a & a'\\  b &
  b'\\ \end{pmatrix}$ le nombre $ab'-a'b$ et on note~:


\renewcommand{\myunit}{0.7 cm}

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

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


\node  at (-1.65,0) { $\det(A)=$};




% la matrice en blanc
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = |,%
             right delimiter = |%
            ] at (0,0)
{%
 a & a'   \\ 
  b &b'\\  
}; 

% les barres
\draw[gray] (A-1-1.north west) -- (A-2-2.center);
\draw[gray](A-2-2.center)--(A-1-2.center);
\draw[gray](A-1-2.center)--(A-2-1.south west);
\node at (2,0) { $=ab'-a'b$};



 \end{tikzpicture} 
 \end{center}


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

Dans la  suite, $A=(a_{ij})$, $B=(b_{ij})$ sont des  matrices carrées de
taille $n$, $\lambda$ est un scalaire. $L_i$ est une ligne quelconque de
A.  On note $\Delta_{ij}$ le déterminant de la matrice obtenue à partir de A en \og
   barrant\fg{} la ligne $i$ et la colonne $j$.

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

$$\det A= \displaystyle\boxsum_{k=1}^{n}a_{1k}\boxdot(-1)^{1+k}\boxdot\Delta_{1k}=\displaystyle\boxsum_{k=1}^{n}a_{ik}\boxdot(-1)^{i+k}\boxdot\Delta_{ik}=\displaystyle\boxsum_{k=1}^{n}a_{kj}\boxdot(-1)^{k+j}\boxdot\Delta_{kj}$$
\end{propriete}

On admettra cette  propriété. Voyons ce que cela  donne pour une matrice
de taille 3:













\renewcommand{\myunit}{0.35 cm}
\small

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

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


\node  at (-2,0) { $(-1)^{(1+1)}$};




% la matrice en blanc
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             color=white,%
            %
            ] at (0,0)
{%
 a_{11} & a_{12}  & a_{13}  \\ 
  a_{21} &a_{22}& a_{23} \\ 
  a_{31}& a_{32}  & a_{33}  \\ 
}; 

% les barres
\draw[blue] (A-1-1.south) -- (A-3-1.south);
\draw[blue] (A-1-1.east) -- (A-1-3.east);


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


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

% 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}  \\ 
}; 
% \end{tikzpicture} 
% \end{center}





\node at (2,0) { $+(-1)^{(2+1)}$};




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

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

% la matrice en blanc
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             color=white,%
            %
            ] at (4,0)
{%
 a_{11} & a_{12}  & a_{13}  \\ 
  a_{21} &a_{22}& a_{23} \\ 
  a_{31}& a_{32}  & a_{33}  \\ 
}; 

% les barres
\draw[blue] (A-2-1.south) -- (A-3-1.south);
\draw[blue] (A-2-1.north) -- (A-1-1.north);
\draw[blue] (A-2-1.east) -- (A-2-3.east);


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

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

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

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

\node at (6.3,0) { $+(-1)^{(3+1)}$};


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

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

% la matrice en blanc
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             color=white,%
            %
            ] at (8.5,0)
{%
 a_{11} & a_{12}  & a_{13}  \\ 
  a_{21} &a_{22}& a_{23} \\ 
  a_{31}& a_{32}  & a_{33}  \\ 
}; 

% les barres
\draw[blue] (A-3-1.north) -- (A-1-1.north);
\draw[blue] (A-3-1.east) -- (A-3-3.east);


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


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

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


\normalsize

C'est-à-dire~:

$$\det(A)=
a_{11}\begin{vmatrix}a_{22}&a_{23}\\ 
       a_{32}& a_{33}\end{vmatrix}-
a_{21}\begin{vmatrix}a_{12}&a_{13}\\ 
       a_{32}& a_{33}\end{vmatrix}+
a_{31}\begin{vmatrix}a_{12}&a_{13}\\ 
       a_{22}& a_{23}\end{vmatrix}
$$


Par exemple, calculons le déterminant de $A=\begin{pmatrix}
1&2&3\\
2&1&-2\\
-2&3&1
\end{pmatrix}$



\small

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

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


\node  at (-2,0) { $(-1)^{(1+1)}$};




% la matrice en blanc
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             color=white,%
            %
            ] at (0,0)
{%
 1&2&3\\
2&1&-2\\
-2&3&1\\
}; 

% les barres
\draw[blue] (A-1-1.south) -- (A-3-1.south);
\draw[blue] (A-1-1.east) -- (A-1-3.east);


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


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

% les noms
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = |,%
             right delimiter = |] at (0,0)
{%
1&2&3\\
2&1&-2\\
-2&3&1\\
}; 
% \end{tikzpicture} 
% \end{center}





\node at (2,0) { $+(-1)^{(2+1)}$};




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

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

% la matrice en blanc
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             color=white,%
            %
            ] at (4,0)
{%
1&2&3\\
2&1&-2\\
-2&3&1\\
}; 

% les barres
\draw[blue] (A-2-1.south) -- (A-3-1.south);
\draw[blue] (A-2-1.north) -- (A-1-1.north);
\draw[blue] (A-2-1.east) -- (A-2-3.east);


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

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

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

% les noms
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = |,%
             right delimiter = |] at (4,0)
{%
1&2&3\\
2&1&-2\\
-2&3&1\\
}; 
% \end{tikzpicture} 
% \end{center}

\node at (6.3,0) { $+(-1)^{(3+1)}$};


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

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

% la matrice en blanc
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             color=white,%
            %
            ] at (8.5,0)
{%
1&2&3\\
2&1&-2\\
-2&3&1\\
}; 

% les barres
\draw[blue] (A-3-1.north) -- (A-1-1.north);
\draw[blue] (A-3-1.east) -- (A-3-3.east);


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


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

% les noms
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = |,%
             right delimiter = |] at (8.5,0)
{%
1&2&3\\
2&1&-2\\
-2&3&1\\
}; 
\end{tikzpicture} 
\end{center}

\normalsize

C'est-à-dire~:

\begin{align*}
\det(A)&=
1\times\begin{vmatrix}1&-2\\ 
       3& 1\end{vmatrix}-
2\times\begin{vmatrix}2&3\\ 
       3& 1\end{vmatrix}+
(-2)\times\begin{vmatrix}2&3\\ 
       1& -2\end{vmatrix}\\
&=(1+6)-2(2-9)-2(-4-3)\\
&=7+14+14\\
&=35
\end{align*}





\begin{lstlisting}[caption={}]
# det entier [[1;2;3];[2;1;-2];[-2;3;1]];;
- : int = 35
\end{lstlisting}



\begin{recherche}
  

Appliquez la même méthode pour calculer de tête le déterminant de la matrice suivante:

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

\end{recherche}





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


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

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

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


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

On admettra cette propriété.


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

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

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

Démontrez cette propriété. 

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

Démontrez cette propriété.


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

Démontrez cette propriété.


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

Démontrez cette propriété.

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

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

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


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


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

Démontrez cette propriété.




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


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

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




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

Faites de même lorsqu'on utilise l'algorithme Fang Tcheng %\begin{CJK}{UTF8}{song}  方程 \end{CJK} ^J.

En juin 2012, un ordinateur américain de la firme \textsc{Ibm} a établi un nouveau record
de vitesse de calcul de 16,32 péta-flops, soit $16,32\times 10^{16}$ opérations
mathématiques  à  virgule  flottante  par seconde.  En  comparaison,  un
ordinateur individuel standard a une puissance d'environ 100 giga-flops.
L'ordinateur utilisé  compte  $\numprint{ 1572864 }$  c\oe urs. 
Combien de temps  lui faudra-t-il environ pour effectuer  le calcul d'un
déterminant de taille 30 à l'aide de la définition? Avec l'algorithme Fang Tcheng %\begin{CJK}{UTF8}{song}  方程 \end{CJK} ^J
?

Il  est  à noter  que  le  test de  performance  servant  à classer  les
superordinateurs est le LINPACK: il mesure le temps mis pour résoudre un
système dense (sans zéros) de $n$ équations à $n$ inconnues en utilisant
l'algorithme Fang Tcheng %\begin{CJK}{UTF8}{song}  方程 \end{CJK} ^J.



\begin{propriete}
  Soit  A  et B  deux  matrices  carrées  de  même taille  alors  $$\det
  (A\times B)=\det A \cdot \det B$$
\end{propriete}

Nous  admettrons cette  propriété. Démontrez  alors les propriétés
suivantes:


\begin{proprietes}
  \begin{itemize}
  \item Si A est inversible alors $\det A \neq 0$;
  \item Si A est singulière (non-inversible) alors $\det A = 0$;
  \item A est inversible si, et seulement si, $\det A \neq 0$.
  \end{itemize}
\end{proprietes}

\section{Résolution de systèmes}




\subsection{Généralités}

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

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

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

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

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

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

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

\subsection{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 
\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{A}%
\end{array}%
\right.
\end{equation*}%
sous la forme 
\begin{equation*}
\left[ A\mid B\right]
\end{equation*}%
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=\text{lré}\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 
\begin{eqnarray*}
R &=&P\times A \\
H &=&P\times B
\end{eqnarray*}%
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.








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

\modeexercice % entre en mode exercice







\section{EXERCICES}




















\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}
$A$ et $B$ sont deux matrices carrées d'ordre $n,$ développer
\end{exercice}

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

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



\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}
Déterminer les $\ell$-réduites échelonnées (lré) 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}
  \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$ en fonction 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}$.
\item[c)] 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{itemize}
\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 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}
  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{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}
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}
Les déterminants  peuvent servir à calculer certaines  surfaces. On peut
montrer par  exemple que  l'aire du triangle  dont les sommets  sont les
points $A(x_1,y_1)$,  $B(x_2,y_2)$ et $C(x_3,y_3)$ est égal  à la valeur
absolue de $$
\frac{1}{2}\begin{vmatrix}
  x_1&y_1&1\\
  x_2&y_2&1\\
  x_3&y_3&1
\end{vmatrix}
$$

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

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

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

%\vfill\eject

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



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



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

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

\begin{multicols}{2}

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

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

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

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



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

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

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



\subsection{Chiffrement de \textsc{Hill}}


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

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

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

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


Nous  allons   utiliser  nos  outils  de calcul  matriciel  en
cryptographie. En  1929, Lester \textsc{Hill} (1891 -  1961) proposa une
méthode  de chiffrement  par blocs  de lettres  en travaillant  avec des
matrices à  coefficients dans $\bbz/26\bbz$  (combien y a-t-il  de lettres
dans notre alphabet?).  Par la suite nous noterons $\bbz_{n}$ l'ensemble
$\bbz/n\bbz$.

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

\subsubsection{Codage}

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


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


Par exemple:

\begin{lstlisting}
# open Char;;
# code('@');;
- : int = 64
\end{lstlisting}

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

\begin{lstlisting}
# code('AB');;
Characters 5-6:
  code('AB');;
       ^
Error: Syntax error
\end{lstlisting}

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



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

Par exemple:

\begin{lstlisting}
# encode "COUCOU@MAMAN";;
- : int list = [3; 15; 21; 3; 15; 21; 0; 13; 1; 13; 1; 14]
\end{lstlisting}

Pour cela, on commencera par créer une fonction \verb+explose+ qui transforme une chaine en la liste des caractères qui la composent.
On utilisera:


\begin{lstlisting}[caption={}]
let tete_ch s = String.get s 0;;

let queue_ch s = String.sub s 1 (String.length s -1);;
\end{lstlisting}


Par exemple:

\begin{lstlisting}[caption={}]
# explose "COUCOU@MAMAN";;
- : char list = ['C'; 'O'; 'U'; 'C'; 'O'; 'U'; '@'; 'M'; 'A'; 'M'; 'A'; 'N']
\end{lstlisting}

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


Par exemple:

\begin{lstlisting}
# decode [3; 15; 21; 3; 15; 21; 0; 13; 1; 13; 1; 14];;
- : string = "COUCOU@MAMAN"
\end{lstlisting}


On pourra utiliser \verb+List.rev_map+, \verb+Char.escaped+, \verb+Char.chr+
et  \verb+String.concat+. Voici  des  extraits de  la documentation  des
différentes bibliothèques impliquées: 

\begin{Verbatim}
val chr : int -> char
Return the character with the given ASCII code. 
Raise Invalid_argument "Char.chr" if the argument is outside the range 0--255.

val escaped : char -> string
Return a string representing the given character, 
with special characters escaped following the lexical conventions of OCaml.

val concat : string -> string list -> string
String.concat sep sl concatenates the list of strings sl, 
inserting the separator string sep between each.

val rev_map : ('a -> 'b) -> 'a list -> 'b list
List.rev_map f l gives the same result as List.rev (List.map f l), but is tail-recursive and more efficient.
\end{Verbatim}


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

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


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


\begin{lstlisting}
# let lc = encode("JE@NE@SUIS@PAS@UN@NUMERO@JE@SUIS@UN@HOMME@LIBRE");;
\end{lstlisting}

Le  principe consiste  alors  à  regrouper les  nombres  par paquets  de
longueur  constante  $p$ et  donc  à construire  à  partir  de la  liste
\verb+L+ une 
matrice de $p$ lignes complétée éventuellement de zéros où les codes des
caractères seront rentrés colonne par colonne.

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


Attention! Nous devons travailler modulo 27. 

On commencera par créer un type \verb+classe+

\begin{lstlisting}[caption={}]
type classe  =
  {representant : int ; modulo : int};;
\end{lstlisting}

Vous reverrez les résultats obtenus en arithmétique l'an passé.

Créez ensuite un
anneau général \verb+ quotient n+ puis on posera:

\begin{lstlisting}[caption={}]
# let z27 = quotient 27;;
val z27 : classe anneau =
  {zero = {representant = 0; modulo = 27};
   un = {representant = 1; modulo = 27}; som = <fun>; prod = <fun>;
   sous = <fun>; div = <fun>; to_string = <fun>; egal = <fun>; ordre = <fun>}
\end{lstlisting}


Par exemple, on pourra obtenir la lré d'une matrice modulo 27:


\begin{lstlisting}[caption={}]
# let m27 = [[1%27 ; 22%27 ; 25%27] ; [0%27 ; 25%27 ; 1%27] ; [25%27 ; 3%27 ; 1%27]];;
val m27 : classe list list =
  [[{representant = 1; modulo = 27}; {representant = 22; modulo = 27};
    {representant = 25; modulo = 27}];
   [{representant = 0; modulo = 27}; {representant = 25; modulo = 27};
    {representant = 1; modulo = 27}];
   [{representant = 25; modulo = 27}; {representant = 3; modulo = 27};
    {representant = 1; modulo = 27}]]
# printm (z27) m27;;
 |  1%27  22%27  25%27  | 
 |  0%27  25%27   1%27  | 
 | 25%27   3%27   1%27  | 

- : unit = ()
# printm z27 (lre z27 m27);;
 |  1%27   0%27   0%27  | 
 |  0%27   1%27   0%27  | 
 |  0%27   0%27   1%27  | 

- : unit = ()
\end{lstlisting}


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


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

 Utilisez  à bon  escient  les fonctions  crées  autour de  l'algorithme
 Fang-Tcheng.


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

\verb+"LQVPQNDUGNPENPAEZ@RYUTFEULHYJXVPLEZ@OJOOQPQKETQF"+.
\end{center}




Si on le compare au message initial:

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

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


Nous pouvons résumer tout le codage en une seule fonction.


\begin{lstlisting}
# codage ("JE@NE@SUIS@PAS@UN@NUMERO@JE@SUIS@UN@HOMME@LIBRE") cle
- : string = "LQVPQNDUGNPENPAEZ@RYUTFEULHYJXVPLEZ@OJOOQPQKETQF"
\end{lstlisting}


\subsubsection{Décodage}

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

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


\vfill

\eject


\subsection{Algèbre linéaire}


































%
%%
%
%


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

\item Que repr\'{e}sente ${\rm Vect}\left( \mathcal{F}\right) $\ avec $%
\mathcal{F}=\left( u,v\right) $ ?

\item D\'{e}montrer que $w=\left( 2,-3\right) \in {\rm Vect}\left( 
\mathcal{F}\right) .$

\item $u$\ et $v$\ sont-ils colin\'{e}aires ?

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

\item D\'{e}montrer que ${\rm Vect}\left( \mathcal{F}\right) ={\rm Vect}%
\left( w\right) .$

\item D\'{e}montrer que $\left( 1,2\right) \notin {\rm Vect}\mathcal{F}.$

\item $t=\left( 1,2\right) ,$\ et $\mathcal{F}^{\prime }=\left( w,t\right) $%
\ ; d\'{e}montrer que ${\rm Vect}\left( \mathcal{F}^{\prime }\right) =%
\mathbb{R}^{2}.$
\end{enumerate}

   \end{exercice}







  \begin{exercice}
     On sait que $\bbr^{2\times 2}$, l'ensemble des
matrices carr\'{e}es d'ordre 2 \`{a} coefficients r\'{e}els, est un espace
vectoriel sur $\mathbb{R}$ avec les deux op\'{e}rations: addition de deux
matrices et la multiplication d'une matrice par un r\'{e}el (scalaire). On
consid\`{e}re%
\begin{equation*}
F=\left\{ \left( 
\begin{array}{cc}
a & b \\ 
b & a%
\end{array}%
\right) \mid \left( a,b\right) \in \mathbb{R}^{2}\right\}
\end{equation*}%
D\'{e}montrer que $F$ est un sev de $E$ puis d\'{e}terminer deux matrices $%
M_{1}$ et $M_{2}$ v\'{e}rifiant $F={\rm Vect}\left( \mathcal{F}\right) $
avec $\mathcal{F}=\left( M_{1},M_{2}\right)$.

Cette famille est-elle libre? A-t-elle d'autres propriétés?

   \end{exercice}






 \begin{exercice}
     \begin{enumerate}
     \item D\'{e}montrer que toute \og sous famille\fg{} d'une famille libre est libre.
     \item D\'{e}montrer que toute \og sur famille\fg{} d'une famille li\'{e}e est li\'{e}e.

     \end{enumerate}
   \end{exercice}




\begin{exercice}
     Dire si les familles $\mathcal{F}=\left( u_{i}\right) $ suivantes de $%
     \mathbb{R}^{3}$ sont libres ou li\'{e}es:
     \begin{enumerate}
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2)$
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2),u_{3}=(0,1,-2)$
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2),u_{3}=(0,1,-1)$
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2),u_{3}=(0,1,-1),u_{4}=\left(
         12,155,703\right) $
     \end{enumerate}
   \end{exercice}


\begin{exercice}
     Dire si les familles $\mathcal{F}=\left( u_{i}\right) $ suivantes de $%
     \mathbb{R}^{3}$ sont libres ou li\'{e}es:
     \begin{enumerate}
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2)$
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2),u_{3}=(0,1,-2)$
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2),u_{3}=(0,1,-1)$
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2),u_{3}=(0,1,-1),u_{4}=\left(
         12,155,703\right) $
     \end{enumerate}
   \end{exercice}







  \begin{exercice}
     Dire si les familles $\mathcal{F}=\left( u_{i}\right) $ suivantes de $%
     \mathbb{R}^{3}$ sont libres ou li\'{e}es:
     \begin{enumerate}
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2)$
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2),u_{3}=(0,1,-2)$
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2),u_{3}=(0,1,-1)$
     \item $u_{1}=(1,1,0),u_{2}=(1,0,2),u_{3}=(0,1,-1),u_{4}=\left(
         12,155,703\right) $
     \end{enumerate}
   \end{exercice}




 \begin{exercice}
    \begin{enumerate}
\item $\mathcal{F}%
_{1}=(u_{1,}u_{1}+u_{2},u_{1}+u_{2}+u_{3},u_{1}+u_{2}+u_{3}+u_{4})$ est-elle
une base de\textit{\ }$\mathbb{R}^{4}?$

\item $\mathcal{F}_{2}=(u_{1}+u_{2},u_{2}+u_{3},u_{3}+u_{4},u_{4}+u_{1})$%
\textit{\ }est-elle une base de\textit{\ }$\mathbb{R}^{4}$\textit{\ ?}
\end{enumerate}
  \end{exercice}






 \begin{exercice}
    \begin{enumerate}
\item On note $H=\left\{ \left( x,y,z\right) \in \mathbb{R}^{3}\mid
x+2y+3z=0\right\} ,$\ d\'{e}montrer que $H$\ est un sev de $\mathbb{R}^{3}$
en d\'{e}terminant $u$\ et $v,$\ deux vecteurs de $\mathbb{R}^{3},$\ de
sorte que $H=\limfunc{Vect}\left( u,v\right) .$

\item Donner une famille g\'{e}n\'{e}ratrice de $H.$

\item La famille $\left( u,v\right) $\ est-elle libre ?

\item Donner une base de $H.$

\item Quelle est la dimension de $H$\ ?

\item On note $w=(1,2,3)$, d\'{e}montrer que $w\notin H.$

\item On note $K=\limfunc{Vect}(w).$\ Donner une base de $K.$

\item Quelle est la dimension de $K$\ ?

\item D\'{e}montrer que $\left( u,v,w\right) $ est une base de $\mathbb{R}%
^{3}.$
\end{enumerate}
  \end{exercice}





\begin{exercice}
    \begin{enumerate}
    \item D\'{e}montrer que $H=\left\{ \left( x,y,z\right) \in \mathbb{R}^{3}\mid
        x-z=0\right\} $ est un sev de $\mathbb{R}^{3}$ et en donner une base.
    \item D\'{e}montrer que $H=\left\{ \left( x,y,z\right) \in \mathbb{R}^{3}\mid
        x=0\right\} $ est un sev de $\mathbb{R}^{3}$ et en donner une base.
    \item   $H=\left\{   \left(  x,y,z\right)   \in   \mathbb{R}^{3}\mid
          ax+by+cz=0\right\} $ o\`{u} $a$, $b$ et $c$ sont des r\'{e}els
          fix\'{e}s.   Dans  quel   cas   a-t-on  $H=\mathbb{R}^{3}$   ?
          D\'{e}montrer que $H$ est un sev de $\mathbb{R}^{3}$.  
    \end{enumerate}
  \end{exercice}





 \begin{exercice}
    On travaille dans $\mathbb{R}^{3}:$
    \begin{enumerate}
    \item R\'{e}soudre le syst\`{e}me $\left\{ 
        \begin{array}{l}
          x+2y+3z=0 \\ 
          2x+y-z=0%
        \end{array}%
      \right. $\ par la m\'{e}thode de la $\ell$-r\'{e}duite \'{e}chelonn\'{e}e.
    \item On note $H=\left\{ \left( x,y,z\right) \in \mathbb{R}^{3}\mid
        x+2y+3z=0\right\} $\ et $K=\left\{ \left( x,y,z\right) \in \mathbb{R}%
        ^{3}\mid 2x+y-z=0\right\} .$\ D\'{e}terminer une base de $H\cap K.$
    \end{enumerate}
  \end{exercice}





 \begin{exercice}
    On travaille dans $\mathbb{R}^{3}$ et on note $u=\left( 1,2,2\right)
    $ et $v=\left( -2,1,2\right)$. D\'{e}terminer des r\'{e}els $a$, $b$
    et                   $c$                  pour                   que
    $\limfunc{Vect}\left(  u,v\right)=\left\{  \left(  x,y,z\right)  \in
    \mathbb{R}^{3}\mid ax+by+cz=0\right\}$. 
  \end{exercice}





 \begin{exercice}
    \begin{enumerate}
    \item $\mathcal{B}$  et $\mathcal{B}^{\prime  }$ sont deux  bases de
      $\mathbb{K}^{n}.$ 
      Qu'appelle-t-on la  matrice de passage de  $\mathcal{B}$ \`{a}
      $\mathcal{B}^{\prime  }$ ?  On note  $P$ cette  matrice, \`{a}
      quoi sert-elle ?  
    \item $\mathcal{B}$ et $\mathcal{B}^{\prime }$ sont des bases de
      $\mathbb{R}^{3}$    et    $A$    est   la    matrice    de
      $\mathcal{B}^{\prime       }$      dans       la      base
      $\mathcal{B}$. D\'{e}montrer que le rang  de $A$ est 3. La
      matrice $A$ est-elle inversible ? 
    \end{enumerate}
  \end{exercice}







 \begin{exercice}
    $u_{1}=(1,2)$    et   $u_{2}=(2,3)$    sont    deux   vecteurs    de
    $\mathbb{R}^{2},$  $\mathcal{B}=(e_{1},e_{2})$  d\'{e}signe la  base
    canonique de $\mathbb{R}^{2}$. 
    \begin{enumerate}
    \item Expliciter la base canonique.
    \item Quelles sont les coordonn\'{e}es de $u_{2}$\ dans $\mathcal{B}$\ ?
    \item Quelles sont les coordonn\'{e}es de $e_{1}$\ dans $\mathcal{B}$\ ?
    \item D\'{e}montrer que la famille $\mathcal{F}=(u_{1},u_{2})$\ est une base
      de $\mathbb{R}^{2}.$
    \item D\'{e}terminer la matrice $P$\ de passage de $\mathcal{B}$\ \`{a} $%
      \mathcal{F}.$
    \item D\'{e}terminer la matrice de passage de $\mathcal{F}$\ \`{a} $B.$\ Que
      repr\'{e}sentent les colonnes de cette matrice ?
    \item D\'{e}terminer  les coordonn\'{e}es  de $u_{1}$\ dans  la base
      $\mathcal{F}$. 
    \item D\'{e}terminer  les coordonn\'{e}es  de $e_{1}$\ dans  la base
      $\mathcal{F}$. 
    \item  $x=(-1,5),$\ d\'{e}terminer  les coordonn\'{e}es  de $x$\
      dans   la   base   $\mathcal{B}$\    et   dans   la   base
      $\mathcal{F}$. 
    \item  D\'{e}terminer  les  coordonn\'{e}es  de $x$\  dans  la  base
      $\mathcal{B}^{\prime }=(-3u_{2},7u_{1})$. 
    \end{enumerate}
  \end{exercice}






  \begin{exercice}
    On note $\mathcal{B}=\left( e_{1},e_{2},e_{3}\right) $ la base canonique de $%
    \mathbb{R}^{3}$. 
    \begin{enumerate}
    \item $x=\left( 2,3,-5\right) ,$\ d\'{e}terminer les coordonn\'{e}es de $x$\
      dans $\mathcal{B}.$
    \item $u=\left( 1,1,-1\right) ,$\ $v=\left( 1,-1,2\right)$, $w=\left(
        2,0,2\right)$. D\'{e}terminer les coordonn\'{e}es des vecteurs
      $u,$\ $v$ et $w$ dans la base $B$\ ainsi que la matrice $A$ de la
      famille $F=\left(u,v,w\right)$ dans $B$. 
    \item  $\limfunc{Vect}\left( \mathcal{F}\right)$  est-il  un sev  de
      $\mathbb{R}^{3}$ ? 
    \item D\'{e}terminer la LR\'{E} de $A$. Quel est le rang de $A$ ?
    \item D\'{e}montrer que $\mathcal{F}$ est libre.
    \item D\'{e}montrer que $\mathcal{F}$ est une base de $\mathbb{R}^{3}.$
    \item Est-il vrai que $\mathbb{R}^{3}=\limfunc{Vect}\mathcal{F}$?
    \item D\'{e}terminer la matrice $A^{\prime }$\ de la famille $\mathcal{B}$
      dans la base $\mathcal{F}$.
    \item D\'{e}terminer la matrice de $\mathcal{F}$\ dans la base $\mathcal{F}$
      et la matrice de $\mathcal{B}$\ dans la base $\mathcal{B}.$
    \item D\'{e}terminer les coordonn\'{e}es de $x$\ dans la base $\mathcal{F}.$
    \item D\'{e}montrer de plusieurs fa\c{c}ons que $\mathcal{G}=\left(
        u,v\right) $\ n'est pas une base de $\mathbb{R}^{3}.$
    \end{enumerate}
  \end{exercice}



  \begin{exercice}
    $f\in \mathcal{L}\left( \mathbb{R}^{3}\right) ,$ $\mathcal{B=}\left(
e_{1},e_{2},e_{3}\right) $ est une base de $\mathbb{R}^{3},$ $A=\left( 
\begin{array}{ccc}
1 & 1 & 0 \\ 
1 & 0 & 1 \\ 
1 & 1 & 1%
\end{array}%
\right) =\func{Mat}_{\mathcal{B}}\left( f\right) .$




\begin{enumerate}
\item $f$\ est-il un endomorphisme de $\mathbb{R}^{3}$\ ?

\item Quelles sont les coordonn\'{e}es de $e_{1}$\ dans la base $\mathcal{B}$%
\ ?

\item Quelles sont les coordonn\'{e}es de $f\left( e_{2}\right) $\ dans la
base $\mathcal{B}$ ?

\item Quelles sont les coordonn\'{e}es de $f\left( x\right) $\ dans la base $%
\mathcal{B}$\ si $x=e_{1}+e_{2}-2e_{3}$\ ?

\item Qu'est $\ker f$\ ?
\end{enumerate}





  \end{exercice}







  \begin{exercice}
    On travaille dans l'espace vectoriel $\mathbb{R}^{3}$ rapport\'{e} \`{a} la
base canonique $\mathcal{B}=\left( e_{1},e_{2},e_{3}\right) .$ On donne : 
\begin{equation*}
\text{la lr\'{e} de }\left( 
\begin{array}{ccc}
0 & 1 & 1 \\ 
1 & 2 & 1 \\ 
-1 & 1 & 2%
\end{array}%
\right) =\left( 
\begin{array}{ccc}
1 & 0 & -1 \\ 
0 & 1 & 1 \\ 
0 & 0 & 0%
\end{array}%
\right)
\end{equation*}%
On consid\`{e}re la famille $\mathcal{F}\mathbf{=}\left(
u_{1},u_{2},u_{3}\right) $ avec 
\begin{equation*}
u_{1}\left( 
\begin{array}{c}
0 \\ 
-1 \\ 
1%
\end{array}%
\right) _{\mathcal{B}},u_{2}\left( 
\begin{array}{c}
1 \\ 
1 \\ 
2%
\end{array}%
\right) _{\mathcal{B}},u_{3}\left( 
\begin{array}{c}
1 \\ 
2 \\ 
1%
\end{array}%
\right) _{\mathcal{B}}\vspace{0.5cm}
\end{equation*}




\begin{enumerate}
\item D\'{e}terminer la matrice $A$\ de la famille $\mathcal{F}$\ dans la
base $B$.

\item Donner la lr\'{e} de $A$.

\item On note $f$\ l'endomorphisme de $\mathbb{R}^{3}$\ dont la matrice dans
la base $\mathcal{B}$\ est $A.$

\begin{enumerate}
\item Que repr\'{e}sentent les colonnes de $A$\ ?

\item D\'{e}terminer $\mathcal{B}$\ la matrice de la famille $\left( f\left(
u_{1}\right) ,f\left( u_{2}\right) ,f\left( u_{3}\right) \right) $\ dans la
base $\mathcal{B}.$

\item On note $\ker \left( f\right) $\ le noyau de $f,$\ d\'{e}finir $\ker
\left( f\right) .$

\item On note $x=\left( x_{1},x_{2},x_{3}\right) $\ un vecteur quelconque de 
$\mathbb{R}^{3}.$\ D\'{e}terminer les coordonn\'{e}es de $f\left( x\right) $%
\ dans la base $\mathcal{B}.$

\item D\'{e}terminer une base de $\ker \left( f\right) $, on notera $%
\mathcal{F}_{\ker }$\ cette famille.

\item Donner une famille g\'{e}n\'{e}ratrice de $\func{Im}\left( f\right) .$

\item D\'{e}terminer une base de $\func{Im}\left( f\right) .$\ On notera $%
\mathcal{F}_{\func{Im}}$\ cette famille.
\end{enumerate}

\item On note $\mathcal{B}^{\prime }=\left( e_{1}^{\prime },e_{2}^{\prime
},e_{3}^{\prime }\right) $\ la famille obtenue en juxtaposant le ou les
vecteurs de $\mathcal{F}_{\func{Im}}$\ et le ou les vecteurs de $\mathcal{F}%
_{\ker }$. On admet que $\mathcal{B}^{\prime }$\ est une base (il suffit de v%
\'{e}rifier qu'elle est libre) ; $x_{1}^{\prime },x_{2}^{\prime }$\ et $%
x_{3}^{\prime }$\ d\'{e}signent les coordonn\'{e}es d'un vecteur $x$\ de $%
\mathbb{R}^{3}$\ dans cette base.

\begin{enumerate}
\item D\'{e}terminer $H$\ la matrice de passage de $\mathcal{B}$\ \`{a} $%
\mathcal{B}^{\prime }$.

\item On note $U$\ la matrice de $f$\ relativement ou dans la base $\mathcal{%
B}^{\prime },$\ $U=\func{Mat}_{\mathcal{B}^{\prime }}\left( f\right) ,$\
exprimer $U$\ en fonction des matrices $H$\ et $A.$
\end{enumerate}

\item On note $g$\ l'application de $\mathbb{R}^{3}$\ dans $\mathbb{R}^{3}$\
d\'{e}finie par :%
\begin{equation*}
x\left( 
\begin{array}{c}
x_{1}^{\prime } \\ 
x_{2}^{\prime } \\ 
x_{3}^{\prime }%
\end{array}%
\right) _{\mathcal{B}^{\prime }}\rightarrow g\left( x\right) \left( 
\begin{array}{c}
x_{1}^{\prime } \\ 
x_{2}^{\prime } \\ 
0%
\end{array}%
\right) _{\mathcal{B}^{\prime }}
\end{equation*}%
et $g$\ est manifestement un endomorphisme de $\mathbb{R}^{3}.$

\begin{enumerate}
\item D\'{e}terminer $V$\ la matrice de $g$\ dans la base $\mathcal{B}%
^{\prime }.$

\item D\'{e}terminer une base de $\ker \left( g\right) .$

\item D\'{e}terminer une base de\ $\func{Im}\left( g\right) .$

\item Exprimer en fonction de $V$\ et de $H$\ la matrice de $g$\ dans la
base $\mathcal{B}.$

\item Exprimer \`{a} l'aide "de lettres" la matrice de $g\circ f$\ dans la
base $\mathcal{B}^{\prime }.$
\end{enumerate}
\end{enumerate}














  \end{exercice}










  \begin{exercice}
    $\mathcal{B}=\left( u,v,w\right) $ est une base de l'e.v. $\mathbb{R}^{3}$, $%
f$ est un automorphisme de $\mathbb{R}^{3}$ et $A=\func{Mat}_{\mathcal{B}%
}\left( f\right) .$






\begin{enumerate}
\item D\'{e}montrer que $\mathcal{F}=\left( f\left( u\right) ,f\left(
v\right) ,f\left( w\right) \right) $\ est une famille libre et donc que
c'est une base de $\mathbb{R}^{3}.$

\item D\'{e}terminer la matrice de $f$\ dans la base $\mathcal{F}.$
\end{enumerate}





  \end{exercice}



  \begin{exercice}
    $A=\left( 
\begin{array}{lll}
1 & 0 & 1 \\ 
0 & 0 & 1 \\ 
1 & 1 & 1 \\ 
0 & 1 & 0 \\ 
1 & 1 & 0%
\end{array}%
\right) $ est la matrice de l'application lin\'{e}aire $\varphi $ de $%
\mathbb{F}_{2}^{3}$ dans $\mathbb{F}_{2}^{5}$ relativement aux bases
canoniques.




\begin{enumerate}
\item D\'{e}montrer que $\varphi $\ est injective. D\'{e}terminer $\ker
\varphi .$

\item D\'{e}terminer une base de $\func{Im}\varphi .$\ Quelle est la
dimension de $\func{Im}\varphi $\ ? $\varphi $\ est-elle surjective ? Donner
une matrice g\'{e}n\'{e}ratrice de $\func{Im}\varphi $\ dans la base
canonique de $\mathbb{F}_{2}^{5}.$

\item Quelle est la dimension de $\func{Im}\varphi $\ ?
\end{enumerate}





  \end{exercice}

























































\vfill

\eject








\modenormal % restaure les définitions de sections, sous-sections, etc.








































\vfill

\eject


\section{Matrices et CAML}



\subsection{Comment modéliser?}

Au   moment   de   choisir   une   modélisation   pour   nos   matrices,
l'informaticien(ne)  se  pose des  questions:  vais-je  choisir un  type
\verb+array+ mutable ou un type \verb+list+ immuable?

Ça se  discute. Le premier  peut paraître plus  maniable a priori:  on a
accès à tout  le tableau construit statiquement ce qui  ne nous gène pas
car on connaît la taille de la matrice a priori.

D'un  autre côté,  un type  mutable est  dangereux: il  laisse la  porte
ouverte aux  effets de  bord, source  de nombreux  bugs car  souvent mal
maîtrisés.  De  plus, la  machine  ne  gère  pas très  efficacement  les
tableaux statiques. 

Tournons-nous vers les listes: un  langage muni d'un bon ramasse-miettes
les traitera  très efficacement,  voire plus efficacement  qu'un tableau
statique. Elles  permettent de créer  dynamiquement les matrices  ce qui
engendre plus  de souplesse et  cela sans effets  de bord ce  qui assure
plus de sécurité dans la programmation. 

Nous choisirons  donc de programmer  sans effet de bord:  du fonctionnel
aussi pur  que possible. Cela  entraîne un changement des  habitudes: au
lieu  de  raisonner en  termes  de  grosses  boucles imbriquées  et  pas
toujours    contrôlées,   nous    utiliserons    des   petits    modules
fonctionnels. Cela pourra avoir  quelques désavantages dans certains cas
en termes  d'efficacité mais  nous améliorerons  la performance  dans un
deuxième temps.

Nous  essaierons  dans  une  certaine  mesure  de  créer  des  fonctions
polymorphes: cela pourra passer pour une contrainte forte au départ mais
cela vous facilitera la vie pour votre mini-projet sur le chiffrement de
\textsc{Hill}:  vous  n'aurez  qu'à  changer d'anneau  mais  toutes  les
fonctions sur les matrices resteront valables sans aucun changement!

\subsection{Le type anneau}



Nous travaillerons sur des  matrices de $\bba^{n\times m}$ c'est-à-dire,
des  matrices  de $n$  lignes  et  $m$  colonnes dont  les  coefficients
appartiennent à un ensemble $\bba$ muni de deux opérations $\boxplus$ et
$\boxdot$ vérifiant un certain nombre de propriétés (voir cours...).
Nous aurons besoin  des propriétés des opérations sur  $\bba$ pour créer
les opérations sur $\bba^{n\times m}$.

Nous utiliserons un enregistrement:


\begin{lstlisting}[caption={}]
type 'a anneau =
  {zero      : 'a;
   un        : 'a;
   som       : 'a -> 'a -> 'a;
   prod      : 'a -> 'a -> 'a;
   sous      : 'a -> 'a -> 'a;
   div       : 'a -> 'a -> 'a;
   to_string : 'a -> string;
   egal      : 'a -> 'a -> bool;
   ordre     : 'a -> 'a -> bool;
  };;
\end{lstlisting}


\begin{recherche}
Créez les  anneaux \verb+entier+  correspondant à $(\bbz,+,\times)$  et \verb+reel+
correspondant à $(\bbr,+,\times)$.

Créez également  l'anneau booléen $\BR_2$  dont les deux  seuls éléments
sont \verb+true+ et \verb+false+.
\end{recherche}


L'appel de champs des enregistrements se fait à l'aide du point comme en
POO:

\begin{lstlisting}[caption={}]
# entier.zero;;
- : int = 0
# reel.zero;;
- : float = 0.
# entier.som 2 3;;
- : int = 5
# entier.to_string 2;;
- : string = "2"
\end{lstlisting}


\subsection{Joli affichage}


Une matrice  sera modélisée  par une  liste de listes  (la liste  de ses
lignes). Par exemple
$\left(\begin{smallmatrix}
  1&2&3\\
  4&5&6
\end{smallmatrix}\right)$ sera modélisée par \verb+[[1;2;3];[4;5;6]]+ ce
qui n'est  pas joli. Nous allons  donc créer une fonction  permettant un
joli  affichage:  c'est  de  l'E/S  non  fonctionnel  mais  nous  sommes
tolérants. 


Comme dans de nombreuses situations  à venir, nous nous occupons d'abord
d'une ligne:

\begin{lstlisting}[caption={}]
let rec printv a v =
match v with
  |[] -> print_string " | ";
  |t::q ->
    Printf.printf "%7s" (" "^(a.to_string t)^" ");
    (printv a q);;

\end{lstlisting}

Nous précisons l'anneau a utilisé pour pouvoir appeler la bonne fonction
d'affichage (pas de surcharge javaesque...):

\begin{lstlisting}[caption={}]
# printv entier [1;2;3];;
     1      2      3  | - : unit = ()
\end{lstlisting}

Le  type  \verb+unit+, c'est  tout  ce  qui  n'est pas  fonctionnel.  On
retrouve le \verb+printf+ \og à la C\fg{}.


Ensuite, on parcours une liste de liste:


\begin{lstlisting}[caption={}]
let rec printm a m = 
match m with 
  |[] -> print_newline();
  |t::q ->
    print_string " |";
    printv a t;
    print_newline();
    printm a q;
;; 
\end{lstlisting}

On fait du mutable donc on utilise l'horrible \verb+;+ de Java...

\begin{lstlisting}[caption={}]
# printm entier [[1;2;3];[4;5;6]];;
 |     1      2      3  | 
 |     4      5      6  | 

- : unit = ()
\end{lstlisting}



\subsection{Remplissage de matrices}

Nous voudrions construire  des matrices Attila ou  des matrices remplies
de zéros voire d'éléments identiques quelconques.


On commencera comme toujours par fabriquer des lignes puis des listes de
lignes de \verb+x+.

On pense à cela:

\begin{lstlisting}[caption={}]
let make_vec long x =
   match long with
   |0 -> acc
   |_ -> x::(make_vec (long-1) x);;
\end{lstlisting}

Le \verb+::+  ou l'ajout en  tête est  l'opérateur le plus  important en
programmation  fonctionnelle.  Cela  consiste  en fait  à  rajouter  une
branche à notre peigne.

Le problème  est que cette  fonction n'est pas récursive  terminale (\og
\textit{tail recursive}\fg{}: nous en avons parlé l'an passé).

Il est très simple d'y remédier:


\begin{lstlisting}[caption={}]
let make_vec long x =
  let rec local long x acc =
      match long with
      |0 -> acc
      |_ -> local (long-1) x (x::acc)
  in local long x [];;
\end{lstlisting}


\begin{recherche}
À vous de jouer pour fabriquer:

\begin{lstlisting}[caption={}]
(* une matrice de taille row*col remplie de x *)
let make_mat row col x = ...

(* matrice remplie de 1  *)
let attila a (r,c) = ...

(* matrice remplie de neutres *)
let zeros a (r,c) = ...

\end{lstlisting}

Vous obtiendrez par exemple:

\begin{lstlisting}[caption={}]
# printm booleen (attila booleen (2,3));;
 |  vrai   vrai   vrai  | 
 |  vrai   vrai   vrai  | 
\end{lstlisting}




\end{recherche}



\subsection{Utilitaires de collecte d'informations}


Pour  calculer  la longueur  d'une  liste,  on  dispose de  la  fonction
\verb+length+.

\begin{recherche}
Déduisez-en les deux fonctions:

\begin{lstlisting}[caption={}]
(* nb de lignes *)
let n_rows = function ...

(* nb de colonnes *)
let n_cols = function
\end{lstlisting}
\end{recherche}

Pour s'amuser, on peut la  fabriquer de différentes façons. Une rigolote
consiste  à utiliser  \verb+fold_left+,  le pliage  d'une  liste par  la
gauche qui est très utile en programmation fonctionnelle.

Voici un extrait de la documentation:

\begin{lstlisting}[caption={}]
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn.
\end{lstlisting}


On peut l'utiliser ainsi:

\begin{lstlisting}[caption={}]
let compte a somme_partielle y = a.som a.un somme_partielle;;

let long a liste = fold_left (compte a) a.zero liste;;

# long entier [1;2;3;4;5;6;6];;
- : int = 7
\end{lstlisting}


Pour  extraire  la $n$\eme  composante  d'une  liste  on dispose  de  la
fonction \verb+nth+.

\begin{recherche}
Déterminez les fonctions:

\begin{lstlisting}[caption={}]
(* extraction de la ligne no i de la matrice mat *)
let extract_line = function
   mat -> ...

(*extraction de la colonne no i de la matrice mat *)
let rec extract_col = function
   match mat with 
   | ...
(* extraction de la 1ère colonne *)
let tete_col = function
   mat -> ...

(* extraction de la matrice privée de sa 1ère colonne *)
let rec queue_col = function
   ...
\end{lstlisting}

Vous pouvez essayer de rendre vos récursions terminales.

Pour  rendre  la dernière  fonction  terminale,  on pourrait  utiliser  la
fonction \verb+append+  qui rajoute un n\oe  ud au peigne par  la droite
mais cette fonction n'est pas récursive terminale.

Nous allons donc plutôt utiliser \verb+rev+ qui retourne la liste retournée...


\medskip

Définissez enfin une fonction \verb+transpose+ qui renvoie la transposée
d'une matrice en utilisant les fonctions précédentes.

\end{recherche}


\subsection{Opérations sur les matrices}

Nous allons faire un peu de polymorphisme, comme en Java, mais sans
surcharge, contrairement à Java.

Nous voudrions  dans un  premier temps effectuer  une opération  terme à
terme sur des vecteurs: par exemple, la somme terme à terme de $[1;2;3]$
et $[4;5;6]$  est $[5;7;9]$, le  produit terme à terme  est $[4;10;18]$,
etc.

Regardons la description du module \verb+List+:

\begin{lstlisting}[caption={}]
val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
List.map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f an bn]. Raise Invalid_argument if the two lists have different lengths. Not tail-recursive.

val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
List.rev_map2 f l1 l2 gives the  same result as List.rev (List.map2 f l1
l2), but is tail-recursive and more efficient.

val map : ('a -> 'b) -> 'a list -> 'b list
List.map f [a1; ...; an] applies function f to a1, ..., an, and builds the list [f a1; ...; f an] with the results returned by f. Not tail-recursive.

val rev_map : ('a -> 'b) -> 'a list -> 'b list
List.rev_map f l gives the same result as List.rev (List.map f l), but is tail-recursive and more efficient.
\end{lstlisting}


\begin{recherche}
Créez les fonctions:

\begin{lstlisting}[caption={}]
(* opération terme à terme sur deux lignes *)
let vecs_op = fun op v1 v2 -> ...

(* opération terme à terme sur deux matrices *)
let mats_op = fun op m1 m2 -> ...
\end{lstlisting}

puis en pensant à \verb+fold_left+:

\begin{lstlisting}[caption={}]
(* op de tous les termes d'une ligne (v1 op v2 op...) *)

let rec som_vec a vec = ...

let rec prod_vec a vec = ...
\end{lstlisting}

\end{recherche}


Nous en arrivons au produit de deux matrices...

\begin{recherche}

  \begin{lstlisting}[caption={}]
(* multiplication d'une ligne par une matrice *)
let ligne_prod_mat a ligne1 m2 =
  let rec local m2 acc = ...

(* multiplication de deux  matrices *)
let prod_mat a m1 m2 =
  let rec local m1 acc = ...
  \end{lstlisting}


\end{recherche}


\subsection{Matrice définie par une fonction  de ses numéros de ligne et
colonne}

Voici une proposition:

\begin{lstlisting}[caption={}]
let mat_fonc  = fun f r c ->
  let rec aux_ligne = fun f i j acc ->
    match j with
    |j when (j=c)  -> rev acc
    |_ -> aux_ligne f i (j+1)  ((f i j)::acc)
  in
  let rec aux_col = fun f i j acc ->
    match i with
    |i when (i=r) -> rev acc
    |_ -> aux_col f (i+1) j ((aux_ligne f i 0 [])::acc)
  in
  aux_col f 0 0 [];;
\end{lstlisting}


\begin{recherche}
  Commentez...


Déduisez-en une fonction \verb+ unite a  n+ qui renvoie la matrice unité
de taille \verb+n+ dans l'anneau \verb+a+.
\end{recherche}


\subsection{Trace}

Tout est dans le titre...N'oubliez pas la récursion terminale.


\subsection{Matrices élémentaires - Opérations sur les lignes}

Il  faut  bien  connaître  son  cours...Vous  construirez  les  diverses
fonctions comme produit de matrices et composées de fonctions.

\begin{recherche}
  Commencez  par  créer  \verb+elem  a  i  j  n+  i.e.  $E_n^{i,j}$  puis
  \verb+kelem a i j k n+ i.e. $kE_n^{i,j}$.


Ensuite 

\begin{lstlisting}[caption={}]
(* matrice de transvection : (Id +k E(ij))M
  Li <- Li+k.Lj *)
let transvec a i j k mat = ...

(* dilatation : * Diag(1 1 1 k 1 1 1...)   Li <- k Li *)
let dilat a i k mat = ...

(* échange de lignes *)
let swap a i j mat =...
\end{lstlisting}
\end{recherche}


On  aura  enfin  besoin  d'une  fonction qui  élimine  une  ligne  d'une
matrice. Par exemple:

\begin{lstlisting}[caption={}]
# let m4 = [[11;12;13;14];[21;22;23;24];[31;32;33;34];[41;42;43;44]];;
val m4 : int list list =
  [[11; 12; 13; 14]; [21; 22; 23; 24]; [31; 32; 33; 34]; [41; 42; 43; 44]]
# elim entier m4 1;;
- : int list list = [[11; 12; 13; 14]; [31; 32; 33; 34]; [41; 42; 43; 44]]
\end{lstlisting}


\begin{recherche}
  Créez la fonction \verb+elim+.
\end{recherche}

Enfin, il sera  utile de disposer d'une fonction qui  combine des lignes
sous la forme $L_i \leftarrow k_iL_i - k_jL_j$.

\begin{recherche}
  Créez \verb+(* Li <- kiLi - kj Lj *) let comb a i ki j kj mat =...+
\end{recherche}


\subsection{Concaténation de tableaux}


Nous aurons  besoin de  \og concaténer\fg{} deux  matrices, que  ce soit
pour déterminer l'inverse ou résoudre un système linéaire par la méthode
de la LRÉ.

\begin{recherche}
Créez   \verb+concat_mat  =   fun   m1  m2+   en   pensant  à   utiliser
\verb+rev_append+ et \verb+rev_map2+.

Créez ensuite une fonction \verb+mat_to_tab  a mat+ qui \og colle\fg{} à
\verb+mat+ la matrice unité de l'anneau \verb+a+.

Créez enfin  une fonction \verb+tab_to_mat+ qui  extrait le demi-tableau
de droite final.
\end{recherche}




\subsection{Permutations circulaires}

Au moment  de chercher des  pivots, nous  aurons besoin de  permuter des
lignes.  Une  possibilité  est   de  mettre  systématiquement  la  ligne
contenant  le zéro  en dernier  et de  décaler circulairement  celles du
dessous pour  éviter de  faire des \og  \textit{swap}\fg{} sur  les deux
mêmes lignes à chaque fois.


Par exemple, en lançant \verb+permut_circi m 1+ on passera de:


$
\begin{pmatrix}
  11&12&13&14\\
  21&22&23&24\\
  31&32&33&34\\
  41&42&43&44
\end{pmatrix}
$
à
$
\begin{pmatrix}
  11&12&13&14\\
  31&32&33&34\\
  41&42&43&44\\
  21&22&23&24
\end{pmatrix}
$.

\begin{recherche}
  Déterminez une  fonction \verb+permut_circi a  mat i+ en  utilisant si
  besoin \verb+rev_append+, \verb+rev+, \verb+elim+, \verb+nth+.
\end{recherche}



\subsection{Triangulation de Gau\ss{}}



On  commence par  explorer  une colonne  et  trouver un  candidat-pivot,
c'est-à-dire qu'un cherche le premier élément non nul dans une colonne à
partir d'une ligne donnée  (repensez à ce qui a été  fait sur papier les
semaines précédentes).

\begin{recherche}
  Déterminer  \verb+trouve_pivot a  mat pos+  qui trouve  un pivot  dans
  \verb+mat+  à  partir de  la  ligne  \verb+pos+, c'est-à-dire  qu'elle
  teste  $\mathtt{mat_{pos,pos}}$:  s'il  est  non nul,  on  renvoie  la
  matrice inchangée, sinon, on la renvoie après un coup de \verb+permut_circi+.
\end{recherche}

Une fois  le candidat-pivot  trouvé, il faut  faire le  vide en-dessous,
c'est-à-dire combiner les lignes pour y faire apparaître des zéros.

\begin{recherche}
  Déterminez \verb+vide_sous_pivot a mat pos+.
\end{recherche}

Par exemple:


\begin{lstlisting}[caption={}]
# printm entier m4;;
 |    11     12     13     14  | 
 |    21     22     23     24  | 
 |    31     32     33     34  | 
 |    41     42     43     44  | 

# printm entier (vide_sous_pivot entier m4 1);;
 |    11     12     13     14  | 
 |    21     22     23     24  | 
 |    10      0    -10    -20  | 
 |    20      0    -20    -40  | 
\end{lstlisting}


Il ne  reste plus qu'à  composer ces  fonctions pour obtenir  la matrice
trigonalisée par la méthode de \textsc{Gau\ss{}}. 

\begin{recherche}
  Créez \verb+tri_gauss a mat+.
\end{recherche}

\begin{lstlisting}[caption={}]
# let mex = [[1;3;2;-1];[-1;-2;2;6];[2;4;-3;2];[-2;-7;4;1]];;
val mex : int list list =
  [[1; 3; 2; -1]; [-1; -2; 2; 6]; [2; 4; -3; 2]; [-2; -7; 4; 1]]
# printm entier (tri_gauss entier mex);;
 |     1      3      2     -1  | 
 |     0      1      4      5  | 
 |     0      0      1     14  | 
 |     0      0      0   -164  | 
\end{lstlisting}

\begin{recherche}
  Peut-on  en  déduire le  déterminant  de  la matrice?  
\end{recherche}



\subsection{Lé et Lré parla méthode de Gau\ss{}-Jordan}

Cette fois il faut faire le vide  non seulement sous le pivot mais aussi
au-dessus:

\begin{lstlisting}[caption={}]
# printm entier (vide_autour_pivot entier m4 1);;
 |   -10      0     10     20  | 
 |    21     22     23     24  | 
 |    10      0    -10    -20  | 
 |    20      0    -20    -40  | 
\end{lstlisting}


\begin{recherche}
  Créez \verb+vide_autour_pivot+.
\end{recherche}

Il ne reste plus qu'à faire le  vide sur toute la matrice en gardant des
pivots \og  généralisés\fg{} c'est-à-dire  pas forcément  égaux à  1 car
selon les anneaux  dans lesquels on travaille, tous les  nombres ne sont
pas inversibles.

\begin{recherche}
  Créez la fonction \verb+le a mat+ qui renvoie la $\ell$-échelonnée pas
  forcément réduite.
\end{recherche}

Par exemple:

\begin{lstlisting}[caption={}]
# printm entier (le entier [[11;12;13;14];[21;22;23;24];[31;32;33;34];[41;42;43;44]]);;
 |  -110      0    110    220  | 
 |     0    -10    -20    -30  | 
 |     0      0      0      0  | 
 |     0      0      0      0  | 
\end{lstlisting}


Certaines lignes vont  pouvoir être simplifiées. Il faut  donc créer une
fonction  qui \og  simplifie\fg{} une  ligen (mais  quelle opération  se
cache derrière cette notion de simplification?).

\begin{lstlisting}[caption={}]
# simp_vec entier [0;0;3;6;9];;
- : int list = [0; 0; 1; 2; 3]
# simp_vec entier [0;0;3;0;0];;
- : int list = [0; 0; 1; 0; 0]
# simp_vec entier [0;0;3;6;7];;
Exception: Inverse_indefini.
\end{lstlisting}

\begin{recherche}
  Créer \verb+simp_vec  a vec+  puis utilisez  \verb+le+ pour  créer une
  fonction \verb+lre+ qui renvoie, si  elle existe, la lré d'une matrice
  dans un anneau donné.
\end{recherche}


\begin{lstlisting}[caption={}]
# printm entier ( le entier [[2;5;-2;3];[3;6;3;6];[1;2;-1;2]]);;
 |   -72      0      0   -288  | 
 |     0    -36      0     36  | 
 |     0      0     12      0  | 

# printm entier ( lre entier [[2;5;-2;3];[3;6;3;6];[1;2;-1;2]]);;
 |     1      0      0      4  | 
 |     0      1      0     -1  | 
 |     0      0      1      0  | 
\end{lstlisting}



\subsection{Inverse d'une matrice}

Nous avons tout ce qu'il nous faut pour obtenir l'inverse d'une matrice,
si elle  existe, par  la méthode  de \textsc{Gau\ss{}-Jordan}:  on colle
l'identité à droite,  on calcule la lré, on extrait  la partie gauche du
tableau: ya plus qu'à...


\begin{recherche}
  Déterminez la fonction \verb+inverse a mat+:


\end{recherche}
Par exemple:

\begin{lstlisting}[caption={}]
# printm reel (inverse reel [[1.;0.;1.];[0.;1.;1.];[1.;1.;0.]]);;
 |   0.5   -0.5    0.5  | 
 |  -0.5    0.5    0.5  | 
 |   0.5    0.5   -0.5  | 
  \end{lstlisting}


\subsection{Corps des rationnels}

Si  on travaille  dans  $\bbz$, on  est vite  limité  pour inverser  des
matrices: il n'y a que 1 et $-1$ qui soit inversibles.

Nous  allons donc  créer  un type  \verb+rationnel+  pour modéliser  les
nombres appartenant  à $\bbq$ sous  forme d'un enregistrement  puis nous
créerons  un anneau  \verb+rat+ pour  travailler avecc  des matrices  de
rationnels.

Un rationnel est défini par un numérateur et un dénominateur:

\begin{lstlisting}[caption={}]
type rationnel = {
num : int;
den : int;
};;
\end{lstlisting}

Par exemple, $\frac{6}{9}$ sera modélisé par:

\begin{lstlisting}[caption={}]
let r = {num = 6; den = 9};;
\end{lstlisting}


Mais ça se simplifie...Comment?

\begin{recherche}
  Créez  une  fonction   \verb+frac  a  b+  qui   renvoie  le  rationnel
  \verb+{num = a; den= b}+ sous forme simplifiée:

  \begin{lstlisting}[caption={}]
# frac 6 9;;
- : rationnel = {num = 2; den = 3}
  \end{lstlisting}
\end{recherche}


Pour simplifier l'entrée de ces nombres, on peut introduire un opérateur
infixe:

\begin{lstlisting}[caption={}]
let (//) a b = frac a b ;;
\end{lstlisting}

Par exemple:

\begin{lstlisting}[caption={}]
# (-6) // (-9);;
- : rationnel = {num = 2; den = 3}
\end{lstlisting}


Pour  créer notre  anneau de  rationneles, il  faut créer  les fonctions
utiles: somme, produit, etc.

\begin{recherche}
  Créez   \verb+r_plus+,  \verb+r_mult+,   \verb+r_sup+,  \verb+r_egal+,
  \verb+r_div+, \verb+r_sous+.
\end{recherche}


Pour la conversion en chaîne, voici comment faire:

\begin{lstlisting}[caption={}]
let r_to_string r =
  let s = (r.num // r.den) in
  if s.num = 0 then "0"
  else if s.den = 1 then (string_of_int s.num)
  else (string_of_int s.num)^"/"^(string_of_int s.den);;
\end{lstlisting}


Par exemple:

\begin{lstlisting}[caption={}]
# r_to_string (6//9);;
- : string = "2/3"
# r_to_string (8//4);;
- : string = "2"
\end{lstlisting}

Nous sommes donc prêts:

\begin{lstlisting}[caption={}]
let rat = {
   zero = 0//1;
   un   = 1//1;
   som  = r_plus;
   prod = r_mult;
   sous  = (fun x y -> r_plus  x (r_opp y));
   div = (fun x y -> r_mult x (r_inv y));
   to_string = r_to_string;
   egal = r_egal;
   ordre = r_sup;
  };;
\end{lstlisting}

\begin{recherche}
Construisez une fonction qui convertit un entier en rationnel puis une
matrice entière en matrice rationnelle.
\end{recherche}

Nous pouvons alors travailler plus confortablement:

\begin{lstlisting}[caption={}]
# printm rat (inverse rat (mat_rat_of_int ([[1;0;1];[0;1;1];[1;1;0]])));;
 |   1/2   -1/2    1/2  | 
 |  -1/2    1/2    1/2  | 
 |   1/2    1/2   -1/2  | 
\end{lstlisting}


























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