Laplacian Matrix

Laplacian Matrix

Introduction

The heart and core of this paper is to provide an explanation and proof for proposition 3.1 and theorems 3.2 and 3.3 in article “On the asymptotic properties of the group lasso estimator for linear models” written by Yuval Nardi and Alessandro Rinaldo.

Laplacian Matrix

In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be used to find many other properties of the graph, see spectral graph theory.

Proof for Proposition

Given a graph G with n vertices (without loops or multiple edges), its Laplacian matrix is defined as

That is, it is the difference of the degree matrix and the adjacency matrix of the graph. In the case of directed graphs, either the indegree or the outdegree might be used, depending on the application.

The normalized laplacian matrix is defined as

Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a (0,1)-matrix with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise).

For a given connected graph G with n labeled vertices, let be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is

Equivalently the number of spanning trees is equal to the absolute value of any cofactor of the Laplacian matrix of G.

We first construct the Laplacian matrix Q for the graph G which can be shown to be such that:

for i ? j

if vertex i is adjacent to vertex j in G, qi,j ...