\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 D\'eterminants II \hspace{1cm}}\hfill   agreg 2008 (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>
%-------------------Polynome caracteristique et mineurs principaux------------------------------------------------------------------------------
%!s!
\exotitre{Polyn\^ome caract\'eristique; Mineurs principaux}
 Commencer par poser \code{n:=5;}, on le fera \'eventuellement augmenter
apr\`es. Cr\'eer l'ensemble $I_n=\{1,\dots,n\}$. Comment retirer
l'ensemble $\{2,4\}$ de $I_n$.
%n:=5; In:={seq(i,i=1..n)}; In minus {2,4};
\qu En utilisant 2 fois \code{seq} cr\'eer une proc\'edure \code{extr} de
$(A,I,J)$ qui retourne la matrice $A_{i\in I,j\in J}$
% !s!<m>
% extr:=proc(A,II,JJ)
% matrix([seq([seq(A[i,j],j=JJ)],i=II)]);
% end_proc;
% !s!
\qu On condid\`ere une matrice
$A$, formelle de taille $n$, et la matrice diagonale formelle
\verb/d:=diag(seq(x[i],i=1..n));/
\squ Etudier la documentation sur les d\'eriv\'ees, d\'eriv\'ees partielles,
d\'eriv\'ees d'ordre sup\'erieur et liste des d\'eriv\'ees partielles.
% !s!<c>
%Attention, diff(f,x,y) derive en x puis y, alors que diff(f,[x,y])
%donne la liste des derive en x et en y.
%!s!
%diff(x*y,x,y);diff(x*y,[x,y]);
\squ Comparer quelques  mineurs principaux de taille 3 avec $\frac{\partial
  \det(A-d)}{\partial x[i] \partial x[j]}$ \'evalu\'e en $0$
% purge(a,x);
% n:=5;A:=matrix(n,n,(i,j)->a[i,j]);
% d:=diag(seq(x[i],i=1..n));
% II:=In minus {1,3};# on essaye (i,j)=(1,3)
% extr(A,II,II);
% dij:=diff(det(A-d),x[1],x[3]);
% normal(det( extr(A,II,II)) - subs(x=[0,0,0,0,0],dij));
% II:=In minus {2,3};# on essaye (i,j)=(2,3)
% extr(A,II,II);
% dij:=diff(det(A-d),x[2],x[3]);
% normal(det( extr(A,II,II)) - subs(x=[0,0,0,0,0],dij));
% II:=In minus {4,5};# on essaye (i,j)=(4,5)
% extr(A,II,II);
% dij:=diff(det(A-d),x[4],x[5]);
% normal(det( extr(A,II,II)) - subs(x=[0,0,0,0,0],dij));
\squ On note $P=\det(A-x*I)$ le polyn\^ome caract\'eristique de $A$. Quels
sont ses coefficients en fonction de ses d\'eriv\'ees?
% B:=A-x*identity(n);
% d:=seq(normal(subs(x=0,diff(det(B),x,i))/i!),i=n..1);
% P:=charpoly(A);
\squ Conclure\footnote{Pour une application de cette formule, CF TP05,
nombre de triangles dans un graphe, ... prop 3.3, 3.6, 3.7} que le coefficient de $x^{n-i}$ de $P$ est $(-1)^{n-i}$
fois la somme des mineurs\footnote{il y en a $C_n^i$} principaux de taille $i$ de $A$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% !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!
%time(monlagrange(A));
%
\qu Comparer ces 2 m\'ethodes avec un m\^eme logiciel. Par exemple en
utilisant \verb/pari_charpoly/ avec de bonnes options.
\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));
\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{SLn}
\qusqu
En utilisant \code{rand(a,b)} et \code{mod} cr\'eer un \'el\'ement
$(u,v)\in\{1,\dots,n\}^2$ tel que $u\neq v$. (On demande un choix
al\'eatoire uniforme, et pas d'instruction de test. On se documentera
sur  le sens des bornes dans \code{rand(a,b)})
%!s!<m>
% uv:=proc(n)
% u:=rand(1,n+1):v:=(rand(u,u+n-1) mod n)+1:
% [u,v];
% end_proc;
% !s!
% uv(10);
\squ En utilisant une famille de g\'en\'erateurs de $SL_n$ bien connue, en
d\'eduire un moyen de cr\'eer un \'el\'ement de $SL_n$ quelconque.
% !s!<c>
% On obtient tout element de SLn par produit de matrice I+aE_ij
%!s!
\squ Cr\'eer une matrice $B$ non diagonalisable, avec des valeurs propres
d'assez grande multiplicit\'e. Cr\'eer un \'el\'ement de $SL_n$ assez
compliqu\'e, et conjuguer $B$ par cet \'el\'ement. Calculer le polyn\^ome
caract\'eristique de cette matrice par les m\'ethodes pr\'ec\'edentes.
%!s!<m>
% n:=40:k:=200;R:=identity(n):for i from 1 to k do
% T:=identity(n):a:=uv(n):T[a[1],a[2]]:=rand(-5,6):R:=R*T:od;
%!s!
%det(R);
%n:=3:N:=matrix(n,n,(i,j)->if (i=j+1) then 1 else 0 fi)
%T:=diag((3*identity(n)+N),(-2*identity(n)+N),(5*identity(n)+N),(-1*identity(n)+N));
%n:=10;
%T:=diag((3*identity(n)+N),(-2*identity(n)+N),(5*identity(n)+N),(-1*identity(n)+N)):
%A:=R^(-1)*T*R:
%time(pari_charpoly(A,0));
%time(pari_charpoly(A,1));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{introduction aux id\'eaux de Fitting}
\qu Cr\'eer 2 proc\'edures \code{fi(A) }qui calculent le pgcd des
mineurs\footnote{tous, pas seulement les principaux!} de
taille $i$ d'un \'el\'ement $A$ de ${\cal M}_4(\rela)$. (Une pour i=1 et
3, une pour i=2) 
%!s!<p>
%f13:=proc(A)
%II:={1,2,3,4};
%d3:=det(extr(A,{1,2,3},{1,2,3}));
%d1:=A[1,1];
%for i from 1 to 4 do
%for j from i to 4 do
%I1:=II minus {i};I2:=II minus {j};
%d3:=igcd(d3,det(extr(A,I1,I2)));
%d1:=igcd(d1,A[i,j]);
%od;od;
%[d1,d3];
%end proc;
%!s!
%!s!<p>
%f2:=proc(A)
%II:={1,2,3,4};
%d2:=det(extr(A,{1,2},{1,2}));

%for i from 1 to 4 do
%for j from i+1 to 4 do
%for k from 1 to 4 do
%for l from k+1 to 4 do
%I1:=II minus {i,j};I2:=II minus {k,l};
%d2:=igcd(d2,det(extr(A,I1,I2)));
%od;od;
%d2;
%end proc;
%A:=matrix(4,4,(i,j)->rand(21)-10);
\qusqu Cr\'eer une matrice $A\in {\cal M}_4(\rela)$ \`a coefficients dans $\rela$,
assez compliqu\'es, qui soit $GL_4(\rela)$-\'equivalente \`a la matrice diagonale:
$(4,6,24,36)$ 
\squ Trouver dans la documentation du logiciel une instruction permettant de
trouver une matrice diagonale $(d_1,d_2,d_3,d_4)$ avec $d_i|d_{i+1}$ qui soit
$GL(\rela)$-\'equivalente \`a $A$.
\squ Faire afficher la liste des pgcd des mineurs de taille $k$ de $A$ pour
$k\in\{1,\dots,4\}$.
\squ Multiplier $A$ par une transvection, et recalculer la liste
pr\'ec\'edente. Expliquer pourquoi elle ne change pas.
\squ Comment peut on obtenir les $d_i$ \`a partir de cette liste?
\qu D\'eterminer le groupe ab\'elien: $(\rela^4/(\mbox{im} A),+)$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\newpage
\end{multicols}

\end{document}

