\documentclass[12pt,a4paper]{article}
%% \usepackage{multicol}

%%
\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage{frcursive}
\usepackage{amssymb}
\usepackage{url}
%%% 

\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.3cm} TP08 Polynome caract{\'e}ristique\hspace{0.3cm}}\hfill   agreg 2016-2017\\ (F.Han\footnote{\url{http://webusers.imj-prg/frederic.han/agreg}}})\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
% restart;maple_mode(0);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); //radians,pas de cmplx, pas de  Sqrt
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exo
Comparez sur quelques exemples pour une matrice $A$ {\`a} cofficients entiers les temps
de calcul de son polynome caract{\'e}ristique par $\det(A-xI)$ (par une m{\'e}thode de
type pivot) et par une fonction d{\'e}di{\'e}e du logiciel.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\exotitre{Polyn{\^o}me Caract{\'e}ristique; Th Cayley-Hamilton. M{\'e}thode de Faddeev}  
Soit $A$ une matrice de taille $n$, $I$ l'identit{\'e} de taille $n$, et
$M=X.I-A$. Nous allons d{\'e}duire de la formule
$$^tM^{adj}.M=M. ^tM^{adj}=\det(M).I\ (*)$$ une
m{\'e}thode pour calculer le polyn{\^o}me caract{\'e}ristique de $A$, et aussi une
preuve du th{\'e}or{\`e}me de Cayley-Hamilton. (o{\`u} $M^{adj}$ est la matrice
adjointe ou comatrice de $M$)

On note $\det(M)=P_A(X)=\sum_i a_i.X^i$ le polyn{\^o}me caract{\'e}ristique de $A$. On
{\'e}crit $^tM^{adj}=\sum_{i=0}^{n-1} B_i.X^i$ o{\`u} $B_i$ est une matrice de
taille $n$. On d{\'e}duit de la formule $(*)$:
$$a_i.I=B_{i-1}-B_i.A \ (**)$$ et $B_{n-1}=a_n.I=I$

On remarque de plus que $P_A'(X)=tr(M^{adj})=\sum_i tr(B_i).X^i$. On
obtient alors les $B_i$ par r{\'e}currence d{\'e}croissante {\`a} partir de $B_n=I$
gr{\^a}ce aux formules\footnote{prendre la trace dans $(**)$}:
$$\left\{\begin{array}{l}
    a_{i}=\frac{tr(B_{i}A)}{i-n}\\
    B_{i-1}=B_i.A+a_i.I
    \end{array}\right.$$
\qusqu Calculer $P_A$ et $A^{adj}$ par cette m{\'e}thode.
% !s!<p>
% monpolyfaddeev(A):={
% local j,a,n,B,P;
% n:=dim(A)[0];a:=1;B:=identity(n);P:=[a];
% for(j:=n-1; j>-1; j--){ 
%    B:=normal(B*A);
%    a:=trace(B)/(j-n);
%    P:=[op(P),a];// ou bien P:=append(P,a);
%    B:=B+a*identity(n);
% }; 
% P;
% };
% !s!
\squ V{\'e}rifiez et faites quelques tests.
% n:=30;A:=matrix(n,n,(u,v)->rand(21)-10);
% normal(poly2symb(monpolyfaddeev(A),x));
%  charpoly(A)-monpolyfaddeev(A);
%time(monpolyfaddeev(A));// pas si mal pour du language interprete
%time(det(A-x*idn(n))); // temps comparable alors que c'est programme en interne
%time(charpoly(A));// bien plus rapide
\squ Donnez une estimation du nombre de multiplications sur le corps de base
pour trouver $P_A$ par cette m{\'e}thode.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% !s!<c>
%-------------------Polynome caracteristique et mineurs diagonaux------------------------------------------------------------------------------
%!s!
\exotitre{Polyn{\^o}me caract{\'e}ristique; Mineurs diagonaux}
 Commencer par poser \code{n:=5;}, on le fera {\'e}ventuellement augmenter
apr{\`e}s. Cr{\'e}er l'ensemble $I_n=\{1,\dots,n\}$. Comment retirer
l'ensemble $\{2,4\}$ de $I_n$.
% n:=5; In:=%{seq(j,j=0..n-1)%};// on peut aussi utiliser set[]
% In minus %{2,4%};
\qu En utilisant 2 fois \code{seq} cr{\'e}er une proc{\'e}dure \code{extr} de
$(A,I,J)$ qui retourne la matrice $A_{i\in I,j\in J}$
% !s!<m>
% extr(A,II,JJ):={
% matrix([seq([seq(A[ii,jj],jj=JJ)],ii=II)]);
% };
% !s!
\qu On condid{\`e}re une matrice
$A$, formelle de taille $n$, et la matrice diagonale formelle
\linebreak\verb/d:=diag(seq(x[j],j=0..n-1));/
\squ Etudier la documentation sur les d{\'e}riv{\'e}es, d{\'e}riv{\'e}es partielles,
d{\'e}riv{\'e}es d'ordre sup{\'e}rieur et liste des d{\'e}riv{\'e}es 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 diagonaux de taille 3 avec $\frac{\partial
  \det(A-d)}{\partial x[u] \partial x[v]}$ {\'e}valu{\'e} en $0$
% purge(a,x);
% n:=5;A:=matrix(n,n,(u,v)->a[u,v]);
% d:=diag(seq(x[j],j=1..n));
% II:=In minus %{0,2%};// on essaye (i,j)=(0,2)
% 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,0};// on essaye (i,j)=(4,0)
% extr(A,II,II);
% dij:=diff(det(A-d),x[4],x[0]);
% normal(det( extr(A,II,II)) - subs(x=[0,0,0,0,0],dij));
\squ On note $P=\det(A-x*I)$ le polyn{\^o}me caract{\'e}ristique de $A$. Quels
sont ses coefficients en fonction de ses d{\'e}riv{\'e}es?
% B:=A-x*identity(n);
% d:=[seq(normal(subst(diff(det(B),x,j),x=0)/j!),j=n..0)];
% P:=charpoly(A);
% ratnormal(P+d);
\squ Conclure\footnote{Pour une application de cette formule, TP graphes,
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$} diagonaux de taille $i$ de $A$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\qusqu Comment obtient t'on le coefficient de $x^3$ de
\verb/3*x^4+2*x^3+y^3/. Comment cr{\'e}er une matrice ayant les m{\^e}mes
dimensions que la matrice \code{A:=matrix(3,4,2);}
%% coeff(3*x^4+2*x^3+y^3,x,3);
%% A:=matrix(3,4,2);matrix(op(dim(A)));
\squ Cr{\'e}er une proc{\'e}dure \code{cf(P,k);} qui retourne
le coefficient 
de $x^k$ de l'{\'e}l{\'e}ment $P\in{\cal M}_n[x]$. \danger Que devient votre
proc{\'e}dure si $x$ est d{\'e}clar{\'e} comme un variable locale? (On peut en revanche le
d{\'e}clarer comme un symbole)
%% !s!<p>
%% cf:=proc(P,k)
%% local i,j;
%% matrix(op(dim(P)),(i,j)->coeff(P[i,j],x,k));
%% end_proc;
%% !s!
\qu Remarquer/illustrer sur un exemple de taille 3 (lignes par lignes, sans
programmer) que l'on peut d{\'e}finir une division  d'un {\'e}l{\'e}ment $P(X)$ de
${\cal M}_n[X]$ par $X.I-A$ et que son reste est  $P(A)$. On pourra
par exemple prendre pour $P$ un polyn{\^o}me de degr{\'e} $4$ dont les
coefficients sont des matrices de petits entiers al{\'e}atoires, et $A$
une matrice $3\times 3$ formelle.

\danger $P$ est un {\'e}l{\'e}ment de ${\cal M}_n[X]$ qui
n'est pas commutatif. On travaillera donc toujours du m{\^e}me cot{\'e}, pour
les divisions et pour donner un sens {\`a} $P(A)$. Plus pr{\'e}cis{\'e}ment, on a
le ``th{\'e}or{\`e}me de Bezout g{\'e}n{\'e}ralis{\'e}'' (Cf Gantmacher): Le reste de la
division {\`a} droite\footnote{On entend par division {\`a} droite: $P=Q.(xI-A)+R$} de $P(x)$ par $x.I-A$ est $\sum p_i.A^i$ celui de la
division {\`a} gauche est $\sum A^i.p_i$ o{\`u} $p_i$ sont les coefficients de
$P$. ($p_i\in{\cal M}_n$).
%% P:=matrix(3,3,(i,j)->add(rand(7)*x^l,l=0..4));
%%A:=matrix(3,3,(i,j)->a[i,j]);
%%cf(P,4);
%%R:=P;k:=4;Q:=0;
%%R:=normal(R-cf(R,k)*x^(k-1)*(x*identity(3)-A));Q:=cf(R,k)*x^(k-1)+Q:k:=k-1;
%%R:=normal(R-cf(R,k)*x^(k-1)*(x*identity(3)-A));Q:=cf(R,k)*x^(k-1)+Q:k:=k-1;
%%R:=normal(R-cf(R,k)*x^(k-1)*(x*identity(3)-A));Q:=cf(R,k)*x^(k-1)+Q:k:=k-1;
%%R:=normal(R-cf(R,k)*x^(k-1)*(x*identity(3)-A));Q:=cf(R,k)*x^(k-1)+Q:k:=k-1;
%%R2:=add(cf(P,i)*A^i,i=0..4);
%%normal(R2-R);
En d{\'e}duire une preuve
du th{\'e}or{\`e}me de Cayley-Hamilton.\footnote{En effet $(*)$ montre que $P$
  est divisible par $X.I-A$}
