\documentclass{article}
\usepackage[francais]{babel}
%\usepackage[OT1]{fontenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{xspace}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}

\begin{document}

\begin{center}{\Large Algèbre linéaire} \end{center}
\section{Logiciels}
\begin{itemize}
\item En maple il est conseillé d'exécuter {\tt with(linalg);},
en mupad {\tt export(linalg);}. Sinon, il faut précéder
chaque commande de {\tt linalg::}.
\item En maple et mupad, la commande {\tt ?linalg} affiche
la liste des commandes d'algèbre linéaire. Avec xcas, cherchez
dans le menu {\tt Alg}.
\item En maple, attention
il faut utiliser le caractère {\tt \&} avant la multiplication
et il faut souvent utiliser {\tt evalm} dans les programmes
utilisant des matrices et vecteurs. 
\item Pour travailler avec des
coefficients modulaires, en maple on utilise les noms de commandes
avec une majuscule (forme inerte) suivi de {\tt mod n}, en xcas
on fait suivre les coefficients ou matrices de {\tt \% n}, en mupad
on définit les coefficients dans l'anneau, par exemple\\
\verb|Z19:=Dom::IntegerMod(19): MatZ19 := Dom::Matrix(Z19):|\\
\verb|A:=MatZ19([[1, 2], [2]]); Z19(5)*A;|
\end{itemize}

\section{Exercices}
\begin{enumerate}
\item En utilisant un logiciel de calcul formel,
comparez le temps de calcul d'un d\'eterminant de matrice
al\'eatoire \`a coefficients entiers de tailles 50 et 100, 
d'une matrice de taille 6 et 12 avec comme coefficients symboliques
ligne $j$ colonne $k$, $x_{j+k}$ lorsque $j+k$ est pair
et 0 sinon. Peut-on en déduire une indication sur l'algorithme
utilisé?
\item \'Ecrire un programme calculant la borne de Hadamard d'un
déterminant à coefficients réels (rappel~: c'est la borne obtenue en faisant
le produit des normes euclidiennes des vecteurs colonnes).
\item Créez une matrice 4x4 aléatoire avec des coefficients entiers
compris entre -100 et 100, calculer la borne de Hadamard de son déterminant
avec le programme précédent, calculer ce déterminant modulo
quelques nombres premiers choisis en fonction de la borne de Hadamard
et vérifiez le résultat de la reconstruction modulaire du déterminant.
\item Créez une matrice 100x100 aléatoire à coefficients entiers
et calculez son déterminant
modulo quelques nombres premiers. Dans quels cas peut-on
conclure que la matrice est inversible dans $\R$? dans $\Z$?
\item \'Ecrire un programme calculant par interpolation de Lagrange
le polyn\^ome caract\'eristique d'une matrice (en donnant \`a $\lambda$
de $\det(\lambda I -A)$, $n+1$ valeurs distinctes).
\item (Long) \'Ecrire un programme qui calcule un d\'eterminant de matrice
en calculant les mineurs 2x2 puis 3x3 etc. (m\'ethode de Laplace)
\item Recherche du polynôme minimal. On prend un vecteur aléatoire
à coefficients entiers et on calcule $v$, $Av$, ..., $A^nv$ puis
on cherche une relation linéaire minimale entre ces vecteurs, en
calculant le noyau de la matrice ayant ces vecteurs colonnes. Si le
noyau est de dimension 1, alors le polynôme minimal est égal au
polynome caractéristique et correspond à un vecteur de la base du noyau.
Sinon, il faut choisir un vecteur du noyau correspondant au degré
le plus petit possible puis faire le PPCM avec les polynomes obtenurs
avec d'autres vecteurs pour obtenir le polynôme minimal avec une grande
probabilité.
Essayez avec la matrice $A$ de taille 3 ayant des 0 sur la diagonale et 
des 1 ailleurs.
\'Ecrire un programme mettant en oeuvre cette recherche, testez-le avec
une matrice al\'eatoire de taille 30.
\item Testez l'algorithme méthode de Fadeev pour la matrice $A$ ci-dessus.
Même question pour 
\[ A=\left(\begin{array}{ccc}
 3 & -1 & 1 \\
2 &0 &1 \\
1 & -1 & 2 
\end{array}\right), \quad 
A=\left(\begin{array}{ccc}
 3 & 2 & -2 \\
-1 &0 &1 \\
1 & 1 & 0 
\end{array}\right) 
 \]
\item \'Ecrire un programme calculant par une méthode itérative
la valeur propre de module maximal d'une matrice à coefficients
complexes. Dans le cas réel, modifier le programme pour pouvoir
traiter le cas d'un couple de complexes conjugués de module maximal.
Dans le cas hermitien ou réel symétrique, éliminer le couple valeur
propre/vecteur propre et continuer la diagonalisation numérique.
\item Soient $|a|,|b|<\sqrt{n/2}$
\'Ecrire une fonction ayant comme arguments $a/b \pmod n$ 
qui calcule $a$ et $b$.\\
Utiliser ce programme pour résoudre un système 4,4 à coefficients entiers
par une méthode $p$-adique.
\end{enumerate}

\end{document}
