\documentclass[12pt]{article}
\usepackage{kb}
\usepackage{kbexo}
\course{Préparation à l'agrégation}
\num{13}

\begin{document}
\mapletitle{Compléments d'algèbre linéaire}

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

\begin{exo}
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$ et $P_2-P_6$; $C_4$ en fonction de
$P_1+P_5$ et $P_3+P_7$.

\Q Combien d'additions et multiplications de matrices $n/2\times n/2$ 
sont-elles utilisées ?
\Q En déduire que l'algorithme récursif associé calcule 
$C = AB$ en utilisant $O(n^{\log_27})$ opérations dans $K$.
\end{exo}

\begin{exo}[Polynôme minimal d'une suite récurrente linéaire]
Soit $K$ un corps et $(s_0,\dots,s_{2n-1})$ une suite d'éléments de $K$.
Elle vérifie une relation de récurrence linéaire d'ordre $n$
s'il existe $c(T) = \sum_{i\leq n} c_i T^i$ dans $K[T]$ tel que
$$ c_0 s_k + \dots + c_n s_{k+n} = 0,\quad\text{pout tout $0\leq k < n$}.$$

\Q Soit $S := s_{2n-1} + \dots + s_0 T^{2n-1}\in K[T]$, montrer que la
relation ci-dessus est équivalente à l'existence de $a,b$ dans $K[T]$, de
degré $<n$, tels que
$$b = aT^{2n} + c S$$

\Q Montrer que l'algorithme d'Euclide étendu appliqué aux polynômes $T^{2n}$
et $S$ permet de calculer $b$ et $c$ s'ils existent. Plus précisément,
Euclide fournit des suites $(r_i)$, $(u_i)$, $(v_i)$ de polynômes
tels que $r_i = u_i T^{2n} + v_i S$ pour tout $i$: sous l'hypothèse
(nécessaire et suffisante) que $T^n$ ne divise pas $S$, 
$b$ est le premier reste euclidien $r_i$ de degré $<n$; alors
$c = v_i$.
\end{exo}

\begin{exo}[Décomposition de Dunford-Jordan]

En utilisant le lemme de Hensel dans $K[X]/(P^k)$, trouver la décomposition
de Dunford des matrices suivantes.
\begin{small}
$$
\begin{pmatrix}
1&0&0&1&1&0\\
2&2&0&-2&-2&0\\
2&0&-1&1&1&0\\
-5&-1&4&-3&-4&0\\
5&1&-4&4&5&0\\
13&3&-5&5&3&2
\end{pmatrix},
\begin{pmatrix}
1&13&0&0&0&5\\
0&-2&0&0&0&-1\\
-2&-18&1&-1&-1&-6\\
0&-3&0&1&0&-1\\
-2&-23&2&-2&-1&-7\\
0&5&0&0&0&2
\end{pmatrix},
\begin{pmatrix}
1&13&0&5&8&5\\
0&2&0&0&0&-1\\
0&0&3&-1&-1&-6\\
0&0&0&4&0&-1\\
0&0&0&0&5&-7\\
0&0&0&0&0&6
\end{pmatrix}
$$
\end{small}

\begin{verbatim}
def jordan(A):
  P = A.charpoly(x);
  P = P // (P.gcd(derivative(P)));
  Q = derivative(P);
  An = A;
  Ann = An - P(An)*(Q(An)^(-1));
  while An != Ann:
    Ann, An = An-P(An)*Q(An)^(-1), Ann;
  return Ann, A-Ann

D,N = jordan(Matrix(QQ,[[2,3,2],[-1,-2,-6],[1,1,5]]))
\end{verbatim}
\end{exo}

\end{document}
