On sparse random combinatorial matrices. (English) Zbl 1495.60005
Summary: Let \(Q_{n, d}\) denote the random combinatorial matrix whose rows are independent of one another and such that each row is sampled uniformly at random from the subset of vectors in \(\{0, 1 \}^n\) having precisely \(d\) entries equal to 1. We present a short proof of the fact that \(\mathbb{P} [ \det (Q_{n, d}) = 0 ] = O (\frac{n^{1 / 2} \log^{3 / 2} n}{d}) = o(1)\), whenever \(\omega(n^{1 / 2} \log^{3 / 2} n) = d \leq n / 2\). In particular, our proof accommodates sparse random combinatorial matrices in the sense that \(d = o(n)\) is allowed.
We also consider the singularity of deterministic integer matrices \(A\) randomly perturbed by a sparse combinatorial matrix. In particular, we prove that \(\mathbb{P} [ \det (A + Q_{n, d}) = 0 ] = O (\frac{n^{1 / 2} \log^{3 / 2} n}{d})\), again, whenever \(\omega(n^{1 / 2} \log^{3 / 2} n) = d \leq n / 2\) and \(A\) has the property that \((\mathbf{1}, - d)\) is not an eigenpair of \(A\).
We also consider the singularity of deterministic integer matrices \(A\) randomly perturbed by a sparse combinatorial matrix. In particular, we prove that \(\mathbb{P} [ \det (A + Q_{n, d}) = 0 ] = O (\frac{n^{1 / 2} \log^{3 / 2} n}{d})\), again, whenever \(\omega(n^{1 / 2} \log^{3 / 2} n) = d \leq n / 2\) and \(A\) has the property that \((\mathbf{1}, - d)\) is not an eigenpair of \(A\).
MSC:
| 60C05 | Combinatorial probability |
| 60B20 | Random matrices (probabilistic aspects) |
| 15B52 | Random matrices (algebraic aspects) |
References:
| [1] | Allen, P.; Böttcher, J.; Hàn, H.; Kohayakawa, Y.; Person, Y., Blow-up lemmas for sparse graphs (2016) |
| [2] | Cook, N. A., On the singularity of adjacency matrices for random regular digraphs, Probab. Theory Relat. Fields, 167, 1-2, 143-200 (2017), MR3602844 · Zbl 1365.05260 |
| [3] | Ferber, A., Singularity of random symmetric matrices—simple proof, C. R. Math. Acad. Sci. Paris, 359, 743-747 (2021) · Zbl 1472.15043 |
| [4] | Ferber, A.; Jain, V.; Luh, K.; Samotij, W., On the counting problem in inverse Littlewood-Offord theory, J. Lond. Math. Soc. (2), 103, 4, 1333-1362 (2021) · Zbl 1470.60012 |
| [5] | Ferber, A.; Kwan, M.; Sauermann, L., Singularity of sparse random matrices: simple proofs, Comb. Probab. Comput., 31, 1, 21-28 (2022) · Zbl 1511.15029 |
| [6] | Halász, G., Estimates for the concentration function of combinatorial number theory and probability, Period. Math. Hung., 8, 3-4, 197-211 (1977) · Zbl 0336.10050 |
| [7] | Han, H., Singularity of Bernoulli matrices in the sparse regime \(p n = o(\log(n)) (2020)\), arXiv preprint |
| [8] | Jain, V., Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices, Isr. J. Math., 242, 1, 461-500 (2021), MR4282089 · Zbl 1469.15036 |
| [9] | Jain, V., Quantitative invertibility of random matrices: a combinatorial perspective, Discrete Anal., Article 10 pp. (2021), MR4308023 · Zbl 1476.15055 |
| [10] | Jain, V.; Sah, A.; Sawhney, M., Singularity of discrete random matrices, Geom. Funct. Anal., 31, 5, 1160-1218 (2021) · Zbl 1491.15040 |
| [11] | Jain, V.; Sah, A.; Sawhney, M., On the smoothed analysis of the smallest singular value with discrete noise, Bull. Lond. Math. Soc., 54, 2, 369-388 (2022) · Zbl 1540.15035 |
| [12] | Litvak, A. E.; Lytova, A.; Tikhomirov, K.; Tomczak-Jaegermann, N.; Youssef, P., Adjacency matrices of random digraphs: singularity and anti-concentration, J. Math. Anal. Appl., 445, 2, 1447-1491 (2017) · Zbl 1344.05126 |
| [13] | Litvak, A. E.; Tikhomirov, K. E., Singularity of sparse Bernoulli matrices (2020), arXiv preprint |
| [14] | Livshyts, G. V.; Tikhomirov, K.; Vershynin, R., The smallest singular value of inhomogeneous square random matrices, Ann. Probab., 49, 3, 1286-1309 (2021) · Zbl 1467.60010 |
| [15] | Nguyen, H., On the singularity of random combinatorial matrices, SIAM J. Discrete Math., 27, 1, 447-458 (2013) · Zbl 1314.60029 |
| [16] | Sankar, A.; Spielman, D. A.; Teng, S., Smoothed analysis of the condition numbers and growth factors of matrices, SIAM J. Matrix Anal. Appl., 28, 2, 446-476 (2006) · Zbl 1179.65033 |
| [17] | Tao, T.; Vu, V., Random matrices: the circular law, Commun. Contemp. Math., 10, 2, 261-307 (2008) · Zbl 1156.15010 |
| [18] | Tao, T.; Vu, V., Smooth analysis of the condition number and the least singular value, Math. Comput., 79, 272, 2333-2352 (2010) · Zbl 1253.65067 |
| [19] | Tran, T., The smallest singular value of random combinatorial matrices (2020), arXiv preprint |
| [20] | Vu, V., Recent progress in combinatorial random matrix theory, Probab. Surv., 18, 179-200 (2021), MR4260513 · Zbl 1531.60012 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
