On Entries of Spectral Decompositions and Applications

Source abstract

The entries of the spectral idempotents of a graph are its local and crossed local multiplicities. This paper uses these classical quantities in three applications. First, in a graph on $n$ vertices without isolated vertices, every local multiplicity is at most $\frac{n-1}{n}$, and every diagonal entry of the Cesaro average mixing matrix is at most $1-\frac{2}{n}+\frac{2}{n^2}$. In both bounds equality holds only for the complete graph. This proves the connected form of the complete graph trace conjecture of Godsil, Guo and Sobchuk together with its equality case, and component and degree refinements follow. The two upper bounds and their attainment by complete graphs also occur in a recent machine checked proof, without a formal characterization of when equality holds. Second, for the line graph of a connected graph $Γ$, the average return probability at a bridge with a bipartite component on one side is at least the reciprocal of the rank of the unsigned incidence matrix. Equality holds exactly for $P_2$ and $P_3$. The proof combines local moments with known inverse-incidence formulas. Finally, the paper gives a short proof of Godsil's entry criterion, which says that vertices $u$ and $v$ are strongly cospectral exactly when $\left|(E_θ)_{uv}\right|=(E_θ)_{uu}$ for every eigenvalue $θ$. The criterion recovers the known classification in connected noncomplete strongly regular graphs, where the strongly cospectral pairs are precisely the two-vertex parts of cocktail party graphs.