\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} TP09 Anneaux principaux\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
\exotitre{}
\qu Quelle est la bonne instruction pour calculer le pgcd de 2
entiers, 3 entiers, et celle de 2 polyn\^omes?
%gcd(6,3);#Attention, a priori pour lui c'est des polynomes, on a dela chance il les normalise bien.
%gcd(x*(x+3),2*x);
%igcd(4,6,8);
\qu Les majuscules et les minuscules: essayer: \code{gcd(2*X,4*X);}
 \code{Gcd(2*X,4*X);} \verb/evala(Gcd(2*X,4*X));/
 \linebreak\verb/gcdex(2*x^3,9*x^2+x,x,'a','b');a;b;/ (o\`u $a$  
et $b$ sont des variables libres)
\qu L'int\'er\^et de ne pas \'evaluer tout de suite: \code{gcd(x+2,x) mod 2;}
et \code{Gcd(x+2,x) mod 2;}
\qusqu Comment trouver le quotient et le reste d'une division  d'entiers?
Quel est le pgcd d'un entier avec $0$?
%iquo(13,6);igcd(6,0);  
\squ Pour les entiers: Quelle instruction permet de
r\'ecup\'erer un couples de bezout?
% igcdex(4,15,'a','b');#pour un couple de bezout:
% 4*a+15*b;
\qusqu Comment d\'etruire une ligne ou une colonne d'une matrice?
%delrows(matrix([[1,1],[2,3]]),2..2); #pour une colonne: delcols
\squ Quelle instruction permet de trouver une matrice diagonale $GL(\rela)$
\'equivalente \`a un \'el\'ement de ${\cal}_n(\rela)$ donn\'e?
% A:=diag([3,6,18,36]);B:=matrix(4,4,(i,j)->rand(7)-3);det(B);
% ismith(A*B);
% !s!<c>
%-----------------------------------------------------------------------------------------------------
%!s!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Matrices $GL(\rela)$-\'equivalentes}\footnote{$A\sim B \iff
  \exists P,Q \in GL(\rela),\  P^{-1}.A.Q=B$}
(Cf par exemple le\c con "op\'erations lignes/colonnes")
L'algorithme permettant d'obtenir les facteurs invariants: On le
fait sur $\rela$ ou dans le cadre Euclidien, car on n'a pas
d'algorithme pour obtenir les nombres de Bezout dans le cadre
principal.

Cet algorithme est d\'ej\`a programm\'e dans xcas sur $\rela$. (\code{ismith}) On
pourrait aussi le faire dans $k[x]$, mais nous nous limiterons ici \`a
$\rela$. Nous allons proc\'eder en quelques \'etapes.
1a) Trouver un minimum non nul (au sens du stathme) de la matrice. 1c) par
op\'erations lignes/colonnes on fait diminuer les autres coefficients de sa ligne et de
sa colonne. 2) On recommence 1a) et 1c) tant que c'est possible. lorsque l'on a
fini, le minimum n'a que des 0 sur sa ligne et sur sa colonne. On garde cette
valeur, on raye la ligne et la colonne, et l'on recommence avec la matrice plus
petite. On obtient alors une matrice diagonale \'equivalente (dans l'anneau) \`a la
matrice de d\'epart, ce qui est d\'ej\`a bien. 3) On peut passer de cette forme aux diviseurs \'el\'ementaires
par lemme chinois, ou en continuant l'algorithme de maniere un peu modifi\'ee.

\qusqu Faire une proc\'edure \code{minval} qui donne le couple $(i,j)$ tel que $A_{i,j}$
soit un coefficient de la matrice $A$ ayant la plus petite valeur absolue non
nulle. (Elle pourra \'eventuellement retourner $(0,0)$ si $A$ est la matrice nulle)
%!s!<p>
% minval:=proc(A)
% local m,u,v,i,j;
% m:=0;u:=0;v:=0;
% # NB: On retourne 0,0 si A est nulle
% for i from 1 to dim(A)[1] do
% for j from 1 to dim(A)[2] do
% if ((abs(A[i,j])>0) and ((m=0) or (abs(A[i,j])<m))) then m:=abs(A[i,j]);u:=i;v:=j; end if;
% od;
% od;
% u,v;end proc;
%!s!
% A:=matrix([[6, 0, 7, 9], [6, 8, 6, 9], [3, 2, 4, 6], [3, 2, 3, 3]]);
%minval(A);
\squ Prendre\footnote{On s'entraine \`a la main sur un exemple, pour mieux faire
  la proc\'edure de la question suivante}  un exemple \`a coefficients entiers not\'e $A$. Rep\'erer son plus petit
coefficient non nul: $A_{i,j}$ en valeur absolue, et cr\'eer une matrice $U\in
GL(\rela)$ 
 telle que $(A.U)_{i,l}$ soit  le reste de la
 division de $A_{i,l}$ par $A_{i,j}$ pour $l\neq j$, et $(A.U)_{i,j}=A_{i,j}$.
% (i,j):=minval(A);
% U:=identity(4);
%!s!<c>
%normalement il faudrait faire bouger l dans {1..4} sauf j, c'est plus simple de
%ne pas mettre de test, et de corriger U[j,j] ensuite
%!s! 
% for l from 1 to 4 do U[j,l]:=-iquo(A[i,l],A[i,j]) od:U[j,j]:=1:U;
%A*U; 
\squ Faire une proc\'edure \code{trans(A,i,j)} qui pour une matrice $A$ telle que
$A_{i,j}\neq 0$ donne une matrice $A'$,
$GL(\rela)$-\'equivalente \`a $A$, telle que $\forall l\in\{1\dots n\}-\{j\}$,
$|A'_{i,l}|<|A_{i,j}|$ et $\forall l\in\{1\dots n\}-\{i\}$ $|A'_{l,j}|<|A_{i,j}|$.
%!s!<p>
% trans:=proc(A,i,j)
% local n,U,V,l;
% n:=dim(A)[1];
% U:=identity(n);
% V:=identity(n);
% for l from 1 to n do
% V[l,i]:=-iquo(A[l,j],A[i,j]);
% od;
% //on corrige
% V[i,i]:=1;
% for l from 1 to n do
% U[j,l]:=-iquo(A[i,l],A[i,j]);
% od;
% //on corrige
% U[j,j]:=1;
% V*A*U;
% end proc;
% !s!
% A:=matrix([[6, 1, 7, 9], [6, 8, 6, 9], [3, 1, 4, 6], [3, 2, 1, 3]]);
% trans(A,3,1);
\qusqu Essayer\footnote{Remarquer que la d\'ecroissance stricte oblige
  l'algorithme \`a se terminer, ce qui donne une preuve du r\'esultat
  suivant: Tout $\rela$-module de type fini se d\'ecompose en produit de
module monog\`enes. Du m\^eme genre: tout groupe ab\'elien fini est
isomorphe \`a un produit de groupe cyclique.} de programmer la partie qui trouve
une matrice diagonale $GL(\rela)$-\'equivalente \`a $A$. On appellera
cette proc\'edure \code{Zequiv}. (On remarquera qu'une matrice dont les
coefficients non nuls sont les seuls coefficients non nuls de leur
ligne et de leur colonne est \'equivalente  via des permutations \`a une
matrice diagonale. Dans notre proc\'edure on ne cherchera pas \`a trouver
cette permutation.)
%!s!<p>
% Zequiv:=proc(A)
% k:=0;
% n:=dim(A)[1];
% l:=[seq(0,k=1..n)];
% B:=A;
% (i,j):=minval(B);
% //minval retourne les coordonnees du minimum non nul,
% //ou un couple impossible (Ex ici (0,0) en mode maple) si B est nulle.
% while([i,j]<>[0,0]) and size(B)>1 do
% // attention, ne pas oublier de declarer les variables locales
% // dans trans pour  eviter les melanges
% B:=trans(B,i,j);
% if [i,j]=[minval(B)] then
% // on n'a que des zeros sur la ligne i et la colonne j sauf
% // en (i,j) on sauve donc B[i,j] et on raye ligne et colonne.
% k:=k+1; l[k]:=B[i,j];
% B:=delcols(B,j..j);
% B:=delrows(B,i..i);
% //le cas B de taille 1 pose probleme car on ne peut pas rayer
% //une colonne puis une ligne
% fi;
% // ASTUCE: voici comment assigner 2 valeurs d'un coup.
% (i,j):=minval(B);
% end do;
% // On a eventuellement change le signe du determinant
% diag([seq(l[k],k=1..n-1),B[1,1]]);
% end proc;
% !s!
% A:=matrix([[2,2,2],[6,12,6],[6,4,6]]); #Exemple:
% Zequiv(A);
% A[3,3]:=12:A;
% Zequiv(A);
% !s!<c>
% On v\'erifie que A et Zequiv(A) ont bien meme forme de smith:
% !s!
% ismith(A)[2], ismith(Zequiv(A))[2];
\squ Obtient t'on forc\'ement les diviseurs \'el\'ementaires?
% !s!<c>
% Attention, on n'obtient pas forcement les diviseurs elementaires, par exemple:
% !s!
% A:=matrix([[4,0,0],[0,6,0],[0,0,8]]);
% ismith(A)[2];
% Zequiv(A);
\qusqu Dans le cas o\`u $A$ est une matrice du type $
\left(\begin{array}{ccc}
  d_1 & \dots & d_n\\
  0   & \ddots & 0\\
  0 & 0 & d_n
\end{array}\right)$ telle que $d_1$ soit un \'el\'ement de valeur absolue
minimale parmi les coefficients non nuls de $A$, quelle est la valeur du
minimum de la valeur absolue des coefficients non nuls de
\code{ZequivC(A)}? (O\`u \code{ZequivC} est une version de \code{Zequiv}
qui ne travaille que sur les colonnes. ie, on ne touche qu'\`a la
premi\`ere ligne) 
%!s!<c> 
% ca sera forc\'ement le pgcd(d_1,...,d_n) car  l'algorithme reste sur la premiere ligne.
%!s!
% f:=(i,j)->if (i-j)*(i-1)=0 then 1 else 0 fi;
%matrix(3,3,f);A:=matrix(3,3,f)*A;Zequiv(A);
%!s!<c>
%On recopie trans et Zequiv pour qu'ils ne travaillent que sur les  colonnes
%!s!
%!s!<p>
% transC:=proc(A,i,j)
% //attention, si on ne met pas un local n, il modifiera la valeur de n dans ZequivC
% local n,U,l;
% n:=dim(A)[1];
% U:=identity(n);
% for l from 1 to n do
% U[j,l]:=-iquo(A[i,l],A[i,j]);
% od;
% //pour ne pas mettre de test dans la boucle precedente, on n'ecarte pas l=j, mais on le on corrige ici:
% U[j,j]:=1;
% A*U;
% end proc;
% !s!
%!s!<p>
% ZequivC:=proc(A)
% k:=0;
% n:=dim(A)[1];
% l:=[seq(0,k=1..n)];
% B:=A;
% (i,j):=minval(B);
% while([i,j]<>[0,0]) and size(B)>1 do
% // attention, ne pas oublier de declarer les variables locales dans trans pour  eviter les melanges
% B:=transC(B,i,j);
% if [i,j]=[minval(B)] then
% k:=k+1; l[k]:=B[i,j];
% B:=delcols(B,j..j);
% B:=delrows(B,i..i);
% fi;
% // ASTUCE: voici comment assigner 2 valeurs d'un coup.
% (i,j):=minval(B);
% end do;
% // On a eventuellement change le signe du determinant
% diag([seq(l[k],k=1..n-1),B[1,1]]);
% end proc;
% !s!

\squ En d\'eduire que l'on peut obtenir les diviseurs \'el\'ementaires d'une
matrice diagonale de taille $n$ en appliquant au plus $n$ fois
\code{ZequivC(C)} \`a des matrices bien choisies. Cr\'eer une procedure
\code{elem} qui le fasse.
%!s!<p>
% elem:=proc(A)
% n:=dim(A)[1];
% d:=Zequiv(A);
% L:=[];
% for i from 1 to n-1 do
% T:=matrix(n+1-i,n+1-i,f);
% d:=ZequivC(T*d);
% L:=[op(L),d[1,1]];
% d:=delrows(delcols(d,1..1),1..1);
% od;
% [op(L),d[1,1]];
% end proc;
%!s!
% A:=matrix([[2,2,2],[6,12,6],[6,4,12]]);
% elem(A);ismith(A)[2];
% elem(diag(4,6,16));ismith(diag(4,6,16))[2];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


\newpage
\end{multicols}

\end{document}

