Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il la signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.

Ce sujet présente la méthode des traces, algorithme de calcul itératif du polynôme caractéristique d'une matrice. Cette méthode fut utilisée par l'astronome français Urbain Le Verrier pour découvrir la planète Neptune en 1845.

Le principe de la méthode est expliqué en partie I. Le programme informatique qui s'en déduit est analysé en partie II. Trois exemples et une application concluent le problème, partie III. Les parties II et III sont indépendantes et pourront être traitées dans un ordre arbitraire.

Dans tout le problème, ndésigne un entier naturel supérieur ou égal à 2 , et

est l'ensemble des matrices carrées à n lignes et n colonnes. On notera I la matrice identité.

I. La méthode des traces

Soit une matrice

. On souhaite en calculer de façon systématique le polynôme caractéristique

défini sur

par :

où les coefficients

ont volontairement été indexés à rebours pour faciliter l'issue de la question I.6 . Dans le cas général, deux difficultés se posent :

Le développement du déterminant, qui doit être réalisé avec une complexité raisonnable.
La collecte des coefficients à l'issue du développement.

Nous verrons en question II. 4 d/ que ces deux contraintes excluent d'office toute méthode de calcul récursif. Des méthodes plus appropriées ont donc été mises au point, dont la méthode des traces expliquée ci-après.

Que vaut ?
b/ Quelle hypothèse du problème et quel théorème du cours vous permettent - au moins d'un point de vue théorique - de factoriser sous la forme :

où les complexes

sont les valeurs propres (non nécessairement distinctes) de A .
c/ Lorsque ces valeurs propres sont connues, elles permettent de remonter aux coefficients de

. Expliquer comment pour les coefficients

Malheureusement, les valeurs propres ne sont pas toujours connues avant le calcul du polynôme caractéristique. Plutôt que de relier les coefficients aux racines, on peut relier les coefficients à des sommes de puissances de valeurs propres, grâce à des formules de Newton (question I. 7 ): c'est la méthode des traces.
2. Le polynôme caractéristique

étant scindé, on rappelle qu'il est possible de trigonaliser A. Il existe une matrice T triangulaire semblable à A dont les coefficients diagonaux sont précisément

. Exprimer en fonction de

les traces de

puis de

pour tout entier naturel p .
3. On note

la dérivée de

. Établir l'identité :

En déduire que, pour assez grand en module :

On fournira un minorant strict m de

le plus précis possible.
5. En conclure que, pour

Démontrer alors que, pour assez petit en module, on a :

On traitera le cas

à part, et on fournira un majorant strict M de

le plus précis possible.
7. En déduire les relations de Newton, valables pour tout

Expliquer sommairement en quoi ces relations permettent d'obtenir le polynôme caractéristique . Restent-elles valables lorsque ?

II. Mise en place de l'algorithme

Dans cette partie, on s'intéresse à la mise en œuvre pratique de l'algorithme des traces et on en évalue les performances en termes de complexité. Cette partie en appelle à l'expérience du candidat en matière de calcul formel : Maple, Mathematica, ou tout simplement le logiciel de sa calculatrice programmable. Dans tous les cas, indiquez sur la copie le langage utilisé.

Dire qu'un programme a une complexité de l'ordre de

(

entiers naturels non nuls) signifie que le nombre d'additions, de multiplications et de divisions élémentaires à réaliser est équivalent à

lorsque n tend vers

. Par exemple, un programme réalisant le produit de n complexes est d'une complexité de l'ordre de n . En revanche, un programme réalisant n fois un produit de

complexes est d'une complexité de l'ordre de

Les logiciels de calcul formel sont souvent livrés avec une fonction permettant de multiplier deux matrices de . Sans reprogrammer cette fonction, indiquer sa complexité.
Les logiciels de calcul formel sont souvent livrés avec une fonction permettant de calculer la trace d'une matrice de . Sans reprogrammer cette fonction, indiquer sa complexité.
a/ On suppose la matrice A et l'entier n connus du logiciel. Rédiger la partie de programme réalisant le stockage des traces dans un tableau , de sorte que contienne pour k variant de 1 à n .
b/ En général, la complexité d'un tel programme peut varier de à selon la manière dont on s'y prend. Quelle est la complexité du programme conçu en réponse au a/ (justifier) ?

a/ On suppose désormais la matrice A, l'entier n et le tableau t connus du logiciel. Rédiger la partie du programme réalisant le stockage des coefficients

, dans un tableau

, de sorte que

contienne

pour k variant de 0 à n .
b/ Que renseigne le dernier coefficient :

?
c/ Quelle est la complexité totale de l'algorithme des traces (justifier) ?
d/ On revient maintenant à la méthode naïve évoquée au début du problème. Celle-ci consisterait en un développement récursif du déterminant caractéristique : développement du déterminant

par rapport à la première colonne, puis développement des sous-déterminants

par rapport à leur première colonne, etc. Quelle est la complexité de cette méthode (justifier) ? En quoi la collecte des coefficients pose-t-elle difficulté ? Conclure.

III. Trois exemples et une application

La validation d'un algorithme s'accompagne toujours de tests. On fait tourner le programme sur des exemples dont on connaît les résultats intermédiaires ou finaux. Puis on compare ce qui est attendu à ce qui est effectivement retourné. Les questions 1,2 et

de cette partie permettent d'élaborer de tels tests. La question 4 validera encore davantage cette étude, mais pour d'autres raisons.

Dans les trois premières questions de cette partie, on rapporte l'espace vectoriel

à sa base canonique

. Dans la dernière question, on revient sur

1. Exemple 1.

On définit l'endomorphisme f de

vérifiant les conditions :

a/ Pourquoi ces conditions définissent-elles f sans ambiguïté ? Déterminer la matrice A de f dans la base B, puis l'image, le rang et le noyau de f.
b/ Sans utiliser la méthode des traces, déterminer directement le polynôme caractéristique de f.
c/ Retrouver ce résultat en simulant la méthode des traces.

2. Exemple 2.

On définit l'endomorphisme f de

vérifiant les conditions :

Déterminer la matrice A de f dans la base B, puis l'image, le rang et le noyau de f. Sans utiliser la méthode des traces, déterminer directement le polynôme caractéristique de f. Retrouver ce résultat en simulant la méthode des traces.

3. Exemple 3.

On munit dans cette question

de son produit scalaire canonique.
a/ Soit

un vecteur unitaire de

. On définit l'endomorphisme f de

comme étant la projection orthogonale sur la droite

engendrée par

. Déterminer son image, son rang et son noyau. Sans utiliser la méthode des traces, déterminer directement le polynôme caractéristique de f (on choisira une base adaptée au problème).
b/ Déterminer la matrice

dans la base

en fonction des coefficients

. Justifier que

. Retrouver le polynôme caractéristique de f en simulant la méthode des traces sur la matrice A .
4. Une application. On rétablit dans cette question un résultat classique de l'algèbre linéaire grâce - entre autres - à la méthode des traces.
a/ Soit A une matrice de

telle que

. Déterminer

. En déduire que 0 est la seule valeur propre de

. Démontrer alors que

.
b/ Soit maintenant une matrice

vérifiant

. Prouver que 0 est valeur propre de A et qu'il n'y en a pas d'autre.
c/ En déduire l'équivalence, valable pour tout A de

CCINP Mathématiques 2 TSI 2005

Les calculatrices sont autorisées