Question

1. Let G = (V, E) be an undirected and connected graph with Laplacian matrix L.

   1. (a) How are the eigenvalues of L² related to the eigenvalues of L?

   2. (b) If instead of running the consensus protocol, x ̇ = −Lx, one runs the protocol from Homework 1, given by

      x ̇ = −L²x, will consensus still be achieved? Justify your answer.

   3. (c) Assuming both x ̇ = −Lx and x ̇ = −L²x converge, which protocol converges faster? Justify your answer.

Answer 1

Part-(a):

The eigenvalues of are square of the eigenvalues of .

Let be an eigenvalue of having corresponding eigenvector .

Then

Thus is an eigenvalue of with corresponding eigenvector .

Part-(b):

Yes the consensus will still be achieved because as shown above the eigenvalues of   are square of the eigenvalues of ..

Part-(c):

The eigenvalues of converges faster than