Dimension-dependent bounds for the SDIEP via phase optimisation and Paley-type constructions

Abstract

We refine the cycle-walk (Fourier) template of Gnacik and the author to quantify when a~$\delta$-Sule\uımanova spectrum $(1,{\lambda }_2,\dots ,{\lambda }_n)$ (with ${\lambda }_j\le 0$) is realised by a symmetric doubly stochastic matrix. For the canonical cycle basis we compute the \emph{exact} size-dependent threshold \[ δ_n \;=\; 1-\frac{1}{2\cos^2\!\Big(\fracπ{4n}ρ(n)\Big)}, \quad ρ(n)\in\{0,1,2,4\}\ \text{determined by } n\bmod 8, \] which improves $1/2$ if and only if $8\nmid n$; we also prove sharpness for that template. We then introduce an \emph{optimally phase-aligned} cycle basis which removes the `$8\mid n$' artefact and yields better sufficient bound \[ δ_n^{\rm (ph)} \;=\; \begin{cases} \displaystyle 1-\dfrac{1}{2\cos^2(π/n)}, & n\equiv 0\pmod{4},\\[2mm] \displaystyle 1-\dfrac{1}{2\cos^2(π/2n)}, & n\equiv 2\pmod{4},\\[2mm] \displaystyle 1-\dfrac{1}{2\cos^2(π/4n)}, & n\ \text{odd}, \end{cases} \] so that ${\delta }_n^{(\mathrm{ph})}<\frac{1}{2}$ for \emph{every} $n\ge 3$ and ${\delta }_n^{(\mathrm{ph})}={\delta }_n$ unless $8\mid n$. Next, on abelian $2$-groups, the Walsh--Hadamard basis has coherence $M=1$ and hence suffices for \emph{all} Sule\uımanova lists ($\delta =0$); the same conclusion holds in every Hadamard order (\emph{e.g.}, Paley families).

arXiv comment14 pp