On the Group Randomness of 0-1 Real Sequences from Binary Linear Codes

Jul 16, 2026

Upload by Ezra

The paper investigates group randomness for 0-1 real sequences constructed from binary linear codes by analyzing the spectral behavior of a normalized Gram matrix. A p×n random matrix is formed whose rows are drawn uniformly from the associated 0-1 real sequences, with y=p/n fixed in (0,1). As n→∞, the empirical spectral distribution converges to the Marchenko–Pastur law with high probability at least at rate n^-1/4. Under dual distance d⊥≥5, the largest eigenvalue fluctuates asymptotically Gaussian with mean p+1+y and variance 4y.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages34

Reading Time1 h 26 min

Introduction

Group randomness and motivation

Code-based random matrix models

Notation and the ±1 matrix benchmark

arXiv :2607 .05418v1 [math .PR] 26 Jun 2026 On the Group Randomness of 0-1 Real Sequences from Binary Linear Codes Chin Hei Chan Hetao Institute of Mathematics and Interdisciplinary Sciences, Shenzhen, Guangdong, 518000, China [chenzhanxi@himis-sz.cn](chenzhanxi@himis-sz.cn) Abstract In this paper, we study the group randomness of 0-1 real sequences derived from a binary linear code by investigating the spectral behaviour of a suitable normalization of the Gram matrix of a p × n random matrix whose rows are uniformly drawn from those 0-1 real sequences, where y = p/n ∈ (0 , 1) is fixed. We show that as n → ∞ , its empirical spectral distribution converges to the Marchenko-Pastur law at a rate at least of the order n −1/4 with high probability, and the fluctuation of its largest eigenvalue is asymptotically Gaussian with mean p + 1 + y and variance 4y, provided that the dual distance of the code is at least 5 . Index terms—Group randomness, binary linear codes, random matrix theory, empirical spectral distribution, largest eigenvalue, Marchenko-Pastur law, Gaussian distribution. 1 Introduction Group randomness is the term to describe joint randomness of a given class of real or complex sequences. This means that random matrices constructed from these sequences resemble properties satisfied by truly random matrices, that is, matrices whose entries are independently and identically distributed (i.i.d.) . These matrices play a central role in signal processing applications such as compressed sensing [11] . Group randomness was introduced by Babadi and Tarokh in [2, 1], who considered a Gram matrix constructed by picking at random ±1 real sequences derived from binary linear codes. They observed through simulation experiments that the empirical spectral distributions (ESDs) of the Gram matrices based on BCH codes and Gold sequences converge to the Marchenko-Pastur (MP) law as the length increases to infinity, a phenomenon satisfied by truly random sample covariance matrices, while that from pseudo-noise (PN) sequences does not. Xia and Xiong [27] confirmed this by showing that such behaviour holds as long as the minimum Hamming distance of the dual code is at least 5, which is achieved by the Gold codes exactly. Later in [13], the authors proceeded to prove that the convergence rate is at least of the order n −1/4 where n is the code length. In a more recent paper [15], the authors proved a more advanced group randomness property, that the central limit theorem holds for linear spectral statistics of monomials on the same random matrix over binary linear codes with dual distance at least 7 . In this paper we study the group randomness of 0-1 real sequences derived from binary linear codes. While this construction looks simpler and more intuitive, the entries of the matrix whose rows are randomly chosen from these 0-1 sequences are non-central, unlike the previous construction. Nevertheless, we show that as long as the dual distance of the code is at least 5, the Gram matrix of our code matrix resembles the spectral behaviour of the non-central Gaussian sample covariance matrix [16] both globally and locally. That is, its ESD converges to the MP law with high probability at a rate at least of the order n−1/4, and also that it has a dimension-growing largest eigenvalue with asymptotically Gaussian fluctuation as n → ∞ . The former is essentially the same as the ±1-based matrix model. However, the latter introduces a novel group randomness phenomenon for pseudo-random sequences in terms of a single eigenvalue. Before stating explicitly and further comparing the results on the two different codebased random matrices, we introduce some notation. Let C be a binary linear code of length n. Its dual code C ⊥ consists of codewords which are orthogonal to all codewords of C under the usual inner product defined in Fn2 . C ⊥ is also a binary linear code of length n. The dual distance d⊥ of the original code Cis t

FAQs

What does “group randomness” mean in this paper?

It refers to joint randomness of a class of real or complex sequences, producing random matrices with spectral properties similar to those from truly i.i.d. random matrices.

How is the random matrix and Gram matrix constructed for the 0-1 model?

A p×n matrix is built with rows drawn uniformly and independently from 0-1 real sequences derived from a binary linear code, and the Gram matrix is formed from this matrix (with a normalization).

What conditions on the code ensure Marchenko–Pastur convergence and Gaussian fluctuations?

For convergence of the empirical spectral distribution to the Marchenko–Pastur law with high probability, the dual distance is required to be at least 5. The largest eigenvalue then has asymptotically Gaussian fluctuations with mean p+1+y and variance 4y.

Jul 16, 2026

Upload by Ezra