#  Spectra of power hypergraphs and signed graphs via parity-closed walks

Lixiang Chen<EMAIL_ADDRESS>Edwin R. van Dam
<EMAIL_ADDRESS>Changjiang Bu<EMAIL_ADDRESS>College of Mathematical Sciences, Harbin Engineering University, Harbin, PR
China  Department of Econometrics and O.R., Tilburg University, Tilburg,
Netherlands

###### Abstract

The $k$-power hypergraph $G^{(k)}$ is the $k$-uniform hypergraph that is
obtained by adding $k-2$ new vertices to each edge of a graph $G$, for $k\geq
3$. A parity-closed walk in $G$ is a closed walk that uses each edge an even
number of times. In an earlier paper, we determined the eigenvalues of the
adjacency tensor of $G^{(k)}$ using the eigenvalues of signed subgraphs of
$G$. Here, we express the entire spectrum (that is, we determine all
multiplicities and the characteristic polynomial) of $G^{(k)}$ in terms of
parity-closed walks of $G$. Moreover, we give an explicit expression for the
multiplicity of the spectral radius of $G^{(k)}$. Our results are mainly
obtained by exploiting the so-called trace formula to determine the spectral
moments of $G^{(k)}$. As a side result, we show that the number of parity-
closed walks of given length is the corresponding spectral moment averaged
over all signed graphs with underlying graph $G$. We also extrapolate the
characteristic polynomial of $G^{(k)}$ to $k=2$, thereby introducing a pseudo-
characteristic function. Among other results, we show that this function is
the geometric mean of the characteristic polynomials of all signed graphs on
$G$ and characterize when it is a polynomial. This supplements a result by
Godsil and Gutman that the arithmetic mean of the characteristic polynomials
of all signed graphs on $G$ equals the matching polynomial of $G$.

###### keywords:

power hypergraphs, adjacency tensor, signed graphs, spectral moments,
characteristic polynomial, spectral radius, closed walks
_AMS classification(2020):_ 05C65, 05C50.

##  1 Introduction

For a given graph $G=(V,E)$ and a sign function $\pi:E\rightarrow\\{\pm 1\\}$,
we denote by $\phi_{\pi}(\lambda)$ the characteristic polynomial of the signed
adjacency matrix of a signed graph $G_{\pi}$ on $G$. Let $\Pi$ denote the set
of all sign functions on $E$. Godsil and Gutman [14] proved the remarkable
result that the arithmetic mean of the characteristic polynomials of all
signed graphs with underlying graph $G$ equals the matching polynomial
$\alpha(\lambda)$ of $G$, i.e.,

$\displaystyle\alpha(\lambda)=2^{-|E|}\sum_{\pi\in\Pi}{\phi_{\pi}(\lambda)}.$

The result of Godsil and Gutman was used by Marcus, Spielman, and Srivastava
[21] to show the existence of an infinite family of $d$-regular bipartite
Ramanujan graphs, for any $d\geq 3$.

The $k$-power hypergraph $G^{(k)}$ is the $k$-uniform hypergraph that is
obtained by adding $k-2$ new vertices to each edge of a graph $G$, for $k\geq
3$ [18]. A parity-closed walk in $G$ is a closed walk that uses each edge an
even number of times. In an earlier paper [4], we determined all eigenvalues
of the adjacency tensor of $G^{(k)}$ using the eigenvalues of signed subgraphs
of $G$.

Here, we will extend combinatorial methods that are common for ordinary graphs
to power hypergraphs in the sense that we will find a relation between the
spectral moments of $G^{(k)}$ and counts of parity-closed walks in $G$. In
order to determine these spectral moments, we will mainly exploit the so-
called trace formula for tensors by Shao, Qi, and Hu [23].

In particular, we will determine the entire spectrum (and the characteristic
polynomial) of $G^{(k)}$ by determining expressions for the multiplicities of
the eigenvalues in terms of parity-closed walks of $G$. Moreover, we give an
explicit expression for the multiplicity of the spectral radius. Note that
from the Perron-Frobenius Theorem (for matrices), it is known that the
spectral radius of a connected graph is an eigenvalue of the graph with
multiplicity $1$. Part of the Perron-Frobenius Theorem has been generalized to
tensors, in particular, it is known that the spectral radius of a uniform
hypergraph is an eigenvalue [2]. However, it is unknown what its multiplicity
is.

As a side result (that has nothing to do with hypergraphs), we show that the
number of parity-closed walks of given length in a graph $G$ is the
corresponding spectral moment averaged over all signed graphs with underlying
graph $G$. We also extrapolate the characteristic polynomial of $G^{(k)}$ to
$k=2$, thereby introducing a pseudo-characteristic function. Among other
results, we show that this function is the geometric mean of the
characteristic polynomials of all signed graphs on $G$ and characterize when
it is a polynomial. This supplements the result by Godsil and Gutman [14] that
the arithmetic mean of the characteristic polynomials of all signed graphs on
$G$ equals the matching polynomial of $G$.

###  1.1 Organization of the paper

The rest of this paper is organized as follows: In Section 2, we introduce
some notation and give some lemmas about the trace of tensors (Section 2.1),
the spectral moments of hypergraphs (Section 2.2), and the spectral radius of
signed graphs (Section 2.3).

In Section 3, we show that the number of parity-closed walks of given length
in a graph $G$ is the arithmetic mean of spectral moments of all signed graphs
on $G$. This is not a result about hypergraphs, nor eigenvalues, but it will
be used later in the paper.

Section 4 is the main part that relates concepts in the power hypergraph
$G^{(k)}$ to concepts in $G$. The section is divided into a part on Eulerian
walks in related digraphs (Section 4.1), a part on the number of spanning
trees (Section 4.2), and a final part (Section 4.3), where we ultimately
express the spectral moments of the power hypergraph in terms of counts of
parity-closed walks in $G$ in Proposition 4.15.

In Section 5, eigenvalues and their multiplicities come into play. In Theorem
5.16, we determine expressions for the multiplicities and the characteristic
polynomial of a power hypergraph $G^{(k)}$, all in terms of $k$, counts of
parity-closed walks in $G$, and eigenvalues of signed subgraphs of $G$.

In Section 6, we extend the expressions for the characteristic polynomial of
$G^{(k)}$ to the (hypothetical) case $k=2$ and study the obtained pseudo-
characteristic function. In particular, in Theorem 6.18 we show that it is the
geometric mean of the characteristic polynomials of all signed graphs on $G$.

In Section 7, we finish the paper by determining the multiplicity of the
spectral radius of a power hypergraph.

##  2 Preliminaries

In this section, we introduce some basic notation and give auxiliary lemmas on
the trace of tensors, the spectral moments of hypergraphs, and the spectral
radius of signed graphs.

###  2.1 The trace of tensors

For a positive integer $n$, let
$\left[n\right]=\left\\{{1,\ldots,n}\right\\}$. A $k$-order $n$-dimensional
complex tensor $A=\left({{t_{{i_{1}}\cdots{i_{k}}}}}\right)$ is a
multidimensional array with $n^{k}$ entries in $\mathbb{C}$, where
${i_{j}}\in\left[n\right]$, $j=1,\ldots,k$. For
$x={\left({{x_{1}},\ldots,{x_{n}}}\right)^{\top}}\in{\mathbb{C}^{n}}$, we let
${x^{\left[{k-1}\right]}}={\left({x_{1}^{k-1},\ldots,x_{n}^{k-1}}\right)^{\top}}$.
The $i$-th component of the vector $A{x^{k-1}}\in\mathbb{C}^{n}$ is defined as

${\left({A{x^{k-1}}}\right)_{i}}=\sum\limits_{{i_{2}},\ldots,{i_{k}}=1}^{n}{{a_{i{i_{2}}\cdots{i_{k}}}}{x_{{i_{2}}}}\cdots{x_{{i_{k}}}}}.$

If there exists a nonzero vector
$x=(x_{1},x_{2},\ldots,x_{n})^{\top}\in{\mathbb{C}^{n}}$ such that
$A{x^{k-1}}=\lambda{x^{\left[{k-1}\right]}}$, then $\lambda$ is called an
_eigenvalue_ of $A$ and $x$ is an _eigenvector_ of $A$ corresponding to
$\lambda$ [20, 22]. The _characteristic polynomial_ of $A$ is defined as the
resultant of the polynomial system $(\lambda x^{[k-1]}-Ax^{k-1})$ [22]. The
(algebraic) multiplicity of an eigenvalue is the multiplicity as a root of the
characteristic polynomial.

Also the trace of a tensor can be defined such that it generalizes the trace
of a matrix. Shao, Qi, and Hu [23] obtained a useful expression for the trace
of general tensors. Using this, we will give an expression for the spectral
moments of a hypergraph $H$ in terms of the number of connected subhypergraphs
of $H$ in Section 2.2.

In order to describe the tensor trace formula of Shao et al. [23], we
introduce some related notation. Let
$\mathcal{F}_{d}=\\{(i_{1}\alpha_{1},\ldots,i_{d}\alpha_{d}):1\leq
i_{1}\leq\cdots\leq i_{d}\leq n;\alpha_{1},\ldots,\alpha_{d}\in[n]^{k-1}\\}$.
Let $f=(i_{1}\alpha_{1},\ldots,i_{d}\alpha_{d})\in\mathcal{F}_{d}$, where
$i_{j}\alpha_{j}\in[n]^{k}$, $j=1,\ldots,d$. For a $k$-order $n$-dimensional
tensor $A=(a_{i_{1}\cdots i_{k}})$, let
$\pi(f)=\prod_{j=1}^{d}{a_{i_{j}\alpha_{j}}}$. We will now construct a multi-
digraph $D_{f}$, in which we let $(v_{1},v_{2})$ denote an arc from vertex
$v_{1}$ to vertex $v_{2}$. For $i_{j}\alpha_{j}=i_{j}v_{1}\ldots v_{k-1}$, we
let the set of arcs from $i_{j}$ to $v_{1},v_{2},\ldots,v_{k-1}$ be
$\theta(i_{j}\alpha_{j})=\\{(i_{j},v_{1}),\ldots,(i_{j},v_{k-1})\\}$. Let
$\Theta(f)$ be the multi-set $\bigcup_{j=1}^{d}{\theta(i_{j}\alpha_{j})}$. Let
$b(f)$ be the product of the factorials of the multiplicities of the arcs in
$\Theta(f)$. Let $c(f)$ be the product of the factorials of the outdegrees of
all vertices in $\Theta(f)$. Denote the set of all closed walks using all arcs
in $\Theta(f)$ by $\mathcal{W}(f)$.

######  Lemma 2.1.

[23, (3.5)] Let $A$ be a $k$-order $n$-dimensional tensor. Then

$\displaystyle\mathrm{Tr}_{d}(A)=(k-1)^{n-1}\sum_{f\in\mathcal{F}_{d}}{\frac{b(f)}{c(f)}\pi_{f}(A)|\mathcal{W}(f)|}.$

###  2.2 The spectral moments of hypergraphs

A hypergraph $H=(V_{H},E_{H})$ is called _$k$ -uniform_ if each edge of $H$
contains exactly $k$ vertices. Similar to the relation between graphs and
matrices, there is a natural correspondence between uniform hypergraphs and
tensors. For a $k$-uniform hypergraph $H$ with $n$ vertices, its _adjacency
tensor_ ${A}_{H}=(a_{i_{1}i_{2}\ldots i_{k}})$ is a $k$-order $n$-dimensional
tensor, where

${a_{{i_{1}}{i_{2}}\ldots{i_{k}}}}=\left\\{\begin{array}[]{l}\frac{1}{{\left({k-1}\right)!}},{\kern
37.0pt}\mathrm{if}{\kern
2.0pt}{\left\\{{{i_{1}},{i_{2}},\ldots,{i_{k}}}\right\\}\in{E_{H}}},\\\
0,{\kern 57.0pt}\mathrm{otherwise}.\\\ \end{array}\right.$

When $k=2$, ${A}_{H}$ is the usual adjacency matrix of the graph $H$. The
characteristic polynomial of the adjacency tensor $A_{H}$ is called the
characteristic polynomial of hypergraph $H$. We note that expressions for the
coefficients of the characteristic polynomial of uniform hypergraphs have been
obtained, by Clark and Cooper [5], but we will not use these.

It is known that the $d$-th order spectral moment of a graph $G$ is equal to
the $d$-th order trace of the adjacency matrix $A_{G}$ [8]. Similar to the
case of graphs, the $d$-th order spectral moment $\mathrm{S}_{d}(H)$ of a
hypergraph $H$ (i.e., the sum of $d$-th powers of all eigenvalues of $H$) is
equal to the $d$-th order trace $\mathrm{Tr}_{d}(A_{H})$ of the adjacency
tensor $A_{H}$ [16].

From Lemma 2.1, we have

$\displaystyle\mathrm{S}_{d}(H)=\mathrm{Tr}_{d}(A_{H})=(k-1)^{|V(H)|-1}\sum_{f\in\mathcal{F}_{d}}{\frac{b(f)}{c(f)}\pi_{f}(A_{H})|\mathcal{W}(f)|}.$
(2.1)

Without loss of generality, we only consider
$f=(i_{1}\alpha_{1},\ldots,i_{d}\alpha_{d})\in\mathcal{F}_{d}$ for which
$\pi_{f}(A_{H})|W(f)|\neq 0$. Let
$i_{j}\alpha_{j}=i_{j}v^{(j)}_{1}v^{(j)}_{2}\ldots v^{(j)}_{k-1}$ for all
$j\in[d]$. Since $\pi_{f}(A_{H})=\prod_{j=1}^{d}(A_{H})_{i_{j}\alpha_{j}}$, we
know that $e_{j}=\\{i_{j},v^{(j)}_{1},v^{(j)}_{2},\ldots,v^{(j)}_{k-1}\\}$ is
a hyperedge of $H$, i.e., $f$ consists of $d$ rooted hyperedges. We construct
a $k$-uniform hypergraph $H_{f}$ such that $V(H_{f})=\bigcup_{j=1}^{d}{e_{j}}$
and $E(H_{f})=\bigcup_{j=1}^{d}{\\{e_{j}\\}}$. Obviously, $H_{f}$ is a
subhypergraph of $H$. Consider next a set of representatives of isomorphic
such subhypergraphs (so-called motifs)

$\mathcal{H}_{d}=\\{\widehat{H}:H_{f}\cong\widehat{H}~{}\mathrm{and}~{}\pi_{f}(A_{H})|W(f)|\neq
0~{}\mathrm{for}~{}\mathrm{some}~{}f\in\mathcal{F}_{d}\\}.$

For $\widehat{H}\in\mathcal{H}_{d}$, let
$\mathcal{F}_{d}(\widehat{H})=\\{f:f\in\mathcal{F}_{d}~{}\mathrm{and}~{}H_{f}\cong\widehat{H}\\}$.
We use $N_{H}(\widehat{H})$ to denote the number of subhypergraphs of $H$
which are isomorphic to $\widehat{H}$. By (2.1), we have

$\displaystyle\mathrm{S}_{d}(H)$
$\displaystyle=(k-1)^{|V(H)|-1}((k-1)!)^{-d}\sum_{\widehat{H}\in\mathcal{H}_{d}}{N_{H}(\widehat{H})\sum_{f\in\mathcal{F}_{d}(\widehat{H})}{\frac{b(f)}{c(f)}|\mathcal{W}(f)|}}.$

We call the coefficient

$c_{d}(\widehat{H})=((k-1)!)^{-d}\sum_{f\in\mathcal{F}_{d}(\widehat{H})}{\frac{b(f)}{c(f)}|\mathcal{W}(f)|}$
(2.2)

the $d$-th order spectral moment coefficient of $\widehat{H}$. We note that
for a graph $G$, the coefficient $c_{d}(G)$ equals the number of covering
closed walks of length $d$, that is, closed walks that use each edge at least
once. We thus give the following subgraph structure interpretation of the
spectral moments of hypergraphs:

$\displaystyle\mathrm{S}_{d}(H)=(k-1)^{|V(H)|-1}\sum_{\widehat{H}\in\mathcal{H}_{d}}{c_{d}}(\widehat{H})N_{H}(\widehat{H}).$
(2.3)

How to reduce and calculate the $d$-th order spectral moment coefficient
${c_{d}}(\widehat{H})$ is the key question in Section 4. Here we make a first
few steps in this direction. For $f\in\mathcal{F}_{d}(\widehat{H})$, we
constructed in Section 2.1 a multi-digraph
$D_{f}=\left(V(D_{f}),E(D_{f})\right)$ with $V(D_{f})=V(\widehat{H})$ and
$E(D_{f})=\Theta(f)$. Since $\mathcal{W}(f)$ is the set of all closed walks
with all arcs in $\Theta(f)$, we know that $|\mathcal{W}(f)|\neq 0$ if and
only if $D_{f}$ is Eulerian.

Because isomorphic graphs $D_{f}$ contribute the same to the spectral moment
coefficient in (2.2), we consider the set of representatives of isomorphic
Eulerian multi-digraphs

$\mathfrak{D}_{d}(\widehat{H})=\\{D:~{}D_{f}\cong
D~{}\mathrm{is}~{}\mathrm{Eulerian}~{}\mathrm{for}~{}\mathrm{some}~{}f\in\mathcal{F}_{d}(\widehat{H})\\}.$

Then

$\displaystyle
c_{d}(\widehat{H})=((k-1)!)^{-d}\sum_{D\in\mathfrak{D}_{d}(\widehat{H})}{|\\{f:f\in\mathcal{F}_{d}(\widehat{H})~{}\mathrm{and}~{}D_{f}\cong
D\\}|\frac{b(f)}{c(f)}|\mathcal{W}(f)|}.$ (2.4)

In (2.4), $|\mathcal{W}(f)|$ is the number of the Eulerian walks in $D$. An
expression for the number of the Eulerian walks in a multi-digraph was given
by the so-called “BEST Theorem” [13].

######  Lemma 2.2.

[13, Theorem 6] Let $D=(V(D),E(D))$ be a Eulerian multi-digraph. Let $b(D)$
denote the product of the factorials of the multiplicities of the arcs in
$E(D)$. Then the number of Eulerian walks in $D$ is

$\displaystyle\frac{|E(D)|}{b(D)}t(D)\prod_{v\in
V(D)}{(\mathrm{deg}_{D}^{+}(v)-1)!},$

where $\mathrm{deg}_{D}^{+}(v)$ is the outdegree of vertex $v$ and $t(D)$ is
the number of spanning trees of $D$.

In (2.4), we have $b(f)=b(D)$ and $c(f)=\prod_{v\in
V(D)}{\mathrm{deg}_{D}^{+}(v)!}$. From Lemma 2.2, we get the following
expression for the $d$-th order spectral moment coefficient of a fixed
hypergraph $\widehat{H}$.

######  Lemma 2.3.

The $d$-th order spectral moment coefficient of a $k$-uniform hypergraph
$\widehat{H}$ is

$\displaystyle
c_{d}(\widehat{H})=d(k-1)((k-1)!)^{-d}\sum_{D\in\mathfrak{D}_{d}(\widehat{H})}{\frac{\left|\\{f:f\in\mathcal{F}_{d}(\widehat{H})~{}\mathrm{and}~{}D_{f}\cong
D\\}\right|t(D)}{\prod_{v\in V(D)}\mathrm{deg}_{D}^{+}(v)}}.$

We will use this result to further reduce the spectral moment coefficients of
power hypergraphs in Section 4.

The spectrum of a hypergraph is said to be $k$-symmetric if it is invariant
under a rotation of an angle $2\pi/k$ in the complex plane [6]. The spectrum
of a $k$-power hypergraph is indeed $k$-symmetric [17], and hence
$\mathrm{S}_{d}(G^{(k)})=0$ for $k\nmid d$. Note that Lemma 2.4 below shows
$k$-symmetry of the eigenvalues, but it does not say anything about the
corresponding multiplicities.

From (2.3), we then have

$\displaystyle\mathrm{S}_{d}(G^{(k)})=\left\\{\begin{array}[]{l}(k-1)^{|V(G^{(k)})|-1}\sum_{\widehat{G}\in\mathcal{G}_{d}}{c_{d}}(\widehat{G}^{(k)})N_{G}(\widehat{G}),~{}~{}~{}~{}k\mid
d,\\\ 0,{\kern 207.0pt}k\nmid d,\end{array}\right.$ (2.7)

where
$\mathcal{G}_{d}=\\{\widehat{G}:\widehat{G}~{}\mathrm{is}~{}\mathrm{a}~{}\mathrm{subgraph}~{}\mathrm{of}~{}G~{}\mathrm{and}~{}\mathfrak{D}_{d}(\widehat{G}^{(k)})\neq\emptyset\\}$.

###  2.3 Signed graphs and the spectral radius

All the distinct eigenvalues of the power hypergraph $G^{(k)}$ are given by
eigenvalues of signed subgraphs as follows [4].

######  Lemma 2.4.

[4] The complex number $\lambda$ is an eigenvalue of $G^{(k)}$ if and only if
$(a)$ some signed induced subgraph of $G$ has an eigenvalue $\sigma$ such that
$\sigma^{2}=\lambda^{k}$, when $k=3$;
$(b)$ some signed subgraph of $G$ has an eigenvalue $\sigma$ such that
$\sigma^{2}=\lambda^{k}$, when $k\geq 4$.

We call signed graphs $G_{\pi}$ and $G_{\pi^{\prime}}$ switching equivalent if
there is a diagonal matrix $D$ with diagonal entries $\pm 1$ such that
$A(G_{\pi^{\prime}})=D^{-1}A(G_{\pi})D$. Clearly, switching equivalent signed
graphs have the same spectrum. The signed graphs $G_{+}$ and $G_{-}$ are the
ones with all signs $+1$ and all signs $-1$, respectively. If $G_{\pi}$ is
switching equivalent to $G_{+}$, then $G_{\pi}$ is called a balanced signed
graph. Note that $G_{+}$ and $G_{-}$ are switching equivalent if and only if
$G$ is bipartite.

######  Lemma 2.5.

[24, Theorem 3.1] A signed graph $G_{\pi}$ contains a balanced spanning
subgraph, say $H_{\tilde{\pi}}$, which satisfies
$\lambda_{\mathrm{max}}(G_{\pi})\leq\lambda_{\mathrm{max}}(H_{\tilde{\pi}})=\rho(H)$.

We obtain the following result from Lemma 2.5.

######  Lemma 2.6.

Let $G$ be a connected graph and $\pi\in\Pi$. Then $\rho(G_{\pi})\leq\rho(G)$,
with equality if and only if $G_{\pi}$ is switching equivalent to $G_{+}$ or
$G_{-}$. Moreover, $G_{\pi}$ has an eigenvalue $\rho(G)$ if and only if it is
switching equivalent to $G_{+}$, and it has an eigenvalue $-\rho(G)$ if and
only if it is switching equivalent to $G_{-}$.

###### Proof.

Note that
$\rho(G_{\pi})=\max\\{\lambda_{\max}(G_{\pi}),\lambda_{\max}(G_{-\pi})\\}$. It
is clear that if $G_{\pi}$ is switching equivalent to $G_{+}$, then it has an
eigenvalue $\rho(G)$, and if it is switching equivalent to $G_{-}$, then it
has an eigenvalue $-\rho(G)$, hence in both cases $\rho(G_{\pi})=\rho(G)$.

From Lemma 2.5, we have that
$\rho(G_{\pi})=\lambda_{\max}(G_{\pm\pi})\leq\rho(H)\leq\rho(G)$. If equality
holds, then $H=G$, and hence $G_{\pm\pi}=H_{\tilde{\pi}}$, which is balanced,
i.e., $G_{\pi}$ is switching equivalent to $G_{+}$ or $G_{-}$.

If $G_{\pi}$ has an eigenvalue $\rho(G)$, and it would not be switching
equivalent to $G_{+}$, then by the above it must be switching equivalent to
$G_{-}$, in which case it also has an eigenvalue $-\rho(G)$. But then $G$ is
bipartite, in which case $G_{+}$ is switching equivalent to $G_{-}$, and hence
to $G_{\pi}$ after all. Similarly it follows that if $G_{\pi}$ has an
eigenvalue $-\rho(G)$, then it is switching equivalent to $G_{-}$. ∎

##  3 The number of parity-closed walks via spectral moments of signed graphs

Our first goal is to show that the number of parity-closed walks $P_{d}$ of
length $d$ in a graph $G$ is the arithmetic mean of spectral moments of all
signed graphs with underlying graph $G$. Although this result does not concern
hypergraphs, it will become relevant when we apply the results on hypergraphs
in Section 6.

Recall that $\Pi$ denotes the set of all sign functions on the edge set $E$ of
$G$.

######  Theorem 3.7.

Let $G$ be a graph. Then

$\displaystyle{P}_{d}=2^{-|E|}\sum_{\pi\in\Pi}{\mathrm{S}_{d}(G_{\pi})}.$

###### Proof.

We denote the edges of $G$ by $e_{1},e_{2},\ldots,e_{m}$, where $m=|E|$. Let
$\mathcal{A}=\mathcal{A}(a_{1},a_{2},\ldots,a_{m})$ denote the variable
adjacency matrix of $G$ with entries

$\displaystyle\mathcal{A}_{uv}=\left\\{\begin{array}[]{l}a_{i},~{}~{}~{}~{}\mathrm{if}~{}\\{u,v\\}=e_{i},\\\
0,~{}~{}~{}~{}~{}\mathrm{otherwise},\end{array}\right.$

where $a_{i}$ is a variable for each $i\in[m]$. Let $\mathcal{W}_{d}$ be the
set of all closed walks of length $d$ in $G$. For $w\in\mathcal{W}_{d}$, let
$t_{i}(w)$ be the number of times edge $e_{i}$ is used in the closed walk $w$.
The $d$-th order trace of the variable adjacency matrix $\mathcal{A}$ is a
homogeneous polynomial of degree $d$ with respect to
$a_{1},a_{2},\ldots,a_{m}$, i.e.,

$\displaystyle\mathrm{trace}(\mathcal{A}^{d})=\sum_{w\in\mathcal{W}_{d}}{\prod_{e_{i}\in
E(w)}{a_{i}^{t_{i}(w)}}}.$

If $t_{i}(w)$ is even for every $a_{i}\in E(w)$, then the closed walk $w$ is a
parity-closed walk in $G$. In order to account for parity-closed walks only,
we will remove all monomials containing variables of odd degree from
$\mathrm{trace}(\mathcal{A}^{d})$. We then obtain the number of such walks by
substituting $a_{1}=a_{2}=\cdots=a_{m}=1$.

Let $f_{a_{i}}$ be the operation on a polynomial $p$ such that

$f_{a_{i}}\circ
p(a_{1},a_{2},\ldots,a_{m})=\frac{1}{2}p(a_{1},\ldots,a_{i},\ldots,a_{m})+\frac{1}{2}p(a_{1},\ldots,-a_{i},\ldots,a_{m}).$

It follows that $f_{a_{i}}\circ p$ is the polynomial obtained by removing all
terms for which the degree of $a_{i}$ is odd in the polynomial $p$. We
therefore have to use $m$ such operations, and observe that

$\displaystyle f_{a_{m}}\circ f_{a_{m-1}}\circ\cdots\circ f_{a_{1}}\circ
p(a_{1},a_{2},\ldots,a_{m})=2^{-m}\sum_{\pi\in\Pi}p(\pi(e_{1})a_{1},\pi(e_{2})a_{2},\ldots,\pi(e_{m})a_{m})$

Thus, the number of parity-closed walks of length $d$ equals

$\displaystyle{P}_{d}$ $\displaystyle=\left(f_{a_{m}}\circ
f_{a_{m-1}}\circ\cdots\circ
f_{a_{1}}\circ\mathrm{trace}(\mathcal{A}^{d})\right)|_{a_{1}=a_{2}=\cdots=a_{m}=1}$
$\displaystyle=2^{-|E|}\sum_{\pi\in\Pi}{\mathrm{trace}(A(G_{\pi})^{d})}=2^{-|E|}\sum_{\pi\in\Pi}{\mathrm{S}_{d}(G_{\pi})}.$

∎

##  4 The spectral moments of power hypergraphs via the number of parity-
closed walks

Let $\mathcal{G}(m)$ be the set of all connected unlabeled subgraphs (so-
called motifs) of $G$ with at most $m$ edges. For
${\widehat{G}\in\mathcal{G}(m)}$, let $N_{G}(\widehat{G})$ denote the number
of subgraphs of $G$ isomorphic to $\widehat{G}$. A closed walk in
$\widehat{G}$ is called covering if it uses each edge at least once. We use
$p_{d}({\widehat{G}})$ to denote the number of covering parity-closed walks of
length $d$ in ${\widehat{G}}$. Define a function

$\displaystyle{\mathcal{S}}_{d}(k)=\left\\{\begin{array}[]{l}(k-1)^{|V|+|E|(k-2)-1}\sum\limits_{\widehat{G}\in\mathcal{G}(\frac{d}{k})}\frac{2^{|E(\widehat{G})|-|V(\widehat{G})|}k^{|E(\widehat{G})|(k-3)+|V(\widehat{G})|}}{(k-1)^{|V(\widehat{G})|+|E(\widehat{G})|(k-2)-1}}p_{\frac{2d}{k}}(\widehat{G})N_{G}(\widehat{G}),k\mid
d,\\\ 0,{\kern 328.0pt}k\nmid d,\end{array}\right.$ (4.3)

that depends on $G$, $d$, $k$ and involves parity-closed walks. By
substituting $k=2$ in (4.3), it follows that

$\displaystyle\mathcal{S}_{d}(2)=\sum_{\widehat{G}\in\mathcal{G}(\frac{d}{2})}p_{d}(\widehat{G})N_{G}(\widehat{G})=P_{d},$
(4.4)

so the definition $S_{d}(k)$ extends a natural decomposition of counting
parity-closed walks in $G$ to larger $k$.

The goal of this section is to show that ${\mathcal{S}}_{d}(k)$ is an
expression for the spectral moments of the power hypergraph $G^{(k)}$ for
$k\geq 3$. In order to accomplish this, we first need to look closer at the
Eulerian digraphs $D_{f}$ and their numbers of spanning trees.

###  4.1 Eulerian digraphs

A vertex $v\in V({G}^{(k)})\setminus V({G})$ is called a core vertex of
$G^{(k)}$. For $\\{i,j\\}\in E(G)$, we use $\\{i,j\\}^{(k)}$ to denote the
hyperedge of $G^{(k)}$ formed by adding $k-2$ core vertices to $\\{i,j\\}$. We
denote the set of core vertices in $\\{i,j\\}^{(k)}$ by $\mathcal{N}_{ij}$.

We provide the following lemma to give the multiplicity of every arc of the
multi-digraph $D$ in ${\mathfrak{D}_{d}(\widehat{G}^{(k)})}$. This will allow
us to find all multi-digraphs ${D\in\mathfrak{D}_{d}(\widehat{G}^{(k)})}$ to
compute the spectral moment coefficient $c_{d}(\widehat{G}^{(k)})$ from Lemma
2.3.

######  Lemma 4.8.

Let $k\geq 3$. For ${D\in\mathfrak{D}_{d}(\widehat{G}^{(k)})}$, let
$m_{D}(v,u)$ denote the multiplicity of the arc $(v,u)$ in $E(D)$. Let
$\\{i,j\\}\in E(\widehat{G})$. Then $m_{D}(v,u)=m_{D}(v,u^{\prime})$ for any
three distinct vertices $v,u,u^{\prime}$ in $\\{i,j\\}^{(k)}$ and
$m_{D}(i,j)+m_{D}(j,i)=2m_{D}(v,i)=2m_{D}(v,j)$ for every core vertex $v$ of
$\\{i,j\\}^{(k)}$.

###### Proof.

From the construction of $D_{f}\cong D$, it follows that
$m_{D}(v,u)=m_{D}(v,u^{\prime})$ for any three distinct vertices
$v,u,u^{\prime}$ in $\\{i,j\\}^{(k)}$.

Because a core vertex $v\in\mathcal{N}_{ij}$ occurs in only one hyperedge, if
follows that
$\mathrm{deg}_{D}^{+}(v)=\sum_{u\in\\{i,j\\}^{(k)}\setminus\\{v\\}}{m_{D}(v,u)}=(k-1)m_{D}(v,i)$
and

$\displaystyle\mathrm{deg}_{D}^{-}(v)$
$\displaystyle=\sum_{u\in\\{i,j\\}^{(k)}\setminus\\{v\\}}{m_{D}(u,v)}$
$\displaystyle=m_{D}(i,v)+m_{D}(j,v)+\sum_{u\in\mathcal{N}_{ij}\setminus\\{v\\}}{m_{D}(u,v)}$
$\displaystyle=m_{D}(i,j)+m_{D}(j,i)+\sum_{u\in\mathcal{N}_{ij}\setminus\\{v\\}}{m_{D}(u,i)}.$

Since $D\in\mathfrak{D}_{d}(\widehat{G}^{(k)})$ is Eulerian, we have
$\mathrm{deg}_{D}^{-}(v)=\mathrm{deg}_{D}^{+}(v)$. It yields that

$\displaystyle
km_{D}(v,i)=m_{D}(i,j)+m_{D}(j,i)+\sum_{u\in\mathcal{N}_{ij}}{m_{D}(u,i)}$
(4.5)

for all $v\in\mathcal{N}_{ij}$. It follows that $m_{D}(v,i)=m_{D}(u,i)$ for
any $v,u\in\mathcal{N}_{ij}$. By (4.5), we have
$m_{D}(i,j)+m_{D}(j,i)=2m_{D}(v,i)=2m_{D}(v,j)$ for all
$v\in\mathcal{N}_{ij}$. ∎

For ${D\in\mathfrak{D}_{d}(\widehat{G}^{(k)})}$, let $D^{*}$ be the multi-
digraph obtained by removing all core vertices from $D$ and let
$\mathfrak{D}^{*}=\mathfrak{D}^{*}_{d}(\widehat{G}^{(k)})=\\{D^{*}:D\in\mathfrak{D}_{d}(\widehat{G}^{(k)})\\}$.
It follows from Lemma 4.8 that there is a one-one correspondence between
$\mathfrak{D}_{d}(\widehat{G}^{(k)})$ and
$\mathfrak{D}^{*}_{d}(\widehat{G}^{(k)})$, i.e., $D$ can be reconstructed from
$D^{*}$ using the derived equations in the statement of the lemma.

######  Lemma 4.9.

Let $k\geq 3$ and ${D\in\mathfrak{D}_{d}(\widehat{G}^{(k)})}$. Then $D^{*}$ is
Eulerian.

###### Proof.

We use Lemma 4.8. For any $i\in V(\widehat{G})$, we have that

$\mathrm{deg}_{D}^{+}(i)=\sum_{j:\\{i,j\\}\in
E(\widehat{G})}{(k-1)m_{D}(i,j)}$

and

$\displaystyle\mathrm{deg}_{D}^{-}(i)$ $\displaystyle=\sum_{j:\\{i,j\\}\in
E(\widehat{G})}{\left(m_{D}(j,i)+\sum_{v\in\mathcal{N}_{ij}}m_{D}(v,i)\right)}$
$\displaystyle=\sum_{j:\\{i,j\\}\in
E(\widehat{G})}{\left(m_{D}(j,i)+(k-2)\frac{m_{D}(i,j)+m_{D}(j,i)}{2}\right).}$

Since $D$ is Eulerian, we have
$\mathrm{deg}_{D}^{+}(i)=\mathrm{deg}_{D}^{-}(i)$, which implies that

$\sum_{j:\\{i,j\\}\in E(\widehat{G})}{m_{D}(i,j)}=\sum_{j:\\{i,j\\}\in
E(\widehat{G})}{m_{D}(j,i)},$

i.e., $\mathrm{deg}_{D^{*}}^{+}(i)=\mathrm{deg}_{D^{*}}^{-}(i)$ for $i\in
V(\widehat{G})=V(D^{*})$. Thus, $D^{*}$ is Eulerian. ∎

Using Lemma 4.8, we can now give an intuitive description of the set
$\mathcal{G}_{d}$ from (2.7). Recall that $\mathcal{G}(m)$ is the set of all
connected unlabeled subgraphs (motifs) of $G=(V,E)$ with at most $m$ edges.

######  Lemma 4.10.

Let $k\geq 3$. Then $\mathcal{G}_{d}=\mathcal{G}(\frac{d}{k})$ and
$|E(D^{*})|=\frac{2d}{k}$ for $D\in\mathfrak{D}_{d}(\widehat{G}^{(k)})$.

###### Proof.

We will first prove that $\mathcal{G}_{d}\subseteq\mathcal{G}(\frac{d}{k})$.

For any $\widehat{G}\in\mathcal{G}_{d}$ and
$D\in\mathfrak{D}_{d}(\widehat{G}^{(k)})$, first note that $|E(D)|=d(k-1)$. On
the other hand, using Lemma 4.8, we have that

$\displaystyle|E(D)|=\sum_{\\{i,j\\}\in
E(\widehat{G})}{\sum_{u,v\in\\{i,j\\}^{(k)}\atop u\neq v}{m_{D}(u,v)}}$
$\displaystyle=\sum_{\\{i,j\\}\in
E(\widehat{G})}\left({\sum_{v\in\\{i,j\\}^{(k)}\setminus\\{i\\}}m_{D}(i,v)}+{\sum_{v\in\\{i,j\\}^{(k)}\setminus\\{j\\}}m_{D}(j,v)}+{\sum_{u\in\mathcal{N}_{ij}}\sum_{v\in\\{i,j\\}^{(k)}\setminus\\{u\\}}m_{D}(u,v)}\right)$
$\displaystyle=\sum_{\\{i,j\\}\in
E(\widehat{G})}\left({(k-1)m_{D}(i,j)}+{(k-1)m_{D}(j,i)}+{\sum_{u\in\mathcal{N}_{ij}}\sum_{v\in\\{i,j\\}^{(k)}\setminus\\{u\\}}m_{D}(u,v)}\right).$

Because $m_{D}(u,v)=\frac{m_{D}(i,j)+m_{D}(j,i)}{2}$ for any
$u\in\mathcal{N}_{ij}$ and any ${v\in\\{i,j\\}^{(k)}}\setminus\\{u\\}$, it now
readily follows that

$|E(D)|=k(k-1)\sum_{\\{i,j\\}\in
E(\widehat{G})}{\frac{m_{D}(i,j)+m_{D}(j,i)}{2}}.$

Since $|E(D)|=d(k-1)$, we thus have that

$\displaystyle\sum_{\\{i,j\\}\in
E(\widehat{G})}{\frac{m_{D}(i,j)+m_{D}(j,i)}{2}}=\frac{d}{k}.$ (4.6)

From Lemma 4.8, we know that ${\frac{m_{D}(i,j)+m_{D}(j,i)}{2}}$ is a positive
integer for any $\\{i,j\\}\in E(\widehat{G})$. Hence we obtain that
$|E(\widehat{G})|\leq\frac{d}{k}$, i.e,
$\widehat{G}\in\mathcal{G}(\frac{d}{k})$.

From (4.6) it also follows that

$\displaystyle|E(D^{*})|$ $\displaystyle=\sum_{i\in
V(\widehat{G})}\deg_{D^{*}}(i)=\sum_{i\in V(\widehat{G})}\sum_{j:\\{i,j\\}\in
E(\widehat{G})}m_{D}(i,j)$ $\displaystyle=\sum_{\\{i,j\\}\in
E(\widehat{G})}{m_{D}(i,j)+m_{D}(j,i)}=\frac{2d}{k}.$

Finally, we will show that $\mathcal{G}_{d}\supseteq\mathcal{G}(\frac{d}{k})$.
For any $\widehat{G}\in\mathcal{G}(\frac{d}{k})$, there exists a closed walk
$w$ in $\widehat{G}$ with length $\frac{2d}{k}$ such that all edges of
$\widehat{G}$ are used an even number of times. We first construct the multi-
digraph $D_{w}=(V(\widehat{G}),E(w))$ without core vertices from the closed
walk $w$. Then $D_{w}$ is clearly Eulerian. Recall that $m_{D_{w}}(i,j)$
denotes the multiplicity of the arc $(i,j)$ in $E(w)$, and note that
$\frac{m_{D_{w}}(i,j)+m_{D_{w}}(j,i)}{2}$ is a positive integer. Next, we will
add core vertices and their incident arcs to $D_{w}$ in order to obtain a
multi-digraph $D$. For any $\\{i,j\\}\in E(\widehat{G})$ and any core vertex
$v\in\mathcal{N}_{ij}$, we construct $D$ such that
$m_{D}(v,u)=\frac{m_{D_{w}}(i,j)+m_{D_{w}}(j,i)}{2}$ for any
$u\in\\{i,j\\}^{(k)}\setminus\\{v\\}$ and
$m_{D}(i,v)=m_{D}(i,j)=m_{D_{w}}(i,j)$. It is easy to see that $D$ is Eulerian
and $D\in\mathfrak{D}_{d}(\widehat{G}^{(k)})$, i.e,
$\mathfrak{D}_{d}(\widehat{G}^{(k)})$ is not empty, since $D_{w}$ is Eulerian.
Thus, $\widehat{G}\in\mathcal{G}_{d}$. ∎

An additional consequence of the above proof is that every covering parity-
closed walk $w$ gives rise to a Eulerian walk in some
$D^{*}=D_{w}\in\mathfrak{D}^{*}_{d}(\widehat{G}^{(k)})=\mathfrak{D}^{*}$. This
leads to the following result.

######  Lemma 4.11.

Let $k\geq 3$ and $\widehat{G}\in\mathcal{G}(\frac{d}{k})$. Then

$p_{2d/k}(\widehat{G})=\sum_{D^{*}\in\mathfrak{D}^{*}}\frac{|E(D^{*})|}{b(D^{*})}\prod_{v\in
V(D^{*})}(\mathrm{deg}_{D^{*}}^{+}(v)-1)!t(D^{*}).$

###### Proof.

As remarked, every covering parity-closed walk $w$ gives rise to a Eulerian
walk in some $D^{*}$. On the other hand, consider a Eulerian walk in some
$D^{*}\in\mathfrak{D}^{*}$. First, note that the walk gives rise to a covering
closed walk in the underlying graph $\widehat{G}$. Next, let $D$ be the
corresponding multi-digraph in $\mathfrak{D}_{d}(\widehat{G}^{(k)})$. Then
$m_{D}(i,j)=m_{D^{*}}(i,j)$ for any two non-core vertices $i,j$. By Lemma 4.8,
we have $m_{D}(i,j)+m_{D}(j,i)=2m_{D}(v,i)$ for every core vertex $v$ of
$\\{i,j\\}^{(k)}$, and hence $m_{D^{*}}(i,j)+m_{D^{*}}(j,i)$ is even. This
implies that every edge in the corresponding walk is covered an even number of
times, and hence the (covering) walk is parity-closed. The result now follows
by Lemma 2.2 (the “BEST theorem”). ∎

###  4.2 The number of spanning trees

In order to obtain the spectral moments of $G^{(k)}$ from (2.7), we need to
further reduce the spectral moment coefficients $c_{d}(\widehat{G}^{(k)})$,
and hence we have to reduce the number of spanning trees $t(D)$ from Lemma
2.3. By the Matrix-Tree theorem [9] and an expression for the determinant
involving the Schur complement [1], the number of spanning trees of a larger
graph can be reduced to the number of spanning trees of a smaller weighted
graph [7, 11, 15, 25]. Using a similar trick, we reduce the number of spanning
trees $t(D)$ of the digraph $D$ to $t(D^{*})$ as follows.

######  Lemma 4.12.

Let $k\geq 3$ and ${D\in\mathfrak{D}_{d}(\widehat{G}^{(k)})}$. Then

$\displaystyle
t(D)=t(D^{*})k^{|E(\widehat{G})|(k-3)+|V(\widehat{G})|-1}2^{|E(\widehat{G})|-V(\widehat{G})+1}\prod_{\\{i,j\\}\in
E(\widehat{G})}{\left(\frac{m_{D^{*}}(i,j)+m_{D^{*}}(j,i)}{2}\right)}^{k-2}.$
(4.7)

###### Proof.

We write the Laplacian matrix of $D$ as a block matrix

${L_{D}}=\begin{bmatrix}M&N\\\ P&Q\end{bmatrix}.$

The matrix $M$ is a $|V(\widehat{G})|\times|V(\widehat{G})|$ matrix, with
$M_{ii}=\mathrm{deg}_{D}^{+}(i)$ and $M_{ij}=-m_{D}(i,j)$ for $i\in
V(\widehat{G})$.

Denote the edges of $G$ by $e_{1},e_{2},\ldots,e_{|E(\widehat{G})|}$. The
matrix $Q$ is a block diagonal matrix with diagonal blocks
$Q_{mm}=\frac{m_{D}(i,j)+m_{D}(j,i)}{2}(kI-J)$, where $\\{i,j\\}=e_{m}$, $I$
is an identity matrix and $J$ is an all-ones matrix of size
$(k-2)\times(k-2)$.

The matrix $N$ is a block matrix with $|V(\widehat{G})|\times|E(\widehat{G})|$
blocks as follows. Let $\mathbf{1}$ be the all-ones column vector of size
$(k-2)$. Then $N_{im}=-m_{D}(i,j)\mathbf{1}^{\top}$ if $e_{m}=\\{i,j\\}$ and
$N_{im}=0$ if $i\notin e_{m}$. Similarly, the matrix $P$ is a block matrix
with blocks $P_{mi}=-\frac{m_{D}(i,j)+m_{D}(j,i)}{2}\mathbf{1}$ if
$e_{m}=\\{i,j\\}$ and $P_{mi}=0$ if $i\notin e_{m}$.

Let $\widehat{L_{D}}$ denote the submatrix of $L_{D}$ obtained by deleting the
first row and column, then we can write it as block matrix

$\widehat{L_{D}}=\begin{bmatrix}\widehat{M}&\widehat{N}\\\
\widehat{P}&Q\end{bmatrix}.$

From the Matrix-tree Theorem [9], we have
$t(D)=\mathrm{det}(\widehat{L_{D}})$. Note that the matrix $Q$ is invertible
and $(Q^{-1})_{mm}=(Q_{mm})^{-1}=k^{-1}(m_{D}(i,j)+m_{D}(j,i))^{-1}(2I+J)$,
where $\\{i,j\\}=e_{m}$. From the determinant formula involving the Schur
complement [1], we have

$\displaystyle
t(D)=\mathrm{det}(\widehat{L_{D}})=\mathrm{det}(Q)\mathrm{det}(\widehat{M}-\widehat{N}Q^{-1}\widehat{P}).$
(4.8)

Furthermore,

$\displaystyle{\left({\widehat{M}-\widehat{N}{Q^{-1}}\widehat{P}}\right)_{ii}}$
$\displaystyle={\widehat{M}_{ii}}-\sum\limits_{m=1}^{\left|{E(\widehat{G})}\right|}{{\widehat{N}_{im}}{{\left({{Q^{-1}}}\right)}_{mm}}{\widehat{P}_{mi}}}$
$\displaystyle=\mathrm{deg}_{D}^{+}(i)-\sum_{j:\\{i,j\\}\in
E(\widehat{G})}{(2k)^{-1}m_{D}(i,j)\mathbf{1}^{\top}(2I+J)\mathbf{1}}$
$\displaystyle=\mathrm{deg}_{D}^{+}(i)-\frac{k-2}{2}\sum_{j:\\{i,j\\}\in
E(\widehat{G})}{m_{D}(i,j)}$
$\displaystyle=(k-1)\mathrm{deg}_{D^{*}}^{+}(i)-\frac{k-2}{2}\mathrm{deg}_{D^{*}}^{+}(i)=\frac{k}{2}\mathrm{deg}_{D^{*}}^{+}(i)$

and

$\displaystyle{\left({\widehat{M}-\widehat{N}{Q^{-1}}\widehat{P}}\right)_{ij}}$
$\displaystyle={\widehat{M}_{ij}}-\sum\limits_{m=1}^{\left|{E(\widehat{G})}\right|}{{\widehat{N}_{im}}{{\left({{Q^{-1}}}\right)}_{mm}}{\widehat{P}_{mj}}}$
$\displaystyle=-m_{D}(i,j)-\frac{k-2}{2}m_{D}(i,j)=-\frac{k}{2}m_{D^{*}}(i,j).$

Thus, for the Schur complement, we have
${\widehat{M}-\widehat{N}{Q^{-1}}\widehat{P}}=\frac{k}{2}\widehat{L_{D^{*}}}$,
where $\widehat{L_{D^{*}}}$ is obtained from the Laplacian matrix of $D^{*}$
by removing the same row and column as in $M$. Hence
$\mathrm{det}(\widehat{M}-\widehat{N}Q^{-1}\widehat{P})=\mathrm{det}(\frac{k}{2}\widehat{L_{D^{*}}})=(\frac{k}{2})^{|V(\widehat{G})|-1}t(D^{*})$.

Note also that if $e_{m}=\\{i,j\\}$, then

$\displaystyle\mathrm{det}(Q_{mm})$
$\displaystyle={\left(\frac{m_{D^{*}}(i,j)+m_{D^{*}}(j,i)}{2}\right)}^{k-2}\mathrm{det}(kI-J)$
$\displaystyle=2k^{k-3}{\left(\frac{m_{D^{*}}(i,j)+m_{D^{*}}(j,i)}{2}\right)}^{k-2}.$

By (4.8), we thus have that

$\displaystyle t(D)$
$\displaystyle=(\frac{k}{2})^{|V(\widehat{G})|-1}t(D^{*})\mathrm{det}(Q)=(\frac{k}{2})^{|V(\widehat{G})|-1}t(D^{*})\prod_{m=1}^{|E(\widehat{G})|}{\mathrm{det}(Q_{mm})}$
$\displaystyle=t(D^{*})k^{|E(\widehat{G})|(k-3)+|V(\widehat{G})|-1}2^{|E(\widehat{G})|-V(\widehat{G})+1}\prod_{\\{i,j\\}\in
E(\widehat{G})}{\left(\frac{m_{D^{*}}(i,j)+m_{D^{*}}(j,i)}{2}\right)}^{k-2}.$

∎

###  4.3 The number of covering closed walks

In a related paper [3], the spectral moment coefficients of power hypertrees
were reduced to the spectral moment coefficients of trees as follows.

######  Lemma 4.13.

[3] Let $k\geq 3$ and let $\widehat{T}$ be a a tree. Then

$c_{\ell
k}(\widehat{T}^{(k)})=\frac{k^{|E(\widehat{T})|(k-2)+1}}{2(k-1)^{|V(\widehat{T})|+|E(\widehat{T})|(k-2)-1}}c_{2\ell}(\widehat{T}).$

Note that $c_{2\ell}(\widehat{T})$ is the number of covering closed walks of
length $2\ell$ in $\widehat{T}$. We recall that a closed walk in which every
edge is used an even number of times is called a parity-closed walk and that
we denote the number of covering parity-closed walks of length $2\ell$ in
$\widehat{G}$ by $p_{2\ell}(\widehat{G})$. It is clear that for trees, every
closed walk is parity-closed, so
$c_{2\ell}(\widehat{T})=p_{2\ell}(\widehat{T})$.

Lemma 4.13 does not hold in the case of general graphs, but using the earlier
results in this section, it can be generalized as follows.

######  Lemma 4.14.

Let $k\geq 3$ and let $\widehat{G}\in\mathcal{G}(\ell)$. Then

$\displaystyle c_{\ell
k}(\widehat{G}^{(k)})=\frac{2^{|E(\widehat{G})|-|V(\widehat{G})|}k^{|E(\widehat{G})|(k-3)+|V(\widehat{G})|}}{(k-1)^{|V(\widehat{G})|+|E(\widehat{G})|(k-2)-1}}p_{2\ell}(\widehat{G}).$
(4.9)

###### Proof.

From the spectral moment coefficient in Lemma 2.3, we have

$\displaystyle c_{\ell k}(\widehat{G}^{(k)})=\ell k(k-1)((k-1)!)^{-\ell
k}\sum_{D\in\mathfrak{D}_{\ell
k}(\widehat{G}^{(k)})}{\frac{\left|\\{f:f\in\mathcal{F}_{\ell
k}(\widehat{G}^{(k)})~{}\mathrm{and}~{}D_{f}\cong D\\}\right|t(D)}{\prod_{v\in
V(D)}\mathrm{deg}_{D}^{+}(v)}}.$ (4.10)

First recall how $D_{f}\cong D$ is constructed from $\ell k$ rooted hyperedges
of $\widehat{G}^{(k)}$. In order to count the number of $f$ that give rise to
a given $D$, note that we can permute the $k-1$ non-roots of each hyperedge
(without changing $D_{f}$). We can also permute the hyperedges with the same
root. If this root is a core vertex, then this however leads to the same $f$
because the permuted hyperedges are the same. If the root, $i$ say, is not a
core vertex, then it occurs $\deg^{+}_{D^{*}}(i)$ times, but again, permuting
the same hyperedges (with hyperedge $\\{i,j\\}^{(k)}$ with root $i$ occuring
$m_{D^{*}}(i,j)$ times) leads to the same $f$. This implies that

$\displaystyle\left|\\{f:f\in\mathcal{F}_{\ell
k}(\widehat{G}^{(k)})~{}\mathrm{and}~{}D_{f}\cong D\\}\right|=((k-1)!)^{\ell
k}\frac{\prod_{i\in V(\widehat{G})}(\deg^{+}_{D^{*}}(i))!}{\prod_{(i,j)\in
E(D^{*})}{m_{D^{*}}(i,j)!}}$ (4.11)

From Lemma 4.8, it follows that if $v\in\mathcal{N}_{ij}$, then
$\deg_{D}^{+}(v)=(k-1)\frac{m_{D}(i,j)+m_{D}(j,i)}{2}$, which implies that

$\displaystyle\prod_{v\in V(D)}{\mathrm{deg}_{D}^{+}(v)}=\prod_{v\in
V(D^{*})}{\mathrm{deg}_{D}^{+}(v)}\prod_{v\in{V(D)\setminus
V(D^{*})}}{\mathrm{deg}_{D}^{+}(v)}$ $\displaystyle=\prod_{v\in
V(D^{*})}{(k-1)\mathrm{deg}_{D^{*}}^{+}(v)}\prod_{\\{i,j\\}\in
E(\widehat{G})}{\left((k-1)\frac{m_{D^{*}}(i,j)+m_{D^{*}}(j,i)}{2}\right)^{k-2}}$
$\displaystyle=(k-1)^{|V(\widehat{G})|+(k-2)|E(\widehat{G})|}\prod_{v\in
V(\widehat{G})}{\mathrm{deg}_{D^{*}}^{+}(v)}\prod_{\\{i,j\\}\in
E(\widehat{G})}{\left(\frac{m_{D^{*}}(i,j)+m_{D^{*}}(j,i)}{2}\right)^{k-2}}.$
(4.12)

Next, recall that there is a one-one correspondence between
$\mathfrak{D}^{*}=\mathfrak{D}^{*}_{d}(\widehat{G}^{(k)})$ and
$\mathfrak{D}_{d}(\widehat{G}^{(k)})$. After substituting (4.7), (4.11) and
(4.3) into (4.10), eliminating and collecting terms, we then obtain that

$\displaystyle c_{\ell k}(\widehat{G}^{(k)})$
$\displaystyle=\ell\frac{k^{|E(\widehat{G})|(k-3)+|V(\widehat{G})|}2^{|E(\widehat{G})|-|V(\widehat{G})|+1}}{(k-1)^{|V(\widehat{G})|+|E(\widehat{G})|(k-2)-1}}\sum_{D^{*}\in\mathfrak{D}^{*}}\frac{\prod_{v\in
V(D^{*})}(\mathrm{deg}_{D^{*}}^{+}(v)-1)!t(D^{*})}{\prod_{(i,j)\in
E(D^{*})}{m_{D^{*}}(i,j)!}}$
$\displaystyle=\frac{2^{|E(\widehat{G})|-|V(\widehat{G})|}k^{|E(\widehat{G})|(k-3)+|V(\widehat{G})|}}{(k-1)^{|V(\widehat{G})|+|E(\widehat{G})|(k-2)-1}}\sum_{D^{*}\in\mathfrak{D}^{*}}\frac{|E(D^{*})|}{b(D^{*})}\prod_{v\in
V(D^{*})}(\mathrm{deg}_{D^{*}}^{+}(v)-1)!t(D^{*}),$

where in the second equality, we used that $|E(D^{*})|=2\ell$ by Lemma 4.10
and $b(D^{*})$ equals the product of the factorials of the multiplicities of
the edges. By Lemma 4.11, (4.9) now follows. ∎

From (2.7), (4.3), Lemmas 4.10 and 4.14, we finally obtain our claimed
expression for the spectral moment of $k$-power hypergraphs.

######  Proposition 4.15.

Let $k\geq 3$. Then

$\displaystyle\mathrm{S}_{d}(G^{(k)})={\mathcal{S}}_{d}(k).$

##  5 The characteristic polynomial of power hypergraphs

So far, we have used the “trace formula” for tensors to derive the spectral
moments of the power hypergraph $G^{(k)}$. From Lemma 2.4, we can find the
eigenvalues of $G^{(k)}$ from the eigenvalues of the signed graphs on $G$. In
this section, we will discuss how to derive the multiplicities of the
eigenvalues using these eigenvalues, numbers of parity-closed walks in $G$,
and spectral moments. The derived expressions will depend explicitly on $k$.

Let $\Sigma$ denote the set of squares of the nonzero eigenvalues of all
signed subgraphs of $G$, let $\varsigma=|\Sigma|$, and denote the elements of
$\Sigma$ by $\sigma^{2}_{1},\sigma^{2}_{2},\ldots,\sigma^{2}_{\varsigma}$.

By Lemma 2.4 and the fact that the spectrum of $G^{(k)}$ is $k$-symmetric [17]
(see also [23, Theorem 3.1]), we can write the characteristic polynomial
$\phi_{k}(\lambda)$ of $G^{(k)}$ as

$\phi_{k}(\lambda)={\lambda^{\mu_{0}(k)}}\prod_{i=1}^{\varsigma}(\lambda^{k}-\sigma_{i}^{2})^{\mu_{i}(k)},$
(5.1)

where $\mu_{i}(k)$ is the multiplicity of the corresponding eigenvalues
$\lambda$. Note that $\sigma_{i}^{2}\in\Sigma$ does not necessarily give rise
to an eigenvalue of $G^{(3)}$ if $\pm|\sigma_{i}|$ is not an eigenvalue of a
signed induced subgraph. In that case $\mu_{i}(3)=0$.

Let

$\mathrm{M}=\begin{bmatrix}{\sigma^{2}_{1}}&{\sigma^{2}_{2}}&\cdots&{\sigma^{2}_{\varsigma}}\\\
{\sigma^{4}_{1}}&{\sigma^{4}_{2}}&\cdots&{\sigma^{4}_{\varsigma}}\\\
\vdots&\vdots&\ddots&\vdots\\\
{\sigma_{1}^{2\varsigma}}&{\sigma_{2}^{2\varsigma}}&\cdots&{\sigma_{\varsigma}^{2\varsigma}}\end{bmatrix},$

which is an invertible (cf. Vandermonde) matrix of coefficients. Let the
multiplicity vector be
$\mu(k)=\left(\mu_{1}(k),\mu_{2}(k),\ldots,\mu_{\varsigma}(k)\right)^{\top}$
and the spectral moments vector be
$S(k)=\left({{\mathrm{S}_{k}}({G^{(k)}})},{{\mathrm{S}_{2k}}({G^{(k)}})},\ldots,{{\mathrm{S}_{\varsigma
k}}({G^{(k)}})}\right)^{\top}$.

From (5.1), the spectral moments can be written as $\mathrm{S}_{\ell
k}(G^{(k)})=\sum_{i=1}^{\varsigma}{k\mu_{i}(k)\sigma^{2\ell}_{i}}$ for all
positive integers $\ell$, which leads to the (nonsingular) system of equations

$k\mathrm{M}\mu(k)=S(k)$

for the multiplicities.

Next, we will rewrite $S(k)$ using the subgraph structural interpretation
(4.3) of the spectral moments (Proposition 4.15). Let
$\chi=|\mathcal{G}(\varsigma)|$, denote the (non-isomorphic) subgraphs of $G$
with at most $\varsigma$ edges by
$\widehat{G}_{1},\widehat{G}_{2},\ldots,\widehat{G}_{\chi}$ and let the
parity-closed walk matrix be

$\displaystyle\mathrm{P}=\begin{bmatrix}{p_{2}(\widehat{G}_{1})}&{p_{2}(\widehat{G}_{2})}&\cdots&{p_{2}(\widehat{G}_{\chi})}\\\
{p_{4}(\widehat{G}_{1})}&{p_{4}(\widehat{G}_{2})}&\cdots&{p_{4}(\widehat{G}_{\chi})}\\\
\vdots&\vdots&\ddots&\vdots\\\
{p_{2\varsigma}(\widehat{G}_{1})}&{p_{2\varsigma}(\widehat{G}_{2})}&\cdots&{p_{2\varsigma}(\widehat{G}_{\chi})}\end{bmatrix}.$

Moreover, consider the subgraph number vector
$N=\left(N_{G}(\widehat{G}_{1}),N_{G}(\widehat{G}_{2}),\ldots,N_{G}(\widehat{G}_{\chi})\right)^{\top}$
and the diagonal $\chi\times\chi$ matrix $\mathrm{D}(k)$ with

$(\mathrm{D}(k))_{ii}=\frac{2^{|E(\widehat{G}_{i})|-|V(\widehat{G}_{i})|}k^{|E(\widehat{G}_{i})|(k-3)+|V(\widehat{G}_{i})|}}{(k-1)^{|V(\widehat{G}_{i})|+|E(\widehat{G}_{i})|(k-2)-1}}$

for $i\in[\chi]$. From Proposition 4.15 and (4.3), with the additional remark
that ${p_{2\ell}(\widehat{G_{i}})}=0$ when $|E(\widehat{G_{i}})|>\ell$ (i.e.,
$\mathrm{P}_{\ell i}=0$ when $\widehat{G_{i}}\notin\mathcal{G}(\ell)$), we
then have

${\mathrm{S}_{\ell
k}}({G^{(k)}})=(k-1)^{|V|+(k-2)|E|-1}\sum_{i=1}^{\chi}\mathrm{D}(k)_{ii}\mathrm{P}_{\ell
i}N_{i},$

and hence

$\mu(k)=k^{-1}\mathrm{M}^{-1}S(k)=\frac{(k-1)^{|V|+(k-2)|E|-1}}{k}\mathrm{M}^{-1}\mathrm{P}\mathrm{D}(k)N.$

Thus, we have expressions for the multiplicities in $\mu(k)$. The remaining
multiplicity $\mu_{0}(k)$ clearly follows from these, and we may conclude the
following.

######  Theorem 5.16.

Let $k\geq 3$. Then the characteristic polynomial of $G^{(k)}$ is

$\phi_{k}(\lambda)={\lambda^{\mu_{0}(k)}}\prod_{i=1}^{\varsigma}(\lambda^{k}-\sigma_{i}^{2})^{\mu_{i}(k)},$

where
$\mu_{i}(k)=\frac{(k-1)^{|V|+(k-2)|E|-1}}{k}(\mathrm{M}^{-1}\mathrm{P}\mathrm{D}(k)N)_{i}$
for $i\in[{\varsigma}]$ and

$\mu_{0}(k)=(|V|+(k-2)|E|)(k-1)^{|V|+(k-2)|E|-1}-k\sum_{i=1}^{\varsigma}\mu_{i}(k).$

##  6 The geometric mean of the characteristic polynomials of all signed
graphs with the same underlying graph

Using the expression in Theorem 5.16, we can extend the characteristic
polynomial $\phi_{k}(\lambda)$ of a power hypergraph to $k=2$. We thus define
the pseudo-characteristic function

$\displaystyle\beta(\lambda)\equiv\phi_{2}(\lambda)={\lambda^{\mu_{0}(2)}}\prod_{i=1}^{\varsigma}(\lambda^{2}-\sigma_{i}^{2})^{\mu_{i}(2)},$

where $\mu_{i}(2)=\frac{1}{2}(\mathrm{M}^{-1}\mathrm{P}N)_{i}$ for
$i\in[{\varsigma}]$ (note that $\mathrm{D}(2)=I$) and
$\mu_{0}(2)=|V|-2\sum_{i=1}^{\varsigma}\mu_{i}(2)$. Note that $\beta(\lambda)$
is not a polynomial, in general, because the $\mu_{i}(2)$ are not necessarily
integer for $i=0,1,\ldots,\varsigma$.

It is important to note that also for $k=2$, the “spectral moments” (of
$\beta(\lambda)$) are determined by the equation $2\mathrm{M}\mu(2)=S(2)$. On
the other hand, we defined $\mu(2)=\frac{1}{2}\mathrm{M}^{-1}\mathrm{P}N$,
which implies by (4.4) that

$S(2)=\mathrm{P}N=(\mathcal{S}_{2}(2),\mathcal{S}_{4}(2),\ldots,\mathcal{S}_{2\varsigma}(2))^{\top}.$

Thus, it follows that Proposition 4.15 extends to $k=2$ in the sense that the
spectral moment
$\mathrm{S}_{d}(\beta)=\sum_{i=1}^{\varsigma}{2\mu_{i}(2)\sigma^{d}_{i}}$ of
the pseudo-characteristic function equals ${\mathcal{S}}_{d}(2)$, for $d$ even
and $d\leq 2\varsigma$ (and note that both equal $0$ for $d$ odd).

######  Proposition 6.17.

Let $G$ be a graph and $d$ be even with $d\leq 2\varsigma$. Then the number of
parity-closed walks in $G$ equals
$P_{d}=\sum_{i=1}^{\varsigma}{2\mu_{i}(2)\sigma^{d}_{i}}$.

Because $P_{d}=2^{-|E|}\sum_{\pi\in\Pi}{\mathrm{S}_{d}(G_{\pi})}$ by Theorem
3.7, we will next show that the multiplicity $\mu_{i}(2)$ is the average
multiplicity of $\pm|\sigma_{i}|$ over all signed graphs on $G$, and obtain
the following.

######  Theorem 6.18.

The pseudo-characteristic function $\beta(\lambda)$ is the geometric mean of
the characteristic polynomials of all signed graphs with underlying graph $G$,
i.e.,

$\displaystyle\beta(\lambda)=\prod_{\pi\in\Pi}{\phi_{\pi}(\lambda)}^{2^{-|E|}}.$

Moreover, $\beta(\lambda)$ is the characteristic polynomial of $G$ if and only
if $G$ is a forest.

###### Proof.

Note first that $|\sigma_{i}|$ and $-|\sigma_{i}|$ have the same average
multiplicity over all signed graphs as sign functions $\pi$ and $-\pi$ give
opposite eigenvalues. Let $\overline{\mu}_{i}$ then be the average
multiplicity of $\pm|\sigma_{i}|$ over all signed graphs on $G$ and let
$\overline{\mu}$ be the corresponding vector. Because
$P_{d}=2^{-|E|}\sum_{\pi\in\Pi}{\mathrm{S}_{d}(G_{\pi})}$ by Theorem 3.7, it
is clear that $\mathrm{P}N=2\mathrm{M}\overline{\mu}$. Because
$2\mathrm{M}\mu(2)=S(2)=\mathrm{P}N$ and $M$ is invertible, it follows that
$\overline{\mu}=\mu(2)$.

Now it follows that $\beta(\lambda)^{2^{|E|}}$ is a monic polynomial with the
same spectral moments as $\prod_{\pi\in\Pi}\phi_{\pi}(\lambda)$. From Newton’s
identities, also known as the Girard-Newton formulae, it is known that a monic
polynomial is determined by its spectral moments [10, 19], which finishes the
proof of the main statement.

We are left to determine when $\beta(\lambda)$ is the characteristic
polynomial $\phi(G)$ of $G$. Note first that if $G$ is a forest, then
${\phi_{\pi}(\lambda)}=\phi(G)$ for all $\pi\in\Pi$, and hence
$\beta(\lambda)=\prod_{\pi\in\Pi}{\phi_{\pi}(\lambda)}^{2^{-|E|}}=\phi(G)$.

On the other hand, if $\beta(\lambda)=\phi(G)$, then their spectral moments
are the same, hence $P_{d}=S_{d}(G)$ for every $d$, which implies that every
closed walk is a parity-closed walk. But then $G$ cannot have cycles, so it is
a forest.

Thus, $\beta(\lambda)=\phi(G)$ if and only if $G$ is a forest. ∎

######  Corollary 6.19.

Let $G$ be a cycle. Then $\beta(\lambda)=\phi(\lambda^{2}-2)^{\frac{1}{2}}$.

###### Proof.

A signed cycle $(C_{n},{\pi})$ is called positive (resp. negative) if the
product of signs of all edges of $(C_{n},{\pi})$ is positive (resp. negative).
Note that all positive (resp. negative) cycles are switching equivalent. We
use $\phi_{+}(\lambda)$ and $\phi_{-}(\lambda)$ to denote the characteristic
polynomial of a positive and negative cycle, respectively. It is known that
$\phi_{+}(\lambda)=\prod_{i=1}^{n}(\lambda-2\cos\frac{2i\pi}{n})$ [8, p. 72]
and $\phi_{-}(\lambda)=\prod_{i=1}^{n}(\lambda-2\cos\frac{(2i-1)\pi}{n})$ [12,
Lemma 2.3]. From Theorem 6.18, we have

$\displaystyle\beta^{2}(\lambda)$
$\displaystyle=\phi_{+}(\lambda)\phi_{-}(\lambda)=\prod_{i=1}^{2n}(\lambda-2\cos\tfrac{i\pi}{n})=\prod_{i=1}^{n}(\lambda^{2}-4\cos^{2}\tfrac{i\pi}{n})$
$\displaystyle=\prod_{i=1}^{n}(\lambda^{2}-2-2\cos\tfrac{2i\pi}{n})=\phi(\lambda^{2}-2),$

where we have used the well-known identities $\cos\theta=-\cos(\theta-\pi)$
and $2\cos^{2}\theta=1+\cos 2\theta$. ∎

For example, $\beta(\lambda)=(\lambda^{2}-1)(\lambda^{2}-4)^{\frac{1}{2}}$ for
$G=C_{3}$, and note that this is not a polynomial. In fact, when $G$ is
connected, but not a tree, then $\beta(\lambda)$ is not a polynomial because
the multiplicity of the spectral radius is not an integer. Indeed, note that
if $G$ is connected, then its spectral radius has multiplicity $1$, and hence
$G_{\pi}$ has at most one eigenvalue $\rho(G)$ for all sign functions $\pi$.
If $G$ is not a tree, then there is a sign function $\pi$ such that $G_{\pi}$
is not switching equivalent to $G_{+}$ and hence, by Lemma 2.6, $G_{\pi}$ does
not have eigenvalue $\rho(G)$. Thus, the average multiplicity of eigenvalue
$\rho(G)$ over all sign functions is less than $1$, and hence $\beta(\lambda)$
is not a polynomial. In the next section, we will make this more precise and
determine the multiplicity of $\rho(G)$ as a root of $\beta$.

From the arithmetic-geometric mean inequality, we can get an inequality
between the matching polynomial $\alpha(\lambda)$ and the pseudo-
characteristic function $\beta(\lambda)$ of $G$.

######  Corollary 6.20.

Let $\lambda_{0}$ be a real number such that $\phi_{\pi}(\lambda_{0})\geq 0$
for all $\pi\in\Pi$. Then $\alpha(\lambda_{0})\geq\beta(\lambda_{0})$, with
equality if and only if $\phi_{\pi}(\lambda_{0})$ is constant over all
$\pi\in\Pi$.

Godsil and Gutman [14] showed that the matching polynomials $\alpha$ of some
standard graphs can be expressed in terms of some classical orthogonal
polynomials. For example $\alpha_{C_{n}}(\lambda)=2T_{n}(\lambda/2)$, where
$T_{n}$ is a Chebyshev polynomial of the first kind. For the complete graphs
$K_{n}$, they obtained that $\alpha_{K_{n}}(\lambda)={He}_{n}(\lambda)$, where
${He}_{n}$ denotes the probabilist’s Hermite polynomial. Thus, Corollary 6.20
implies that $\beta_{K_{n}}(\lambda_{0})\leq{He}_{n}(\lambda_{0})$, for
example.

##  7 The multiplicity of the spectral radius of a power hypergraph

Let $n_{\rho}(G^{(k)})$ be the total multiplicity of eigenvalues of the power
hypergraph $G^{(k)}$ whose modulus is equal to the spectral radius
$\rho(G^{(k)})$. We note that it follows from Theorem 5.16 that this number is
$k$ times the multiplicity of the spectral radius.

######  Lemma 7.21.

Let $k\geq 3$ and let $G$ be a connected graph. Then

$\displaystyle
n_{\rho}(G^{(k)})=2^{|E|-|V|}k^{|E|(k-3)+|V|}\lim_{\ell\rightarrow\infty}{\frac{{P}_{2\ell}}{\rho(G)^{2\ell}}}.$

###### Proof.

It is known that the spectral radius of a power hypergraph $G^{(k)}$ is a
positive number and $\rho(G^{(k)})^{k}=\rho(G)^{2}$ [26] (this follows also
from Lemmas 2.4 and 2.6). Since the $\ell k$-th order spectral moment
$\mathrm{S}_{\ell k}(G^{(k)})$ is the sum of the $\ell k$-th powers of all
eigenvalues of a power hypergraph $G^{(k)}$, it follows that

$\displaystyle
n_{\rho}(G^{(k)})=\lim_{\ell\rightarrow\infty}{\frac{\mathrm{S}_{\ell
k}(G^{(k)})}{\rho(G^{(k)})^{\ell
k}}}=\lim_{\ell\rightarrow\infty}{\frac{\mathrm{S}_{\ell
k}(G^{(k)})}{\rho(G)^{2\ell}}}.$

By Proposition 4.15, we then have

$\displaystyle
n_{\rho}(G^{(k)})=\lim_{\ell\rightarrow\infty}\frac{\sum_{\widehat{G}\in\mathcal{G}(\ell)}l_{G}(\widehat{G})p_{2\ell}(\widehat{G})}{\rho(G)^{2\ell}},$
(7.1)

where
$l_{G}(\widehat{G})={2^{|E(\widehat{G})|-|V(\widehat{G})|}{(k-1)^{|V(G^{(k)})|-|V(\widehat{G}^{(k)})|}}k^{|E(\widehat{G})|(k-3)+|V(\widehat{G})|}}{N_{G}(\widehat{G})}$.
We claim that in the summation over $\mathcal{G}(\ell)$, only $G$ itself
contributes to the limit in (7.1). Indeed, for any graph
${H}\in\mathcal{G}(\ell)$ with $H\neq G$, let $\mathcal{H}(\ell)$ be the set
of connected subgraphs (motifs) of the graph $H$ with at most $\ell$ edges. By
(7.1), we have

$n_{\rho}(H^{(k)})=\lim_{\ell\rightarrow\infty}\frac{\sum_{\widehat{G}\in\mathcal{H}(\ell)}l_{H}(\widehat{G})p_{2\ell}(\widehat{G})}{\rho(H)^{2\ell}},$

which implies that

$\lim_{\ell\rightarrow\infty}\frac{\sum_{\widehat{G}\in\mathcal{H}(\ell)}l_{H}(\widehat{G})p_{2\ell}(\widehat{G})}{\rho(G)^{2\ell}}=0,$

because $\rho(H)<\rho(G)$.

Note that $l_{H}(\widehat{G}){p_{2\ell}(\widehat{G})}\geq 0$ and
$l_{H}(\widehat{G})>0$ for any ${\widehat{G}\in\mathcal{H}(\ell)}$ and any
$H\in\mathcal{G}(\ell)$ ($H\neq G$), hence it follows that

$\displaystyle\lim_{\ell\rightarrow\infty}\frac{p_{2\ell}(\widehat{G})}{\rho(G)^{2\ell}}=0$

for any ${\widehat{G}\in\mathcal{G}(\ell)}$ with ${\widehat{G}\neq G}$. By
(7.1), we thus have

$\displaystyle n_{\rho}(G^{(k)})$
$\displaystyle={2^{|E|-|V|}k^{|E|(k-3)+|V|}}\lim_{\ell\rightarrow\infty}\frac{p_{2\ell}({G})}{\rho(G)^{2\ell}}$
$\displaystyle={2^{|E|-|V|}k^{|E|(k-3)+|V|}}\lim_{\ell\rightarrow\infty}\frac{\sum_{\widehat{G}\in\mathcal{G}(\ell)}p_{2\ell}(\widehat{G}){N_{G}(\widehat{G})}}{\rho(G)^{2\ell}}$
$\displaystyle=2^{|E|-|V|}k^{|E|(k-3)+|V|}\lim_{\ell\rightarrow\infty}{\frac{{P}_{2\ell}}{\rho(G)^{2\ell}}}.$

∎

From Theorem 3.7, we have that
${{P}_{2\ell}}=2^{-|E|}\sum_{\pi\in\Pi}{\mathrm{S}_{2\ell}(G_{\pi})}$. Using
Lemma 2.6 about the spectral radius of signed graphs, we obtain
$\lim_{\ell\rightarrow\infty}{\frac{{P}_{2\ell}}{\rho(G)^{2\ell}}}$ and
determine the multiplicity of the spectral radius of $G^{(k)}$.

######  Theorem 7.22.

For a connected graph $G$ and $k\geq 3$, the multiplicity of the spectral
radius of $G^{(k)}$ is $k^{|E|(k-3)+|V|-1}$.

###### Proof.

From Theorem 3.7 and Lemma 7.21, we have that

$\displaystyle n_{\rho}(G^{(k)})$
$\displaystyle=2^{-|V|}k^{|E|(k-3)+|V|}\lim_{\ell\rightarrow\infty}{\frac{\sum_{\pi\in\Pi}{\mathrm{S}_{d}(G_{\pi})}}{\rho(G)^{2\ell}}}$
$\displaystyle=2^{-|V|}k^{|E|(k-3)+|V|}\lim_{\ell\rightarrow\infty}{\frac{\sum_{\pi\in\Pi}{\sum_{\lambda_{\pi}\in\sigma(G_{\pi})}\lambda^{2\ell}_{\pi}}}{\rho(G)^{2\ell}}},$
(7.2)

where $\sigma(G_{\pi})$ is the spectrum of $G_{\pi}$.

Let $\mathcal{D}$ be the set of all $|V|\times|V|$ diagonal matrices with
diagonal entries $\pm 1$. Let $\Pi_{+}$ and $\Pi_{-}$ denote the sets of sign
functions $\pi\in\Pi$ such that $A(G_{\pi})=D^{-1}A(G)D$ and
$\Pi_{+}=D^{-1}\left(-A(G)\right)D$ for some $D\in\mathcal{D}$, respectively.
By Lemma 2.6, $\Pi_{+}$ contains the sign functions for which $G_{\pi}$ has an
eigenvalue $\rho(G)$, and $\Pi_{-}$ contains the sign functions for which
$G_{\pi}$ has an eigenvalue $-\rho(G)$.

We observe that since $G$ is connected, $D^{-1}A(G)D=A(G)$ implies that $D=I$
or $D=-I$. This implies that there is a two-one correspondence between
$\mathcal{D}$ and $\Pi_{+}$ and similarly between $\mathcal{D}$ and $\Pi_{-}$.
Thus,

$\displaystyle|\Pi_{+}|=|\Pi_{-}|=\frac{|\mathcal{D}|}{2}=2^{|V|-1}.$

From Lemma 2.6, we now have that

$\displaystyle\lim_{\ell\rightarrow\infty}{\frac{\sum_{\pi\in\Pi}{\sum_{\lambda_{\pi}\in\sigma(G_{\pi})}\lambda^{2\ell}_{\pi}}}{\rho(G)^{2\ell}}}$
$\displaystyle=\lim_{\ell\rightarrow\infty}{\frac{\sum_{\pi\in\Pi_{+}}\rho(G_{\pi})^{2\ell}+\sum_{\pi\in\Pi_{-}}(-\rho(G_{\pi}))^{2\ell}}{\rho(G)^{2\ell}}}$
$\displaystyle=|\Pi_{+}|+|\Pi_{-}|=2^{|V|}$

(note that it is not relevant whether $G$ is bipartite, in which case
$\Pi_{+}=\Pi_{-}$, or not). By (7), we thus have
$n_{\rho}(G^{(k)})=k^{|E|(k-3)+|V|}$, and hence the multiplicity of the
spectral radius of the power hypergraph $G^{(k)}$ is $k^{|E|(k-3)+|V|-1}$. ∎

As a corollary of the proof, we can also extend the above result to the case
$k=2$. Indeed, as $\Pi_{+}$ contains all sign functions $\pi$ such that
$G_{\pi}$ has an eigenvalue $\rho(G)$, each with multiplicity $1$, and the
multiplicity of the spectral radius $\rho(G)$ as a root of $\beta$ is the
average multiplicity over all sign functions, it follows that this
multiplicity equals $2^{-|E|}|\Pi_{+}|$.

######  Proposition 7.23.

For a connected graph $G$, the multiplicity of the spectral radius $\rho(G)$
as a root of $\beta$ is $2^{-|E|+|V|-1}$.

Consequently, we confirm our earlier observation that for a connected graph,
$\beta$ is a polynomial only for a tree.

## Acknowledgement

This work is supported by the National Natural Science Foundation of China
(No. 12071097), the Natural Science Foundation for The Excellent Youth
Scholars of the Heilongjiang Province (No. YQ2022A002) and the Fundamental
Research Funds for the Central Universities.

## References

## References

  * [1] Richard Brualdi and Hans Schneider.  Determinantal identities: Gauss, Schur, Cauchy, Sylvester, Kronecker, Jacobi, Binet, Laplace, Muir, and Cayley.  Linear Algebra and its Applications, 52:769–791, 1983.
  * [2] Kungching Chang, Kelly Pearson, and Tan Zhang.  Perron-Frobenius theorem for nonnegative tensors.  Communications in Mathematical Sciences, 6(2):507–520, 2008.
  * [3] Lixiang Chen, Changjiang Bu, and Jiang Zhou.  Spectral moments of hypertrees and their applications.  Linear and Multilinear Algebra, 2021.  Doi:10.1080/03081087.2021.1953431.
  * [4] Lixiang Chen, Edwin R. van Dam, and Changjiang Bu.  All eigenvalues of the power hypergraph and signed subgraphs of a graph.  arXiv:2209.03709, 2022.
  * [5] Gregory Clark and Joshua Cooper.  A Harary-Sachs theorem for hypergraphs.  Journal of Combinatorial Theory, Series B, 149:1–15, 2021.
  * [6] Joshua Cooper and Aaron Dutle.  Spectra of uniform hypergraphs.  Linear Algebra and its Applications, 436(9):3268–3292, 2012.
  * [7] Douglas Crabtree.  Applications of M-matrices to non-negative matrices.  Duke Mathematical Journal, 33(1):197–208, 1966.
  * [8] Dragoš Cvetković, Horst Sachs, and Michael Doob.  Spectra of Graphs: Theory and Applications.  VEB Deutscher Verlag der Wissenschaften, 1980.
  * [9] Art Duval, Caroline Klivans, and Jeremy Martin.  Simplicial matrix-tree theorems.  Transactions of the American Mathematical Society, 361(11):6073–6114, 2009.
  * [10] J.A. Eidswick.  A proof of Newton’s power sum formulas.  American Mathematical Monthly, 75(4):396–396, 1968.
  * [11] Ky Fan.  Note on M-matrices.  The Quarterly Journal of Mathematics, 11(1):43–49, 1960.
  * [12] Yizheng Fan.  Largest eigenvalue of a unicyclic mixed graph.  Applied Mathematics-A Journal of Chinese Universities Series B, 19(2):140–148, 2004.
  * [13] Matthew Farrell and Lionel Levine.  Multi-Eulerian tours of directed graphs.  The Electronic Journal of Combinatorics, 23(2), 2016.  Article ID #P2.21.
  * [14] Christopher Godsil and Ivan Gutman.  On the matching polynomial of a graph.  In L. Lovász and V.T. Sós, editors, Algebraic Methods in Graph Theory, volume I of Colloquia Mathematica Societatis János Bolyai, pages 241–249, North-Holland, New York, August 1978. the Conderence held in Szged.  papers from the Conderence held in Szged, August 24-31,1978.
  * [15] Alexander Griffing, Benjamin Lynch, and Eric Stone.  Structural properties of the minimum cut of partially-supplied graphs.  Discrete Applied Mathematics, 177:152–157, 2014.
  * [16] Shenglong Hu, Zhenghai Huang, Chen Ling, and Liqun Qi.  On determinants and eigenvalue theory of tensors.  Journal of Symbolic Computation, 50:508–531, 2013.
  * [17] Shenglong Hu and Liqun Qi.  The eigenvectors associated with the zero eigenvalues of the Laplacian and signless Laplacian tensors of a uniform hypergraph.  Discrete Applied Mathematics, 169:140–151, 2014.
  * [18] Shenglong Hu, Liqun Qi, and Jiayu Shao.  Cored hypergraphs, power hypergraphs and their Laplacian H-eigenvalues.  Linear Algebra and its Applications, 439:2980–2998, 2013.
  * [19] Dan Kalman.  A matrix proof of Newton’s identities.  Mathematics Magazine, 73(4):313–315, 2000.
  * [20] Lek-Heng Lim.  Singular values and eigenvalues of tensors: a variational approach.  In 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, pages 129–132. IEEE, 2005.
  * [21] Adam Marcus, Daniel Spielman, and Nikhil Srivastava.  Interlacing families I: Bipartite Ramanujan graphs of all degrees.  Annals of Mathematics, 182(1):307–325, 2015.
  * [22] Liqun Qi.  Eigenvalues of a real supersymmetric tensor.  Journal of Symbolic Computation, 40(6):1302–1324, 2005.
  * [23] Jiayu Shao, Liqun Qi, and Shenglong Hu.  Some new trace formulas of tensors with applications in spectral hypergraph theory.  Linear and Multilinear Algebra, 63(5):971–992, 2015.
  * [24] Zoran Stanić.  Bounding the largest eigenvalue of signed graphs.  Linear Algebra and its Applications, 573:80–89, 2019.
  * [25] Jiang Zhou and Changjiang Bu.  The enumeration of spanning tree of weighted graphs.  Journal of Algebraic Combinatorics, 54(1):75–108, 2021.
  * [26] Jiang Zhou, Lizhu Sun, Wenzhe Wang, and Changjiang Bu.  Some spectral properties of uniform hypergraph.  Electronic Journal of Combinatorics, 21:4–24, 2014.