Laplacian spectrum of $2-$lifts of graphs

Question

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"

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.