Centrale Maths 2 PSI 2011

Thème de l'épreuve Represésentation connaissant les distances mutuelles
Principaux outils utilisés projecteur orthogonal, valeurs propres, géométrie euclidienne dans R3
Mots clefs matrice des distances mutuelles, relation de Torgerson, approximation par les moindres carrés, positionnement multidimensionnel, géométrie euclidienne

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


î, '» Mathématiques 2 "a « __./ PSI EDNEDlIHS EENÏHHLE-EUPËLEE 4 heures Calculatrices autorisées 2011 Représentation connaissant les distances mutuelles Notations Dans tout le problème, n et p désignent des entiers naturels > 1. 1 1) eMn71("äâ). On définit les deux matrices suivantes de Mn(ä) \ On note la matrice colonne Z = k 1 .]:th et P=In----J n On considère l7espace vectoriel Rp muni du produit scalaire canonique que l7on notera < ',. > et l7espace de matrices Mn (R) muni du produit scalaire ( l ) défini par V(M, N) e (Mn(R))2, (M l N) = tr (ÊMN) On note ll ' H la norme euclidienne associée au produit scalaire < ',. > et H ' lan(R) la norme euclidienne sur Mn(R) associée au produit scalaire ( l ). Sn (Q) désigne le sous--espace de Mn(R) des matrices symétriques réelles et 5:{ (R) le sous--ensemble de Sn (R) des matrices à valeurs propres positives ou nulles. On (Q) désigne Pensemble des matrices orthogonales de MAR). I Centrage de matrices I.A * Soit 7r Pend0m0rphisme de R" dont la représentation dans la base canonique est la matrice P. Montrer que W est un projecteur orthogonal et en préciser les éléments caractéristiques. I.B * On considère Vendomorphisme @ de Mn (R) défini par : VM & M..(R), ®(M) = PMP I.B.l) Montrer que (I) est un projecteur orthogonal dans l7espace euclidien (Mn (R), ( \ ).) I.B.2) Montrer que Im = {M EUR Mn(R) \ MZ = 0 et tMZ = 0}. I.C * Soit M = (m") EUR SAR). On pose TL E m1i i=1 S(M) = MZ = || % ,à $ II A N 52 $ v n g mni i=1 Montrer que O'(M) 2 .] ®(M) = M = l (S(M)ÊZ + ZÊS(M)) + TL TL II Produit scalaire à partir des distances mutuelles (relation de Torgerson) n Soient U1,U2, ' ' ' , U... n éléments de Rp vérifiant z Ui = O. 7,=1 Géométriquement, U1, U2, ' ' ' , Un désignent des points dïsobarycentre lbrigine. On définit la matrice des distances mutuelles au carré, élément de Sn (R), de la façon suivante : 20 avril 2011 16:23 Page 1/4 GC) BY--NC-SA M= ii "== tU,-Uj en fonction de 1 1 aij = DE (S(M), + S(M),) + ÆU(M) et de mij (relation de Torgerson). Ainsi la matrice des distances mutuelles au carré permet de retrouuer la matrice des produits scalaires tUU EUR MAR). III Condition pour qu'une matrice soit une matrice de distances mutuelles au carré Soit M = (mij)(i,j)EURfll,nfl2 EUR SAR) telle que pour tout couple (i,j) EUR \\l,n\\2, mij } 0 et rr"... = O. III.A * On suppose dans cette question qu'il existe U1,U2,' .. ,Un éléments de Rp tels que pour tout . . 2 (%])Élllan127mij = \\Ui * Uj\\ . III.A.I) Montrer que les valeurs propres de (M ) sont toutes réelles et négatives ou nulles. III.A.2) On suppose de plus (quitte a effectuer une translation) que les (U,) sont centrés, c'est--à--dire que 2 U,- = O. i=1 Montrer que rg(U) = rg(U1 \ U2 \ ... \ Un) = rg (®(M)) et que p } rg (®(M)). III .B * Réciproquement, on suppose que les valeurs propres de (M ) sont toutes négatives ou nulles et on pose OE(M) = --â(M) et r = rg(OE(M)). III.B.I) Montrer qu'il existe une matrice U E M..., (R) telle que tUU = OE(M). III.B.2) On note U1, U2, ' ' ' , Un les colonnes de la matrice U. iEUR\\1,n\] On cherche a montrer que pour tout (i,j) EUR \\l,n\\2, mij = \\UZ -- Uj\\2. " a) Montrer que les (U,) sont centrés, c'est--à--dire que 2 U,- = O. i=1 b) Montrer que la matrice N = (rw) définie par : . . 2 V(%J) EUR \\17nl\27nij = \\U, * Uj\\ Vérifie OE(N) = OE(M). c) Montrer que M = N et conclure. IV Etude d'un exemple dans l'espace R3 Dans cette partie, on considère quatre points distincts A, B, C et D dans l'espace euclidien canonique R3 telsqueAB=BC=CD=DA=1.0nposeAC=a>0etBD=b>0. On se propose de trouver une condition nécessaire et suffisante sur a et b pour que ces quatre points existent, dans un premier temps par un raisonnement géométrique puis en utilisant les résultats des parties précédentes. IV.A * Étude géométrique On suppose que les quatre points A, B, C et D existent. IV.A.I) On suppose que les quatre points A, B, C et D sont coplanaires. Quelle relation vérifient alors a et b? IV.A.2) On suppose que les quatre points distincts A, B, C et D ne sont pas coplanaires. On note 1 le milieu de \AC\ et .] le milieu de \BD\. a) Montrer que (IJ) est la perpendiculaire commune aux droites (AC) et (BD). b) En projetant les points B et D sur le plan contenant (AC) et perpendiculaire à (I J), montrer que 2 2 a + b < 4. On étudie maintenant la réciproque. IV.A.3) Montrer que si des réels strictement positifs @ et b vérifient la relation a2 + b2 $ 4, alors il existe bien quatre points distincts A, B, C et D dans l'espace euclidien canonique R3 vérifiant AB = BC = CD = DA = 1, AC = a et BD = b. 20 avril 2011 16:23 Page 2/4 @°_ IV.B * Étude algébrique On se propose de retrouver les résultats précédents en utilisant les parties II et III. Pour simplifier l'écriture des relations, on notera U1, U2, U3 et U4 les quatre points A, B, C et D de l'espace R3 vérifiant U1U2 = U2U3 = U3U4 = U4U1 = 1, U1U3 = a et U2U4 = b. IV.B.1) On reprend les notations des parties précédentes avec ici n = 4. o M=(U,--U.2) ESR. npose \\ JH @.j>611.412 4< ) Écrire la matrice M puis calculer S(M) et O'(M). IV.B.2) Montrer que les vecteurs 1 0 f1 1 0 1 1 1 f1 ' 0 ' f1 ' 1 0 f1 1 1 forment une base de vecteurs propres de la matrice OE(M ) et déterminer les valeurs propres de la matrice OE(M ) IV.B.3) Déterminer le rang de OE(M) selon les valeurs prises par a et b. IV.B.4) Quelle égalité Vérifie les réels @ et b lorsque les points U1, U2, U3 et U4 sont coplanaires? IV.B.5) Retrouver que les réels strictement positifs @ et b vérifient a2 + [22 $ 4. IV.B.6) Réciproquement, si a2+b2 $ 4, donner une famille de points U1, U2, U3 et U4 vérifiant les contraintes de distances mutuelles. V Cas où il n'existe pas de points représentant une matrice de distances mutuelles On considère dans cette partie une matrice M = (mlj) E Sn (R) telle que pour tout (i,j) EUR [l1,nfl2, mij } 0 et On suppose que OE(M ) possède au moins une valeur propre strictement négative. Dans la suite, on étudie trois transformations permettant de modifier « légèrement » la matrice M pour obtenir une nouvelle matrice de distances mutuelles au carré. V.A * Par les moindres carrés V.A.1) On cherche a prouver qu'il existe une unique matrice symétrique T0 à valeurs propres positives ou nulles qui minimise H'IJ(M) -- Tlan(R) lorsque T décrit $;," (R). a) Montrer que VQ EUR On(R)7VA EUR MnOE)» ll'QAQll/wn(iæ) = llAlan(R) b) Justifier l'existence d'une matrice QD EUR On (Q) telle que la matrice tQO\IJ(M)QO soit diagonale. 0) Montrer qu'une condition nécessaire pour que H'IJ(M) -- Tolan(R) minimise H'IJ(M) -- Tlan(R) lorsque T décrit $;," (R) est que la matrice 'QOTOQO soit diagonale. d) Prouver l'existence et l'unicité de la matrice TO cherchée. V.A.2) On suppose dans cette question que T0 est non nulle. On veut montrer qu'il existe un entier p EUR [l1, n -- 1] minimal que l'on précisera tel que l'on puisse déterminer des vecteurs U1, U2, ' ' ' , Un éléments de 77, N . . . . _ . _ .* , 2 ; . . RP sat1sfa1sant la condition 1Ê:1 Ui _ 0 et pour lesquels la matrice M _ (HU, U] M ) (,7j)EUR,17n,2 verifie la relation \IJ(M) = TO. On reprend les notations de la partie II et on note U = (Ul \ U2 \ ' ' ' l Un). a) Montrer que l'entier p Vérifie p } rg(T0) et que rg(T0) EUR [l1, n -- 1]. b) Construire une matrice U E M..., (R) telle que tUU = TD pour r = rg(To). Indication. En supposant que 'QngQg soit de la forme (A 0 > avec A E M.(R), diagonale à valeurs non nulles, on cherchera U sous la forme U = ((Al) (O)) >< @@ E M,... (R) avec A1 EUR M.(R), diagonale. " 0) Montrer que 2 U,- = 0 (on pourra étudier le vecteur UZ). i=1 d) En déduire que OE(M) = T0 avec M=  0 telle que OE(MC) soit à valeurs propres positives ou nulles. 2 V.C.l) Montrer que, pour tout X E R", tX'IJ(Z\ÂC)X = ÊXOE(M)X + ËCÊXOE(D)X + %tXPX. V.C.2) Montrer que si Àmin et umin désignent les valeurs propres minimales respectives de OE(M ) et OE(D), alors VX EUR "H, ÊXOEJ(M)X ; A...JXX et ÊXOEJ(D)X ; ......fiXX (L7hyperplan 7--l a été défini a la question V.B.l.) V.C.3) En déduire que pour c = È= +2/imin + )/4/'L12nin + 2Àmin > O, OE(MC) est à valeurs propres positives ou nulles et que pour tout c > Èet pour tout vecteur non nul X E H, tX'Il(l\ÂC)X > O. V.C.4) Nous allons chercher la constante c* > 0 minimale (si elle existe) vérifiant . OE(Mç*) est à valeurs propres positives ou nulles, . pour tout c > c* et pour tout vecteur non nul X E H, tX'IJ(Z\ÂC)X > 0. On sait que c* est majoré par 5. On considère A = {X E 7--l \ HXH = l et 4(ÊX\IJ(D)X)2 + 2tXOEJ(M)X } O} et on définit l7application A + R O' : {X => +2tXOEJ(D)X +\/4(ÊX\1J(D)X)2 -- 2U(\1J(M)X Montrer qu7il existe X* EUR A tel que oz(X*) = sup a(X) et oz(X*) > O. XGA On notera oz* = oz(X*). V.C.5) Montrer que . tX*OE(M...)X* = O, . OE(M...) est à valeurs propres positives ou nulles, . pour tout c > oz* et pour tout vecteur non nul X E H, tX'll(lläc)X > 0. En conclure que c* = oz*. V.C.6) Calcul de c* a) Montrer que OE(Mç*)Xl< = O. 2 On pose Y* = --*OEJ(M)X*. 0 Y* X* que c* est valeur propre de cette matrice. 2OEJ(M))) et . . 0 ) est vecteur propre de la matrice de taille 2n (& +4OE(D b) Montrer que le vecteur colonne < . \ , . 0 2OE(M ) X 1 V.C.7) On cons1dere 'y une valeur propre reelle de la matrice (& 4OE(D)) et  

Extrait du corrigé obtenu par reconnaissance optique des caractères


 Centrale Maths 2 PSI 2011 -- Corrigé Ce corrigé est proposé par Christophe Fiszka (ENS Cachan) ; il a été relu par Jules Svartz (ENS Cachan) et Céline Chevalier (Enseignant-chercheur à l'université). Le problème propose une introduction aux techniques de « positionnement multidimensionnel », classiques dans le domaine de l'analyse de données. Le principe général consiste à trouver un placement de n données dans un espace Rp de dimension p fixée en respectant « au mieux » les distances mutuelles mesurées entre celles-ci. Ces distances sont stockées dans une matrice dont on étudie les propriétés tout au long des cinq parties du sujet. · Les deux premières parties définissent les notations et les outils propres au problème, notamment la relation de Torgerson qui relie les produits scalaires d'une famille de vecteurs (U1 , . . . , Un ) aux carrés des distances mutuelles kUi - Uj k2 . · La troisième partie donne une condition nécessaire et suffisante pour qu'une matrice soit effectivement de distances mutuelles au carré, c'est-à-dire de type M = kUi - Uj k2 16i,j6n · La quatrième partie aborde un problème particulier dans le cas n = 4 et p = 3 : si A, B, C et D désignent quatre points de R3 , à quelles conditions sur les distances AC et BD peut-on avoir AB = BC = CD = DA ? L'énoncé propose deux résolutions, l'une purement géométrique et l'autre plus algébrique, qui utilisent les outils développés dans les trois premières parties. · La dernière partie illustre trois techniques, la méthode des moindres carrés, le décalage de la distance au carré et enfin le décalage suivant une méthode de F. Cailliez, permettant, à partir d'une matrice symétrique, de se ramener à une matrice de distances mutuelles au carré. Ce sujet est intéressant et original, mais il est aussi long et difficile. Indications Partie I t 2 I.A Démontrer que P = P et P = P. I.B.1 Pour le caractère orthogonal, on pourra vérifier que M, N Mn (R) ((M) | N) = (M | (N)) Partie II II.A Relier les produits scalaires avec les distances par la formule kUi - Uj k2 = kUi k2 + kUj k2 - 2hUi , Uj i pour ensuite utiliser la relation démontrée à la question I.C. Partie III III.A.1 En appliquant le résultat de la question II.A, montrer que (M) = -2 t (UP) UP puis calculer kUPX k2 où X est un vecteur propre pour la valeur propre . III.A.2 Démontrer tout d'abord que Ker t U U = Ker U. III.B.1 Commencer par traiter le cas où (M) est diagonale. n P III.B.2.a Remarquer que UZ = Ui . i=1 III.B.2.c En partant de la relation établie à la fin de la partie I, il suffit de montrer que MZ = NZ. Partie IV 2 2 IV.A.1 On doit trouver a + b = 4. IV.B.4 Les points Ui sont coplanaires, pour i = 1, . . . 4, si le rang de U est inférieur ou égal à 2. Partie V V.B.3 Montrer que si X H est un vecteur propre de (M) pour la valeur , il est aussi vecteur propre de (Nk ), mais pour la valeur + k/2. V.C.1 Justifier tout d'abord que (Mc ) = (M) + 2c(D) + c2 P 2 V.C.4 Utiliser un argument de compacité, puis remarquer que la valeur (X) représente le plus grand zéro du polynôme : 1t t t X PXc2 + 2 X (D)Xc + X (M)X 2 V.C.6 Penser à la relation PX : c (Mc ) = (M) + 2c(D) + c2 P 2 V.C.7 Même indication qu'à la question V.C.6. Dans tout ce corrigé, on identifie les matrices de Mn,1 (R) aux vecteurs de Rn . I. Centrage de matrices I.A L'endomorphisme est un projecteur orthogonal si et seulement si = = et où l'on a noté l'adjoint de . Si P est la matrice représentative de dans la base canonique, ces deux conditions sont équivalentes à t P2 = P et P=P 1 2 2 1 Or, P 2 = In - J = In - J + 2 J 2 n n n t t t t t Puisque J2 = (Z Z)(Z Z) = Z( Z Z) Z = nZ Z = nJ, on en déduit que 2 1 1 P 2 = In - J + J = In - J = P n n n t 1 1 1 t De plus, P = In - J = t In - t J = In - J = P n n n car les matrices In et J sont symétriques. En conclusion, est un projecteur orthogonal. Précisons maintenant les éléments caractéristiques de ce projecteur, à savoir le noyau, l'image et le rang. Pour déterminer le noyau, résolvons l'équation PX = 0 pour X Mn,1 (R) ; elle est équivalente à JX = nX t En notant X = (x1 , x2 , . . . , xn ), on en déduit que n P j [[ 1 ; n ]] xp = nxj soit xj = p=1 n 1P xp n p=1 Ainsi, toutes les composantes de X sont égales. Par conséquent, il existe R tel t que X = Z. Réciproquement, on s'assure que (1, . . . , 1) est bien dans le noyau. Traduisons ce résultat en termes d'endomorphisme : Ker est la droite vectorielle engendrée par t (1, . . . , 1). Le projecteur étant orthogonal, l'image n'est autre que l'orthogonal du noyau : Im () = Ker () t Explicitons cet ensemble : soit x = (x1 , . . . , xn ) Ker () . Comme le noyau est engendré par le vecteur t (1, . . . , 1), n P t x Ker () 0 = hx, (1, . . . , 1)i = xi i=1 Autrement dit, l'image est donnée par l'hyperplan Im () = {x = (x1 , . . . , xn ) | n P xi = 0} i=1 et rg () = n - 1 On aurait tout aussi bien pu donner le rang directement à l'aide de la trace. En effet, si l'on regarde la matrice de dans une base adaptée à la décomposition Rn = Ker () Im (), on voit que rg () = Tr () I.B.1 A nouveau, vérifions d'abord que l'endomorphisme satisfait la relation = Soit M Mn (R), on a (M) = P(PMP)P = P2 MP2 Comme P est la matrice d'un projecteur, il vient (M) = PMP = (M) ce qu'il fallait démontrer. Vérifions désormais que est bien orthogonal, c'est-à-dire égal à son adjoint. Il suffit pour cela d'établir que, pour toutes matrices M et N, ((M)|N) = (M|(N)). t Or, pour toutes matrices A, B de Mn (R), Tr AB = Tr BA et P = P. Il vient t t t ((M) | N) = Tr ( (PMP) N) = Tr (P M PN) = Tr ( M PNP) = (M | (N)) Finalement, est un projecteur orthogonal. Attention à ne pas confondre un endomorphisme orthogonal (inversible d'inverse son adjoint) et un projecteur orthogonal, qui n'est pas inversible et pour lequel l'adjectif orthogonal fait référence à l'orthogonalité entre son noyau et son image. I.B.2 Montrons le résultat par double inclusion. Dans le sens direct, comme l'image d'un projecteur est l'ensemble des vecteurs invariants par ce dernier, Im = { M Mn (R) | (M) = M } Soit M Im , elle vérifie M = (M) = PMP et aussi, en transposant, P t M P = t M. t t Puisque PZ = 0, il vient MZ = PMPZ = 0 et M Z = P M PZ = 0. La première inclusion est démontrée. Remarquons que l'on ne connaît pas a priori la dimension de ces espaces. Dès lors, on ne peut pas conclure par un argument de dimension. Il faut maintenant prouver l'inclusion inverse. t Soit M Mn (R) telle que MZ = 0 et M Z = 0. Alors 1 1 1 1 1 PMP = In - J M In - J = In - J M - MJ = In - J M n n n n n puisque MJ = MZ t Z = 0. De plus, 1 1 In - J M = M - JM = M n n t t t car JM = Z Z M = Z ( M Z) = 0. Par conséquent, PMP = M et M Im L'égalité est ainsi justifiée par double inclusion : t Im = { M Mn (R) | MZ = 0 et M Z = 0}