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


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 ith 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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: