Abstract
We show that the family of pseudo-random matrices recently discovered by Soloveychik, Xiang, and Tarokh in their work Symmetric Pseudo-Random Matrices exhibits asymptotic freeness properties. More specifically, any two sequences of matrices of matching sizes from that construction generated using sequences of different non-reciprocal primitive polynomials are asymptotically free.
Introduction
In modern engineering applications—ranging from radar and cryptography to wireless communications like CDMA—there is a persistent need for matrices that exhibit the statistical properties of true randomness. Random matrices, such as those from Wigner ensembles, possess elegant mathematical features like the semicircular law of eigenvalues. However, true randomness is computationally expensive to generate, difficult to reproduce without massive storage, and prone to "atypical" fluctuations that can destabilize a system.
While previous research established deterministic "pseudo-random" matrices that mimic the spectral distribution of random matrices, a critical gap remained: Free Probability Theory (FPT). FPT describes how multiple matrices interact; when two random matrices are independent in a non-commutative sense, they are termed "free." This paper bridges that gap by proving that deterministic pseudo-random matrices can indeed achieve asymptotic freeness, allowing them to replace truly random sources in complex multi-component systems.
The Construction: Golomb Sequences and Non-Reciprocity
The authors utilize a construction based on Golomb sequences (maximal length sequences or m-sequences). The process involves:
- Polynomial Selection: Choosing a binary primitive polynomial $f(x)$ of degree $m$.
- Sequence Generation: Using a linear feedback shift register to produce a pseudo-random binary sequence of length $n = 2^m - 1$.
- Matrix Assembly: Populating a circulant-like symmetric sign matrix with entries of $\pm 1$ derived from the sequence.
A pivotal discovery in this work is the role of non-reciprocity. For two sequences to exhibit freeness, their generating polynomials must not be reciprocals of one another. If a polynomial and its reciprocal are used, the resulting matrices share too much underlying algebraic structure to be considered independent.
Numerical Validation and Results
The core theoretical contribution is a proof using the method of moments, showing that the "mixed centered moments" of two such matrices vanish as the matrix size $n$ approaches infinity. This is the fundamental requirement for asymptotic freeness.
To validate these theoretical findings, the authors conducted numerical experiments with matrix sizes ranging from $n = 127$ to $n = 524,287$. As shown in the figure below, the first mixed moment ($\mu$) decays consistently as $n$ increases. Furthermore, the decay of the standard deviation suggests that freeness is not just an average property but holds for almost any individual pair of large matrices (almost sure convergence).
Insights and Future Directions
This research demonstrates that "statistical independence" can emerge from entirely deterministic processes through careful algebraic selection. Because these matrices are based on shift registers and circulant structures, they are significantly more efficient to compute than generating $n^2$ random bits.
Future work may focus on:
- Convergence Rates: Determining the specific "speed limit" at which these moments reach zero compared to standard random ensembles.
- Broader Constructions: Investigating whether these properties extend to other pseudo-random arrays, such as cyclic codes or perfect maps.
- Quantifying Reciprocity: Measuring exactly how much freeness is compromised when reciprocal polynomials are utilized.
Summary updated