\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}{15\baselineskip}
\topmargin=-6\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}

\begin{document}
\columnsep 0.7cm
\noindent{Universit\'e de Paris 7 \hfill \framebox{\Large \bf    \hspace{ 1cm} TP4 diviseurs \'el\'ementaires\hspace{1cm}}\hfill   agreg 2007 (F.Han)}
\begin{multicols}{2}[]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\def\code#1{{\tt #1}}
%% 
%%\begin{minipage}[t]{0.46\textwidth}
% interface(screenwidth=120);
%with(linalg):with(LinearAlgebra):
\exo
\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'inter\^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;
\qu Comment d\'etruire une ligne ou une colonne d'une matrice?
%DeleteRow(Matrix([[1,1],[2,3]]),2);#pour une colonne: DeleteColumn
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Matrices $GL(\rela)$-\'equivalentes}\footnote{$A\sim B \iff
  \exists P,Q \in GL(\rela),\  P^{-1}.A.Q=B$} 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.
\qu Faire une proc\'edure \code{minval} qui donne le couple $(i,j)$ tel que $a_{i,j}$
soit un coefficient de $a$ ayant la plus petite valeur absolue non
nulle. (Elle pourra \'eventuellement retourner $(0,0)$ si $A$ est la matrice nulle)
% minval:=proc(A)
% m:=0;u:=0;v:=0;
% # NB: On retourne 0,0 si A est nulle
% for i from 1 to Dimension(A)[1] do
% for j from 1 to Dimension(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;
\squ On prend le  coefficient ayant la plus petite valeur absolue non
nulle d'une matrice $A$ \`a co\'efficients entiers notons le
$a_{i,j}$. Faire une proc\'edure qui re\c coit $A,i,j,l$ et donne une
matrice $U\in GL_n(\rela)$ telle que $a'_{i,l}$ soit le reste de la
division de $a_{i,l}$ par $a_{i,j}$.
\squ Faire une proc\'edure \code{trans} qui donne une matrice $A'$,
$GL(\rela)$-\'equivalente \`a $A$, telle que $\forall l\in\{1\dots n\}$,
$a'_{i,l}=a_{i,l} \mbox{   mod }
a_{i,j}$ et  $a'_{l,j}=a_{l,j} \mbox{ mod }a_{i,j}$.
% #############
% trans:=proc(A,i,j)
% n:=Dimension(A)[1];
% U:=Matrix(n,n)+1;
% V:=Matrix(n,n)+1;
% 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;
% #####
% 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 cycliques. 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 conjugu\'ee via une permutation \`a une
matrice diagonale. Dans notre proc\'edure on ne cherchera pas \`a trouver
cette permutation.)
% Zequiv:=proc(A)
% k:=0;
% n:=Dimension(A)[1];
% l:=[seq(0,k=1..n)];
% B:=A;
% (i,j):=minval(B);
% while((i,j)<>(0,0)) do
% B:=trans(B,i,j);
% if (i,j)=minval(B) then k:=k+1;l[k]:=B[i,j];B:=DeleteRow(DeleteColumn(B,j),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
% DiagonalMatrix([seq(l[k],k=1..n)]);
% end proc;
% #Exemple:
% A:=Matrix([[2,2,2],[6,12,6],[6,4,6]]);
% Zequiv(A);
% A[3,3]:=12;
% Zequiv(A);
% #On v\'erifie que A et Zequiv(A) ont bien meme forme de smith:
% ismith(A), ismith(Zequiv(A));
\squ Obtient t'on forc\'ement les diviseurs \'el\'emen\-taires?
%#Non, par exemple:
%A:=Matrix([[4,0,0],[0,6,0],[0,0,8]]);
\squ 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) 
%#ca sera forc\'ement le pgcd(d_1,...,d_n) car  l'algorithme reste sur la premiere ligne.
%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);
%%%%%%
% transC:=proc(A,i,j)
% n:=Dimension(A)[1];
% U:=Matrix(n,n)+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;
% A.U;
% end proc;
% ZequivC:=proc(A)
% k:=0;
% n:=Dimension(A)[1];
% l:=[seq(0,k=1..n)];
% B:=A;
% (i,j):=minval(B);
% while((i,j)<>(0,0)) do
% B:=transC(B,i,j);
% if (i,j)=minval(B) then k:=k+1;l[k]:=B[i,j];B:=DeleteRow(DeleteColumn(B,j),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
% DiagonalMatrix([seq(l[k],k=1..n)]);
% end proc;
\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{Zequiv(C)} a des matrices bien choisies. Cr\'eer une procedure
\code{elem} qui le fasse.
% elem:=proc(A)
% n:=Dimension(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:=DeleteRow(DeleteColumn(D,1),1);
% od;
% [op(L),D[1,1]];
% end proc;
% A:=Matrix([[2,2,2],[6,12,6],[6,4,12]]);
% elem(A);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\newpage
\end{multicols}
\end{document}

