On Entries of Spectral Decompositions and Applications

Keywords. continuous-time quantum walk, average mixing matrix, spectral projection, line graph, strongly cospectral vertices, strongly regular graph

2020 Mathematics Subject Classification. Primary 05C50. Secondary 15A18, 05C76, 05E30, 81P45.

Introduction

Let $A=\sum_\theta\theta E_\theta$ be the spectral decomposition of the adjacency matrix of a finite simple graph. The entries of $E_\theta$ record walks between individual vertices and determine the Cesàro average mixing matrix. Their diagonal entries are the local multiplicities of Fiol and Garriga [11], whose square roots are the angles of Cvetković [8 Chapter 4]. The off diagonal entries are the crossed local multiplicities of Fiol, Garriga and Yebra [12]. The spectral moments of these entries differ from the cosine moments in [21 Theorem 2.1], where uniform average mixing on strongly regular graphs under a freely chosen law for the time reduces to affine conditions on three cosine moments of that law. We use this classical framework in three directions.

1. Graph spectral-entry bounds. For a graph on $n$ vertices without isolated vertices, Lemma 3.1 bounds every local weight by $\frac{n-1}{n}$, with equality only in $K_n$. An inequality for squared weights then gives the sharp diagonal and trace bounds for the average mixing matrix (Theorem 3.3). This proves the connected form of the complete-graph conjecture of Godsil, Guo and Sobchuk

[16 Conjecture 9.1] together with its equality case. We also derive bounds for all graphs, for individual components, and in terms of local degrees. The degree bound is attained exactly at complete components (Remark 3.6). The vertex and diagonal bounds, the trace bound for connected graphs and their attainment by $K_n$ also occur in the formal development [23], without a formal characterization of when equality holds. The relation of Lemma 3.1 to that development and to earlier eigenvector bounds is described after its proof.

(2) Line-graph return bounds. For the line graph of a connected graph $\Gamma$, Theorem 4.1 gives $\widehat{M}_{qq} \ge\frac{1}{\operatorname{rank} B}$ at a bridge $q$ with a bipartite component on one side, where $B$ is the unsigned incidence matrix. The inequality follows from a bound by the size of the eigenvalue support and the absence of weight at zero for $B^{\mathsf{T}}B$. We characterize equality by $\Gamma\in\{P_2, P_3\}$. Equality forces uniform local weights and a simple positive spectrum. Local and global moments then force the bridge to be pendant. Known inverse-incidence formulas reduce the remaining cases to stars and the paw. Proposition 4.7 gives an extension to uniform linear hypergraphs.

(3) A strongly regular graph corollary. We give a short proof of the entry criterion stated in Godsil’s working notes [13]. It says that vertices $u$, $v$ are strongly cospectral precisely when $\lvert(E_\theta)_{uv}\rvert= (E_\theta)_{uu}$ for every $\theta$. Applying it to the entries of the three spectral idempotents recovers the known classification in connected noncomplete strongly regular graphs. There the strongly cospectral pairs are exactly the two-vertex parts of cocktail party graphs (Corollary 5.4). The sources of the criterion and of the classification are identified in § 5. The contribution there is the direct proof from the entries.

Section 2 collects the definitions and notation. Sections 3, 4, and 5 develop the three applications. The upper-bound argument uses the neighbor structure of the graph, the bridge argument also uses global traces and inverse Gram diagonals, and the strongly regular case compares diagonal and off diagonal entries. The elementary support-size lower bound is recorded in Theorem 3.8. The inverse-incidence formulas are recalled with their sources in Lemma 4.5. Section 5 also gives the rational form of the entry criterion (Corollary 5.3).

Definitions and notation

All graphs are finite, simple, undirected, and unweighted. For a graph $G$ with vertex set $V$, write $A=A(G)$ for its adjacency matrix, $u\sim v$ for adjacency, $N(u)$ for the set of neighbors of $u$, $d(u)=\lvert N(u)\rvert$ for the degree of $u$, and $\Delta(G)$ for the maximum degree. A vertex is isolated when its degree is zero. Write $V(G)$ and $E(G)$ for the vertex and edge sets of $G$, and $G\setminus v$ and $G-e$ for the graphs obtained by deleting a vertex $v$ and an edge $e$. Write $K_n$, $P_n$ and $C_n$ for the complete graph, the path and the cycle on $n$ vertices, $K_{1,m}$ for the star with $m$ edges, $G_1\sqcup G_2$ for a disjoint union, and $nK_1$ for the edgeless graph on $n$ vertices. Write $\mathbf{e}_v$ for the standard basis vector at $v$, $\mathbf{1}$ for the all-ones vector, and $J_n$, or $J$, for the all-ones matrix of order $n$. A partition of $V$ is equitable when, for any two cells $X$ and $Y$, every vertex of $X$ has the same number of neighbors in $Y$.

For a graph $\Gamma$ with $m$ edges, the unsigned vertex-edge incidence matrix $B$ has, in the column of an edge, a one at each endpoint and zeros elsewhere. The line graph $L(\Gamma)$ has the edges of $\Gamma$ as vertices, two of them adjacent when they share an endpoint. With the diagonal degree matrix $D(\Gamma)$,

by [17 Lemmas 8.2.2 and 8.2.3]. The matrix $BB^{\mathsf{T}}$ is the signless Laplacian of $\Gamma$, and $D(\Gamma)-A(\Gamma)$ is its Laplacian. A finite $k$-uniform linear hypergraph $\mathcal{H}$, with $k\ge2$, has hyperedges of $k$ vertices, and two distinct hyperedges meet in at most one vertex. Its line graph $L(\mathcal{H})$ has the hyperedges as vertices, two of them adjacent when they intersect. Its vertex-hyperedge incidence matrix $B_{\mathcal{H}}$ satisfies $B_H^{\mathsf T}B_H=kI+A(\mathcal{L}(H))$. A graph is strongly regular with parameters $(n,k,\lambda,\mu)$ when it is $k$ regular on $n$ vertices, adjacent vertices have $\lambda$ common neighbors, and distinct nonadjacent vertices have $\mu$ common neighbors. It is primitive when both it and its complement are connected. A connected graph is distance regular when, for vertices $u$ and $v$ at distance $i$, the numbers of neighbors of $v$ at distances $i-1$, $i$ and $i+1$ from $u$ depend only on $i$. The cocktail party graph $K_{2,\ldots,2}$ is the complete multipartite graph whose parts have two vertices each. A signed graph carries a sign $\pm1$ on each edge, and its signed adjacency matrix has these signs in place of the ones of $A$. Switching at a vertex set $X$ negates the signs of the edges between $X$ and $V\setminus X$, and $-K_n$ is $K_n$ with all signs negative.

The spectral decomposition of $A$ over its distinct eigenvalues is

where the $E_\theta$ are real orthogonal projections. The multiplicity of $\theta$ is $m_\theta=\operatorname{tr}E_\theta$, the eigenvalue support of a vector $z$ is $\operatorname{supp}z=\{\theta:E_\theta z\ne0\}$, and $\varphi(G,t)=\det(tI-A(G))$ is the characteristic polynomial, with derivative $\varphi'(G,t)$ in $t$. The same notation is used for a Hermitian matrix $H$, called a Hamiltonian, in place of $A$, with complex projections. The identities (2.1) and (2.2) below then hold with $H^j$ in place of $A^j$ and $\lvert(E_\theta)_{uv}\rvert^2$ in place of $(E_\theta)_{uv}^2$. The continuous-time quantum walk of $H$, its mixing matrix, and its Cesàro average are

where $\circ$ denotes entrywise multiplication. The spectral formula $\widehat{M}_H=\sum_\theta E_\theta\circ\overline{E_\theta}$, standard for graphs [14], holds because the time average of $\exp(it(\theta-\eta))$ vanishes for $\theta\ne\eta$. Replacing $H$ by $H+cI$, where $c\in\mathbb{R}$, multiplies $U_H(t)$ by the scalar $\exp(itc)$, so it changes neither the projections nor $M_H(t)$ nor $\widehat{M}_H$. For a graph we write $\widehat{M}_A(G)=\widehat{M}_{A(G)}$, or $\widehat{M}$ when the graph is clear, and $\widehat{M}_{vv}$ is the average return probability at $v$.

For vertices $u,v$ and every nonnegative integer $j$, the local weights $p_\theta(v)$ and the entries of the projections satisfy

The diagonal entries $p_\theta(v)$ are the local multiplicities and the off diagonal entries $(E_\theta)_{uv}$ are the crossed local multiplicities [9 Section 1.2].

Vertices $u$ and $v$ are cospectral when $(E_\theta)_{uu}=(E_\theta)_{vv}$ for every $\theta$, equivalently $\varphi(G\setminus u,t)=\varphi(G\setminus v,t)$ [18 Theorem 3.1], and they are strongly cospectral when

where the sign may depend on $\theta$ [18].

For $n\ge2$, the spectral projections of $K_n$ are $\frac{1}{n}J_n$ and $I_n-\frac{1}{n}J_n$, so

Graph spectral-entry bounds

Godsil, Guo and Sobchuk [16 Conjecture 9.1] propose that $K_n$ maximizes the trace of the adjacency average mixing matrix. We use the connected formulation, which is also stated in [22 Section 8].

Among connected graphs of order $n$, the maximum is attained by $K_n$. A restriction is necessary, since $\widehat{M}_A(nK_1)=I_n$ has trace $n$. The regular-graph statement [16 Corollary 6.3] likewise fails for $nK_1$ when $n>1$. For a connected $k$-regular graph, however, $E_k=\frac{1}{n}J$ gives directly

and summing over $v$ gives [16 Corollary 6.3] for connected regular graphs. The proof in [16] passes through [16 Lemmas 6.1 and 6.2], which fail for general equitable partitions. For $K_4$ with the equitable partition into two pairs, the eigenspace of $K_4$ for the eigenvalue $-1$ has dimension three and lies in no eigenspace of $2K_2$, contrary to [16 Lemma 6.1]. For the same partition [16 Lemma 6.2] gives the bound $2$, whereas $\operatorname{tr}\widehat{M}_A(K_4)=\frac{5}{2}$ by (4). The Laplacian analogue is [16 Corollary 5.2]. This section proves the adjacency bound without regularity and treats isolated vertices separately.

The first step controls every local spectral weight without any regularity hypothesis.

For a unit eigenvector $x$ with eigenvalue $\theta$, Cioabă and Gregory [3 Theorem 3.2] proved $x_v^2 \le\frac{d(v)}{d(v)+\theta^2}$ for the principal eigenvector, and Van Mieghem [24 equation (18)] proved it for every eigenvalue. Taking $x=\frac{E_\theta e_v}{\lVert E_\theta e_v\rVert}$ when $E_\theta e_v\ne0$ gives

This right side is at most $\frac{n-1}{n}$ precisely when $\theta^2\ge\frac{d(v)}{n-1}$, in particular when $|\theta|\ge1$. When $\theta^2<\frac{d(v)}{n-1}$ it exceeds $\frac{n-1}{n}$, and at $\theta=0$ it equals one. The neighbor argument above covers this remaining range. For the Laplacian, Mohan, Tamon, Xu and Zhan [22 Lemma 6.1] bound the diagonal entries of partial sums of spectral idempotents by a related Cauchy–Schwarz argument over the neighbors of a vertex.

The Cauchy–Schwarz inequalities at the vertex and at a neighbor also occur in [23], with the degrees bounded by $n-1$. That development eliminates $\theta$ to prove the uniform vertex bound, derives the diagonal bound by the squared-weight inequality of Lemma 3.2, and proves the connected trace bound and attainment by $K_n$. Its local bounds apply at vertices with a neighbor, without a connectivity assumption. Its notes observe the extension to graphs without isolated vertices and give an informal sketch of why equality in the trace bound forces $K_n$. Neither [23] nor [3, 24] states the equality case of Lemma 3.1, where equality at one vertex and one eigenvalue already forces $G\cong K_n$.

Proof. Let $s_0=\max_i p_i$. If $s_0\le\frac{1}{2}$, then $\sum_i p_i^2\le s_0\sum_i p_i=s_0\le\frac{1}{2}\le\alpha^2+(1-\alpha)^2$, because $x^2+(1-x)^2$ has minimum value $\frac{1}{2}$ at $x=\frac{1}{2}$. If $s_0\ge\frac{1}{2}$, separating an entry equal to $s_0$ gives

because $x^2+(1-x)^2$ is increasing on $\left[\frac{1}{2},1\right]$. For $\alpha>\frac{1}{2}$, the first case cannot be tight, because $\alpha^2+(1-\alpha)^2>\frac{1}{2}$. Equality then requires $s_0=\alpha$ and exactly one positive entry among the remaining entries. For $\alpha=\frac{1}{2}$, equality in $\sum_i p_i^2\le\frac{1}{2}\sum_i p_i$ requires each positive entry to equal $\frac{1}{2}$. □

Equality holds at some vertex if and only if $G \cong K_n$. In particular,

with equality if and only if $G \cong K_n$. Thus the connected form of [16 Conjecture 9.1] holds for every $n \ge2$, and it holds for $n=1$ because $K_1$ is the only graph of order one.

Proof. Apply Lemma 3.2 to the weights in (2.1), whose squares sum to $\widehat{M}_A(G)_{vv}$ by (2.2), using Lemma 3.1 and the cap $\alpha=\frac{n-1}{n}$. This gives

which is (3.2).

For $n\ge3$, equality implies that some local spectral weight is $\frac{n-1}{n}$. Lemma 3.1 then gives $G\cong K_n$. For $n=2$, the only graph without isolated vertices is $K_2$. Conversely, (2.4) verifies equality at every vertex of $K_n$. Summing (3.2) over the $n$ vertices proves (3.3). If equality holds in the trace bound, every diagonal bound is an equality, so $G\cong K_n$.

The spectral projections of a disjoint union are block diagonal, so its average mixing matrix is the direct sum of those of its components.

Proof. By (2.1) and (2.2), $\widehat{M}_A(G)_{vv}=\sum_\theta p_\theta(v)^2\le\sum_\theta p_\theta(v)=1$, with equality if and only if one weight equals one, that is, if and only if $e_v$ is an eigenvector of $A$. Since $(Ae_v)_v=0$, this happens exactly when $Ae_v=0$, that is, when $v$ is isolated. Summing over $v$ proves the first statement. For the second, let $G'$ be the graph obtained from $G$ by deleting its $n-n'$ isolated vertices, so that $G'$ has $n'\ge2$ vertices and no isolated vertices. The isolated vertices contribute $n-n'$ to the trace, and Theorem 3.3 applied to $G'$ gives

with equality throughout if and only if $n'=2$ and $G'\cong K_2$.

Proof. Apply Theorem 3.3 to each component of order at least two. A component $K_1$ contributes $1$, which is the value of $n_i-2+\frac{2}{n_i}$ at $n_i=1$. Equality holds exactly when every component is complete.

This is the adjacency analogue of [16 Corollary 5.2].

Remark 3.6 (A degree dependent refinement). The proof of Lemma 3.1 only uses $n-1$ as an upper bound for $d(v)$ and for the degree of one neighbor of $v$. Let $v$ be nonisolated and put

The two displayed chains give $1-p\ge\frac{1}{d(v)+1}$ when $|\theta|\ge1$ and $1-p\ge\frac{1}{d(u)+1}$ for every neighbor $u$ when $|\theta|\le1$. For $|\theta|\ge1$ the first of these also follows from the inequality of Van Mieghem discussed after Lemma 3.1. Hence

where the second bound follows from Lemma 3.2 with $\alpha=\frac{D_v}{D_v+1}\ge\frac{1}{2}$. This is never weaker than (3.2), because $D_v\le n-1$ and $\frac{x^2+1}{(x+1)^2}$ increases for $x\ge1$. It is much stronger when $D_v$ is small compared with $n$, for instance for graphs of bounded maximum degree. Since the entries of the idempotents at $v$ only depend on the component of $v$, both bounds and (3.2) also hold with that component in place of $G$ whenever $v$ is not isolated.

Equality in the first bound for some $\theta$, or in the second bound, holds precisely when the component of $v$ is the complete graph $K_{D_v+1}$. By the equality case of Lemma 3.2, equality in the second bound forces $(E_\theta)_{vv}=\frac{D_v}{D_v+1}$ for some $\theta$, so it suffices to treat the first bound. Suppose that $p=(E_\theta)_{vv}$ equals $\frac{D_v}{D_v+1}$. If $|\theta|>1$, the chain with $u=v$ gives $1-p\ge\frac{\theta^2}{d(v)+\theta^2}\ge\frac{1}{d(v)+1}$. If $|\theta|<1$, the chain with a neighbor $u$ of minimum degree gives $1-p\ge\frac{1}{d(u)+\theta^2}\ge\frac{1}{d(u)+1}$. Both contradict $1-p=\frac{1}{D_v+1}$, so $\theta^2=1$. The chain with $u=v$ then forces $d(v)=D_v$ and equality in (3.1). Hence $(I-E_\theta)e_v=c\,y$ for $y=(A-\theta I)e_v$ and a scalar $c\ne0$, and applying $A-\theta I$ gives $y=c(A-\theta I)y$. A vertex $w$ at distance two from $v$ would have $y_w=0$ but $((A-\theta I)y)_w=|N(w)\cap N(v)|>0$. So the component of $v$ consists of $v$ and its $D_v$ neighbors, and Lemma 3.1 applied to this component shows that it is $K_{D_v+1}$. Conversely, at a vertex of $K_{D_v+1}$ the eigenvalue $-1$ has weight $\frac{D_v}{D_v+1}$ and the eigenvalue $D_v$ has weight $\frac{1}{D_v+1}$, so both bounds are attained.

Remark 3.7 (Other Hamiltonians). The proof of Lemma 3.1 uses three properties of $A$. The diagonal of $A$ vanishes, so that $\|(A-\theta I)e_u\|^2=\|Ae_u\|^2+\theta^2$. The squared row norms $\|Ae_u\|^2=d(u)$ are at most $n-1$. Finally $|A_{vu}|=1$ for a neighbor $u$ of $v$. Let $H$ be a Hermitian matrix with zero diagonal, let $v$ be an index for which some $u\ne v$ has $H_{vu}\ne0$, and put $w=|H_{vu}|$ and $R=\max\{\|He_v\|^2,\|He_u\|^2\}$. The same two chains give

for every eigenvalue $\theta$ of $H$. Indeed, if $\theta^2\ge w^2$ the chain with $u=v$ gives $1-(E_\theta)_{vv}\ge\frac{\theta^2}{\|He_v\|^2+\theta^2}\ge\frac{w^2}{R+w^2}$, and if $\theta^2\le w^2$ the chain with $u$ gives $1-(E_\theta)_{vv}\ge\frac{w^2}{\|He_u\|^2+\theta^2}\ge\frac{w^2}{R+w^2}$. Since $R\ge w^2$, Lemma 3.2 applies with $\alpha=\frac{R}{R+w^2}$ and bounds the diagonal entry of the average mixing matrix of $H$ at $v$ by $\alpha^2+(1-\alpha)^2$. The matrices $H$ and $H+cI$ have the same idempotents and the same average mixing matrix, so a constant diagonal may replace the zero diagonal. For a signed graph, or for a graph with equal loop weights at all vertices, this recovers $\frac{n-1}{n}$ and $1-\frac{2}{n}+\frac{2}{n^2}$, and the Laplacian and the signless Laplacian of a regular graph are covered. For a signed graph the equality statement of Lemma 3.1 carries over, but its converse does not. Equality still forces $\theta^2=1$ and the underlying graph to be $K_n$. The equality cases of the Cauchy–Schwarz steps make every column of $H-\theta I$ parallel to $(I-E_\theta)e_v$, so $H=\theta(I-\mathbf{x}\mathbf{x}^{\mathsf{T}})$ with $\mathbf{x}\in\{1,-1\}^n$, and the signed graph is switching equivalent to $K_n$ or to $-K_n$. Both attain equality. A signed complete graph need not attain it. For $K_5$ with the five edges of a Hamilton cycle negative, the spectrum is $0$ and $\pm\sqrt{5}$ with multiplicity two. Its signed adjacency matrix $H$ has $H_{vv}=0$ and $(H^2)_{vv}=4$ at every vertex $v$, so the moments (2) with $j=0,1,2$ give the local weights $\frac{1}{5}$ at $0$ and $\frac{2}{5}$ at $\sqrt{5}$ and at $-\sqrt{5}$. Hence every diagonal entry of an idempotent is at most $\frac{2}{5}$.

The weights in (1) also give a lower bound for the diagonal entries of the average mixing matrix. Unlike Theorem 3.3, it needs no hypothesis on isolated vertices, and its Cauchy–Schwarz step reappears in § 4.

Proof. Since $p_\theta(v)=\lVert E_\theta e_v\rVert^2$, the weight $p_\theta(v)$ is positive exactly when $\theta\in\operatorname{supp}e_v$. By the Cauchy–Schwarz inequality on these $|\operatorname{supp}e_v|$ positive weights,

The number $|\operatorname{supp}e_v|$ is at most the number of distinct eigenvalues, hence at most $n$. Equality $\widehat{M}_{vv}=\frac{1}{n}$ forces $|\operatorname{supp}e_v|=n$, so all $n$ eigenvalues are distinct and have positive weight at $v$, and equality in the Cauchy–Schwarz inequality forces all weights to be equal to $\frac{1}{n}$. Conversely, if $A$ has $n$ distinct eigenvalues and every weight equals $\frac{1}{n}$, then $\widehat{M}_{vv}=n\left(\frac{1}{n}\right)^2=\frac{1}{n}$ by (2). For the polynomial form, Cramer’s rule and the spectral decomposition give

By the uniqueness of partial fraction expansions, $n\varphi(G\setminus v,t)=\varphi'(G,t)$ holds exactly when $np_\theta(v)=m_\theta$ for every $\theta$. When $\varphi(G,t)$ has $n$ distinct roots, every $m_\theta$ equals $1$ and this says that every weight equals $\frac{1}{n}$. The simple spectrum cannot be dropped. Every vertex $v$ of $K_3$ has $3\varphi(K_3\setminus v,t)=3t^2-3=\varphi'(K_3,t)$, while $\widehat{M}_A(K_3)_{vv}=\frac{5}{9}$.

Summing the final bound $\widehat{M}_{vv}\ge\frac{1}{n}$ in Theorem 3.8 gives $\operatorname{tr}\widehat{M}_A(G)\ge1$. Coutinho and Godsil [4 Lemma 15.3.2] prove this trace bound and show that equality forces $n\le2$. Hence for $n\ge3$ the value $\widehat{M}_{vv}=\frac{1}{n}$ cannot occur at every vertex. The question of attainment at a single vertex is discussed in Remark 4.8.

Line-graph return bounds and bridge equality

Let $\Gamma$ be a connected graph on $n$ vertices with $m$ edges and unsigned incidence matrix $B \in\{0,1\}^{n \times m}$. Edges are denoted by letters such as $q$ and $f$, and $e_q \in\mathbb{R}^{m}$ denotes the coordinate vector of the edge $q$. By § 2,

where $D = D(\Gamma)$ and $Q$ is the signless Laplacian. Since the two Hamiltonians $C$ and $A(L(\Gamma))$ differ by $2I_m$, we write

Thus $\widehat{M}_{qq}$ is an average return probability at an edge of $\Gamma$. Average mixing matrices of trees, where every edge is a bridge, were studied by Godsil, Guo and Sinkovic [15].

Lemma 4.3 proves the inequality. The proof of the equality classification follows Lemma 4.5.

Proof. This is a classical result, see [17 Theorem 8.2.1]. A vector $z$ lies in $\ker B^{\mathsf{T}}$ exactly when $z_u+z_v=0$ for every edge $uv$. In a connected bipartite graph the solutions are the scalar multiples of the vector taking the values $1$ and $-1$ on the two parts. If the graph has an odd cycle, alternation around that cycle forces $z$ to vanish on the cycle, and connectedness then forces $z=0$. This description of $\ker B^{\mathsf{T}}$ is used below.

Proof. Let $S$ be the vertex set of a bipartite component of $\Gamma-q$. Give its two parts values $1$ and $-1$, and give all vertices outside $S$ value zero. The resulting vector $z$ satisfies $B^{\mathsf{T}}z=\pm e_q$, because $q$ is the only edge leaving $S$. Thus $e_q \in\operatorname{im} B^{\mathsf{T}}=(\ker B)^\perp$.

Let $F_\lambda$ be the spectral projection of $C$ at $\lambda$, and write $p_\lambda=(F_\lambda)_{qq}$, with $F_0=0$ if $0$ is not an eigenvalue. Since $\ker C=\ker B$, we have $p_0=0$. If $s$ positive eigenvalues have $p_\lambda>0$, then $s\le r$ and

For $m \ge2$, the first inequality is the support-size bound of Theorem 3.8, since $C$ and $A(L(\Gamma))$ have the same projections. The incidence condition removes the weight at $\lambda= 0$ for $C$, equivalently at eigenvalue $-2$ for $A(L(\Gamma))$.

Equality with $\frac{1}{r}$ requires $s=r$ and $p_\lambda=\frac{1}{r}$ on the support. The total multiplicity of positive eigenvalues is $r$, so these are all the positive eigenvalues and each is simple. Using $C_{qq}=2$ and $\operatorname{tr} C=2m$, the first moment gives

Hence $m=r$. In particular, $C$ is positive definite. By Lemma 4.2, the bipartite case has $m=n-1$ and hence is a tree. The nonbipartite case has $m=n$, so it is unicyclic, and its unique cycle must be odd.

The next steps use the second and third local moments at $q$. In any equality case from Lemma 4.3, the uniform spectral weights imply

for every real function $f$ on the spectrum of $C$. We use $f(x)=x^2,x^3,x^{-1}$. The inverse is defined because $C$ is positive definite.

Proof. Assume equality, and write $q=uv$, $a=d(u)$, and $b=d(v)$. Let $\tau$ be the number of triangles in $\Gamma$ and set

The vertex $q$ of $L(\Gamma)$ has degree $a+b-2$. Since $uv$ is a bridge, its endpoints have no common neighbor. Thus the triangles of $L(\Gamma)$ containing $q$ are exactly those formed by three edges incident with $u$ or by three edges incident with $v$. Using $C=2I+A(L(\Gamma))$, we obtain

The matrices $C$ and $Q$ have the same nonzero eigenvalues with multiplicities. Expanding $Q=D+A(\Gamma)$ gives

For example, $\operatorname{tr}(DA(\Gamma)^2)=S_2$ and $\operatorname{tr} A(\Gamma)^3=6\tau$.

Combining (4.3) with (4.4) to (4.5) yields

Since $\Gamma$ is connected with at least one edge, all degrees are positive. Cauchy–Schwarz with weights $d(x)-1\ge0$ gives

Substituting (13) and $\sum_x d(x)=2m$ therefore gives

Suppose, for a contradiction, that $a,b\ge2$, and put

Then

with equality if and only if $a=b=2$.

If $\Gamma$ is a tree, then $m=n-1$ and $\tau=0$. Equation (14) implies

contradicting $Y\ge X$.

If $\Gamma$ is unicyclic, then $m=n$, and (14) implies

Thus $a=b=2$, $\tau=0$, and equality must hold in the weighted Cauchy–Schwarz inequality. Equality there forces all degrees strictly larger than one to have the same value. That value is two, since $d(u)=d(v)=2$. Hence every degree is at most two. A connected unicyclic graph with maximum degree two is a cycle, which has no bridge. This is another contradiction. Therefore $\min\{a,b\}=1$, and $q$ is pendant.

The pendant condition leaves trees and odd unicyclic graphs with a pendant bridge. The inverse Gram matrix reduces them to the stars $K_{1,m}$ and the paw, a triangle with one pendant edge. The average mixing matrix of $K_m$ and the degree identities (13) then exclude all of these except $P_2$ and $P_3$. For trees and odd unicyclic graphs $B$ has full column rank by Lemma 4.2, so $C$ is invertible.

Part (i) is the minimum norm property of the Moore–Penrose inverse [2 Chapter 3]. Part (ii) follows from Bapat’s tree-incidence formula [1]. If $N$ is an oriented incidence matrix of the tree, then $B=D_1ND_2$ for diagonal sign matrices $D_1$ and $D_2$, because a tree is bipartite. Hence $(B^{\mathsf T}B)^{-1}=D_2(N^{\mathsf T}N)^{-1}D_2$ has the same diagonal as $(N^{\mathsf T}N)^{-1}$. Part (iii) follows from the inverse-incidence formula of Hessert and Mallik [19 arXiv version, Theorem 3.1], also recorded in [20 arXiv version, Theorem 1.4]. The values in (ii) and (iii) are also the diagonal cases of their formulas for $C^{-1}$ in [19 arXiv version, Theorems 2.12 and 3.9]. We give direct proofs.

Proof. (i) The vector $z_f = BC^{-1}e_f$ solves $B^{\mathsf T}z_f = e_f$ and lies in $\operatorname{im} B = (\ker B^{\mathsf T})^\perp$. Every solution differs from $z_f$ by an element of $\ker B^{\mathsf T}$, so $z_f$ is the unique minimum norm solution, and $\lVert z_f\rVert^2 = e_f^{\mathsf T}C^{-1}B^{\mathsf T}BC^{-1}e_f = (C^{-1})_{ff}$.

(ii) Let $\sigma\in\{1,-1\}^n$ be a bipartition vector of the tree and let $S$ be a component of $\Gamma-f$, of order $s_f$. The vector $z$ equal to $\sigma$ on $S$ and zero elsewhere satisfies $B^{\mathsf T}z = \pm e_f$, and we fix the sign so that $B^{\mathsf T}z = e_f$. By Lemma 4.2, $\ker B^{\mathsf T}$ is spanned by $\sigma$, so the orthogonal projection of $z$ onto $\sigma^\perp$ is the minimum norm solution in (i), and its squared norm is

(iii) Here $B$ is square and invertible by Lemma 4.2, so $B^{\mathsf T}z=e_f$ has a unique solution $z$ and (i) gives $(C^{-1})_{ff}=\lVert z\rVert^2$. If $f$ is a bridge, let $z$ vanish on the component of $\Gamma-f$ containing the cycle and alternate between $1$ and $-1$ on the tree component, with the sign chosen so that the entries at the two ends of $f$ sum to one. Then $B^{\mathsf T}z=e_f$ and $\lVert z\rVert^2=s_f$. If $f$ lies on the cycle of length $\ell$, then $\Gamma-f$ is a tree in which the two ends of $f$ are joined by a path of even length $\ell-1$. The equations on $\Gamma-f$ force $z$ to alternate between $t$ and $-t$ with equal values at the two ends of $f$, and the equation at $f$ gives $2t=1$. Hence every entry of $z$ has absolute value $\frac{1}{2}$ and

Proof of Theorem 4.1. The inequality and the displayed values of rank $B$ follow from Lemmas 4.2 and 4.3. Suppose equality holds. By Lemmas 4.3 and 4.4, the graph is a tree or an odd unicyclic graph, $m=\operatorname{rank} B$, and $q$ is pendant. Equation (10) gives

First suppose $\Gamma$ is a tree, so $m=n-1$. Since $q$ is pendant, Lemma 4.5(ii) gives

For every edge $f$,

Thus every diagonal entry of $C^{-1}$ is at least $\frac{m}{n}$, with equality precisely at pendant edges. Equation (15) forces every edge to be pendant. Such a tree has diameter at most two and hence is the star $K_{1,m}$.

Now $L(K_{1,m})=K_m$, and (2.4), which also holds for $m=1$ because $\widehat{M}_A(K_1)=[1]$, gives

This vanishes exactly for $m=1,2$, that is, for $\Gamma\cong P_2$ and $\Gamma\cong P_3$. Conversely, every edge of $P_2$ and of $P_3$ is a pendant bridge with a bipartite side, $\operatorname{rank}B=m$, and the display gives

Next suppose $\Gamma$ is odd unicyclic, with cycle length $\ell$. Here $n=m$. Since $q$ is pendant, Lemma 4.5(iii) gives $(C^{-1})_{qq}=1$. Equation (15) would therefore require $\operatorname{tr}C^{-1}=m$. On the other hand,

The odd cycle has at least three edges and $q$ is not on it, so $m \ge4$. If $m > 4$, the last quantity is strictly larger than $m$, a contradiction.

If $m = 4$, the graph is a triangle with a single pendant vertex, the paw. At its unique bridge the endpoint degrees are $a = 3$ and $b = 1$, whereas the full degree sequence is $3, 2, 2, 1$. Thus

contradicting (13). No odd unicyclic graph can attain equality. □

Remark 4.6 (Scope of the two hypotheses). The inequality in (8) holds for every edge $q$ with $\mathbf{e}_q \in\operatorname{im} B^{\mathsf{T}}$, whether or not $q$ is a bridge, because the proof of Lemma 4.3 only uses this property, and this is Proposition 4.7 below with $k = 2$. The property cannot be dropped. For the cycle $C_4$ with one pendant vertex attached at a vertex $w$, the alternating vector of the cycle lies in $\ker B$, $\operatorname{rank} B = 4$, and an exact computation gives $\widehat{M}_{qq} = \frac{71}{296} < \frac{1}{4}$ at either cycle edge $q$ at $w$.

For a bridge $q$, the condition $\mathbf{e}_q \in\operatorname{im} B^{\mathsf{T}}$ is equivalent to the existence of a bipartite component of $\Gamma-q$. Lemma 4.3 proves one direction. Conversely, suppose $\mathbf{e}_q = B^{\mathsf{T}}z$ and both components are nonbipartite. On every edge $xy \ne q$ we have $z_x + z_y = 0$. The odd-cycle argument of Lemma 4.2 forces $z$ to vanish on both components, contradicting $(B^{\mathsf{T}}z)_q = 1$.

The rank bound is the support bound $\widehat{M}_{qq} \ge\frac{1}{s}$ of Lemma 4.3 made explicit through rank $B$, and the gap can be large. For the star $K_{1,m}$ with $m \ge2$ the support bound gives $\frac{1}{2}$, the rank bound gives $\frac{1}{m}$, and the actual value is $1 - \frac{2}{m} + \frac{2}{m^2}$ by (4).

The rank bound has an incidence formulation for the uniform linear hypergraphs of § 2. Let $\mathcal{H}$ be a $k$-uniform linear hypergraph with $m \ge1$ hyperedges and incidence matrix $B_{\mathcal{H}}$, and put

let $P_0$ be the orthogonal projection onto $\ker B_{\mathcal{H}}$ and set $\kappa_q = (P_0)_{qq}$ for a hyperedge $q$.

The proof uses only $C_{\mathcal{H}} = B_{\mathcal{H}}^{\mathsf{T}}B_{\mathcal{H}}$, so (4.9) holds for the average mixing matrix of the Gram matrix $Z^{\mathsf{T}}Z$ of any nonzero real matrix $Z$, with $r = \operatorname{rank} Z$ and $\kappa_q = (P_0)_{qq}$ for the orthogonal projection $P_0$ onto $\ker Z$.

By Proposition 4.7, equality under (4.10) with $m \ge3$ requires $\widehat{M}_{qq} = \frac{1}{m}$ in the line graph on $m$ vertices. Conversely, every graph $G$ on $m$ vertices is $L(\mathcal{H})$ for such a hypergraph with full column rank. Set $k = \Delta(G) + 2$, and let the hyperedge indexed by $x$ consist of the edges incident with $x$ and $k - d(x)$ private vertices. Two distinct hyperedges share only the edge joining their indices, if it exists, so $\mathcal{H}$ is linear and $L(\mathcal{H}) = G$. A private vertex in each hyperedge supplies a row $\mathbf{e}_x^{\mathsf{T}}$ of $B_{\mathcal{H}}$, so $r = m$ and (4.10) holds at every hyperedge.

Thus the question is whether a graph on $m \ge3$ vertices can have $\widehat{M}_{vv} = \frac{1}{m}$ at one vertex. An exhaustive exact computation finds no such vertex in a graph with $3 \le m \le7$ vertices. This computation only delimits the scope of the results, and no proof depends on it. The question remains open for $m \ge8$.

An entry criterion and a strongly regular graph corollary

Throughout this section $G$ is a graph with vertex set $V$, $A = A(G)$, and $\widehat{M} = \widehat{M}_{A(G)}$. Strong cospectrality is defined in (3). Fan and Godsil [10 arXiv version, Lemma 3.1] characterize it by $(E_\theta)_{uu} = (E_\theta)_{vv} = \pm(E_\theta)_{uv}$ for every $\theta$. Coutinho, Juliano and Spier [7 Section 2] use the condition $(E_\theta)_{uu} = \pm(E_\theta)_{uv}$ for every $\theta$ together with cospectrality. Godsil’s working notes [13] state the following criterion without a separate cospectrality condition and without a proof. We include a proof that uses only the projections and their sum.

Proof. Necessity follows by taking inner products in (3). Conversely, write $(E_\theta)_{uv} = \varepsilon_\theta(E_\theta)_{uu}$ with $\varepsilon_\theta\in\{-1,1\}$. Then

because $\varepsilon_\theta^2=1$ and $\sum_\theta E_\theta=I$. Every summand on the left is nonnegative, so each summand vanishes. This proves (3).

An exact test over $\mathbb{Q}$ avoids the eigenvalues. Let $\psi$ be the minimal polynomial of $A$ and $\psi= \prod_g g$ its factorization into distinct monic irreducible polynomials $g$ over $\mathbb{Q}$. For each factor $g$ put $\psi_g = \frac{\psi}{g}$. Since $\psi$ has distinct roots, $g$ and $\psi_g$ are coprime, so by the Chinese remainder theorem there is a polynomial $h_g$ with $h_g \equiv1 \pmod{g}$ and $h_g \equiv0 \pmod{\psi_g}$, unique modulo $\psi$. Put

a rational symmetric idempotent that does not depend on the choice of $h_g$, because $\psi(A) = 0$.

This restates, through the rational idempotents, the rational orthogonal involution of Godsil and Smith [18 Theorem 10.2], see also [4 Lemma 6.8.1], and the proof uses the same Galois argument.

Proof. If $(E_g)_{uv} = \varepsilon_g(E_g)_{uu}$ for every $g$, the computation in the proof of Theorem 5.1 with $E_g$ in place of $E_\theta$ gives $\sum_g \lVert E_g e_v - \varepsilon_g E_g e_u\rVert^2 = 0$, so $E_g e_v = \varepsilon_g E_g e_u$ for every $g$, and applying $E_\theta$ for a root $\theta$ of $g$ gives (2.3). Conversely let $u,v$ be strongly cospectral. The entries of $E_\theta$ lie in $\mathbb{Q}(\theta)$, and an automorphism $\sigma$ of the splitting field of $\psi$ maps $E_\theta$ to $E_{\sigma(\theta)}$, because $E_\theta$ is the Lagrange polynomial in $A$ at $\theta$. Hence $\sigma$ maps $(E_\theta)_{uu}$ to $(E_{\sigma(\theta)})_{uu}$, so it maps the eigenvalue support $\operatorname{supp} e_u$, the set of $\theta$ with $(E_\theta)_{uu} = \lVert E_\theta e_u\rVert^2 \ne0$, onto itself. For $\theta\in\operatorname{supp} e_u$, Theorem 5.1 gives the sign $\varepsilon_\theta= \frac{(E_\theta)_{uv}}{(E_\theta)_{uu}} \in\{1,-1\}$, and $\sigma$ maps it to $\varepsilon_{\sigma(\theta)}$. A rational number is fixed by $\sigma$, so $\varepsilon_{\sigma(\theta)} = \varepsilon_\theta$. The Galois group acts transitively on the roots of each irreducible factor $g$. Hence either all roots of $g$ lie in $\operatorname{supp} e_u$ and $\varepsilon_\theta$ has a common value $\varepsilon_g$ on them, or no root of $g$ lies in $\operatorname{supp} e_u$. In the first case, summing $(E_\theta)_{uv} = \varepsilon_g(E_\theta)_{uu}$ over the roots of $g$ gives $(E_g)_{uv} = \varepsilon_g(E_g)_{uu}$. In the second case (5.1) gives $(E_\theta)_{uv} = (E_\theta)_{uu} = 0$ for every root $\theta$ of $g$, so $(E_g)_{uv} = (E_g)_{uu} = 0$.

We close with strongly regular graphs. Let $G$ be a connected strongly regular graph with parameters $(n,k,\lambda,\mu)$ that is not complete, so that $\mu\ge1$. The adjacency matrix has the eigenvalue $k$ with idempotent $E_k = \frac{1}{n}J$ and two restricted eigenvalues $r > s$ with

see [17 Chapter 10]. Godsil and Smith [18 Section 6] prove that a connected strongly regular graph that is not complete multipartite has no strongly cospectral pair. Since $G$ is distance regular of diameter two, the full classification below is a consequence of [18 Theorem 10.3] and the involution observation in [5 arXiv version, Section 4, before Theorem 4.3]. If distinct vertices $u$ and $v$ are strongly cospectral, the former makes the distance-two matrix $T=J-I-A$ a permutation matrix of order two with $Te_u=e_v$. The latter gives $TE_\theta=\pm E_\theta$ for such a permutation relation $T$. We give a direct proof from the entries.

Proof. Since $G$ is regular and not complete, every vertex has $n-k-1 \ge1$ non-neighbors. If $u$ and $v$ are strongly cospectral, we show that they are nonadjacent and that $n-k-1=1$. Let $\theta\in\{r,s\}$ have multiplicity $m_\theta$. The idempotent $E_\theta$ is a polynomial in $A$, so it lies in the span of $I$, $A$ and $J-I-A$, and its diagonal is constant, equal to $\frac{m_\theta}{n}$. The relations $AE_\theta=\theta E_\theta$ and $E_\theta\mathbf{1}=0$ give

For $\theta=k$ both entries equal $\frac{1}{n}$. By Theorem 5.1, $u$ and $v$ are strongly cospectral exactly when the second factor has absolute value one for $\theta=r$ and for $\theta=s$.

If $u\sim v$, then $|r|=|s|=k$. Since $r\ne s$, one of them equals $k$, which is impossible because $k$ is a simple eigenvalue. The adjacent-vertex argument is also in [13].

If $u\not\sim v$, then $|1+r|=|1+s|=n-k-1$, and $r>s$ forces $1+r=n-k-1$ and $1+s=-(n-k-1)$. Hence $\lambda-\mu=r+s=-2$ and $\mu-k=rs=1-(n-k-1)^2$, so $k-\lambda-1=(n-k-1)^2$. The identity $k(k-\lambda-1)=\mu(n-k-1)$ [17 Chapter 10] becomes $k(n-k-1)^2=(k+1-(n-k-1)^2)(n-k-1)$, that is $((n-k-1)-1)(k+(n-k-1)+1)=0$. Thus $n-k-1=1$. Every vertex has exactly one non-neighbor, so $G$ is a cocktail party graph and $\{u,v\}$ is one of its parts. Conversely, a cocktail party graph has $n-k-1=1$, $r=0$ and $s=-2$, and then $|1+r|=|1+s|=1$.

Acknowledgments

Acknowledgments. Theorem 4.1 grew out of the author’s poster On a new type of quantum random weighted graphs, presented at the poster session of the 80th Anniversary Meeting of the Korean Mathematical Society in Seoul in June 2026. The poster stated the inequality (4.1) and asked whether equality holds only for $P_3$ once the trivial case $P_2$ is excluded. Theorem 4.1 answers that question.

During the preparation of this paper the author became aware of the machine checked proof [23], posted on 1 October 2026. The results of this paper were obtained independently. The overlap is described after Lemma 3.1.

Disclosure statement

Disclosure statement. The author does not have any conflicts of interest.

Data availability

Data availability. The exhaustive computation reported in Remark 4.8 examined all graphs with three to seven vertices in exact rational arithmetic. The value in Remark 4.6 was also computed exactly. These computations describe the scope of the results, and no proof depends on them.