# How to prove $\sum_{i,j}y_{i}^{T}y_{j} W_{i,j}=tr(Y^{T}WY)$

How to prove $\sum_{i,j}\mathbf{y_{i}}^{T}\mathbf{y_{j}} \mathbf{W_{i,j}}=tr(Y^{T}WY)$, where $Y,W\in\mathbb{R}^{n\times n}, Y=[y_{1},y_{2},...,y_{n}]$? I know that $\mathrm{tr}(X^{\rm T}Y)=\sum_{i,j}X_{i,j} Y_{i,j}$, but have no idea about the trace of product of three matrices.

-
Isn't it $=\mathrm{tr}Y^TLY$, where $L$ is the Laplacian matrix (en.wikipedia.org/wiki/Laplacian_matrix)? – ziyuang Apr 18 '12 at 18:06
Try playing with the fact that $tr(ABC)=tr(BCA)=tr(CAB)$. It might help to think of $Y^TY$ as a single matrix. What are its entries? – Alex R. Apr 18 '12 at 18:08
@ziyuang Yes, you're right. Thanks. – Stupident Apr 18 '12 at 18:17
@Sam I know it, but still can't figure out how to rewrite the summation as trace of product of matrices. – Stupident Apr 18 '12 at 18:25
So for two matrices $A=(a_{ij})$ and $B=(b_{ij})$, letting $C=(c_{ij})=AB$ we have $c_{ij}=\sum_k a_{ik}b_{kj}$ so then $tr(C)=\sum_i\sum_k a_{ik}b_{ki}$. – Alex R. Apr 18 '12 at 18:30

I think $Y$ should be written as $Y^T=[y_1,\dots,y_n]$ instead of $Y=[y_1,\dots,y_n]$. Then we can have the result.
$\mathrm{tr}(Y^TWY)=\mathrm{tr}(YY^TW)=\mathrm{tr}(AW)$, where $A=YY^T$. Since $[AW]_{ij}=\sum_kA_{ik}W_{kj}$, $\mathrm{tr}(AW)=\sum_{i}[AW]_{ii}=\sum_{i}\sum_{k}A_{ik}W_{ki}$. Note $A=YY^T$, so $[A]_{ik}=y_i^Ty_k$. Thus $\mathrm{tr}(AW)=\sum_{i}\sum_{k}y_i^Ty_kW_{ki}$.