Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
175 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

sommation vers trace de produit matrices

Envoyé par Fies_ 
sommation vers trace de produit matrices
il y a treize jours
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.



Edité 4 fois. La dernière correction date de il y a douze jours et a été effectuée par Fies_.
Re: sommation vers trace de produit matrices
il y a treize jours
Des deux côtés de l'égalité, on a une forme linéaire sur $\R^{n\times n}$. Il suffit donc de vérifier l'égalité sur une base de cet espace.
Re: sommation vers trace de produit matrices
il y a treize jours
Je vous remercie pour votre réponse. Pourriez vous me la détailler un peu svp? je sais que le premier terme $$ \sum_{i=1}^{n}\sum_{j=1}^{n} (m^i-m^j)^2,$$ revient à calculer une sorte de matrice de similarité entre les $n$ ligne de $R$.



Edité 1 fois. La dernière correction date de il y a douze jours et a été effectuée par Fies_.
Re: sommation vers trace de produit matrices
il y a treize jours
Je dis tout bêtement que $A\mapsto \dfrac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} \|m^i-m^j\|_{2}^2 a_{ij}$ et $A\mapsto tr(M^\top {(D-A)} M)= tr( M^\top {LM}) $ sont deux formes linéaires, et qu'elles sont égales si et seulement si elles coïncident sur une base de $\R^{n\times n}$ correction : l'espace des matrices symétriques. Je suis sûr que tu connais une base de $\R^{n\times n}$ correction : l'espace des matrices symétriques qui facilite le calcul.



Edité 1 fois. La dernière correction date de il y a treize jours et a été effectuée par GaBuZoMeu.
Re: sommation vers trace de produit matrices
il y a treize jours
Je te remercie pour la réponse même si j'ai toujours du mal à voir comment prouver cette égalité. Merci
Re: sommation vers trace de produit matrices
il y a treize jours
Ne connais-tu pas une base de l'espace des matrices symétriques, formée de matrices "simples" ?
Re: sommation vers trace de produit matrices
il y a treize jours
Non je connais pas. Numériquement, cette égalité est vérifiée mais je dois fournir une preuve pour utiliser la formulation en trace dans mon algorithme d'optimisation.
Re: sommation vers trace de produit matrices
il y a treize jours
Par exemple une base est fournie par les matrices $E_{i,i}$ et les matrices $E_{i,j}+E_{j,i}$ pour $j\neq i$ (au cas où tu ne le saurais pas, $E_{i,j}$ est la matrice qui a des $0$ partout, sauf un $1$ à l'intersection de la ligne $i$ et de la colonne $j$).
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$ ?
Re: sommation vers trace de produit matrices
il y a treize jours
Je te remercie GaBuZoMeu, mais là j'y comprends rien du tout. Je te remercie pour l'effort, si tu peux m'expliquer via un exemple (en l’occurrence, le mien) ça sera beaucoup plus abordable pour moi.
Re: sommation vers trace de produit matrices
il y a treize jours
J'ai l'impression que tu ne fais pas beaucoup d'effort pour comprendre, et que tu attends du "tout cuit". Prends plus de temps pour approfondir.
Prenons par exemple cette question :
Citation

Quelle est la valeur des formes linéaires de chaque côté de l'égalité à démontrer pour $A=E_{i,i}$ ?
Par exemple, pour $A=E_{1,1}$ ? Je suis sûr que si tu y réfléchis trois secondes, tu sauras répondre.
Re: sommation vers trace de produit matrices
il y a treize jours
Je te remercie pour la piste, je suis en train de voir un cours sur le formes linéaires. Sinon tu veux dire quoi par $A$ ? une application c'est bien ça ? $E_{ii}$ ça représente la matrice où il y a des 1 par tout la diagonale.
Re: sommation vers trace de produit matrices
il y a treize jours
Pour répondre à la question $A=E_{ii}$ je pense que la forme linéaire de $tr(M ^\top LM) $ est $$ \sum_{i=1}^n [M^\top LM]_{ii},$$ et pour l'autre côté c'est déjà en forme linéaire ?
Re: sommation vers trace de produit matrices
il y a treize jours
Pour l'instant j'arrive à formuler les différentes matrices $ M$, $A$ et $D$ avec la forme linéaire:
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



Edité 9 fois. La dernière correction date de il y a treize jours et a été effectuée par Fies_.
Re: sommation vers trace de produit matrices
il y a treize jours
Si $A=E_{i,j}+E_{j,i}$, alors $D-A=E_{i,i}+E_{j,j}-E_{i,j}-E_{j,i}$.
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é.
Re: sommation vers trace de produit matrices
il y a douze jours
Je te remercie pour la réponse, en effet je viens de faire le développement du premier terme de l'égalité et j'arrive à me rapprocher de la solution mais il me manque toujours la dernière étape :
\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.



Edité 3 fois. La dernière correction date de il y a douze jours et a été effectuée par AD.
Re: sommation vers trace de produit matrices
il y a douze jours
Ce que tu écris ne fait pas sens. Regarde par exemple
$$\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$ ?
Re: sommation vers trace de produit matrices
il y a douze jours
Pardon je me suis trompé dans les indices c'est plutôt $\sum_{i,j} {m^i}^\top a_{ij} m^i$ et non pas $m^j$ ce qui donne
$$ \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.



Edité 2 fois. La dernière correction date de il y a douze jours et a été effectuée par Fies_.
Re: sommation vers trace de produit matrices
il y a douze jours
Tu écris un scalaire égal à une matrice, ça ne va pas. Je t'ai indiqué une façon de procéder, je ne vois pas que tu en tiennes compte.
Re: sommation vers trace de produit matrices
il y a douze jours
Pourtant, j'ai bien $$\sum_{i,j} {m^i}^\top a_{ij} m^i = M^\top DM, $$ et $$ \sum_{i,j} {m^i}^\top a_{ij}m^j= M^\top AM$$ À vrai dire, je me suis perdu avec la méthode que tu m'as proposée, donc j'ai essayé autrement,



Edité 2 fois. La dernière correction date de il y a douze jours et a été effectuée par AD.
Re: sommation vers trace de produit matrices
il y a douze jours
En effet, je ne vois pas comment utiliser la propriété du produit scalaire standard que tu m'as donnée. Aussi, pourquoi $D=E_{i,i}+E_{j,j}$ ? normalement $D=E_{i,i}$ uniquement ? ou bien $(E_{i,i}+E_{j,j})$ est une base des matrices diagonales ?
Re: sommation vers trace de produit matrices
il y a douze jours
La démarche de la preuve que j'ai postée vient de ce papier , dans la section 3.1.1 ( Graph Regularization (Undirected Graph)) . J'ai essayé de faire la même chose que les auteur du papier mais je n'y arrive pas !

[pdfs.semanticscholar.org]
Re: sommation vers trace de produit matrices
il y a douze jours
Tu mélanges un peu tout. Pour commencer, cette égalité
$$\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).
Re: sommation vers trace de produit matrices
il y a onze jours
Je te remercie GaBuZoMeu pour ta réponse. C'est vrai qu'à la base je ne suis pas matheux mais bon j'essaie de me débrouiller avec le peu que j'ai. En suivant ta démarche j'ai tenté d'aller du terme gauche au terme droit mais j'ai toujours le problème de la trace, pourrais-tu m'aider à aller jusqu'au bout ? Voici ma deuxième tentative.
\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*}



Edité 1 fois. La derni&egrave;re correction date de il y a onze jours et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: sommation vers trace de produit matrices
il y a onze jours
Il suffit d'utiliser $\mathrm{tr}(M^{\mathsf T} E_{i,j} M)= m^i\cdot m^j$.
Re: sommation vers trace de produit matrices
il y a onze jours
Si j'ai bien compris, $\sum_{i,j}<m^i,m^j>a_{ij}$ est équivalent à $tr(M^\top A M)$ ? Je ne vois pas comment vous avez fait pour passer à la notation matricielle, alors que si je développe encore j'aurai :
\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 $ ?



Edité 1 fois. La derni&egrave;re correction date de il y a onze jours et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: sommation vers trace de produit matrices
il y a onze jours
C'est bien la peine d'avoir détaillé le calcul de $\mathrm{tr}(M^{\mathsf T} E_{i,j} M)$ à la fin de ce message !
N.B. $A=\sum_{i,j} a_{i,j}E_{i,j}$.
Re: sommation vers trace de produit matrices
il y a dix jours
Je vous remercie beaucoup pour votre aide, c'est plutôt clair maintenant.
P.
Re: sommation vers trace de produit matrices
il y a dix jours
Si $M^T=[m_1,\ldots,m_n]$ alors $MM^T=(\langle m_i,m_j\rangle)_{1\leq i,j\leq n}.$ Alors puisque $\mathrm{trace}(BC)=\mathrm{trace}(CB) $ on a $$
\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.$$



Edité 1 fois. La derni&egrave;re correction date de il y a dix jours et a &eacute;t&eacute; effectu&eacute;e par AD.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 124 440, Messages: 1 188 305, Utilisateurs: 19 594.
Notre dernier utilisateur inscrit senpai.


Ce forum
Discussions: 14 989, Messages: 145 232.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page