\documentclass[12pt,a4paper]{article}
\usepackage{multicol}
\usepackage[french]{babel}
\newfont{\mini}{cmssi10 scaled 480}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\euro{\mbox{\textsf{C}\kern -2.33em{\raise0.24ex\vbox{\small\it =}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\fin{\nolinebreak \raise-0.1em\hbox{$\Box$}}
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}
\def\dual{ ^{\rm v}}
\def\bidual{ ^{\rm vv}}
\def\primedual{ ^{\prime \rm v}}
\def\ideal{{\cal J}}
\def\LL{{\cal L}}
\def\max{{\cal M}}
\def\quot#1#2{\mbox{\raise 0.1cm\hbox{$#1$}{\big /}\raise -0.1cm\hbox{$#2$}}}
\def\danger{{\Large \bf
    $\bigtriangleup$}\kern-0.32cm\raise0.05cm\hbox{\small
    !}\kern0.32cm\lower0.05cm\hbox{}}
%%%%%%%
\newlength{\largeurtmp}
\def\rela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.6\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.6\largeurtmp}
\def\petitrela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.4\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.4\largeurtmp}
\def\petitcomplex{{
    \settoheight{\largeurtmp}{$_C$}{\rm C}\kern -\largeurtmp
    \rule{0.25pt}{1.3\largeurtmp}\kern \largeurtmp}}
\def\complex{{
    \settoheight{\largeurtmp}{Q}{\rm C}\kern -0.66\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.66\largeurtmp}}
\def\ratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.75\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.75\largeurtmp}}
\def\petitratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.6\largeurtmp
    \rule{0.25pt}{0.6\largeurtmp}\kern 0.6\largeurtmp}}
\newcommand{\proj}{{\rm I} \! {\rm P}}
\newcommand{\reel}{{\rm I} \! {\rm R}}
\newcommand{\Fp}{{\rm I} \! {\rm F}_p}
\newcommand{\nat}{{\rm I} \! {\rm N}}
%%%%%%%%%%%%%%%Debut de macros de fiches d'exos
%%les macros sont \exo, \qu, \quskip \squ \qusqu \qusquskip
\newcounter{exo}
\newcounter{question}
\newlength{\lng}
\newcounter{sousquestion}
\setcounter{exo}{1}
\def\exo{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}:}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\exotitre#1{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}: #1}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\qu{

  \addtocounter{question}{1}\arabic{question})
  \setcounter{sousquestion}{1} }
\def\quskip{

  \bigskip
  \qu}
\def\squ{

  \settowidth{\lng}{\arabic{question})
  }\hspace{\the\lng}\alph{sousquestion}) \addtocounter{sousquestion}{1}} 
\def\qusqu{\qu\nopagebreak \vskip -1\baselineskip \squ}
\def\qusquskip{\quskip\nopagebreak \vskip -1\baselineskip \squ}

%%reference pour exos,squ \`a placer avant la question, qu est a placer apres
\def\labelexo#1{\expandafter\edef\csname refexo#1\endcsname {\Roman{exo}}}
\def\refexo#1{\csname refexo#1\endcsname}
\def\labelqu#1{\expandafter\edef\csname refqu#1\endcsname {\arabic{question})}}
\def\refqu#1{\csname refqu#1\endcsname}
\def\labelsqu#1{\expandafter\edef\csname refsqu#1\endcsname
  {\arabic{question}\alph{sousquestion})}} 
\def\refsqu#1{\csname refsqu#1\endcsname}  

%%%%%%%%%%fin de macros fiche d'exos
%%macros taille page
\newlength{\elargir}
\setlength{\elargir}{2.5cm}
\addtolength{\leftmargin}{-\elargir}
%%\addtolength{\hoffset}{-\elargir}
\addtolength{\oddsidemargin}{-\elargir}
\addtolength{\evensidemargin}{-\elargir}
\addtolength{\elargir}{\elargir}
\addtolength{\textwidth}{\elargir}
\addtolength{\textheight}{13\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit\'e de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP06 Alg\`ebre lin\'eaire II \hspace{1cm}}\hfill   agreg 2010 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/agreg})}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
\begin{multicols}{2}
% restart;maple_mode(1);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); #radians,pas de cmplx, pas de  Sqrt
% !s!<c>
%----------------------------calcul du determinant par interpolation----------------------------
%!s!
\exotitre{M\'ethode de Lagrange:}
Nous pouvons interpoler le polyn\^ome caract\'eristique en les valeurs
$0\dots n$. Autrement dit, nous calculons $n+1$ d\'eterminants $d_i$, et
la r\'eponse sera: $\sum_{i=0}^n d_i \prod_{j\neq i}
\frac{(x-j)}{(i-j)}$.
\qu Impl\'ementer cette m\'ethode en utilisant la
fonction d\'eterminant pour les rationnels.
%!s!<p>
%monlagrange:=proc(A)
%local n,i,j,P,L,M;
%n:=dim(A)[1];P:=0;
%L:=[seq(i,i=0..n)];
%for i from 0 to n do
%M:=1;
%for j in L minus [i] do M:=M*(x-j)/(i-j) od;
%P:=P+det(i*identity(n)-A)*M;
%od:
%normal(P);
%end_proc;
%!s!
% k:=50:A:=matrix(k,k,(i,j)->rand(21)-10):
%time(monlagrange(A));
%time(det(A-x*idn(k)));
%
\qu Comparer ces 2 m\'ethodes avec un m\^eme logiciel. Par exemple en
utilisant \verb/pari_charpoly/ avec de bonnes options ou bien la fonction
impl\'ement\'ee dans xcas.
\squ Pour une matrice \`a coefficients entiers.
% k:=50:A:=matrix(k,k,(i,j)->rand(21)-10):
% pari();
% time(pari_charpoly(A,0));
% time(pari_charpoly(A,1));
% pcar(A,lagrange);
% !s!<c>
%Pour obtenir le polynome caract\'eristique sous forme d'un symbole, on passe la
%variable x en seconde option:
%!s!
% pcar(A,x,fadeev);
% pcar(A,pmin);
% det(A-x*idn(k));
\squ Pour une matrice \`a coefficients rationnels.
% k:=30:A:=matrix(k,k,(i,j)->(rand(21)-10)/(rand(4)^2+rand(1,3)^2)):
% time(pari_charpoly(A,0));
% time(pari_charpoly(A,1));
\qu Quel est le cout en terme d'op\'erations sur le corps de base de cette
m\'ethode?
% !s!<c>
%c'est en O(n^4), en fait n^4/3, alors que Faddeev est en n^4. Mais il y a plus
%de fractions chez lagrange, ce qui peut donner l'avantage a faddeev.
%!s!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Polyn\^ome minimal}
%!s!<c>
%-------------------------Polynome minimal-----------------------------------------------
%!s!
\qusqu Comment cr\'eer un polyn\^ome \`a partir de la liste de ses coefficients.
%v:=[seq(i,i=1..8)];
%poly2symb(v,x);
\squ Comment renverser une liste?
%revlist(v);
\squ Comment \'evaluer un polyn\^ome lorsqu'il est sous forme d'un symbole. Comment
le faire \`a partir de la liste de ses  coefficients.
% P:=x^2+1;LP:=[1,0,1];
% subs(x=sqrt(2),P);
%unapply(P,x)(sqrt(2));
% peval(LP,sqrt(2));
Soit $v$ un vecteur et $u$ un endomorphisme de $E$ (E ev de dim $n$). On note
$P_{u,v}$ un g\'en\'erateur de l'id\'eal: $\{P \in k[x], P(u)(v)=0\}$.
\qu Expliquer sur un exemple de taille $n$ al\'eatoire (on commencera par
$n=8$)comment on peut trouver $P_{u,v}$ \`a partir d'une recherche de noyau. 
% n:=8:v:=[seq(i,i=1..n)]; A:=matrix(n,n,(i,j)-> rand(20)-10);
% B:=v; AA:=v
% for i from 1 to n do AA:=A*AA;B:=B,AA; od;
% N:=nullspace(transpose([B]))[1];
% !s!<c>
%Attention, les polyn\^omes commencent a la puissance maximale, il faut inverser l'ordre
%!s! 
% P:=poly2symb(revlist(N),x);
% normal(subs(x=A,P));
\qu Recommencer sur un exemple o\`u $P_{u,v}$ est de degr\'e inf\'erieur \`a la dimension
de $E$. 
% A:=diag(companion(x^4-1,x),companion((x^2-1)^2,x));
% B:=v; AA:=v
% for i from 1 to n do AA:=A*AA;B:=B,AA; od;
% nullspace(B);
%N:=nullspace(transpose([B]))[1];
% P:=poly2symb(revlist(N),x);
% normal(subs(x=A,P));
\squ Optimiser le calcul des $A^k(v)$, et regardez si le polyn\^ome obtenu annule
$A$. Estimer le nombre d'op\'erations sur le corps de base.
% !s!<c>
%On a calcul\'e les A^k(v) par recurence. AA est un vecteur donc A*AA a un cout de
%n^2, et l'on fait n tours, donc c'est en O(n^3)
%!s!
\squ Justifier l'interet de cette m\'ethode pour trouver le polyn\^ome minimal de
$u$.
% !s!<c>
% Il existe toujours un vecteur v tel que P_(u,v)=pmin(u), les vecteurs a eviter
% sont dans ker(P(u)) ou P divise pmin, donc nom fini despace vectoriels a eviter.  
%!s!

\newpage
\end{multicols}

\end{document}

