Eigenvalues of special matrices follow semicircle law accurately
Comment on "Symmetric Pseudo-Random Matrices"
Information Theory
Summary
Some researchers previously claimed that certain large symmetrical matrices built from special binary sequences behave in a predictable way when looking at their eigenvalues. This paper points out flaws in their proof and provides a clearer and more reliable understanding by connecting these eigenvalues to well-studied mathematical sums. Using known results from number theory, the authors show that the eigenvalues of these matrices follow a specific pattern called the semicircle distribution without relying on probabilistic arguments.
What this means in practice
- •For signal processing engineers: Analyze spectral properties of matrices similar to those used in pseudo-random sequence generation for secure communication design.
- •For cryptography developers: Use the clarified spectral behavior of these matrices to evaluate and improve cryptographic constructions based on Golomb sequences.
A theory result. No direct application yet.
Authors
Chin Hei Chan
Abstract
In 2018, Soloveychik, Xiang and Tarokh considered a pseudo-random symmetric circulant matrix constructed from binary Golomb sequences of length $n=2^m-1$, and claimed a proof that its empirical spectral distribution converges almost surely to the semicircle law as $n$ grows to infinity by the method of moments. In this comment note we show that their argument contains several technical flaws and inappropriate applications of technical lemmas. Instead we demonstrate that the eigenvalues of the matrix are simply a normalized twisted Kloosterman sum varying over the multiplicative character, to which we apply Katz's result directly to establish the asymptotically semicircle spectral distribution deterministically.