\documentclass[a4paper,12pt]{amsart}
\usepackage{kbexo}


%%%%%%%%%%%%%%%%%%%%%
%% Alice's packages
%%%%%%%%%%%%%%%%%%%%%
\usepackage{xcolor}
\usepackage{hyperref}

%%%%%%%%%%%%%%%%%%%
%% Alice's macros
%%%%%%%%%%%%%%%%%%%
\newcommand{\comment}[1]{{\color{gray}#1}}
\newcommand{\FF}{\mathbb{F}}

\def\pow{\^{}\hskip0pt}

\course{Algèbre et calcul formel -- Agrégation}
\num{6}

\begin{document}
\exotitle[Algèbre linéaire]

\section{Déclaration}

\Q On peut définir un vecteur et une matrice de la manière suivante.
\begin{verbatim}
  w = vector([1,1,-4])
  A = matrix([[1,2,3],[4,5,6],[7,8,9]]); A
\end{verbatim}
Remarquons d'abord que les indices commencent à $0$. Si l'on tape {\tt
A[0,0]}, on obtient {\tt 1}.

\Q Exécuter les commandes
\begin{verbatim}
  A.det()
  A*w
  w*A
  parent(A)
  parent(w)
\end{verbatim}
\Q Comme les coefficients de $A$ sont des entiers, $A$ est considérée par
défaut comme une matrice de $M_n(\ZM)$. Pour entrer la même matrice en temps
qu'élément de $M_n(\QM)$, on peut utiliser la commande
\begin{verbatim}
  B = matrix(QQ,[[1,2,3],[4,5,6],[7,8,9]])
\end{verbatim}
ou bien, comme $A$ est déjà définie
\begin{verbatim}
  B = matrix(QQ,A)
  v = vector(QQ,[1,1,-4])
\end{verbatim}
Vérifier ensuite ce que donnent {\tt parent(B)} et {\tt parent(v)}.

\Q On peut également indiquer la taille, puis les coefficients :
\begin{verbatim}
  C = matrix(2,3,[1,2,3,4/3,5,6])
  C
  parent(C)
\end{verbatim}
\Q On peut également utiliser une formule sur les indices, pour définir une
matrice, par exemple :
\begin{verbatim}
  C = matrix(3, lambda i,j: i-j); C
\end{verbatim}
ou bien, pour une matrice rectangulaire
\begin{verbatim}
  C = matrix(3,4, lambda i,j: i-j); C
\end{verbatim}
ou bien, pour indiquer l'anneau (ou corps) de base
\begin{verbatim}
  C = matrix(QQ, 3,4, lambda i, j: i-j); C
\end{verbatim}
Définir de cette façon la matrice de $M_{3,4}(\ZM)$ dont tous les
coefficients sont égaux à $1$.

\Q Pour les vecteurs, la commande
\begin{verbatim}
  vector(QQ,3, lambda i: i^2)
\end{verbatim}
ne fonctionne pas. On peut par exemple utiliser
\begin{verbatim}
  vector(QQ, [i^2 for i in range(3)])
\end{verbatim}

\Q On peut aussi commencer par définir l'espace des matrices ou des vecteurs
\begin{verbatim}
  MatrixSpace(ZZ,3,2)
  VectorSpace(QQ,3)
\end{verbatim}
Cette commande désigne réellement un espace vectoriel, donc défini sur un
corps; si l'on écrit {\tt ZZ} à la place de {\tt QQ}, on obtient un message
d'erreur. Il faut alors écrire ``module libre'' à la place de ``espace
vectoriel''.
\begin{verbatim}
  FreeModule(ZZ,3)
\end{verbatim}
Par exemple, pour définir la matrice $A$ ci-dessus, on peut utiliser les
commandes suivantes
\begin{verbatim}
  M3Z = MatrixSpace(ZZ,3); M3Z
  A = M3Z([1,2,3,4,5,6,7,8,9]); A
\end{verbatim}
Vérifier ce que donne alors {\tt parent(A)}. De même, pour définir $B$,
connaissant déjà $A$:
\begin{verbatim}
  M3Q = MatrixSpace(QQ,3); M3Q
  B = M3Q(A); B
  parent(B)
\end{verbatim}

\Q Définir $M_3(\FM_3)$, puis la matrice {\tt Abar}, réduction de la matrice
{\tt A} modulo $3$. Quelle commande donne une matrice choisie au hasard dans
$M_3(\FM_3)$?

\Q Expérimenter les commandes
\begin{verbatim}
  M3Q(0)
  M3Q(1)
  M3Q(2)
\end{verbatim}
Pour définir la matrice identité, on peut aussi utiliser {\tt
identity\_matrix}. Regarder ce que donnent les commandes
\begin{verbatim}
  identity_matrix(4)
  identity_matrix(QQ,4)
  identity_matrix(RR,4)
\end{verbatim}

\section{Addition, multiplication, déterminant, inverse}

\noindent Tout cela se fait de façon naturelle.
\begin{verbatim}
  set_random_seed(42)
  M = M3Z.random_element()
  N = M3Z.random_element()
  M + N
  M * N
  M.determinant()
  M.det()
  M^2
  M.is_invertible()
  Minv = M^(-1)
  M*Minv
\end{verbatim}

\Q Expliquer pourquoi {\tt M.is\_invertible()} renvoie {\tt False} alors que Sage arrive ensuite à calculer {\tt M\pow(-1)}.

\section{Extraction, concaténation}

Essayons sur la matrice

{\tt M = matrix(6,4,lambda i,j: i+j)}

\noindent{}
On se souvient que la numérotation des indices commence à $0$:
{\tt M[0,0]} donne {\tt 0}.

\Q Essayer
\begin{verbatim}
  M[[0,2,3],1]
  parent(_)
\end{verbatim}
(le caractère «\texttt{\_}» désigne le résultat de la dernière commande
exécutée).

\Q Essayer 
\begin{verbatim}
  M[[0,2,3], [1..3]]
\end{verbatim}
Plus généralement, si {\tt l1} et {\tt l2} sont des listes, {\tt M[l1, l2]}
donne la sous matrice de $M$ formée des lignes de la liste {\tt l1} et des
colonnes de la liste {\tt l2}. Remarquons qu'il est possible de répéter des
lignes, ou des colonnes:
\begin{verbatim}
  M[[1,1], [0..3]+[0]]
\end{verbatim}

\Q Les commandes
\begin{verbatim}
  M.nrows()
  M.ncols()
\end{verbatim}
donnent les dimensions de $M$. On peut concaténer à $M$ une matrice de $6$
lignes. Prenons une matrice $N$ au hasard dans $M_{6,3}(\QM)$. Définir pour
cela cet espace de matrice, puis utiliser la commande {\tt random\_element}.
Pour concaténer $M$ et $N$, on utilise
\begin{verbatim}
  M.augment(N)
\end{verbatim}
on obtient alors un message d'erreur parce-que $M$ est définie sur $\ZM$ et
$N$ sur $\QM$. Il faut replacer $M$ dans $M_{6,4}(\QM)$. 
\begin{verbatim}
  M64Q = MatrixSpace(QQ,6,4)
  M64Q(M).augment(N)
\end{verbatim}


\section{Noyau, image, équations linéaires}

\Q Exécuter la commande
\begin{verbatim}
  A = matrix(ZZ,3,3,[1,2,3,3,2,1,1,1,1])
  KA = A.kernel(); KA
\end{verbatim}
Remarquons que pour sage, le noyau d'une matrice $A$ est le noyau à gauche,
c'est-à-dire le noyau de l'application qui à $x$ associe $xA$. Pour le noyau
à droite, on utilise
\begin{verbatim}
  A.right_kernel()
\end{verbatim}
Bien sûr, le résultat de ces commandes dépend de l'anneau de base,
c'est-à-dire de l'espace où se situe \kbd{A}. Avec $A$, on a obtenu un
$\ZM$-module alors que si l'on fait 
{\tt B = matrix(QQ,A); KB = B.kernel()}, on obtient un
$\QM$-espace vectoriel. Pour obtenir une base:
\begin{verbatim}
  KB.basis()
\end{verbatim}

\Q Pour l'image, on utiliser la commande {\tt B.image()}, qui donne l'image à
gauche, c'est-à-dire l'espace vectoriel engendré par les lignes de $B$. On
peut pour cela également utiliser {\tt B.row\_module()}. De même, l'image de
$B$ à droite est donnée par
\begin{verbatim}
  B.column_module()
\end{verbatim}

\Q Voyons maintenant les résolutions d'équations.

{\tt Y = vector(QQ,[0, -4, -1])}

\noindent{} On veut résoudre l'équation $BX=Y$:
\begin{verbatim}
  X0 = B.solve_right(Y)
  X0; B*X0
\end{verbatim}
Cette commande {\tt solve\_right} ne donne qu'une solution {\tt X0}. Comme on
connaît aussi le noyau de $B$, on a l'ensemble de toutes les solutions de
l'équation.

Si {\tt Y} n'est pas dans l'image des colonnes de {\tt B}, la fonction {\tt solve\_right} renvoie une erreur.
\begin{verbatim}
  Y = vector(QQ,[1, -4, -1])
  X0 = B.solve_right(Y)
\end{verbatim}

\section{Générateur pseudo-aléatoire}
Fixons un entier premier $q$. Pour tout $a,b \in \FF_q$, on définit la fonction
\begin{align*}
F_{a,b}: \FF_q &\rightarrow \FF_q \\
x &\mapsto a \cdot x + b
\end{align*}
On peut se servir d'une telle fonction pour générer du pseudo-aléa. Étant donnée une graine $x_0$, on définit une suite de nombres pseudo-aléatoires en faisant $x_{n+1} = F_{a,b}(x_n)$.
Ces générateurs de pseudo-aléa (appelés générateur congruentiel linéaire\footnote{\url{en.wikipedia.org/wiki/Linear\_congruential\_generator}}) ne sont pas très bons, et l'objectif de l'exercice est de montrer que même si $a$ et $b$ sont secrets, la connaissance de $3$ termes consécutifs de la suite est suffisante pour les retrouver et également retrouver la graine $x_0$.\\
\noindent\comment{(Conséquence : il ne faut pas utiliser ce genre de générateurs pseudo-aléatoires en cryptographie).}

\Q Expliquer comment, étant donné $x_n, x_{n+1}$ et $x_{n+2}$, on peut retrouver $a$ et $b$ en résolvant un système affine.

\Q Expliquer comment, étant donné $x_0$, $a$ et $b$, on peut calculer $x_n$ en $O(\log n)$ opérations dans $\FF_q$.\\
\noindent\comment{(Indice 1 : on définira $v_n$ un vecteur de dimension $2$ dépendant de $x_n$ tel que $v_{n+1} = A \cdot v_n$, où $A$ est une matrice $2 \times 2$.)\\
\noindent(Indice 2 : On pourra utiliser l'exponentiation rapide pour calculer $v_n$ à partir de $v_0$ rapidement.)}

\Q Adapter la question précédente pour obtenir $x_0$ à partir de $a$, $b$ et $x_n$ en temps $O(\log n)$ (opérations dans $\FF_q$).

\Q On donne $q = 521$ et $x_{33} = 205, x_{34} = 473, x_{35} = 506$. Utiliser Sage pour retrouver $a$ et $b$, puis la graine $x_0$.

\comment{\noindent(Solution : on doit trouver $x_0 = 42$.)}


\section{Réduction}

\Q Soit
$
A=
\smallmat{
1&2&3\\
3&2&1\\
1&1&1}$.
Appliquer à $A$ les commandes
\begin{verbatim}
  characteristic_polynomial
  minimal_polynomial
  eigenvalues
  eigenvectors_right
  eigenspaces_right
  eigenmatrix_right
\end{verbatim}
Cette dernière commande rend un couple de matrices $(B,U)$. Vérifier que
$U^{-1}AU=B$.

\Q Même exercice avec $B=\smallmat{ 0&2\\ 1&0}$. 

\Q Avec cette matrice $B$, on utilise des approximation
car ses valeurs propres sont $\pm\sqrt2$. On peut aussi
manier formellement les valeurs exactes. Pour cela, définir
$\texttt{K}=\QM(\sqrt2)$, puis $\texttt{M2K}=M_2(K)$. Alors on indique
que l'on veut considérer $B$ comme élément de $M_2(K)$ en écrivant
\kbd{B = M2K(B)}. Appliquer les fonctions précédentes à cette nouvelle
matrice $B$.

\Q Soit $M=
\smallmat{
 0&  0&  1\\
 1&  0&  1\\
 0&  1& -2
}$.
Calculer son polynôme minimal $m$ et vérifier qu'il est irréductible. Soit
$K$ un corps de rupture de $m$. Définir $M_3(K)$ et appliquer {\tt
eigenvalues} à $M$, considérée comme un élément de $M_3(K)$.

\Q Même exercice avec la matrice
$M=
\smallmat{
-3& -1&  1\\
 5&  2& -1\\
 1&  6& -1
}$. Commenter.
%Calculer {\tt factor(m.discriminant())}.
%Définir {\tt L.<c>=K.extension(x^2+379)} 

\Q Reprenons la matrice
$M=
\smallmat{
-3& -1&  1\\
 5&  2& -1\\
 1&  6& -1
}$.
%Définir $\texttt{M3F7}=M_3(\FM_7)$, et poser {\tt M = M3F7(M)}. Essayer la
%fonction {\tt eigenvalues} sur cette nouvelle matrice $M$. 
Définir l'espace
de matrices dans lequel on pourra calculer les valeurs propres de $M$.
Diagonaliser $M$ dans cet espace.

\Q Dans $M_5(\QM)$, on considère les matrices
suivantes.
$$
A=
\frac14
\begin{pmatrix}
-1&1&-4&4&-3\\
1&-1&4&-4&3\\
10&-2&12&-8&6\\
7&1&4&0&3\\
6&-6&8&-8&10
\end{pmatrix}
\hbox{, \quad}
B=\frac14
\begin{pmatrix}
12&-4&4&-4&2\\
-4&12&-4&4&-2\\
17&-25&28&-24&13\\
17&-25&20&-16&13\\
-8&8&-8&8&4
\end{pmatrix}.
$$
Calculer $AB-BA$. Trouver une matrice $P\in\Gl_5(\QM)$ telle que $P^{-1}AP$
et $P^{-1}BP$ soient diagonales.

\section{Algorithme de Strassen}
Soient $A$ et $B$ deux matrices $n\times n$ sur un corps, où $n$ est
une puissance de $2$. Nous voulons calculer le produit $C=AB$ le plus
économiquement possible. On subdivise $A$, $B$ et $C$ en quatre blocs de
taille $n/2\times n/2$ :
$$
A=
\begin{pmatrix}
A_1 & A_2\\
A_3 & A_4\\
\end{pmatrix}
,\quad B=
\begin{pmatrix}
B_1 & B_2\\
B_3 & B_4\\
\end{pmatrix}
\quad \text{et}\quad C=
\begin{pmatrix}
C_1 & C_2\\
C_3 & C_4\\
\end{pmatrix}.
$$
Soit
$$
\left\{\begin{array}{lll}
P_1&=&A_1(B_2-B_4)\\
P_2&=&(A_1+A_2)B_4\\
P_3&=&(A_3+A_4)B_1\\
P_4&=&A_4(B_3-B_1)\\
P_5&=&(A_1+A_4)(B_1+B_4)\\
P_6&=&(A_2-A_4)(B_3+B_4)\\
P_7&=&(A_1-A_3)(B_1+B_2)
\end{array}\right.
$$
\Q Écrire $C_2$ en fonction de $P_1,P_2$; $C_3$ en fonction de $P_3, P_4$;
$C_1$ en fonction de $P_4, P_5, P_2$ et $P_6$; $C_4$ en fonction de
$P_1$, $P_5$,  $P_3$ et $P_7$.

\Q Combien d'additions et multiplications de matrices $n/2\times n/2$ 
sont utilisées ?
\Q En déduire la complexité (en terme d'opérations dans $K$) de l'algorithme récursif associé, qui calcule 
$C = AB$. \comment{(C'est l'algorithme de Strassen).}\\
\noindent Quelle est la complexité de l'algorithme naïf de multiplication de matrices ?

\Q Implémenter l'algorithme de Strassen, et le tester sur des matrices aléatoires de dimension $16$ dans $\FF_{13}$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Exercice possible sur les équations différentielles
%% (commenté pour l'instant, c'est un exercice des années
%% précédentes)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse %% comment this and the \fi command on the last line to uncomment the exercise
\section{Équation différentielle}
\Q Reprenons l'équation différentielle de la feuille $2$
\begin{equation}\label{homo}
(3t-2)y''+2t^2y'-2(2t-1)y=0
\end{equation}
Nous allons utiliser le calcul matriciel pour calculer les solutions
polynomiales de degré inférieur ou égal à $2$ de cette équation
différentielle, toujours en utilisant un polynôme à coefficients
indéterminés. Comme dans la feuille $2$, on définit~:
\begin{verbatim}
  PR = PolynomialRing(QQ,3,'a')
  v = list(PR.gens())
  PRt.<t> = PolynomialRing(PR)
  p = v[2]*t^2+v[1]*t+v[0]
  p1 = diff(p,t)
  p2 = diff(p1,t)
  q = (3*t-2)*p2+2*t^2*p1-2*(2*t-1)*p
  l = q.coeffs()
\end{verbatim}
puis on définit la matrice des coefficients de $q$:
\begin{verbatim}
  M = matrix(QQ,3,3, lambda i,j: l[i].coefficient(v[j]))
\end{verbatim}
Alors {\tt M.right\_kernel()} donne l'ensemble des polynômes de degré
inférieur ou égal à $2$ qui sont solutions de (\ref{homo}).

\Q En utilisant {\tt solve\_right}, trouver les polynômes de degré inférieur
ou égal à $2$ qui sont solution de l'équation avec second membre
$$ (3t-2)y''+2t^2y'-2(2t-1)y = 2t^2+10t-6. $$

\Q Même question avec l'équation
$$ (3t-2)y''+2t^2y'-2(2t-1)y = -6t^2+10t+2. $$

\Q Écrire une fonction qui, étant donnés $a$, $b$, $c$, $d$ dans $\QM[t]$ et
un entier $n$ utilise cette méthode pour donner les polynômes de degré
inférieur ou égal à $n$, qui sont solutions de l'équation
$$ay''+by'+cy=d.$$
\fi


\end{document}
