4
$\begingroup$

I'm a noob cs masters student trying to understand how the laplacian and the Dirichlet sum are related. So there is this popular expression with graph adjacency matrix $A$ and the laplacian $L$,

$$ \sum_{ij}A_{ij}(x_i -x_j)^2 = x^tLx. $$

I'm trying to find the proof for this (for specific problem of undirected graphs). I tried to expand this out as $$ \sum_{ij}A_{ij}(x_i -x_j)^2 = \sum_{ij}A_{ij}x_i^2 + \sum_{ij}A_{ij}x_j^2 - 2\sum_{ij}A_{ij}x_ix_j \\ = \sum_{i}x_id_i + \sum_{j}x_jd_j - 2\sum_{ij}A_{ij}x_ix_j. \\ $$ Where $d$ is the degree vector. Now, I know that $L = diag(d)-A$. My question is how do I get from the result before to $x^tLx$. I apologize if this is a stupid question, I tried finding proofs online but could not find a simple solution.

edit: typo in equation

$\endgroup$
3
  • $\begingroup$ I'm glad it helped, good question too $\endgroup$
    – Dabed
    Mar 17, 2020 at 20:58
  • $\begingroup$ Thanks Daniel, one question though. Shouldn't the dirac function be $\delta_{ii}$? That would mean the value is one only in the diagonals right? $\endgroup$ Mar 18, 2020 at 21:15
  • $\begingroup$ yes is only one value what we desire but we have to go trough all them $(\delta_{i1},\delta_{i2},...,\delta_{ii},...,\delta_in)=(0,0,...,\delta_{ii}=1,...0)$ so effectively only survives the one that is in the diagonal that is $\delta_{ii}=1$ and $\delta_{ij\neq i}=0$, notice $\delta_{ij}$ is a function of $j$ then if you write $\delta_{ii}$ you have already evaluated you variable at the point $j=i$ so is no longer a function of $j$ that means $\sum_jd_j\delta_{ii}=\delta_{ii}\sum_jd_j=\sum_jd_j$, instead of $\sum_jd_j\delta_{ij}=d_i$ $\endgroup$
    – Dabed
    Mar 18, 2020 at 21:49

1 Answer 1

3
$\begingroup$

$\sum_{ij,j<i}A_{ij}(x_i -x_j)^2\\ =\frac{1}{2}\sum_{ij}A_{ij}(x_i-x_j)^2\\ =\frac{1}{2}\sum_i\sum_jA_{ij}(x_i^2+x_j^2-2x_ix_j)\\ =\frac{1}{2}(\sum_ix_i^2\sum_jA_{ij}+\sum_jx_j^2\sum_iA_{ij}-2\sum_{ij}A_{ij}x_ix_j)\\ =\frac{1}{2}(\sum_ix_i^2d_i+\sum_jx_j^2d_j-2\sum_{ij}A_{ij}x_ix_j)\\ =\frac{1}{2}(\sum_ix_i^2d_i+\sum_ix_i^2d_i-2\sum_{ij}A_{ij}x_ix_j)\\ =\frac{1}{2}(2\sum_ix_i^2d_i-2\sum_{ij}A_{ij}x_ix_j)\\ =\sum_ix_i(x_id_i-\sum_j A_{ij}x_j)\\ =\sum_ix_i(d_i\sum_j\delta_{ij}x_j-\sum_j A_{ij}x_j)\\ =\sum_i x_i\sum_j(d_i\delta_{ij}-A_{ij})x_j\\ =\sum_i\sum_j x_i(d_i\delta_{ij}-A_{ij})x_j\\ =\sum_{ij}x_iLx_j\\ =x^tLx $

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .