\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{ 0.5cm} TP04: D\'eterminants\hspace{0.5cm}}\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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Gauss-Bareiss; Bordant, applications}
(Cf H. Cohen, "A course in computationnal algebraic number theory"; et
dans xcas \verb/aide>algorithmes>pivot/)
Cr\'eer une matrice $M$ formelle carr\'ee de taille 3.
\qu Comment afficher tr\`es simplement la premi\`ere ligne de $M$?
\qu On consid\`ere une suite ( $0 \leq k < n$, l'indice $k$ sera
parfois not\'e en exposant) de matrices carr\'ees de
taille $n-k$: 
$M_k=(a_{i,j}^{(k)})_{k+1\leq i,j   \leq n}$ d\'efinie par la relation de
r\'ecurence suivante: ($c_0=1$)
\begin{center}
$1\leq k<n,\  a^{(k)}_{i,j}=\frac{1}{c_{k-1}}
\left|\begin{array}{cc}
    a^{(k-1)}_{k,k}&a^{(k-1)}_{k,j} \\
    a^{(k-1)}_{i,k} & a^{(k-1)}_{i,j}
\end{array}\right|$, $c_k=a^{(k-1)}_{k,k}$
\end{center}
{\sc Proposition:} {\it Toutes les divisions par $c_k$ sont exactes, et
  $\det(M_k)=c_k^{n-k-1} \det(M_0) $. En particulier $\det(M_0)=c_n$.}
\squ Montrer la proposition pour une matrice formelle $3\times 3$
\squ A partir d'une matrice formelle $M_0=A$ de taille 5,
illustrer\footnote{Ne pas utiliser d'indice $k$ ie
  ecraser les $M$ interm\'edaires sauf $A$. Si l'on n'y arrive pas, le
  faire lorsque $A$ est de taille 3 } le fait
que: $$a_{i,j}^{(k)}=\det(A_{u,v})_{u\in I,v\in J}$$ o\`u $I=\{1,\dots,k,i\}$,
$J=\{1,\dots,k,j\}$. 
% n:=5;A:=matrix(n,n,(i,j)->a[i,j]);M:=A;c:=1;k:=1;
% !s!<c>
% Pour M, On peut ecraser car i,j>k
%!s!<m>
%Lk:=[];
%for i from k+1 to n do 
%for j from k+1 to n do 
%M[i,j]:=simplify(1/c*(M[k,k]*M[i,j]-M[i,k]*M[k,j]));
%II:=[seq(l,l=1..k),i];JJ:=[seq(l,l=1..k),j];
%AIIJJ:=matrix([seq([seq(A[u,v],v=JJ)],u=II)])
%Lk:=[op(Lk),AIIJJ];
%print(simplify(det(AIIJJ)-M[i,j]));
%od:od:
%c:=M[k,k]:k:=k+1;
%Lk;
% !s!<m>
%Lk:=[];
%for i from k+1 to n do 
%for j from k+1 to n do 
%M[i,j]:=simplify(1/c*(M[k,k]*M[i,j]-M[i,k]*M[k,j]));
%II:=[seq(l,l=1..k),i];JJ:=[seq(l,l=1..k),j];
%AIIJJ:=matrix([seq([seq(A[u,v],v=JJ)],u=II)])
%Lk:=[op(Lk),AIIJJ];
%print(simplify(det(AIIJJ)-M[i,j]));
%od:od:
%c:=M[k,k]:k:=k+1;
%Lk;
% !s!<m>
%Lk:=[];
%for i from k+1 to n do 
%for j from k+1 to n do 
%M[i,j]:=simplify(1/c*(M[k,k]*M[i,j]-M[i,k]*M[k,j]));
%II:=[seq(l,l=1..k),i];JJ:=[seq(l,l=1..k),j];
%AIIJJ:=matrix([seq([seq(A[u,v],v=JJ)],u=II)])
%Lk:=[op(Lk),AIIJJ];
%print(simplify(det(AIIJJ)-M[i,j]));
%od:od:
%c:=M[k,k]:k:=k+1;
%Lk;
% !s!<m>
%Lk:=[];
%for i from k+1 to n do 
%for j from k+1 to n do 
%M[i,j]:=simplify(1/c*(M[k,k]*M[i,j]-M[i,k]*M[k,j]));
%II:=[seq(l,l=1..k),i];JJ:=[seq(l,l=1..k),j];
%AIIJJ:=matrix([seq([seq(A[u,v],v=JJ)],u=II)])
%print(simplify(det(AIIJJ)-M[i,j]));
%od:od:
%c:=M[k,k]:k:=k+1;
%!s!
\squ Montrer que
$\det(M_k)=\frac{c^{n-k-1}_k}{c_{k-1}^{n-k}}\det(M_{k-1})$, et prouver la
proposition.
%!s!<c>
%On passe de Mk-1 a Mk par: L_i<-(c_k.L_i-a_{i,k}.L_k)/c_{k-1}. Chacune de ces operatons
%multiplie le determinant par c_k/c_{k-1}, et on ne touche pas a la premiere ligne de
%M_{k-1}. Donc le determinant de M_{k} fois le premier coefficient de M_{k-1} (qui est
%c_k) vaut  (c_k/c_{k-1})^(dim Mk) fois det M_(k-1). d'ou la formule:
%det(M_k)=(c^{n-k-1}_k)/(c_{k-1}^{n-k}) *det(M_{k-1}). D'autre part, la matrice M_{n-1}
%est de taille 1 et vaut c_n. Ce qui donne bien det(M_0)=c_n. Donc c_n est entier. Si l'on
%applique ce resultat a A_{I,J}, alors le dernier c sera a^(k)_{i,j}, il vaudra donc det
%A_{I,J} et sera entier. Ce qui prouve que ces divisions sont exactes. 
%!s!
\squ En d\'eduire une variante  du pivot o\`u l'on n'introduit pas de
d\'enominateurs. (Gauss-Bareiss) Remarquer qu'elle est impl\'ement\'ee (Cf
par exemple \code{pivot}). Illustrez l'importance de la simplification
en affichant le produit des $c_k$ pour une matrice de taille 10 \`a coefficients
entiers  entre $-10$ et $10$
% n:=10;A:=matrix(n,n,(i,j)->rand(21)-10);M:=A;c:=1;k:=1;s:=1;
%!s!<m>
%for k from 1 to n-1 do
%for i from k+1 to n do 
%for j from k+1 to n do 
%M[i,j]:=simplify(1/c*(M[k,k]*M[i,j]-M[i,k]*M[k,j]));
%od:od:
%c:=M[k,k]:k:=k+1;s:=s*c;
%od:s; 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%!s!<c>
%-------------------------------------------------------------------------------------------------------------------------  
%!s!
\exotitre{Tests; Utilisation de pari}
La m\'ethode du pivot n'est pas forc\'ement int\'eressante si la complexit\'e
des coefficients augmente trop.
\qusqu Cr\'eer une matrice $A$ de taille $4$ \`a coefficients entiers entre
$-10$ et $10$. On pose \code{B:=A-x*identity(4);}. R\'eduire $B$ en
utilisant la commande \code{pivot} (et \code{normal} pour les
simplifications) le long de la diagonale, puis recommencer
avec l'autre diagonale. Commentez les coefficients.
% A:=matrix(4,4,(i,j)->rand(21)-10);B:=A-x*identity(4);
% P:=normal(poly2symb(charpoly(A,x)));
% for i from 1 to 3 do B:=normal(pivot(B,i,i)); od;
% simplify(B[4,4]/P);#le dernier terme diagonal est un multiple du poly carateristique
% B:=A-x*identity(4);
% for i from 1 to 3 do B:=normal(pivot(B,5-i,i)); od;
% simplify(B[1,4]/P);#le dernier terme diagonal est un multiple du poly carateristique
\squ Comparez avec le polyn\^ome caract\'eristique de
$A$. (\code{charpoly}, vous pouvez convertir un polyn\^ome $P$ en symbole
avec \code{poly2symb(P,x);}
\qu Cr\'eer une matrice $A$ de taille $k$ \`a coefficients entiers entre
$-10$ et $10$. On essayera d'abord avec
$k=30$ puis lorsque ca sera au point on affectera a $k$ les valeurs
$40$ voire $50$. Et poser: \code{B:=A-x*identity(k);}
\qu Dans cette question nous allons illustrer les temps obtenus par
les differentes m\'ethodes avec un m\^eme logiciel. Il faut pour cela
trouver dans la documentation de votre logiciel comment calculer un
determinant par pivot, par gauss-bareiss, et comment calculer un
polynome caracteristique par une methode specifique. Pour xcas nous
passerons par pari et aussi par xcas. 
Pour utiliser une instruction de pari,  soit
on tape \verb/pari(Mod(2,5)^10)/, soit on tape une fois par session:
\code{pari();} puis l'instruction \verb/pari_charpoly/ ou
\code{charpoly} s'il n'y a pas d'ambigu\"\i t\'e.
\squ Etudier dans la documentation de xcas les diff\'erentes options de
la fonction d\'eterminant, et faites quelques tests.
%pari()#pour charger pari; sinon faire pari_matdet
% k:=100;A:=matrix(k,k,(i,j)->rand(21)-10):
% time(d1:=matdet(A,0));#par gauss-bareiss via pari
% time(d2:=det(A,bareiss));# par bareiss via xcas
% time(d3:=det(A));# par reduction modulaire  via xcas
%d1-d2;d1-d3;
\squ Etudier dans la documentation de pari la fa\c con dont est calcul\'e
le d\'eterminant, et le polyn\^ome caract\'eristique. 
\squ En utilisant \code{time()} et le calcul du d\'eterminant par pari,
calculez $\det(B)$ par pivot usuel et par Gauss-Bareiss, et le
polyn\^ome caract\'eristique par Faddeev via pari(Calcul de l'adjointe avec
les traces). (Eventuellement \'etudier la doc xcas partie
algorithmes). Attention, \code{charpoly} existe aussi sous xcas, pour
\^etre sur d'utiliser celui de pari, taper \verb/pari_charpoly/
% k:=30;A:=matrix(k,k,(i,j)->rand(21)-10):B:=A-x*identity(k):
% time(d1:=matdet(B,1));#par pivot via pari
% time(d2:=matdet(B,0));#par gauss-bareiss
% !s!<c>
% time(d3:=det(B,rational_det));# par pivot via xcas (un peu long)
%!s!
% time(d4:=det(B,bareiss));# par bareiss via xcas
% time(d5:=det(B,lagrange));# par lagrange via xcas
% normal(d1-d2);normal(d1-d4);normal(d1-d5);
% time(pari_charpoly(A,0));#par faddeev
% k:=40;A:=matrix(k,k,(i,j)->rand(21)-10):B:=A-x*identity(k):
% !s!<c>
%pour k>40 par pivot usuel on depasse la taille apr defaut de pari,
%donc on arrete.
%!s!
% time(matdet(B,0));#par gauss-bareiss
% time(pari_charpoly(A,0));#par faddeev
% k:=50;A:=matrix(k,k,(i,j)->rand(21)-10):B:=A-x*identity(k):
% time(matdet(B,0));#par gauss-bareiss
% time(pari_charpoly(A,0));#par faddeev
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%!s!<c>
%-----------------------------------------------------------------------------------------------------------
%!s!
\exo
  \qu Cr\'eer un exemple $4\times 4$ pertinent (avec par exemple deux pivots
  nuls) pour expliquer le pivot
  de Gauss au Jury. Le faire \'etapes par \'etapes par produit de
  matrices. On pourra faire une fonction \code{T(i,j,s)} pour les
  transformations \'el\'ementaires.
% A := [[0,-2,1,3],[0,0,0,1],[1,1,0,0],[-3,4,1,0]];
% B:=matrix(4,4):B[1,2]:=1:B[2,1]:=1:B[3,3]:=1:B[4,4]:=1:B;
% B*A;
%!s!<m>
% T:=proc(i,j,a)
% local TT;  
% TT:=identity(4):TT[i,j]:=a:TT;
% end proc;
%!s!  
% T(3,1,1/2)*B*A;
% T(4,1,3/2)*T(3,1,1/2)*B*A;
% F:=matrix(4,4):F[1,1]:=1:F[3,3]:=1:F[2,4]:=1:F[4,2]:=1:F;
% F*T(4,1,3/2)*T(3,1,1/2)*B*A;#On compose les transpositions
\qu Utiliser \code{LU} pour ce m\^eme syst\`eme et
  expliquer le lien, mais aussi la diff\'erence.
% LU(A,L,U,P);inv(P)*L*U-A;
  \qusqu Notons $\sigma$ la transposition $(k,l)$, et $S$ la matrice
  associ\'ee \`a la transposition des $k$ et $l$ i\`emes vecteurs de
  base. Etudier $S.T(i,j,s)$ et $T(i',j',s).S$.
% !s!<c>
%il faut deplacer les transpositions: On a S.T(i,j,s)=T(i',j',s).S pour i=\sigma(i'),j=\sigma(j') 
%!s!
  \squ Comment obtenir la d\'ecompostion LU \`a partir du pivot?
%U:=T(4,3,-2)*F*T(4,1,3/2)*T(3,1,1/2)*B*A;
%L:=(F*T(3,1,-1/2)*F^(-1))*(F*T(4,1,-3/2)*F^(-1))*T(4,3,2);
%S:=B*F^(-1);
%S*L*U-A;  
\newpage
\end{multicols}
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\qu 

\exotitre{Mini-expos\'e: pr\'eparation 15min}
A l'oral on cherche souvent un exemple o\`u l'on d\'etaille les \'etapes \`a
la main pour accompagner une explication orale. Il est donc important
d'obtenir des illustrations courtes o\`u l'on est sur d'aboutir en peu
de temps, ce qui permet ensuite de continuer \`a comprendre le texte.

Exemple, en utilisant la commande \code{pivot}

\exo
\qu Remarquer que votre logiciel est trop sophistiqu\'e pour les erreurs
d'arrondis ce qui pose probl\`eme pour illustrer les avantages
num\'eriques de LU. Par exemple on voudrait ne travailler qu'avec 2 chiffres:
essayer: \code{Digits:=2;a:=approx(1/3);} \code{a*3;0.33*3;}  
%%r:=rand(-10..10);
%%A:=matrix(4,4,r);

%%LU(A,L,U,P);inv(P)*L*U;A
%%#maple selon la doc de linalg, en taille <=4, il n'utilise pas LU.
%%inverse(A);inv(U)*inv(L)*P;inverse(A)*A;
%%\qu Etudions maintenant le cas o\`u l'inverse est calcul\'e par la m\'ethode
%%LU, obtient t'on forcement la m\^eme chose en calculant en flottants:
%%$(L.U)^{-1}(v)$ et $U^{-1}(L^{-1}(v))$?
%%# Non, la mutiplication des flottants est commutative mais pas associative.
%%!s!<m>
%%ml:=proc(A,B)
%%local C,i,j,k;
%%Digits:=2; approx_mode:=1;
%%for i from 1 to 4 do
%%for j from 1 to 4 do
%%C[i,j]:=sum(round(A[i,k]*B[k,j]),k=1..4)
%%od;od;C;
%%end proc;
%%
