PreprintarXiv licencearXiv
The smallest singular value of products of random combinatorial and deterministic matrices
Abstract
Let p∈(0,1/2] be fixed, and let d,n be positive integers satisfying d=pn. Let Qn be an n× n random combinatorial matrix whose rows are independent and uniformly distributed over the vectors in {0,1}n having exactly d ones. For an arbitrary deterministic invertible n× n matrix M, we establish two-sided bounds for the smallest singular value of QnM. More precisely, for every ε∈(0,1), ℙ ( ε≤ sn(QnM)· |M−1|HS ≤ ε−2 ) ≥ 1−C( ε+d−1/2+e−c sr(M−1) )−2e−cn, where positive constants $C, c$ depend only on p and sr denotes the stable rank. Consequently, for any sequence of deterministic invertible matrices M satisfying sr(M−1)→∞, sn(QnM) is typically of order |M−1|HS−1. In particular, taking M=In recovers the known n−1/2 scale for sn(Qn).
Related
- An upper bound on the smallest singular value of dense signed random combinatorial matrices
- Smallest Singular Value Estimates for Nonuniform Fourier Matrices via Periodic Nonuniform Sampling
- Asymptotic expansion of smooth functions in deterministic and iid Haar unitary matrices, and application to tensor products of matrices
- Least singular values of Gaussian matrices with deterministic shifts
- A Combinatorial Proof of an Identity of Malik and Sarma on Overpartitions with Repeated Smallest Non-Overlined Part
BibTeX
@misc{shi2026smallest,
title = {{The smallest singular value of products of random combinatorial and deterministic matrices}},
author = {Yuxiao Shi and Kexin Yu and Tingzhou Yu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38588},
eprint = {2610.38588},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38588},
}
RIS
TY - UNPB
TI - The smallest singular value of products of random combinatorial and deterministic matrices
AU - Yuxiao Shi
AU - Kexin Yu
AU - Tingzhou Yu
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38588
UR - https://arxiv.org/abs/2610.38588
AB - Let p∈(0,1/2] be fixed, and let d,n be positive integers satisfying d=pn. Let Q_n be an n× n random combinatorial matrix whose rows are independent and uniformly distributed over the vectors in {0,1}^n having exactly d ones. For an arbitrary deterministic invertible n× n matrix M, we establish two-sided bounds for the smallest singular value of Q_nM. More precisely, for every ε∈(0,1), ℙ ( ε≤ s_n(Q_nM)· |M^−1|_HS ≤ ε^−2 ) ≥ 1−C( ε+d^−1/2+e^−c sr(M^−1) )−2e^−cn, where positive constants $C, c$ depend only on p and sr denotes the stable rank. Consequently, for any sequence of deterministic invertible matrices M satisfying sr(M^−1)→∞, s_n(Q_nM) is typically of order |M^−1|_HS^−1. In particular, taking M=I_n recovers the known n^−1/2 scale for s_n(Q_n).
ER -