sommation vers trace de produit matrices
Bonjour,
Soit $M \in R ^{n\times p} $, $A \in R^{n\times n}$ et $D$ une matrice diagonale de taille $n$ avec $d_{ii}=\sum_{j=1}^na_{ij}$. Je cherche à prouver que l'égalité suivante est juste en partant de du terme à gauche : $$
\frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} (m^i-m^j)^2 a_{ij} = tr(M^\top {(D-A)} M)= tr( M^\top {LM}) ,$$ avec $L$ qui représente la matrice Laplacienne $D-A$.
Sachant que:
$m^i$ désigne la ligne $i$ de la matrice $M$
$a_{ij}$ désigne l'élément de la matrice $A$ se trouvant dans la ligne $i$ et la colonne $j$
Merci d'avance
Fies
EDIT: j'ai oublié de noter que dans mon cas la matrice $A$ est symétrique. On peut la voir comme une matrice d'adjacence.
Soit $M \in R ^{n\times p} $, $A \in R^{n\times n}$ et $D$ une matrice diagonale de taille $n$ avec $d_{ii}=\sum_{j=1}^na_{ij}$. Je cherche à prouver que l'égalité suivante est juste en partant de du terme à gauche : $$
\frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} (m^i-m^j)^2 a_{ij} = tr(M^\top {(D-A)} M)= tr( M^\top {LM}) ,$$ avec $L$ qui représente la matrice Laplacienne $D-A$.
Sachant que:
$m^i$ désigne la ligne $i$ de la matrice $M$
$a_{ij}$ désigne l'élément de la matrice $A$ se trouvant dans la ligne $i$ et la colonne $j$
Merci d'avance
Fies
EDIT: j'ai oublié de noter que dans mon cas la matrice $A$ est symétrique. On peut la voir comme une matrice d'adjacence.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Quelle est la valeur des formes linéaires de chaque côté de l'égalité à démontrer pour $A=E_{i,i}$ ?
Quelle est la valeur des formes linéaires de chaque côté de l'égalité à démontrer pour $A=E_{i,j}+E_{j,i}$ avec $j\neq i$ ?
Prenons par exemple cette question : Par exemple, pour $A=E_{1,1}$ ? Je suis sûr que si tu y réfléchis trois secondes, tu sauras répondre.
On a $M=\sum_{1\leq i,j\leq n} m_{ij}E_{ij}$ et $D=\sum_{1\leq i \leq n}^n d_{ii} E_{ii}$ alors que la matrice symétrique $A$ peut être générée via la base $(E_{ij}+E_{ji})_{i\leq j}$ ce qui donne $A=\sum_{1\leq i\leq j \leq n}^n a_{ij}(E_{ij}+E_{ji})$
En suite j'essayé de formuler $D$ en fonction de la matrice $A$ mais je bloque sur ce point: voici où j'en suis :
On a $$ d_{ii}=\sum_{j=1}^n a_{ij} $$ on peut donc écrire:
$$ D=\sum_{1\leq i \leq n}^n d_{ii} E_{ii} = \sum_{1\leq i \leq n}^n ( \sum_{j=1}^n a_{ij}) E_{ii} $$
et là pour développer $A$ je fais:
$$ A= \sum_{1\leq k \leq p \leq n} a_{kp} (E_{kp}+E{pk})$$
ce qui donne la formulation finale de D (je ne sais pas comment finir):
$$ D= \sum_{1\leq i \leq n}^n \sum_{j=1}^n \bigg[\sum_{1\leq k \leq p \leq n} a_{kp} (E_{kp}+E{pk}) \bigg ]_{ij}E_{ii} $$
donc $L=D-M$ revient à avoir cette forme linéaire:
$$ L= \sum_{1\leq i \leq n}^n \sum_{j=1}^n \bigg[\sum_{1\leq k \leq p \leq n} a_{kp} (E_{kp}+E{pk}) \bigg ]_{ij}E_{ii} - \sum_{1\leq i,j\leq n}^n m_{ij}E_{ij} $$
EDIT: suite
Si $M=\sum_{1\leq i,j\leq n} m_{ij}E_{ij}$ alors on a $$M^\top=\sum_{1\leq i,j\leq n} m_{ij}E_{ji}$$
Et $$M^\top LM= \sum_{1\leq i,j\leq n} m_{ij}l_{ij}m_{ij}E_{ji} E{ij}E_{ij} $$
suis je sur la bonne voie ? je me suis perdu...
Merci
Par ailleurs $\mathrm{tr}(M^{\mathsf T} E_{i,j} M)$ est le produit scalaire standard de $m^i$ et de $m^j$. C'est tout ce qu'il faut pour établir l'égalité.
\begin{align*}
\frac{1}{2} \sum_{i,j}(m^i-m^j)^2 a_{ij}&= \sum_{i,j} {m^i}^\top a_{ij} m^i - \sum_{i,j} {m^i}^\top a_{ij}m^j\\
&= \sum_{i} {m^i}^\top (\sum_{i} a_{ij}) m^i - \sum_{i,j} {m^i}^\top a_{ij}m^j \\
&= \sum_{i} {m^i}^\top d_{ii} m^i - \sum_{i,j} {m^i}^\top a_{ij}m^j \\
&= M^\top DM - M^\top AM \\
&= M^\top (D-A)M \\
&= M^\top LM .
\end{align*}
Mais là je ne tombe pas sur la trace mais plutôt sur la matrice. En effet, je voulais avoir $tr(M^\top LM)$. C'est comme si il me manquait un indice et une boucle quelque part...
Merci pour votre aide.
$$\sum_{i,j} {m^i}^\top a_{ij} m^j - \sum_{i,j} {m^i}^\top a_{ij}m^j$$
Ça ne ferait pas $0$ ?
$$ \sum_{i,j} {m^i}^\top a_{ij} m^i - \sum_{i,j} {m^i}^\top a_{ij} m^j $$
J'ai vérifié le tout numériquement et ça marche, il faut juste que je somme les éléments de la diagonale de la dernière matrice mais je ne vois comme rajouter cette somme.
Merci encore
PS : j'ai modifié la preuve.
https://pdfs.semanticscholar.org/1d9e/493a34df3fc2d7eec5b343ea91f9fc474678.pdf
$$\frac{1}{2} \sum_{i,j}(m^i-m^j)^2 a_{ij} = = \sum_{i,j} {m^i}^\top a_{ij} m^i - \sum_{i,j} {m^i}^\top a_{ij}m^j$$
n'a pas de sens : à gauche tu as un scalaire, à droite une matrice $p\times p$ (ne pas oublier que les $m^i$ sont des vecteurs lignes).
J'(ai l'impression qu'il te manque pas mal de bases d'algèbre linéaire - et en particulier que la notion de base d'un espace vectoriel t'es étrangère.
Pour vérifier que ton égalité vaut pour toute matrice symétrique $A$, il suffit, par linéarité, de la vérifier pour les éléments d'une base de l'espace des matrices symétriques. Comme je l'ai déjà dit, on a une base de l'espace des matrices symétriques formées des matrices $E_{i,i}$ et des matrices $E_{i,j}+E_{j,i}$ pour $i<j$.
Si $A=E_{i,i}$ (tous les coefficients de $A$ sont nuls, sauf $a_{i,i}=1$), alors $D-A=\mathbf 0$.
Le terme de gauche de l'égalité se réduit à $\dfrac12 \Vert m^i-m^i\Vert^2=0$ et celui de droite à $\mathrm{tr}(M^{\mathsf T} \mathbf 0\, M)=0$.
Si $A=E_{i,j}+E_{j,i}$ avec $i<j$ (tous les coefficients de $A$ sont nuls, sauf $a_{i,j}=a_{j,i}=1$), alors $D-A=E_{i,i}+E_{j,j}-E_{i,j}-E_{j,i}$.
Le terme de gauche de l'égalité se réduit à $\Vert m^i-m^i\Vert^2 = \Vert m^i\Vert^2 + \Vert m^j\Vert ^2 -2\,m^i\cdot m^j$, où $\cdot$ désigne le produit scalaire standard.
Le terme de droite de l'égalité se réduit à $$\mathrm{tr}(M^{\mathsf T} (E_{i,i}+E_{j,j}-E_{i,j}-E_{j,i}) M)=\mathrm{tr}(M^{\mathsf T}E_{i,i} M) + \mathrm{tr}(M^{\mathsf T} E_{j,j} M)-\mathrm{tr}(M^{\mathsf T} E_{i,j} M) -\mathrm{tr}(M^{\mathsf T}E_{j,i} M)\;.$$
L'égalité est vérifiée parce qu'on a pour tous $i,j$
$$\mathrm{tr}(M^{\mathsf T} E_{i,j} M)= m^i\cdot m^j\;.$$
On peut vérifier cette dernière égalité en calculant :
$$\begin{aligned}
\mathrm{tr}(M^{\mathsf T} E_{i,j} M) &= \sum_{k=1}^p \sum_{\ell=1}^n\sum_{q=1}^n m_{\ell,k} \delta_{\ell,i}\delta_{q,j} m_{q,k}\\
&=\sum_{k=1}^p m_{i,k} m_{j,k} =m^i\cdot m^j\;.
\end{aligned}$$
On a utilisé dans ce calcul que le coeffcient de $E_{i,j}$ à l'intersection de la ligne $\ell$ et de la colonne $q$ est $ \delta_{\ell,i}\delta_{q,j}$ (produit de symboles de Kronecker).
\begin{align*}
\frac{1}{2} \sum_{i,j}(m^i-m^j)^2 a_{ij} =
&\frac{1}{2} \sum_{i,j}({m^i}^2+{m^j}^2-2m^im^j)a_{ij}\\
&\frac{1}{2} \sum_{i,j}{m^i}^2a_{ij}+{m^j}^2a_{ij}-2m^im^ja_{ij}\\
&\frac{1}{2} \sum_{i,j} {m^i}^2a_{ij}+{m^j}^2a_{ij}- \frac{1}{2} \sum_{i,j}2m^im^ja_{ij} \\
&\frac{1}{2} \sum_{i,j} {m^i}^2a_{ij}+{m^j}^2a_{ij}-\sum_{i,j}m^im^ja_{ij}\\
&\frac{1}{2} \sum_{i,j} {m^i}^2a_{ij} + \frac{1}{2} \sum_{i,j} {m^j}^2a_{ij}-\sum_{i,j}m^im^ja_{ij}\\
&\frac{1}{2} \sum_{i} {m^i}^2d_{ii} + \frac{1}{2} \sum_{i} {m^i}^2d_{ii}-\sum_{i,j}m^im^ja_{ij}\\
& \sum_{i} {m^i}^2d_{ii}-\sum_{i,j}m^im^ja_{ij}
\end{align*}
\begin{align*}
\sum_{i,j}<m^i,m^j>a_{ij}&=
\sum_{i,j}\sum_{p}m^i_pm^i_p a_{ij}\\
&=\sum_{p}\sum_{i,j}m^i_pm^i_p a_{ij}
\end{align*}
Est-ce que $\sum_{i,j}m^i_pm^i_p a_{ij}$ est équivalent à $M^\top A M $ ?
N.B. $A=\sum_{i,j} a_{i,j}E_{i,j}$.
\mathrm{trace}(M^T(D-A)M)=\mathrm{trace}(D-A)MM^T=\sum_{i=1}^nd_i\|m_i\|^2-\sum_{i,j=1}^na_{ij}\langle m_i,m_j\rangle=\frac{1}{2}\sum_{i,j=1}^na_{ij}\|m_i-m_j\|^2.$$