Matrice de distance euclidienne

Modèle:Voir homonymes En mathématiques, une matrice de distance euclidienne est une matrice de taille n × n représentant l'espacement d'un ensemble de $n$ points dans un espace euclidien. Si l'on note $A$ une matrice de distance euclidienne et $x_{1}, x_{2}, \dots, x_{n}$ des points sont définis dans un espace de dimension $m$ , alors les éléments de $A$ sont donnés par

\begin{matrix} A & = (a_{i j}); \\ a_{i j} & = d_{i j}^{2} = ‖ x_{i} - x_{j} ‖_{2}^{2} \end{matrix}

où $‖ \cdot ‖_{2}$ désigne la norme euclidienne sur $ℝ^{m}$ . Ainsi, la matrice des distances euclidienne sera de la forme :

A = [\begin{matrix} 0 & d_{12}^{2} & d_{13}^{2} & \dots & d_{1 n}^{2} \\ d_{21}^{2} & 0 & d_{23}^{2} & \dots & d_{2 n}^{2} \\ d_{31}^{2} & d_{32}^{2} & 0 & \dots & d_{3 n}^{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ d_{n 1}^{2} & d_{n 2}^{2} & d_{n 3}^{2} & \dots & 0 \end{matrix}]

Propriétés

Pour faire simple, l'élément $a_{i j}$ décrit le carré de la distance entre les $i$ ^ème et $j$ ^ème points de l'ensemble. Par les propriétés de la norme euclidienne, la matrice $A$ a les propriétés suivantes :

Tous les éléments sur la diagonale de $A$ sont nuls (propriété de la séparation d'une distance, la distance séparant un point de lui même est nulle).
La trace de $A$ est zéro (par la propriété ci-dessus).
$A$ est symétrique (c'est-à-dire que $a_{i j} = a_{j i}$ , un corollaire de la symétrie d'une distance).
$\sqrt{a_{i j}} \leq \sqrt{a_{i k}} + \sqrt{a_{k j}}$ (par l'inégalité triangulaire)
$a_{i j} \geq 0$
Le nombre de valeurs uniques (distinctes) non nulles d'une matrice de distance euclidienne de taille $n \times n$ est borné supérieurement par $n (n - 1) / 2$ en raison de la symétrie et du fait d'avoir une diagonale nulle.
En dimension m, le rang d'une matrice de distance euclidienne est inférieur ou égal à $m + 2$ . Si les points $x_{1}, x_{2}, \dots, x_{n}$ sont en position générale, le rang est exactement Modèle:Nobr