betaFeedback

WorksMathematics

Non-backtracking Laplacian for hypergraphs

Abstract

We extend the non-backtracking Laplacian for graphs, introduced by Jost, Mulas and Torres, to hypergraphs. The operator is defined on the permutations of the edges and is normalized by the number of edges through which a non-backtracking walk can continue. We show that it satisfies a symmetry that generalizes the graph case, and that it can be obtained from the random walk Laplacian of a directed graph by rescaling if and only if all edges have the same cardinality. Moreover, we show that, up to copies of the eigenvalue 11, its spectrum can be computed from a much smaller matrix indexed by the incidences of the hypergraph, and we use this reduction to bound the remaining eigenvalues away from 11.

Introduction

Spectral graph theory studies the structural properties of a graph that are encoded in the eigenvalues of its associated operators, such as the adjacency matrix and the various Laplacians [15, 12, 21]. Among these, the non-backtracking matrix is of theoretical interest [18, 37, 36] and has proved remarkably effective in applications ranging from community detection [11, 22, 31, 10, 9] to node centrality [4, 23, 24, 39] and percolation [33, 13, 25]. Moreover, in [20], Jost, Mulas and Torres introduced the non-backtracking Laplacian and showed, computationally for graphs with a small number of nodes, that cospectral pairs are rarer for this operator than for the adjacency matrix, the Kirchhoff Laplacian, the normalized Laplacian and the non-backtracking matrix. Further spectral properties of this operator were established in [29], and a graph coloring number arising from that work was studied in [27].

The idea behind non-backtracking operators for graphs is the following. Fix a simple graph G=(V,E)G = (V, E) on NN nodes and MM edges, with minimum degree ≥2\ge2. Choosing an orientation for an edge means letting one of its endpoints be its input and the other its output, and we write e=[v,w]e = [v, w] for the oriented edge with input in⁡(e)=v\operatorname{in}(e) = v and output out⁡(e)=w\operatorname{out}(e) = w. Moreover, we let e−1:=[w,v]e^{-1} := [w, v] be the inverse of ee, and we let e1,…,e2Me_1, \ldots, e_{2M} denote the 2M2M oriented edges of GG. A non-backtracking random walk on GG is the Markov process on the oriented edges in which the walker at eie_i moves to each eje_j with out⁡(ei)=in⁡(ej)\operatorname{out}(e_i) = \operatorname{in}(e_j) and ej≠ei−1e_j \ne e_i^{-1} with equal probability 1/(deg⁡(out⁡(ei))−1)1/(\deg(\operatorname{out}(e_i)) - 1), and the minimum degree assumption guarantees that at least one such eje_j exists. Seen as a process on VV the same walk is not Markovian, since the steps available at a vertex depend on how the walker arrived there, which is why we look at the oriented edges (Figure 1). The non-backtracking graph of GG (Figure 2), denoted NB(G)\mathcal{NB}(G), was introduced in 1989 by Hashimoto [19] as the directed graph whose vertices are the 2M2M oriented edges of GG, having a directed edge from eie_i to eje_j precisely when the above transition is admissible, that is, when out⁡(ei)=in⁡(ej)\operatorname{out}(e_i)=\operatorname{in}(e_j) and ej≠ei−1e_j \ne e_i^{-1}. The transpose of the adjacency matrix of NB(G)\mathcal{N}\mathcal{B}(G) is the non-backtracking matrix of GG, while the random walk Laplacian of NB(G)\mathcal{N}\mathcal{B}(G) is the non-backtracking Laplacian of GG [20].

A non-backtracking walk on vertices and oriented edges

Figure 1. A non-backtracking walk is not Markovian as a process on the vertices, but it becomes Markovian as a process on the oriented edges. In (a) the cyclist only knows that they are at the vertex ww, and this is not enough to decide along which of the three edges at ww they may continue. In (b) their position is the oriented edge [v,w][v,w], which already records the vertex they came from: they may continue along [w,z][w,z] or along [w,u][w,u] (in purple), but not back along [w,v][w,v] (dashed).

Figure 2. From a graph to its non-backtracking graph: the nodes of NB(G)\mathcal{NB}(G) are the oriented edges of GG, with a directed edge from eie_i to eje_j when the output of eie_i is the input of eje_j and ej≠ei−1e_j \ne e_i^{-1}.

Hypergraphs, in which an edge may join any number of vertices, are the natural model for higher-order interactions, and their spectral theory has been developed for several operators; see, for instance, [6, 21] and the references therein. Non-backtracking techniques for hypergraphs have appeared as well: operators defined on the incidences of a hypergraph, that is, the edge–vertex pairs (e,v)(e,v) with v∈ev \in e, go back to the zeta function of Storm [35], and underlie spectral clustering and detectability methods [3, 14, 34] as well as the theory of percolation on hypergraphs [8]. These operators, however, are all of adjacency type, and to the best of our knowledge no Laplacian analogue has been proposed so far.

The closest object appears in the literature on hypergraph sampling: Nakajima, Kodakari and Aida [30] consider a non-backtracking walk that avoids both the previously visited node and the previously traversed edge, and derive its stochastic transition matrix on the incidences, together with its stationary distribution, with the aim of obtaining unbiased estimators of structural properties of large hypergraphs. Such a transition matrix does induce a Laplacian; being row-stochastic by construction, however, it is the random walk Laplacian of a weighted directed graph on the incidences, and its spectral theory is therefore that of a directed graph. This is an instance of a general phenomenon: transition probabilities are pairwise relations between states, and every hypergraph random walk Laplacian coincides with the random walk Laplacian of a weighted graph [28 Theorem 4.5]. An operator that is not reducible to a graph Laplacian must therefore fail to be row-stochastic, and the one we introduce below does. When and why higher-order models resist reduction to graph descriptions is currently under active discussion [38, 26, 32].

In this paper, we propose and study a generalization of the non-backtracking Laplacian for graphs [20, 29] to the case of hypergraphs. In line with the above discussion, a hypergraph Laplacian that cannot be reduced to the graph case must give up row stochasticity, and the off-diagonal entries of our operator are therefore not always probabilities.

Structure of the paper

In Section 2 we introduce the non-backtracking graph, matrix and Laplacian of a hypergraph, which reduce to those of [20] for graphs, and in Section 3 we compute the degrees and the size of the non-backtracking graph. In Section 4 we establish the first spectral properties of the non-backtracking Laplacian, including a symmetry that generalizes that of the graph case, and we show that it is an affine function of the random walk Laplacian of the non-backtracking graph if and only if the hypergraph is uniform. Finally, in Section 5, we study the eigenvalue 1, we show that the remaining eigenvalues can be computed from a smaller matrix, indexed by the incidences of the hypergraph, and we bound these eigenvalues away from 1.

Non-backtracking operators for hypergraphs

Throughout the paper we fix a hypergraph G=(V,E)G=(V,E) on NN nodes and MM edges. We let e1,…,eMe_1,\ldots,e_M denote the edges of GG and, given i∈{1,…,M}i\in\{1,\ldots,M\}, we let ci:=∣ei∣c_i:=|e_i| denote the cardinality of eie_i. We assume that GG has no repeated edges, that is, ei≠eje_i\ne e_j for i≠ji\ne j.

The degree of a vertex v∈Vv\in V, denoted deg⁡v\deg v, is the number of edges in which it is contained. We assume, from here on, that GG has minimum vertex degree δ≥2\delta\ge2 and minimum edge cardinality κ≥2\kappa\ge2. We also let

K:=max⁡iciandΔ:=max⁡v∈Vdeg⁡v.K:=\max_{i}c_i \quad\text{and}\quad\Delta:=\max_{v\in V}\deg v.

Moreover, given i∈{1,…,M}i\in\{1,\ldots,M\}, we let

ei(1),…,ei(ci!)e_i^{(1)},\ldots,e_i^{(c_i!)}

denote the ci!c_i! permutations of the vertices in eie_i, listed with a fixed order.

Definition 2.1. Given a permutation ei(α)e_i^{(\alpha)} of eie_i, we say that its first entry is its input, and we denote it by in⁡(ei(α))\operatorname{in}(e_i^{(\alpha)}); we say that its last entry is its output, and we denote it by out⁡(ei(α))\operatorname{out}(e_i^{(\alpha)}). Moreover, we let

d(ei(α)):=deg⁡(out⁡(ei(α)))−1.d(e_i^{(\alpha)}):=\deg\bigl(\operatorname{out}(e_i^{(\alpha)})\bigr)-1.

Example 2.2. If ei={v1,v2,v3}e_i=\{v_1,v_2,v_3\}, then ci!=3!=6c_i!=3!=6, and we can let

ei(1):=(v1,v2,v3),ei(2):=(v1,v3,v2),e_i^{(1)}:=(v_1,v_2,v_3),\qquad e_i^{(2)}:=(v_1,v_3,v_2),
ei(3):=(v2,v1,v3),ei(4):=(v2,v3,v1),e_i^{(3)}:=(v_2,v_1,v_3),\qquad e_i^{(4)}:=(v_2,v_3,v_1),
ei(5):=(v3,v1,v2),ei(6):=(v3,v2,v1).e_i^{(5)}:=(v_3,v_1,v_2),\qquad e_i^{(6)}:=(v_3,v_2,v_1).

With this fixed order of the permutations of eie_i, we have that

v1=in⁡(ei(1))=in⁡(ei(2))=out⁡(ei(4))=out⁡(ei(6)),v_1=\operatorname{in}(e_i^{(1)})=\operatorname{in}(e_i^{(2)})=\operatorname{out}(e_i^{(4)})=\operatorname{out}(e_i^{(6)}),

and

d(ei(4))=deg⁡(out⁡(ei(4)))−1=deg⁡(v1)−1.d(e_i^{(4)})=\deg\bigl(\operatorname{out}(e_i^{(4)})\bigr)-1=\deg(v_1)-1.

Remark 2.3 (Permutations as orientations). The permutations of the edges generalize the orientations of graph edges. In fact, if GG is a graph, i.e. ci=2c_i=2 for all ii, then each edge ei={v,w}e_i=\{v,w\} has exactly two permutations, (v,w)(v,w) and (w,v)(w,v), and these are precisely its two orientations [v,w][v,w] and [v,w]−1=[w,v][v,w]^{-1}=[w,v] in the sense of [20]. In particular, the input and the output of Definition 2.1 are those of the corresponding oriented edge, and d(ei(α))d(e_i^{(\alpha)}) is the number of edges along which a non-backtracking walk that reaches out⁡(ei(α))\operatorname{out}(e_i^{(\alpha)}) through eie_i can continue. When ci≥3c_i\ge3, on the other hand, eie_i has more than two permutations, and when ci≥4c_i\ge4, a permutation is no longer determined by its input and output, since it also fixes the order in which the remaining ci−2c_i-2 vertices appear.

This generalization is not the only possible one, and several non-equivalent notions of orientation for hypergraph edges exist in the literature: an oriented edge may be defined as a pair of disjoint vertex sets, its tail and its head [17], as an ordered partition of its vertices [16], or as a list of its vertices in a fixed order [5]. All of them reduce to the orientations of a graph edge when ci=2c_i=2. We adopt the last notion: the permutations ei(1),…,ei(ci!)e_i^{(1)},\ldots,e_i^{(c_i!)} are precisely the orientations of eie_i in the sense of [5], and their first and last entries provide the input and the output needed by the non-backtracking walk.

Generalizing the construction for graphs, we now define the non-backtracking graph of GG by letting the permutations of the edges play the role of the oriented edges. More precisely, a non-backtracking walk on GG moves from a permutation of eie_i to a permutation of a different edge eje_j, provided that the input of the latter is the output of the former (Figure 3).

A step of the non-backtracking walk on a hypergraph

Figure 3. A step of the non-backtracking walk on a hypergraph. The cyclist’s position is the permutation (u,v,w)(u,v,w) of e1e_1, whose output is ww. They may continue along any permutation of a different edge whose input is ww, namely (w,x,y)(w,x,y) and (w,y,x)(w,y,x) (in purple), but not along a permutation of e1e_1, such as (w,v,u)(w,v,u) (dashed).

Definition 2.4. The non-backtracking graph of GG is the directed graph G:=NB(G)=(V,E)\mathcal{G} := \mathcal{N}\mathcal{B}(G) = (\mathcal{V},\mathcal{E}) such that:

  • V:={ei(α):i∈{1,…,M} and α∈{1,…,ci!}}\mathcal{V} := \{e_i^{(\alpha)} : i \in\{1,\ldots,M\} \text{ and } \alpha\in\{1,\ldots,c_i!\}\};

  • There exists a directed edge ei(α)→ej(β)e_i^{(\alpha)} \to e_j^{(\beta)} in E\mathcal{E} if and only if

out⁡(ei(α))=in⁡(ej(β)) and i≠j.\operatorname{out}(e_i^{(\alpha)}) = \operatorname{in}(e_j^{(\beta)}) \text{ and } i \ne j.

Note that G\mathcal{G} has ∣V∣=∑i=1Mci!|\mathcal{V}| = \sum_{i=1}^{M} c_i! nodes, which reduces to the 2M2M oriented edges when GG is a graph.

We now generalize the non-backtracking matrix and the non-backtracking Laplacian of a graph as follows.

Definition 2.5. Let A\mathcal{A} be the adjacency matrix of G\mathcal{G}, i.e. the ∣V∣×∣V∣|\mathcal{V}| \times|\mathcal{V}| matrix with (0,1)(0,1)–entries such that

Aei(α),ej(β)=1⟺out⁡(ei(α))=in⁡(ej(β)) and i≠j.\mathcal{A}_{e_i^{(\alpha)},e_j^{(\beta)}} = 1 \Longleftrightarrow\operatorname{out}(e_i^{(\alpha)}) = \operatorname{in}(e_j^{(\beta)}) \text{ and } i \ne j.

The non-backtracking matrix of GG is AT\mathcal{A}^{\mathsf{T}}.

Definition 2.6. The non-backtracking Laplacian of GG is the ∣V∣×∣V∣|\mathcal{V}| \times|\mathcal{V}| matrix

L:=Id⁡−D−1A,\mathcal{L} := \operatorname{Id} - D^{-1}\mathcal{A},

where Id⁡\operatorname{Id} denotes the identity matrix and

D:=diag⁡(d(e1(1)),…,d(e1(c1!)),…,d(eM(1)),…,d(eM(cM!))).D := \operatorname{diag}\left(d(e_1^{(1)}),\ldots,d(e_1^{(c_1!)}),\ldots,d(e_M^{(1)}),\ldots,d(e_M^{(c_M!)})\right).

Note that DD is invertible, since the assumption that δ≥2\delta\ge2 implies that

d(ei(α))=deg⁡(out⁡(ei(α)))−1≥1d(e_i^{(\alpha)}) = \deg(\operatorname{out}(e_i^{(\alpha)})) - 1 \ge1

for every ei(α)∈Ve_i^{(\alpha)} \in\mathcal{V}. Hence, L\mathcal{L} is well-defined.

Remark 2.7 (Consistency with the graph case). If GG is a graph, then Definitions 2.4, 2.5 and 2.6 recover the non-backtracking graph, matrix and Laplacian of [20]. In fact, by Remark 2.3, in this case the nodes of G\mathcal{G} are the oriented edges of GG, and two oriented edges e,fe,f with out⁡(e)=in⁡(f)\operatorname{out}(e)=\operatorname{in}(f) belong to distinct edges if and only if in⁡(e)≠out⁡(f)\operatorname{in}(e)\ne\operatorname{out}(f). Moreover, d(ei(α))d(e_i^{(\alpha)}) is the out-degree of ei(α)e_i^{(\alpha)} in GG; therefore L\mathcal{L} is the random walk Laplacian of GG.

Degrees and size of the non-backtracking graph

In this section we study the first structural properties of the non-backtracking graph G\mathcal{G}. Recall from Definition 2.1 that

d(ei(α))=deg⁡(out⁡(ei(α)))−1d(e_i^{(\alpha)})=\deg(\operatorname{out}(e_i^{(\alpha)}))-1

counts the edges through which a non-backtracking walk can continue after leaving eie_i through its output. If GG is a graph, this number coincides with the out-degree of ei(α)e_i^{(\alpha)} in GG (Remark 2.7). We now compute the in- and out-degrees of the nodes of G\mathcal{G}, and we show that d(ei(α))d(e_i^{(\alpha)}) coincides with the out-degree deg⁡Gout(ei(α))\deg_{\mathcal{G}}^{\mathrm{out}}(e_i^{(\alpha)}) for every node of G\mathcal{G} only in the graph case. In general, the out-degree counts the permutations, rather than the edges, through which the walk can continue. To count these permutations, we introduce the following notion.

Definition 3.1. The permutation degree of a vertex v∈Vv\in V is

pdeg⁡v:=∑ei∋v(ci−1)!,\operatorname{pdeg} v:=\sum_{e_i\ni v}(c_i-1)!,

i.e. the number of permutations ei(α)∈Ve_i^{(\alpha)}\in\mathcal{V} whose input is vv or, equivalently, the number of permutations whose output is vv.

Note that, if GG is a graph, then pdeg⁡v=deg⁡v\operatorname{pdeg}v=\deg v for every v∈Vv\in V.

Lemma 3.2. Let ei(α)∈Ve_i^{(\alpha)}\in\mathcal{V}, and let v:=out⁡(ei(α))v:=\operatorname{out}(e_i^{(\alpha)}) and w:=in⁡(ei(α))w:=\operatorname{in}(e_i^{(\alpha)}). Then,

deg⁡Gout(ei(α))=pdeg⁡v−(ci−1)!anddeg⁡Gin(ei(α))=pdeg⁡w−(ci−1)!.\deg_{\mathcal{G}}^{\mathrm{out}}(e_i^{(\alpha)})=\operatorname{pdeg}v-(c_i-1)! \qquad\text{and}\qquad \deg_{\mathcal{G}}^{\mathrm{in}}(e_i^{(\alpha)})=\operatorname{pdeg}w-(c_i-1)!.

In particular, every node of G\mathcal{G} has out-degree at least 1, and D\mathcal{D} coincides with the out-degree matrix of G\mathcal{G} if and only if GG is a graph.

Proof. By Definition 2.4, the out-neighbors of ei(α)e_i^{(\alpha)} are the permutations ej(β)e_j^{(\beta)} with j≠ij\ne i and in⁡(ej(β))=v\operatorname{in}(e_j^{(\beta)})=v. For each j≠ij\ne i with ej∋ve_j\ni v, there are exactly (cj−1)!(c_j-1)! permutations of eje_j whose input is vv. Therefore,

deg⁡Gout(ei(α))=∑j≠i,ej∋v(cj−1)!=pdeg⁡v−(ci−1)!,\deg_{\mathcal{G}}^{\mathrm{out}}(e_i^{(\alpha)})=\sum_{\substack{j\ne i,\,e_j\ni v}}(c_j-1)!=\operatorname{pdeg}v-(c_i-1)!,

and the formula for the in-degree follows in the same way, by counting, for each j≠ij\ne i with ej∋we_j\ni w, the (cj−1)!(c_j-1)! permutations of eje_j whose output is ww. Since deg⁡v≥δ≥2\deg v\ge\delta\ge2, there exists at least one j≠ij\ne i with ej∋ve_j\ni v, hence the out-degree is at least 1. Moreover, the sum above has exactly deg⁡v−1=d(ei(α))\deg v-1=d(e_i^{(\alpha)}) terms, each of which is at least 1. Hence, deg⁡Gout(ei(α))=d(ei(α))\deg_{\mathcal{G}}^{\mathrm{out}}(e_i^{(\alpha)})=d(e_i^{(\alpha)}) if and only if (cj−1)!=1(c_j-1)!=1, i.e. cj=2c_j=2, for every j≠ij\ne i with ej∋ve_j\ni v. Since every vertex of eie_i is the output of some permutation of eie_i, letting ei(α)e_i^{(\alpha)} range over all of V\mathcal{V} shows that D\mathcal{D} coincides with the out-degree matrix of G\mathcal{G} if and only if cj=2c_j=2 for every edge eje_j that meets some other edge. Since δ≥2\delta\ge2, every edge meets some other edge, hence this condition is equivalent to cj=2c_j=2 for all jj, that is, to GG being a graph. □

Remark 3.3. Fix ei(α)∈Ve_i^{(\alpha)} \in\mathcal{V} and let v:=out⁡(ei(α))v := \operatorname{out}(e_i^{(\alpha)}). The row of A\mathcal{A} indexed by ei(α)e_i^{(\alpha)} has an entry equal to 1 for each out-neighbor of ei(α)e_i^{(\alpha)} in G\mathcal{G}, and all other entries equal to 0, therefore it sums to deg⁡Gout(ei(α))\deg_{\mathcal{G}}^{\mathrm{out}}(e_i^{(\alpha)}). Multiplying by D−1D^{-1} divides this row by d(ei(α))=deg⁡v−1d(e_i^{(\alpha)}) = \deg v - 1. Hence, by Lemma 3.2, the row of D−1AD^{-1}\mathcal{A} indexed by ei(α)e_i^{(\alpha)} sums to

pdeg⁡v−(ci−1)!deg⁡v−1=1deg⁡v−1∑j≠i, ej∋v(cj−1)!.\frac{\operatorname{pdeg} v - (c_i - 1)!}{\deg v - 1} = \frac{1}{\deg v - 1} \sum_{\substack{j \ne i,\ e_j \ni v}} (c_j - 1)!.

The sum on the right has exactly deg⁡v−1\deg v - 1 terms, one for each edge through which the walk can continue after leaving eie_i at vv, and each term is at least 1. Therefore, the row sum is at least 1, with equality if and only if cj=2c_j = 2 for every j≠ij \ne i with ej∋ve_j \ni v. As in the proof of Lemma 3.2, this condition holds for every node of G\mathcal{G} if and only if G\mathcal{G} is a graph. Hence, in contrast with the graph case, D−1AD^{-1}\mathcal{A} is row-stochastic, and L\mathcal{L} is the random walk Laplacian of G\mathcal{G}, if and only if G\mathcal{G} is a graph.

We can now prove the following generalization of [20 Lemma 3.1].

Lemma 3.4. The non-backtracking graph G\mathcal{G} has

∣V∣=∑i=1Mci!nodes and∣E∣=∑v∈V∑(i,j):i≠j,v∈ei∩ej(ci−1)!(cj−1)!edges.|\mathcal{V}| = \sum_{i=1}^{M} c_i! \qquad\text{nodes and} \qquad |\mathcal{E}| = \sum_{v \in V} \sum_{\substack{(i,j):\,i \ne j,\\ v \in e_i \cap e_j}} (c_i - 1)!(c_j - 1)! \qquad\text{edges}.

Proof. The number of nodes was already observed after Definition 2.4. Now, observe that ∣E∣|\mathcal{E}| equals the sum of the out-degrees of the nodes of G\mathcal{G}. We group the nodes of G\mathcal{G} according to their edge and their output vertex: for each v∈Vv \in V and each ei∋ve_i \ni v, there are exactly (ci−1)!(c_i - 1)! permutations of eie_i whose output is vv, and by Lemma 3.2 each of them has out-degree pdeg⁡v−(ci−1)!\operatorname{pdeg} v - (c_i - 1)!. Hence,

∣E∣=∑v∈V∑ei∋v(ci−1)!(pdeg⁡v−(ci−1)!)|\mathcal{E}| = \sum_{v \in V} \sum_{e_i \ni v} (c_i - 1)! \left(\operatorname{pdeg} v - (c_i - 1)!\right)
=∑v∈V∑ei∋v(ci−1)!∑ej∋vj≠i(cj−1)!= \sum_{v \in V} \sum_{e_i \ni v} (c_i - 1)! \sum_{\substack{e_j \ni v\\ j \ne i}} (c_j - 1)!
=∑v∈V∑(i,j):i≠j,v∈ei∩ej(ci−1)!(cj−1)!.= \sum_{v \in V} \sum_{\substack{(i,j):\,i \ne j,\\ v \in e_i \cap e_j}} (c_i - 1)!(c_j - 1)!.

Remark 3.5. If G\mathcal{G} is a graph, then (ci−1)!=1(c_i - 1)! = 1 for all ii, therefore Lemma 3.4 gives

∣E∣=∑v∈Vdeg⁡v(deg⁡v−1)=∑v∈V(deg⁡v)2−2M,|\mathcal{E}| = \sum_{v \in V} \deg v(\deg v - 1) = \sum_{v \in V}(\deg v)^2 - 2M,

which is the same as in [20 Lemma 3.1].

We illustrate the results above on two families of hypergraphs. The first is a family of uniform hypergraphs, that is, hypergraphs whose edges all have the same cardinality; if this cardinality is κ\kappa, we say that the hypergraph is κ\kappa-uniform. Moreover, we say that a hypergraph is rr-regular if all its vertices have degree $r`.

Example 3.6. Given ℓ≥2\ell\ge2, the ℓ\ell-lattice is the hypergraph whose vertices are the ℓ2\ell^2 cells of an ℓ×ℓ\ell\times\ell grid and whose 2ℓ2\ell edges are its rows and columns [2, 1]. It is ℓ\ell-uniform and 22-regular, and for ℓ=2\ell= 2, it is the cycle graph on 4 vertices.

Let G\mathcal{G} be the 3-lattice (Figure 4a): its vertices are vabv_{ab} for a,b∈{1,2,3}a,b \in\{1,2,3\}, while its edges are the rows ea={va1,va2,va3}e_a = \{v_{a1},v_{a2},v_{a3}\} and the columns e3+b={v1b,v2b,v3b}e_{3+b} = \{v_{1b},v_{2b},v_{3b}\}. In this case, N=9N = 9, M=6M = 6, and ci=3c_i = 3 for all ii. Since deg⁡v=2\deg v = 2 for every vertex, we have d(ei(α))=1d(e_i^{(\alpha)}) = 1 for every permutation, so that D=Id⁡\mathcal{D} = \operatorname{Id} and L=Id⁡−A\mathcal{L} = \operatorname{Id} - \mathcal{A}. Moreover, pdeg⁡v=2⋅2!=4\operatorname{pdeg} v = 2 \cdot2! = 4 for every v∈Vv \in V, so that, by Lemmas 3.2 and 3.4, every node of G\mathcal{G} has out-degree pdeg⁡v−(ci−1)!=2\operatorname{pdeg} v - (c_i - 1)! = 2, and G\mathcal{G} has

The 3-lattice and a step of the walk from a permutation of $e_1$

Figure 4. In (a), the 3-lattice, whose edges are the rows e1,e2,e3e_1,e_2,e_3 and the columns e4,e5,e6e_4,e_5,e_6. In (b), the cyclist’s position is the permutation (v11,v12,v13)(v_{11},v_{12},v_{13}) of e1e_1, whose output is v13v_{13}. The only other edge through v13v_{13} is e6e_6, so the cyclist may continue along its (c6−1)!=2(c_6 - 1)! = 2 permutations with input v13v_{13} (in purple), but not along a permutation of e1e_1 (dashed).

∣V∣=6⋅3!=36nodes and∣E∣=∑v∈V2⋅2!⋅2!=72edges.|\mathcal{V}| = 6 \cdot3! = 36 \quad\text{nodes and} \quad|\mathcal{E}| = \sum_{v \in V} 2 \cdot2! \cdot2! = 72 \quad\text{edges}.

since each vertex lies in exactly two edges, which give two ordered pairs (i,j)(i,j). The local structure of G\mathcal{G} is shown in Figure 4b: from a permutation of a row with output vv, the walk can only continue into the unique column through vv, along either of its (3−1)!=2(3 - 1)! = 2 permutations with input vv, and vice versa. In particular, every walk on G\mathcal{G} alternates between permutations of rows and permutations of columns, therefore G\mathcal{G} is bipartite.

The 3-lattice

Figure 4a. The 3-lattice.

A step of the walk from a permutation of $e_1$

Figure 4b. A step of the walk from a permutation of e1e_1.

In the lattices, all edges have the same cardinality. In the next family, the cardinalities of the edges vary.

Example 3.7. Given k≥2k \ge2 and p≥2p \ge2, consider the rooted tree in which every node other than the leaves has exactly kk children and all leaves are at distance pp from the root (the complete kk-ary tree of depth pp). The (k,p)(k,p)-laminar hypergraph Λk,p\Lambda_{k,p} has as vertices the kpk^p leaves of the tree and, as edges, for each internal node of the tree, that is, for each node that is not a leaf, the set of leaves below it (Figure 5).

If an internal node has height ℓ∈{1,…,p}\ell\in\{1,\ldots,p\}, that is, if its leaves are at distance ℓ\ell below it, then it gives an edge of cardinality kℓk^\ell, which we call a level-ℓ\ell edge. In particular, any two edges are either disjoint or one of them contains the other.

Labeling the leaves by the words in {1,…,k}p\{1,\ldots,k\}^p, the level-ℓ\ell edges are the sets of words sharing the first p−ℓp-\ell letters. Hence, Λk,p\Lambda_{k,p} has N=kpN = k^p nodes and M=(kp−1)/(k−1)M = (k^p - 1)/(k - 1) edges, of which $k^{p-\ell}

Laminar hypergraph $\Lambda_{2,3}$ obtained from the binary tree of depth 3

Figure 5. The laminar hypergraph Λ2,3\Lambda_{2,3} obtained from the binary tree of depth 3. Each internal node of the tree gives the edge formed by the leaves below it, drawn in the same color: the four nodes at height 1 give the level-1 edges e1,…,e4e_1, \ldots, e_4, the two nodes at height 2 give the level-2 edges e5,e6e_5, e_6, and the root gives the level-3 edge e7e_7.

have cardinality kℓk^{\ell}; since every leaf has exactly one ancestor at each height, deg⁡v=p\deg v = p for all vv, and Λk,p\Lambda_{k,p} is non-uniform. Since δ=p\delta= p and κ=k\kappa= k, the hypergraph Λk,p\Lambda_{k,p} satisfies our assumptions.

We consider Λ2,3\Lambda_{2,3} (Figure 5), which has N=8N = 8, M=7M = 7, and edges of cardinality 2 (four of them, level 1), 4 (two of them, level 2) and 8 (one, level 3). Since deg⁡v=3\deg v = 3 for every vertex, we have that d(eiα)=2d(e_i^{\alpha}) = 2 for every permutation, therefore D=2Id⁡\mathcal{D} = 2\operatorname{Id} and

L=Id⁡−12A.\mathcal{L} = \operatorname{Id} - \frac{1}{2}\mathcal{A}.

Moreover, pdeg⁡v=∑ℓ=13(2ℓ−1)!=1!+3!+7!=5047\operatorname{pdeg} v = \sum_{\ell=1}^{3}(2^{\ell} - 1)! = 1! + 3! + 7! = 5047 for every v∈Vv \in V, hence, by Lemmas 3.2 and 3.4, a permutation of a level-ℓ\ell edge has out-degree 5047−(2ℓ−1)!5047 - (2^{\ell} - 1)! in G\mathcal{G} – namely 5046, 5041 and 7 for ℓ=1,2,3\ell= 1, 2, 3 – and G\mathcal{G} has

∣V∣=∑ℓ=1323−ℓ(2ℓ)!=4⋅2!+2⋅4!+8!=40376nodes and|\mathcal{V}| = \sum_{\ell=1}^{3} 2^{3-\ell}(2^{\ell})! = 4 \cdot2! + 2 \cdot4! + 8! = 40376 \quad\text{nodes and}
∣E∣=8(50472−(12+62+50402))=564576edges.|\mathcal{E}| = 8(5047^{2} - (1^{2} + 6^{2} + 5040^{2})) = 564576 \quad\text{edges.}

Comparing with Example 3.6 shows the effect of non-uniformity. As for the 3-lattice, all vertices of Λ2,3\Lambda_{2,3} have the same degree, therefore D\mathcal{D} is a scalar matrix; yet, since Λ2,3\Lambda_{2,3} is not uniform, the out-degrees in G\mathcal{G} depend on the level, ranging from 7 to 5046. Hence, the row sums of D−1A\mathcal{D}^{-1}\mathcal{A} equal 2523, 2520.5 and 3.5 on the permutations of the level-1, level-2 and level-3 edges, respectively, and D−1A\mathcal{D}^{-1}\mathcal{A} is far from being row-stochastic (Remark 3.3).

First spectral properties

We now turn to the spectral properties of L\mathcal{L}. Given a square matrix O\mathcal{O}, we let σ(O)\sigma(\mathcal{O}) denote its spectrum, and we let D(z,r)⊆CD(z,r) \subseteq\mathbb{C} denote the closed disk of center zz and radius rr.

If GG is a graph, then by [20 Remark 3.3], L\mathcal{L} has 2M2M eigenvalues (counted with algebraic multiplicity) that sum to 2M2M. Moreover, in this case σ(L)⊆D(1,1)\sigma(\mathcal{L}) \subseteq D(1,1) [7] and therefore, the real eigenvalues of L\mathcal{L} are contained in the interval [0,2][0,2]. For hypergraphs, these facts generalize as follows.

Proposition 4.1. The non-backtracking Laplacian L\mathcal{L} has ∑i=1Mci!\sum_{i=1}^{M} c_i! eigenvalues (counted with algebraic multiplicity) that sum to ∑i=1Mci!\sum_{i=1}^{M} c_i!. Moreover,

σ(L)⊆D(1,(K−1)!),\sigma(\mathcal{L}) \subseteq D(1,(K-1)!),

where KK is the largest edge cardinality. In particular, the real eigenvalues of L\mathcal{L} are contained in the interval [1−(K−1)!,1+(K−1)!][1-(K-1)!,1+(K-1)!].

Proof. Since L\mathcal{L} is a ∣V∣×∣V∣|\mathcal{V}|\times|\mathcal{V}| matrix, it has ∣V∣=∑i=1Mci!|\mathcal{V}|=\sum_{i=1}^{M}c_i! eigenvalues, counted with algebraic multiplicity, and their sum is tr⁡L\operatorname{tr}\mathcal{L}. Since all diagonal entries of L\mathcal{L} equal 11, we have that tr⁡L=∣V∣\operatorname{tr}\mathcal{L}=|\mathcal{V}|. This proves the first claim.

Now, all the Gershgorin disks of L\mathcal{L} are centered at 11. By Lemma 3.2, the radius of the disk corresponding to the row of L\mathcal{L} indexed by ei(α)e_i^{(\alpha)}, with v:=out⁡(ei(α))v:=\operatorname{out}(e_i^{(\alpha)}), is

1deg⁡v−1∑j≠i,ej∋v(cj−1)!≤(deg⁡v−1)⋅(K−1)!deg⁡v−1=(K−1)!,\frac{1}{\deg v-1}\sum_{\substack{j\ne i,e_j\ni v}}(c_j-1)! \le\frac{(\deg v-1)\cdot(K-1)!}{\deg v-1}=(K-1)!,

since the sum has exactly deg⁡v−1\deg v-1 terms, each bounded above by (K−1)!(K-1)!. Hence, by the Gershgorin Disk Theorem,

σ(L)⊆D(1,(K−1)!).\sigma(\mathcal{L})\subseteq D(1,(K-1)!).

:::

We now generalize [20 Theorem 3.8] to hypergraphs. To this end, we give the following definitions.

Definition 4.2. The reversal of a permutation ξ=(v1,v2,…,vc)∈V\xi=(v_1,v_2,\ldots,v_c)\in\mathcal{V} is the permutation ξˉ:=(vc,…,v2,v1)∈V\bar{\xi}:=(v_c,\ldots,v_2,v_1)\in\mathcal{V} of the same edge. We let PP be the ∣V∣×∣V∣|\mathcal{V}|\times|\mathcal{V}| permutation matrix of the map ξ↦ξˉ\xi\mapsto\bar{\xi}, and, given x,y∈C∣V∣\mathbf{x},\mathbf{y}\in\mathbb{C}^{|\mathcal{V}|}, we define their PP-product as

(x,y)P:=⟨x,Py⟩=x‾TPy,(\mathbf{x},\mathbf{y})_P:=\langle\mathbf{x},P\mathbf{y}\rangle=\overline{\mathbf{x}}^{\mathsf{T}}P\mathbf{y},

where ⟨x,y⟩:=x‾Ty\langle\mathbf{x},\mathbf{y}\rangle:=\overline{\mathbf{x}}^{\mathsf{T}}\mathbf{y} is the usual complex inner product.

With this notation, [20 Theorem 3.8] generalizes as follows.

Theorem 4.3. Let L\mathcal{L} be the non-backtracking Laplacian of a hypergraph. Then,

  1. LT=PLP\mathcal{L}^{\mathsf{T}}=P\mathcal{L}P, i.e., L\mathcal{L} is PTPT-symmetric;

  1. L\mathcal{L} is self-adjoint with respect to the PP-product, i.e., L\mathcal{L} is PP-self-adjoint;

  1. If (λ,x)(\lambda,\mathbf{x}) is an eigenpair for L\mathcal{L} and λ∈C\lambda\in\mathbb{C} is not real, then

∑i=1M∑ξ permutationof eixξˉ‾xξ=0.\sum_{i=1}^{M}\sum_{\substack{\xi\ \text{permutation}\\\text{of }e_i}}\overline{x_{\bar{\xi}}}x_{\xi}=0.

Proof. Note that, by definition, in⁡(ξˉ)=out⁡(ξ)\operatorname{in}(\bar{\xi})=\operatorname{out}(\xi) and out⁡(ξˉ)=in⁡(ξ)\operatorname{out}(\bar{\xi})=\operatorname{in}(\xi) for every ξ∈V\xi\in\mathcal{V}, and that PT=PP^{\mathsf{T}}=P and P2=Id⁡P^2=\operatorname{Id}, since reversing a permutation twice gives back the original one.

  1. Let ξ,η∈V\xi,\eta\in\mathcal{V} be permutations of eie_i and eje_j, respectively, so that ξˉ\bar{\xi} and ηˉ\bar{\eta} are also permutations of eie_i and eje_j. We write LξηL_{\xi\eta} for the entry of L\mathcal{L} in the row indexed by ξ\xi and the column indexed by η\eta. For ξ≠η\xi\ne\eta we have that

Lξˉηˉ=−1d(ξˉ)1[out⁡(ξˉ)=in⁡(ηˉ)]⋅1[i≠j]=−1d(ξˉ)1[in⁡(ξ)=out⁡(η)]⋅1[i≠j],L_{\bar{\xi}\bar{\eta}}=-\frac{1}{d(\bar{\xi})}\mathbb{1}\left[\operatorname{out}(\bar{\xi})=\operatorname{in}(\bar{\eta})\right]\cdot\mathbb{1}[i\ne j]=-\frac{1}{d(\bar{\xi})}\mathbb{1}\left[\operatorname{in}(\xi)=\operatorname{out}(\eta)\right]\cdot\mathbb{1}[i\ne j],

where 1\mathbb{1} denotes the indicator function. When this entry is non-zero, let u:=in⁡(ξ)=out⁡(η)u:=\operatorname{in}(\xi)=\operatorname{out}(\eta). Then,

d(ξˉ)=deg⁡(out⁡(ξˉ))−1=deg⁡u−1=deg⁡(out⁡(η))−1=d(η),d(\bar{\xi})=\deg(\operatorname{out}(\bar{\xi}))-1=\deg u-1=\deg(\operatorname{out}(\eta))-1=d(\eta),

so that Lξˉηˉ=LηξL_{\bar{\xi}\bar{\eta}}=L_{\eta\xi}. On the diagonal, both LξˉξˉL_{\bar{\xi}\bar{\xi}} and LξξL_{\xi\xi} equal 11, and ξˉ=ηˉ\bar{\xi}=\bar{\eta} if and only if ξ=η\xi=\eta. Therefore,

(PLP)ξη=Lξˉηˉ=Lηξ=(L⊤)ξη(PLP)_{\xi\eta}=L_{\bar{\xi}\bar{\eta}}=L_{\eta\xi}=(\mathcal{L}^{\top})_{\xi\eta}

for all ξ,η∈V\xi,\eta\in\mathcal{V}, which proves the first claim.

  1. Since P⊤=PP^{\top}=P and P2=Id⁡P^2=\operatorname{Id}, we have that

(x,Ly)P=⟨x,PLy⟩=⟨x,L⊤Py⟩=⟨Lx,Py⟩=(Lx,y)P,(\mathbf{x},\mathcal{L}\mathbf{y})_P=\langle\mathbf{x},P\mathcal{L}\mathbf{y}\rangle=\langle\mathbf{x},\mathcal{L}^{\top}P\mathbf{y}\rangle=\langle\mathcal{L}\mathbf{x},P\mathbf{y}\rangle=(\mathcal{L}\mathbf{x},\mathbf{y})_P,

where we have used that PL=L⊤PP\mathcal{L}=\mathcal{L}^{\top}P, which follows from the first claim, and that L\mathcal{L} is a real matrix. Therefore, L\mathcal{L} is self-adjoint with respect to the PP-product.

  1. The second claim implies that, if (λ,x)(\lambda,\mathbf{x}) is an eigenpair for L\mathcal{L}, then

λ(x,x)P=(x,λx)P=(x,Lx)P=(Lx,x)P=(λˉx,x)P=λˉ(x,x)P.\lambda(\mathbf{x},\mathbf{x})_P=(\mathbf{x},\lambda\mathbf{x})_P=(\mathbf{x},\mathcal{L}\mathbf{x})_P=(\mathcal{L}\mathbf{x},\mathbf{x})_P=(\bar{\lambda}\mathbf{x},\mathbf{x})_P=\bar{\lambda}(\mathbf{x},\mathbf{x})_P.

Hence, if λ≠λˉ\lambda\ne\bar{\lambda}, i.e. λ\lambda is not real, then (x,x)P=x⊤Px=0(\mathbf{x},\mathbf{x})_P=\mathbf{x}^{\top}P\mathbf{x}=0. Since (Px)ξ=xξˉ(P\mathbf{x})_{\xi}=x_{\bar{\xi}} for every ξ∈V\xi\in\mathcal{V}, this is the identity in the statement.

Remark 4.4. The proof of Theorem 4.3 only uses the fact that d(ei(α))d(e_i^{(\alpha)}) depends on out⁡(ei(α))\operatorname{out}(e_i^{(\alpha)}) alone. This singles out D\mathcal{D} among the natural ways of counting how the walk can continue after exiting eie_i at v:=out⁡(ei(α))v:=\operatorname{out}(e_i^{(\alpha)}), namely:

  • the number deg⁡v−1\deg v-1 of edges ej∋ve_j\ni v with j≠ij\ne i, which is our choice;

  • the number ∑ej∋v, j≠i(cj−1)\sum_{e_j\ni v,\ j\ne i}(c_j-1) of pairs (ej,w)(e_j,w) with ej∋ve_j\ni v, j≠ij\ne i and w∈ej∖{v}w\in e_j\setminus\{v\};

  • the number pdeg⁡v−(ci−1)!\operatorname{pdeg}v-(c_i-1)! of permutations, i.e. the out-degree of ei(α)e_i^{(\alpha)} in G\mathcal{G} (Lemma 3.2).

The last two also depend on ii, and therefore yield a PT-symmetric operator if and only if any two edges sharing a vertex have the same cardinality, i.e. if and only if every connected component of G\mathcal{G} is uniform; in this case, the three normalizations are proportional on each component.

On the other hand, only the last one always makes D−1A\mathcal{D}^{-1}\mathcal{A} row-stochastic: the first does so if and only if G\mathcal{G} is a graph (Remark 3.3), and the second if and only if all edges have at most 3 vertices. Hence, unless every connected component of G\mathcal{G} is uniform, none of these normalizations is both PT-symmetric and stochastic: our choice preserves the symmetry, at the price of stochasticity.

We conclude this section by showing that the uniform hypergraphs are precisely those for which L\mathcal{L} is an affine image of the random walk Laplacian of G\mathcal{G}, so that its spectrum is obtained from that of a random walk Laplacian by an affine transformation. To this end, we let DG\mathcal{D}_{\mathcal{G}} denote the out-degree matrix of G\mathcal{G}, and we let

Lrw:=Id−DG−1A\mathcal{L}_{\mathrm{rw}} := \mathrm{Id} - \mathcal{D}_{\mathcal{G}}^{-1}\mathcal{A}

denote the random walk Laplacian of G\mathcal{G}. Recall that GG is κ\kappa-uniform if all its edges have cardinality κ\kappa.

Proposition 4.5. There exist constants a,b∈Ra,b \in\mathbb{R} such that

L=aId+bLrw\mathcal{L} = a\mathrm{Id} + b\mathcal{L}_{\mathrm{rw}}

if and only if GG is uniform. In this case, if GG is κ\kappa-uniform, then a=1−(κ−1)!a = 1 - (\kappa- 1)! and b=(κ−1)!b = (\kappa- 1)!, and

  1. σ(L)\sigma(\mathcal{L}) is the image of σ(Lrw)\sigma(\mathcal{L}_{\mathrm{rw}}) under the map z↦1+(κ−1)!(z−1)z \mapsto1 + (\kappa- 1)!(z - 1);

  2. the constant functions are eigenfunctions of L\mathcal{L} with eigenvalue 1−(κ−1)!1 - (\kappa- 1)!.

Proof. Assume first that GG is κ\kappa-uniform. By Lemma 3.2, every ξ∈V\xi\in\mathcal{V} with v:=out⁡(ξ)v := \operatorname{out}(\xi) satisfies

deg⁡Gout(ξ)=(deg⁡v−1)(κ−1)!=(κ−1)!d(ξ).\deg^{\mathrm{out}}_{\mathcal{G}}(\xi) = (\deg v - 1)(\kappa- 1)! = (\kappa- 1)!d(\xi).

Hence DG=(κ−1)!D\mathcal{D}_{\mathcal{G}} = (\kappa- 1)!\mathcal{D}, and therefore

L=Id−D−1A=Id−(κ−1)!DG−1A=(1−(κ−1)!)Id+(κ−1)!Lrw.\mathcal{L} = \mathrm{Id} - \mathcal{D}^{-1}\mathcal{A} = \mathrm{Id} - (\kappa- 1)!\mathcal{D}_{\mathcal{G}}^{-1}\mathcal{A} = (1 - (\kappa- 1)!)\mathrm{Id} + (\kappa- 1)!\mathcal{L}_{\mathrm{rw}}.

Conversely, assume that L=aId+bLrw\mathcal{L} = a\mathrm{Id} + b\mathcal{L}_{\mathrm{rw}}. Let ξ∈V\xi\in\mathcal{V} be a permutation of eie_i with output vv. By Lemma 3.2, ξ\xi has at least one out-neighbor η\eta in G\mathcal{G}, and comparing the entries in position (ξ,η)(\xi,\eta) gives 1/d(ξ)=b/deg⁡Gout(ξ)1/d(\xi) = b/\deg^{\mathrm{out}}_{\mathcal{G}}(\xi), that is,

b=deg⁡Gout(ξ)d(ξ)=pdeg⁡v−(ci−1)!deg⁡v−1.b = \frac{\deg^{\mathrm{out}}_{\mathcal{G}}(\xi)}{d(\xi)} = \frac{\operatorname{pdeg}v - (c_i - 1)!}{\deg v - 1}.

If two edges eie_i and eje_j share a vertex vv, applying this to a permutation of eie_i and to a permutation of eje_j, both with output vv, gives (ci−1)!=(cj−1)!(c_i - 1)! = (c_j - 1)!, i.e. ci=cjc_i = c_j. Hence, every connected component of GG is uniform. Moreover, if the edges of a component have cardinality cc, then for every vertex vv of this component we have pdeg⁡v=deg⁡v(c−1)!\operatorname{pdeg}v = \deg v(c - 1)!, and the identity above gives b=(c−1)!b = (c - 1)!. Since bb does not depend on the component, all components have the same edge cardinality, that is, GG is uniform. Finally, comparing the diagonal entries, which are all equal to 11 in both L\mathcal{L} and Lrw\mathcal{L}_{\mathrm{rw}}, gives a=1−ba = 1 - b.

Claim 1 follows from the identity

L=(1−(κ−1)!)Id+(κ−1)!Lrw,\mathcal{L} = (1 - (\kappa- 1)!)\mathrm{Id} + (\kappa- 1)!\mathcal{L}_{\mathrm{rw}},

which maps each eigenvalue zz of Lrw\mathcal{L}_{\mathrm{rw}} to 1+(κ−1)!(z−1)1 + (\kappa- 1)!(z - 1), with the same eigenvectors. For Claim 2, observe that every node of G\mathcal{G} has at least one out-neighbor by Lemma 3.2, so that DG−1A\mathcal{D}_{\mathcal{G}}^{-1}\mathcal{A} is row-stochastic and the constant functions lie in the kernel of Lrw\mathcal{L}_{\mathrm{rw}}. By the identity above, they are therefore eigenfunctions of L\mathcal{L} with eigenvalue 1−(κ−1)!1 - (\kappa- 1)!.

The reduced non-backtracking Laplacian

Recall that the incidences of GG are the edge–vertex pairs (ei,v)(e_i,v) with v∈eiv \in e_i, and let

I(G):={(ei,v):v∈ei},so that ∣I(G)∣=∑i=1Mci.I(G) := \{(e_i,v) : v \in e_i\}, \qquad\text{so that } |I(G)| = \sum_{i=1}^{M} c_i.

In this section we show that, although L\mathcal{L} is defined on the ∑ici!\sum_i c_i! permutations of the edges, its spectrum can be computed from a much smaller matrix indexed by the ∑ici\sum_i c_i incidences of GG, namely the reduced non-backtracking Laplacian of Definition 5.1 below. For instance, for the laminar hypergraph Λ2,3\Lambda_{2,3} of Example 3.7, this reduces the size of the eigenvalue problem from 40376 to 24. This is possible because, by definition of the non-backtracking graph, the out-neighbors of a permutation in G\mathcal{G} depend only on its edge and its output, and its in-neighbors depend only on its edge and its input. As a consequence, the eigenvalues of L\mathcal{L} are those of the reduced non-backtracking Laplacian, together with ∑i(ci!−ci)\sum_i(c_i! - c_i) additional eigenvalues that are equal to 1 (Theorem 5.4). The permutations still play a role in the spectrum, but only through their number: the entry of the reduced matrix corresponding to a step through eje_j from vv to ww is proportional to (cj−2)!(c_j - 2)!, which is the number of permutations of eje_j with input vv and output ww.

Since the spectra of L\mathcal{L} and of the reduced non-backtracking Laplacian determine each other, one might take the latter as the definition of the non-backtracking Laplacian of a hypergraph. We explain in Remark 5.5 why we nevertheless work with L\mathcal{L}.

Definition 5.1. The reduced non-backtracking Laplacian of GG is the ∣I(G)∣×∣I(G)∣|I(G)| \times|I(G)| matrix

L^:=Id⁡−R,\widehat{\mathcal{L}} := \operatorname{Id} - \mathcal{R},

where R\mathcal{R} is the matrix defined by

R(ei,v),(ej,w):={(cj−2)!deg⁡v−1if j≠i, v∈ej, w∈ej and w≠v,0otherwise.\mathcal{R}_{(e_i,v),(e_j,w)} := \begin{cases} \frac{(c_j - 2)!}{\deg v - 1} & \text{if } j \ne i,\ v \in e_j,\ w \in e_j\text{ and }w \ne v,\\ 0 & \text{otherwise.} \end{cases}

In words, the incidence (ei,v)(e_i,v) represents a walker that has just left eie_i through vv, and R\mathcal{R} moves it through a different edge ej∋ve_j \ni v and out of it through a vertex w≠vw \ne v, with weight (cj−2)!/(deg⁡v−1)(c_j - 2)!/(\deg v - 1), where (cj−2)!(c_j - 2)! counts the permutations of eje_j with input vv and output ww.

If GG is a graph, then (cj−2)!=1(c_j - 2)! = 1 and L^\widehat{\mathcal{L}} is the non-backtracking Laplacian L\mathcal{L}, after identifying each incidence (ei,v)(e_i,v) with the orientation of eie_i whose output is vv.

The key ingredient in the proofs of Theorem 5.4 and Corollary 5.6 is the following factorization of D−1AD^{-1}A through the incidences. In the statement, for a positive integer nn, we let JnJ_n denote the n×nn \times n all-ones matrix.

Lemma 5.2. Let Φ\Phi and Ψ\Psi be the ∣V∣×∣I(G)∣|\mathcal{V}| \times|I(G)| matrices defined, for ξ∈V\xi\in\mathcal{V} and (ej,w)∈I(G)(e_j,w) \in I(G), by

Φξ,(ej,w):=1[ξ is a permutation of ej]⋅1[out⁡(ξ)=w],\Phi_{\xi,(e_j,w)} := \mathbb{1}[\xi\text{ is a permutation of }e_j]\cdot\mathbb{1}[\operatorname{out}(\xi)=w],
Ψξ,(ej,w):=1[ξ is a permutation of ej]⋅1[in⁡(ξ)=w],\Psi_{\xi,(e_j,w)} := \mathbb{1}[\xi\text{ is a permutation of }e_j]\cdot\mathbb{1}[\operatorname{in}(\xi)=w],

and let TT and D~\widetilde{D} be the ∣I(G)∣×∣I(G)∣|I(G)| \times|I(G)| matrices

T(ei,v),(ej,w):=1[v=w]⋅1[i≠j],T_{(e_i,v),(e_j,w)} := \mathbb{1}[v=w]\cdot\mathbb{1}[i\ne j],
D~:=diag⁡(deg⁡v−1)(ei,v)∈I(G).\widetilde{D} := \operatorname{diag}(\deg v - 1)_{(e_i,v)\in I(G)}.

Moreover, let H:=D~−1TH := \widetilde{D}^{-1}T and C:=ΨTΦC := \Psi^{\mathsf{T}}\Phi. Then:

  1. D−1A=ΦHΨT\mathcal{D}^{-1}\mathcal{A}=\Phi H\Psi^{\mathsf{T}};

  1. R=HC\mathcal{R}=HC;

  1. HH and CC are symmetric. Moreover, grouping the incidences by their vertex, HH is block diagonal with blocks

Jdeg⁡v−Id⁡deg⁡vdeg⁡v−1,v∈V,\frac{J_{\deg v}-\operatorname{Id}_{\deg v}}{\deg v-1},\qquad v\in V,

and therefore its eigenvalues are 11 and −1/(deg⁡v−1)-1/(\deg v-1). Grouping the incidences by their edge, CC is block diagonal with blocks

(ci−2)!(Jci−Id⁡ci),i∈{1,…,M},(c_i-2)!(J_{c_i}-\operatorname{Id}_{c_i}),\qquad i\in\{1,\ldots,M\},

and therefore its eigenvalues are (ci−1)!(c_i-1)! and −(ci−2)!-(c_i-2)!.

In particular, HH, CC and R\mathcal{R} are invertible.

Proof. Note that each row of Φ\Phi (respectively, of Ψ\Psi) contains exactly one non-zero entry, marking the incidence given by the output (respectively, the input) of the corresponding permutation. The matrix TT encodes the admissible changes of edge, since the walk leaves eie_i and enters a different edge through the same vertex, and D~\widetilde{D} normalizes by the number of such choices.

  1. Let ξ,η∈V\xi,\eta\in\mathcal{V} be permutations of eie_i and eje_j, respectively. A direct computation gives

(ΦTΨT)ξη=1[out⁡(ξ)=in⁡(η)]⋅1[i≠j]=Aξη,(\Phi T\Psi^{\mathsf{T}})_{\xi\eta} =\mathbb{1}[\operatorname{out}(\xi)=\operatorname{in}(\eta)]\cdot\mathbb{1}[i\ne j] =\mathcal{A}_{\xi\eta},

so that A=ΦTΨT\mathcal{A}=\Phi T\Psi^{\mathsf{T}}. Moreover, D−1Φ=ΦD~−1\mathcal{D}^{-1}\Phi=\Phi\widetilde{D}^{-1}, since Φξ,(ej,w)≠0\Phi_{\xi,(e_j,w)}\ne0 only if w=out⁡(ξ)w=\operatorname{out}(\xi), in which case d(ξ)=deg⁡w−1d(\xi)=\deg w-1. Hence,

D−1A=ΦD~−1TΨT=ΦHΨT.\mathcal{D}^{-1}\mathcal{A} =\Phi\widetilde{D}^{-1}T\Psi^{\mathsf{T}} =\Phi H\Psi^{\mathsf{T}}.
  1. Observe that

(ΨTΦ)(ei,v),(ej,w)=1[i=j]⋅#{ξ permutation of ei:in⁡(ξ)=v and out⁡(ξ)=w}=1[i=j]⋅(ci−2)!⋅1[v≠w],\begin{aligned} (\Psi^{\mathsf{T}}\Phi)_{(e_i,v),(e_j,w)} =\mathbb{1}[i=j]\cdot\#\{\xi\text{ permutation of }e_i:\operatorname{in}(\xi)=v\text{ and }\operatorname{out}(\xi)=w\} \\ &=\mathbb{1}[i=j]\cdot(c_i-2)!\cdot\mathbb{1}[v\ne w], \end{aligned}

since the permutations of eie_i with fixed distinct input vv and output ww are exactly (ci−2)!(c_i-2)!, while no permutation has equal input and output. Therefore,

(HC)(ei,v),(ej,w)=1deg⁡v−1∑(el,u)∈I(G)1[u=v]1[l≠i]⋅1[l=j](cj−2)!1[u≠w]=(cj−2)!deg⁡v−1⋅1[j≠i]1[v∈ej]1[w∈ej]1[w≠v]=R(ei,v),(ej,w).\begin{aligned} (HC)_{(e_i,v),(e_j,w)} =\frac{1}{\deg v-1} \sum_{(e_l,u)\in I(G)} \mathbb{1}[u=v]\mathbb{1}[l\ne i]\cdot\mathbb{1}[l=j](c_j-2)!\mathbb{1}[u\ne w] \\ &=\frac{(c_j-2)!}{\deg v-1}\cdot\mathbb{1}[j\ne i]\mathbb{1}[v\in e_j]\mathbb{1}[w\in e_j]\mathbb{1}[w\ne v] \\ &=\mathcal{R}_{(e_i,v),(e_j,w)}. \end{aligned}
  1. Symmetry of HH and CC is clear from their entries, and the block structure follows from the computations above. Since Jn−Id⁡nJ_n-\operatorname{Id}_n has eigenvalues n−1n-1 and −1-1, the eigenvalues are as stated, and they are non-zero because deg⁡v≥δ≥2\deg v\ge\delta\ge2 and ci≥κ≥2c_i\ge\kappa\ge2. Hence HH and CC are invertible, and so is R=HC\mathcal{R}=HC.

Example 5.3. We illustrate Lemma 5.2 on a single edge ei={v1,v2,v3}e_i=\{v_1,v_2,v_3\}, with the permutations ordered as in Example 2.2. With rows and columns grouped by edge, Φ\Phi and Ψ\Psi are block diagonal, with one block for each edge. The blocks of Φ\Phi and Ψ\Psi corresponding to eie_i, with rows indexed by ei(1),…,ei(6)e_i^{(1)},\ldots,e_i^{(6)} and columns by the incidences (ei,v1),(ei,v2),(ei,v3)(e_i,v_1),(e_i,v_2),(e_i,v_3), are

Φi=(001010001100010100),Ψi=(100100010010001001).\Phi_i= \begin{pmatrix} 0&0&1\\ 0&1&0\\ 0&0&1\\ 1&0&0\\ 0&1&0\\ 1&0&0 \end{pmatrix}, \qquad \Psi_i= \begin{pmatrix} 1&0&0\\ 1&0&0\\ 0&1&0\\ 0&1&0\\ 0&0&1\\ 0&0&1 \end{pmatrix}.

Here, each row of Φi\Phi_i marks the output of the corresponding permutation, and each row of Ψi\Psi_i its input. In particular, two permutations of eie_i have the same row of Φi\Phi_i precisely when they have the same output. Moreover, the corresponding block of C=ΨTΦC=\Psi^{\mathsf T}\Phi is

ΨiTΦi=(011101110)=(ci−2)!(J3−Id⁡3).\Psi_i^{\mathsf T}\Phi_i= \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{pmatrix} =(c_i-2)!(J_3-\operatorname{Id}_3).

whose (v,w)(v,w) entry counts the permutations of eie_i with input vv and output ww, which here is exactly one for every v≠wv\ne w. For an edge eie_i with ci=4c_i=4, the corresponding block would be 2(J4−Id⁡4)2(J_4-\operatorname{Id}_4), the factor 2=(ci−2)!2=(c_i-2)! recording the two possible orders of the two vertices of eie_i other than the input and the output. Through the identity R=HCR=HC of Lemma 5.2, this is where the factor (cj−2)!(c_j-2)! in the entries of RR comes from.

We can now prove the main result of this section: by Lemma 5.2, the non-backtracking Laplacian L\mathcal{L} is similar to the direct sum of the reduced non-backtracking Laplacian L^\widehat{\mathcal{L}} and an identity matrix. For a multiset, we write {λ}(m)\{\lambda\}^{(m)} for the element λ\lambda repeated mm times.

Theorem 5.4. The non-backtracking Laplacian L\mathcal{L} is similar to the block diagonal matrix

L^⊕Id⁡q,whereq:=∑i=1M(ci!−ci).\widehat{\mathcal{L}}\oplus\operatorname{Id}_q,\qquad\text{where}\quad q:=\sum_{i=1}^{M}(c_i!-c_i).

In particular:

  1. as multisets, σ(L)=σ(L^)⊎{1}(q)\sigma(\mathcal{L})=\sigma(\widehat{\mathcal{L}})\uplus\{1\}^{(q)};

  2. 11 is an eigenvalue of L\mathcal{L} if and only if GG is not a graph, in which case it is semisimple, with multiplicity qq;

  3. L\mathcal{L} is diagonalizable if and only if L^\widehat{\mathcal{L}} is diagonalizable.

Proof. Let X:=ΦX:=\Phi and Y:=HΨTY:=H\Psi^{\mathsf T}. By Lemma 5.2, D−1A=XY\mathcal{D}^{-1}A=XY and YX=RYX=R, which is invertible. It follows that XX has full column rank ∣I(G)∣|I(G)| and YY has full row rank, therefore ker⁡Y\ker Y has dimension ∣V∣−∣I(G)∣=q|V|-|I(G)|=q. Moreover, im⁡X∩ker⁡Y={0}\operatorname{im}X\cap\ker Y=\{0\}: if Xu∈ker⁡YXu\in\ker Y, then Ru=YXu=0Ru=YXu=0, therefore u=0u=0. Hence, C∣V∣=im⁡X⊕ker⁡Y\mathbb{C}^{|V|}=\operatorname{im}X\oplus\ker Y, and both subspaces are invariant under XYXY, since XY(Xu)=X(Ru)XY(Xu)=X(Ru) and XYz=0XYz=0 for z∈ker⁡Yz\in\ker Y. In a basis formed by the columns of XX followed by a basis of ker⁡Y\ker Y, the matrix D−1A=XY\mathcal{D}^{-1}A=XY is therefore represented by R⊕0qR\oplus0_q, and L\mathcal{L} by L^⊕Id⁡q\widehat{\mathcal{L}}\oplus\operatorname{Id}_q. We now prove the three claims.

  1. Similar matrices have the same eigenvalues, with the same algebraic multiplicities, and the eigenvalues of a block diagonal matrix are those of its blocks.

  1. Since R\mathcal{R} is invertible, 11 is not an eigenvalue of L^=Id⁡−R\widehat{\mathcal{L}}=\operatorname{Id}-\mathcal{R}. Hence, the eigenvalue 11 of L\mathcal{L} only comes from the block Id⁡q\operatorname{Id}_{q}, so that its algebraic and geometric multiplicities both equal qq, and it is semisimple. Moreover, q>0q>0 if and only if ci≥3c_i\ge3 for some ii, that is, if and only if GG is not a graph.

  1. A block diagonal matrix is diagonalizable if and only if each of its blocks is, and Id⁡q\operatorname{Id}_{q} is diagonal.

Remark 5.5 (Why L\mathcal{L} and not L^\widehat{\mathcal{L}}). By Theorem 5.4, the spectra of L\mathcal{L} and L^\widehat{\mathcal{L}} determine each other, since 1∉σ(L^)1\notin\sigma(\widehat{\mathcal{L}}) and qq only depends on the cardinalities of the edges. Moreover, if GG is a graph, then L^=L\widehat{\mathcal{L}}=\mathcal{L}, after identifying each incidence (ei,v)(e_i,v) with the orientation of eie_i whose output is vv. One might therefore take L^\widehat{\mathcal{L}} as the definition of the non-backtracking Laplacian of a hypergraph. We nevertheless work with L\mathcal{L}, because it is conceptually more natural. Indeed, L\mathcal{L} is obtained from the (0,1)(0,1) adjacency matrix of a directed graph, normalized by the number of edges through which the walk can continue, whereas the weights (cj−2)!/(deg⁡v−1)(c_j-2)!/(\deg v-1) of L^\widehat{\mathcal{L}} would be hard to motivate directly: they arise from L\mathcal{L}, as the numbers of permutations of eje_j with fixed input and output.

While Theorem 5.4 determines the multiplicity of the eigenvalue 11, Lemma 5.2 also allows us to bound the other eigenvalues of L\mathcal{L} away from 11.

Corollary 5.6. Every eigenvalue λ≠1\lambda\ne1 of L\mathcal{L} satisfies

(κ−2)!Δ−1≤∣1−λ∣≤(K−1)!.\frac{(\kappa-2)!}{\Delta-1}\le\lvert1-\lambda\rvert\le(K-1)!.

Proof. By Theorem 5.4, λ∈σ(L^)\lambda\in\sigma(\widehat{\mathcal{L}}), that is, λ=1−μ\lambda=1-\mu for some μ∈σ(R)\mu\in\sigma(\mathcal{R}), so that ∣1−λ∣=∣μ∣\lvert1-\lambda\rvert=\lvert\mu\rvert. By Lemma 5.2, R=HC\mathcal{R}=HC, where HH and CC are symmetric and invertible. Since the spectral norm of a symmetric matrix is the largest absolute value of its eigenvalues, the eigenvalues given in Lemma 5.2 yield

∥H∥=1,∥H−1∥=Δ−1,∥C∥=(K−1)!,∥C−1∥=1(κ−2)!.\lVert H\rVert=1,\qquad\lVert H^{-1}\rVert=\Delta-1,\qquad\lVert C\rVert=(K-1)!,\qquad\lVert C^{-1}\rVert=\frac{1}{(\kappa-2)!}.

Since every eigenvalue of a matrix is bounded in absolute value by its spectral norm, and μ−1\mu^{-1} is an eigenvalue of R−1=C−1H−1\mathcal{R}^{-1}=C^{-1}H^{-1}, we obtain

∣μ∣≤∥H∥∥C∥=(K−1)!and∣μ∣−1≤∥C−1∥∥H−1∥=Δ−1(κ−2)!,\lvert\mu\rvert\le\lVert H\rVert\lVert C\rVert=(K-1)!\qquad\text{and}\qquad\lvert\mu\rvert^{-1}\le\lVert C^{-1}\rVert\lVert H^{-1}\rVert=\frac{\Delta-1}{(\kappa-2)!},

which proves the claim.

In Corollary 5.6, the upper bound is the radius of the disk of Proposition 4.1, while the lower bound is new. For graphs, the lower bound is 1/(Δ−1)1/(\Delta-1), which is the bound of [20 Section 4].

Remark 5.7. Operators indexed by the incidences of a hypergraph also appear in [14], where the incidences are called pointed edges. There, the non-backtracking operator, which we denote by K\mathcal{K}, has entry 11 from (v,ei)(v,e_i) to (w,ej)(w,e_j) if and only if w∈ei∖{v}w\in e_i\setminus\{v\}, w∈ejw\in e_j and ej≠eie_j\ne e_i [14 Definitions 2.1–2.2]: the walk crosses eie_i from vv to ww, and then moves to another edge at ww. Identifying (v,ei)(v,e_i) with the incidence (ei,v)(e_i,v), Definition 5.1 gives

R=D~−1KTW,W:=diag⁡((cj−2)!)(ej,w)∈I(G).(1)\mathcal{R}=\widetilde{\mathcal{D}}^{-1}\mathcal{K}^{\mathsf{T}}W,\qquad W:=\operatorname{diag}\bigl((c_j-2)!\bigr)_{(e_j,w)\in I(G)}. \tag*{(1)}

with D~\widetilde{D} as in Lemma 5.2. That is, R\mathcal{R} is obtained from KT\mathcal{K}^{\mathsf{T}} by weighting each crossing of an edge eje_j by the number (cj−2)!(c_j-2)! of permutations of eje_j with the corresponding input and output, and by normalizing by the number of edges through which the walk can continue. Since D~\widetilde{D} and WW are both diagonal, conjugating by WW shows that R\mathcal{R} is similar to WD~−1KTW\widetilde{D}^{-1}\mathcal{K}^{\mathsf{T}}, where

WD~−1=diag⁡((ci−2)!deg⁡v−1)(ei,v)∈I(G).W\widetilde{D}^{-1}=\operatorname{diag}\left(\frac{(c_i-2)!}{\deg v-1}\right)_{(e_i,v)\in I(G)}.

In particular, if (ci−2)!/(deg⁡v−1)(c_i-2)!/(\deg v-1) takes the same value ν\nu on all incidences, as is the case when all vertices have the same degree Δ\Delta and either GG is κ\kappa-uniform, with ν=(κ−2)!/(Δ−1)\nu=(\kappa-2)!/(\Delta-1), or all edges have at most 3 vertices, with ν=1/(Δ−1)\nu=1/(\Delta-1), then σ(R)=ν σ(K)\sigma(\mathcal{R})=\nu\,\sigma(\mathcal{K}). In general, WD~−1W\widetilde{D}^{-1} is not scalar, and the two spectra need not be related in such a simple way.

Example 5.8 (Example 3.6, continued). Let GG be the 3-lattice of Example 3.6. Its set of incidences I(G)I(G) has ∑ici=18\sum_i c_i=18 elements and, since deg⁡v=2\deg v=2 and cj=3c_j=3 for all vv and jj, all non-zero entries of R\mathcal{R} equal (cj−2)!/(deg⁡v−1)=1(c_j-2)!/(\deg v-1)=1: that is, R\mathcal{R} is the adjacency matrix of the directed graph on I(G)I(G) in which, from an incidence (ei,v)(e_i,v), the walk moves to the unique other edge ej∋ve_j\ni v and exits it at either of the two vertices w≠vw\ne v of eje_j (Figure 6). A direct computation shows that the characteristic polynomial of R\mathcal{R} is

(x2−4)(x2−1)4(x2+2)4,(x^2-4)(x^2-1)^4(x^2+2)^4,

so that σ(R)\sigma(\mathcal{R}) consists of ±2\pm2, of ±1\pm1 with multiplicity 4 each, and of ±i2\pm i\sqrt{2} with multiplicity 4 each. Hence, by Theorem 5.4, as a multiset,

σ(L)={1}(18)⊔{−1,3}⊔{0}(4)⊔{2}(4)⊔{1−i2}(4)⊔{1+i2}(4).\sigma(\mathcal{L})=\{1\}^{(18)}\sqcup\{-1,3\}\sqcup\{0\}^{(4)}\sqcup\{2\}^{(4)}\sqcup\{1-i\sqrt{2}\}^{(4)}\sqcup\{1+i\sqrt{2}\}^{(4)}.

We point out three facts. First, −1=1−(κ−1)!-1=1-(\kappa-1)! is the eigenvalue of the constant functions, in accordance with Proposition 4.5. Second, σ(L)\sigma(\mathcal{L}) is symmetric with respect to the map λ↦2−λ\lambda\mapsto2-\lambda. As in the graph case [20 Proposition 3.4], this follows from the bipartiteness of GG observed in Example 3.6. Third, both bounds of Corollary 5.6 are sharp in this example: the upper bound (K−1)!=2(K-1)!=2, which is also the radius of the disk of Proposition 4.1, is attained by the eigenvalues −1-1 and 33, and the lower bound (κ−2)!/(Δ−1)=1(\kappa-2)!/(\Delta-1)=1 by the eigenvalues 00 and 22.

Directed graph on the 18 incidences of the 3-lattice

Figure 6. The directed graph on the 18 incidences of the 3-lattice whose weighted adjacency matrix is R\mathcal{R}; all weights equal (3−2)!/(2−1)=1(3-2)!/(2-1)=1. Top: the incidences of the rows; bottom: those of the columns. From (ea,vab)(e_a,v_{ab}), the walk crosses the column e3+be_{3+b} and exits it at either of its two other vertices (in purple); from (e3+b,vab)(e_{3+b},v_{ab}), it crosses the row eae_a and exits it at either of its two other vertices (in teal). The arcs out of (e1,v13)(e_1,v_{13}) and (e6,v33)(e_6,v_{33}) are highlighted: they continue the walk of Figure 4, from the cyclist’s position (e1,v13)(e_1,v_{13}).

Example 5.9 (Example 3.7, continued). Let G=Λ2,2G=\Lambda_{2,2}, with vertices v11,v12,v21,v22v_{11},v_{12},v_{21},v_{22}, level-1 edges e1={v11,v12}e_1=\{v_{11},v_{12}\} and e2={v21,v22}e_2=\{v_{21},v_{22}\}, and level-2 edge e3=Ve_3=V. As for the 3-lattice, deg⁡v=2\deg v=2 for every vertex, therefore D=Id⁡\mathcal{D}=\operatorname{Id} and L=Id⁡−A\mathcal{L}=\operatorname{Id}-\mathcal{A}, but in this case, GG is not uniform. The matrix R\mathcal{R} has size 8, while L\mathcal{L} has size ∣V∣=28|V|=28 (Figure 7): from an incidence of a level-1 edge, the walk enters e3e_3 and exits it at any of its three other vertices, with weight (c3−2)!=2(c_3-2)!=2; from an incidence (e3,v)(e_3,v), it enters the level-1 edge of vv and exits it at its other vertex, with weight 1. A direct computation gives the characteristic polynomial (x2−6)(x2+2)(x2−2)2(x^2-6)(x^2+2)(x^2-2)^2 of R\mathcal{R}, hence, by Theorem 5.4,

Figure 7. The weighted directed graph on the 8 incidences of Λ2,2\Lambda_{2,2} whose weighted adjacency matrix is R\mathcal{R}. From an incidence of a level-1 edge, the walk crosses e3e_3 and exits it at any of its three other vertices (in purple, weight 2); from an incidence (e3,v)(e_3,v), it crosses the level-1 edge of vv and exits it at its other vertex (in teal, weight 1). The arcs out of (e1,v11)(e_1,v_{11}) and (e3,v21)(e_3,v_{21}) are highlighted: they show two steps of the walk from the cyclist’s position (e1,v11)(e_1,v_{11}).

σ(L)={1}(20)⊔{1±6}⊔{1±i2}⊔{1±2}(2).\sigma(\mathcal{L})=\{1\}^{(20)}\sqcup\{1\pm\sqrt{6}\}\sqcup\{1\pm i\sqrt{2}\}\sqcup\{1\pm\sqrt{2}\}^{(2)}.

As for the lattice, σ(L)\sigma(\mathcal{L}) is symmetric with respect to λ↦2−λ\lambda\mapsto2-\lambda, since every walk on GG alternates between the level-1 edges and e3e_3, therefore GG is bipartite. Unlike for the lattice, however, neither bound of Corollary 5.6 is sharp: the eigenvalues of L\mathcal{L} different from 1 lie at distance between 2\sqrt{2} and 6\sqrt{6} from 1, while the two bounds equal 1 and (K−1)!=6(K-1)!=6. Moreover, the constant functions are not eigenfunctions of L\mathcal{L}, since the row sums of A\mathcal{A} equal 6 on the permutations of the level-1 edges and 1 on those of e3e_3 (Remark 3.3); accordingly, unlike in the uniform case of Proposition 4.5, L\mathcal{L} has no eigenvalue of the form 1−(κ−1)!1-(\kappa-1)!.

Tool and computational resource disclosure

The authors used Claude as a tool for language polishing, for identifying possible inconsistencies or errors in preliminary drafts, and for drafting figures.

Funding

Raffaella Mulas is supported by the Dutch Research Council (NWO) through the grant VI.Veni.232.002 (Grant ID: https://doi.org/10.61686/NLUFV33835), which also supported Eleonora Andreotti’s research visit to VU Amsterdam in June 2026, during which this project was developed. Eleonora cycled from Trento to Amsterdam for this visit and returned by bus, so her bike ride was non-backtracking.

References

  1. [1]E. Andreotti. Generalizing lattice structures to hypergraphs: spectra of clique and hyperedge- based Laplacians. Linear Algebra and its Applications, 751:100–125, 2026.arxiv.org/abs/2511.11138
  2. [2]E. Andreotti and R. Mulas. Signless normalized Laplacian for hypergraphs. Electronic Journal of Graph Theory and Applications, 10(2):485–500, 2022.DOI
  3. [3]M. C. Angelini, F. Caltagirone, F. Krzakala, and L. Zdeborová. Spectral detection on sparse hypergraphs. In 53rd Annual Allerton Conference on Communication, Control, and Computing, pages 66–73. IEEE, 2015.DOI
  4. [4]F. Arrigo, P. Grindrod, D. J. Higham, and V. Noferini. Non-backtracking walk centrality for directed networks. Journal of Complex Networks, 6(1):54–78, 2018.DOI
  5. [5]T. Austin and T. Tao. Testability and repair of hereditary hypergraph properties. Random Structures & Algorithms, 36(4):373–463, 2010.DOI
  6. [6]A. Banerjee. On the spectrum of hypergraphs. Linear Algebra and its Applications, 614:82–110, 2021. Special Issue ILAS 2019.arxiv.org/abs/1711.09356
  7. [7]F. Bauer. Normalized graph Laplacians for directed graphs. Linear Algebra and its Applications, 436(11):4193–4222, 2012.arxiv.org/abs/1107.4847
  8. [8]G. Bianconi and S. N. Dorogovtsev. Theory of percolation on hypergraphs. Physical Review E, 109(1):014306, 2024.DOI
  9. [9]M. Bolla. The non-backtracking random walk and its usage for vertex clustering. arXiv preprint arXiv:2512.24434, 2025.arxiv.org/abs/2512.24434
  10. [10]M. Bolla, H. Reittu, and F. Abdelkhalek. Clustering the nodes of sparse edge-weighted graphs via non-backtracking spectra. In Future of Information and Communication Conference, pages 81–99. Springer, 2025.DOI
  11. [11]C. Bordenave, M. Lelarge, and L. Massoulié. Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1347–1357. IEEE, 2015.DOI
  12. [12]A.E. Brouwer and W.H. Haemers. Spectra of graphs. Springer Science & Business Media, 2011.
  13. [13]C. Castellano and R. Pastor-Satorras. Relevance of backtracking paths in recurrent-state epidemic spreading on networks. Physical Review E, 98(5):052313, 2018.DOI
  14. [14]P. S. Chodrow, N. Eikmeier, and J. Haddock. Nonbacktracking spectral clustering of nonuniform hypergraphs. SIAM J. Math. Data Sci., 5(2):251–279, 2023.arxiv.org/abs/2204.13586
  15. [15]F. Chung. Spectral graph theory. American Mathematical Soc., 1997.
  16. [16]H. Galeana-Sánchez and M. Manrique. Directed hypergraphs: a tool for researching digraphs and hypergraphs. Discussiones Mathematicae Graph Theory, 29(2):313–335, 2009.
  17. [17]G. Gallo, G. Longo, S. Pallottino, and S. Nguyen. Directed hypergraphs and applications. Discrete Applied Mathematics, 42(2-3):177–201, 1993.DOI
  18. [18]C. Glover and M. Kempton. Some spectral properties of the non-backtracking matrix of a graph. Linear Algebra and its Applications, 618:37–57, 2021.DOI
  19. [19]K. Hashimoto. Zeta functions of finite graphs and representations of p-adic groups. In Automorphic Forms and Geometry of Arithmetic Varieties, volume 15 of Advanced Studies in Pure Mathematics, pages 211–280. Elsevier, 1989.
  20. [20]J. Jost, R. Mulas, and L. Torres. Spectral theory of the non-backtracking Laplacian for graphs. Discrete Mathematics, 346(10):113536, 2023.DOI
  21. [21]J. Jost, R. Mulas, and D. Zhang. Spectra of Discrete Structures. Number 221 in Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2026.DOI
  22. [22]F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013.DOI
  23. [23]Y. Lin and Z. Zhang. Non-backtracking centrality based random walk on networks. The Computer Journal, 62(1):63–80, 2019.arxiv.org/abs/1803.03087
  24. [24]T. Martin, X. Zhang, and M. E. J. Newman. Localization and centrality in networks. Physical Review E, 90(5):052808, 2014.DOI
  25. [25]F. Morone and H. A. Makse. Influence maximization in complex networks through optimal percolation. Nature, 524:65–68, 2015.DOI
  26. [26]E. M. Moutiou. Graphs are focal hypergraphs: strict containment in higher-order interaction dynamics. arXiv preprint arXiv:2603.04215, 2026.
  27. [27]R. Mulas. Maximal colourings for graphs. Graphs and Combinatorics, 40(93), 2024.arxiv.org/abs/2307.10910
  28. [28]R. Mulas, C. Kuehn, T. Böhle, and J. Jost. Random walks and laplacians on hypergraphs: When do they match? Discrete Applied Mathematics, 317:26–41, 2022.arxiv.org/abs/2106.11663
  29. [29]R. Mulas, D. Zhang, and G. Zucal. There is no going back: Properties of the non-backtracking Laplacian. Linear Algebra Appl., 680:341–370, 2024.arxiv.org/abs/2303.00373
  30. [30]K. Nakajima, M. Kodakari, and M. Aida. Sampling nodes and hyperedges via random walks on large hypergraphs. Applied Network Science, 10:19, 2025.
  31. [31]M. Newman. Spectral community detection in sparse networks. arXiv preprint arXiv:1308.6494, 2013.arxiv.org/abs/1308.6494
  32. [32]C. Rommens, P. Traversa, G. Ferraz de Arruda, and Y. Moreno. The informational cost of structure: Representational complexity in networked dynamical systems, 2026.arxiv.org/abs/2607.03608
  33. [33]M. Shrestha, S. V. Scarpino, and C. Moore. Message-passing approach for recurrent-state epidemic models on networks. Physical Review E, 92(2):022821, 2015.pubmed.ncbi.nlm.nih.gov/26382468
  34. [34]L. Stephan and Y. Zhu. Sparse random hypergraphs: Non-backtracking spectra and community detection. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 567–575. IEEE, 2022.arxiv.org/abs/2203.07346
  35. [35]C. K. Storm. The zeta function of a hypergraph. Electron. J. Combin., 13(1):R84, 2006.DOI
  36. [36]L. Torres. Non-backtracking Spectrum: Unitary Eigenvalues and Diagonalizability. arXiv preprint arXiv:2007.13611, 2020.arxiv.org/abs/2007.13611
  37. [37]L. Torres. Geometric multiplicity of unitary non-backtracking eigenvalues. arXiv preprint arXiv:2205.02004, 2022.arxiv.org/abs/2205.02004
  38. [38]L. Torres. The cost of representing higher-order dynamics on graphs: A theoretical framework, 2026. Scroll Press.DOI
  39. [39]L. Torres, K. S. Chan, H. Tong, and T. Eliassi-Rad. Nonbacktracking eigenvalues under node removal: X-centrality and targeted immunization. SIAM Journal on Mathematics of Data Science, 3(2):656–675, 2021.DOI

Paper details

vlnc:W_u68zfuka
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents