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}