We know that a $2-$ lift of a graph is specified by a $\pm 1$ assignment on the edges of the graph ( given as a signing matrix) denoting which edge is to be duplicated by the identity permutation on two elements or which is to be lifted with a flip.

We know that the adjacency spectrum of the 2-lifted graph is the union (with multiplicity) of the adjacency spectrum of the initial graph and the spectrum of the signing matrix.

  • Is there any generalization of the above for the spectrum of any of the Laplacians as given below? (I am particularly interested in $L4$)

$L1 = D - A$ where $D$ is the diagonal matrix of vertex degrees and $A$ is the adjacency matrix. (the ordinary "Laplacian")

$L2 = BB^T$, the ``Unsigned Laplacian" where $B$ is the vextex-edge incidence matrix. ($B(v,(a,b)) = 1,0,-1$ depending on whether $v=a$ or $v \neq a,b$ or $v=b$ respectively)

$L3$ s.t $L3_{ii} = deg(v_i)$ and $L3_{ij} = \frac{ -1}{ \sqrt{ deg(v_i) deg(v_j) } } $. This is the ``Normalized Laplacian"

$L4 = \sum _{edges} (v_{+} v_{+}^T \text{ or } v_{-} v_{-}^T)$ where for any edge $(s,t)$ $v_{+} = e_s + e_t$ and $v_{-} =e_s -e_t$ where $e_i$ is a $\vert V \vert$ size column vector with $1$ at the $i^{th}$ row and $0$ elsewhere. This is the ``Signed Laplacian"


1 Answer 1


If $Y$ is a 2-lift of $X$, there is a partition $\pi$ of $V(Y)$ into pairs, such that vertices in a pair are not adjacent and two distinct pairs are joined by a 2-matching, or by no edges at all. Assume $n=|V(X)|$ and let $P$ be the $2n\times n$ matrix whose columns are the characteristic vectors of the pairs. Let $Q$ be the $2n\times n$ matrix we get by replacing one 1 in each column of $P$ by $-1$. Note that $P^TQ=0$ and both $P$ and $Q$ have rank $n$. Let $M$ be the matrix $[P Q]$. Note that $M^TM=2I$.

Let $A$ be the adjacency matrix of $Y$ and let $D$ be its diagonal matrix of degrees and consider the matrix $B=\frac12 M^TAM$. The column space of $P$ is $A$-invariant (because $\pi$ is an equitable partition for $Y$); since the column space of $Q$ is the orthogonal complement of the column space of $P$, it is also $A$-invariant. Therefore $B$ is block diagonal. The $(1,1)$-block is $A(X)$ and the $(2,2)$-block is the signed adjacency matrix of $X$, which I will denote by $S$.

Now let $D$ be the diagonal matrix of degrees of $Y$, let $D_X$ be the diagonal matrix of degrees of $X$ and let $A_X$ be the adjacency matrix of $X$. Since two vertices in the same cell of $\pi$ have the same degree, $DP=PD_X$ and $DQ=QD_X$. Hence $M^TDM$ is block diagonal, with both diagonal blocks equal to $D_X$.

From this we see that $\frac12 M^T(A+D)M$ is block diagonal with blocks $A_X+D_X$ and $S+D_X$, and $\frac12 M^T(D-A)M$ is block diagonal with blocks $D_X-A_X$ and $D_X-S$.

I'll leave the other two cases as exercises.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.