# Laplacian and Energy in Graphs

If $E$ is a digraph (say, irreflexive binary relation on a set $V$), we then defined the incidence matrix $[E]$ as the $|V|\times |V|$ matrix whose $ij$ entry was $1$ iff $(i,j)\in E$ for vertices $i,j.$  NOTE:  This definition is not the traditional one;  I accidentally wrote it incorrectly in a previous post and have made the correction to that definition.  The correct definition of $[E]$ is the $|V|\times |E|$ matrix where the $i,(j,k)$ entry is $1$ iff $1=i$ or $1=j$.  That is, the entry $i,(j,k)$ is $1$ iff $i$ is a vertex on the edge $(j,k).$  We can then define the Laplacian of $E$ as

$L(E)=[E][E]^\top.$

We will simply write $L$ as the Laplacian when it is clear what digraph we are discussing.

Now consider a map $f:V\to\mathbb{R}^m$ and the corresponding $|V|\times m$ matrix whose $i$th row is $f(i).$  We will denote this matrix $f(V).$  The authors ([1]) call the map $f$ a representation of the graph (or digraph in our case) in $\mathbb{R}^m.$  As the $m$-vectors $f(i)$ aren’t operators on $\mathbb{R}^m,$ it seems counterintuitive to call the map a representation, but I will discuss an $m\times m$ matrix they mention in a bit.

Definition 1.  Let $\|\cdot\|=\|\cdot\|_2.$  We define the energy with respect to $f$ of the graph $E$ by

$\displaystyle\mathcal{E}_f(E)=\sum_{(i,j)\in E}\|f(i)-f(j)\|^2.$

Furthermore we can define each edge to have a weight $w((i,j))=w_{ij}\in\mathbb{R}^+$ and define the weighted energy of $E$ with respect to $f$ and $w$ by

$\displaystyle\mathcal{E}_{f,w}(E)=\sum_{(i,j)\in E}w_{ij}\|f(i)-f(j)\|^2.$

Now let $W$ be the diagonal $|E|\times |E|$ matrix whose diagonal $(i,j),(i,j)$ entry is $w_{ij}$ for a chosen weight function $w.$

Proposition 2.  Let $E$ be an antisymmetric ($(i,j)\in E\Rightarrow (j,i)\notin E$) digraph on $V$, $f:V\to\mathbb{R}^m,$ and $w$ be a weight function on $E.$  Then

$\displaystyle\mathcal{E}_{f,w}(E)=\mbox{tr~}f(V)^\top[E]W[E]^\top f(V).$

One may call the matrix $[E]W[E]^\top$ the weighted Laplacian of $E.$  Now the matrix $f(V)^\top [E]W[E]^\top f(V)$ is an $m\times m$ matrix which depends upon a triple $(E,f,w)$ with $E$ an antisymmetric digraph on $V,$ $f:V\to\mathbb{R}^m,$ and $w:E\to\mathbb{R}^+.$  So we could define a map $\rho_E:F\times W\to L(\mathbb{R}^m)$ where

$\displaystyle\rho_E((f,w))=f(V)^\top [E]W[E]^\top f(V).$

Unfortunately this map isn’t a homomorphism, and hence not technically a representation;  I couldn’t find a simple structure on $F\times W$ compatible with addition of $m\times m$ matrices.

[1]  Godsil, Chris and Gordon Royle.  Algebraic Graph Theory.  Graduate Texts in Mathematics.  Vol. 207.  Springer Science and Business Media.  2004.