On the number of Hadamard matrices via anti-concentration
Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations Ax=b , where the coordinates of the vector x are restricted to take values in some small subset (e.g. {±1} ) of the underlying field. The classical ways of...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press (CUP)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/145894 |
| _version_ | 1826213786961313792 |
|---|---|
| author | Ferber, Asaf Jain, Vishesh Zhao, Yufei |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Ferber, Asaf Jain, Vishesh Zhao, Yufei |
| author_sort | Ferber, Asaf |
| collection | MIT |
| description | Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations Ax=b , where the coordinates of the vector x are restricted to take values in some small subset (e.g. {±1} ) of the underlying field. The classical ways of bounding this quantity are to use either a rank bound observation due to Odlyzko or a vector anti-concentration inequality due to Halász. The former gives a stronger conclusion except when the number of equations is significantly smaller than the number of variables; even in such situations, the hypotheses of Halász’s inequality are quite hard to verify in practice. In this paper, using a novel approach to the anti-concentration problem for vector sums, we obtain new Halász-type inequalities that beat the Odlyzko bound even in settings where the number of equations is comparable to the number of variables. In addition to being stronger, our inequalities have hypotheses that are considerably easier to verify. We present two applications of our inequalities to combinatorial (random) matrix theory: (i) we obtain the first non-trivial upper bound on the number of n×n Hadamard matrices and (ii) we improve a recent bound of Deneanu and Vu on the probability of normality of a random {±1} matrix. |
| first_indexed | 2024-09-23T15:54:49Z |
| format | Article |
| id | mit-1721.1/145894 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:54:49Z |
| publishDate | 2022 |
| publisher | Cambridge University Press (CUP) |
| record_format | dspace |
| spelling | mit-1721.1/1458942022-10-19T03:04:19Z On the number of Hadamard matrices via anti-concentration Ferber, Asaf Jain, Vishesh Zhao, Yufei Massachusetts Institute of Technology. Department of Mathematics Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations Ax=b , where the coordinates of the vector x are restricted to take values in some small subset (e.g. {±1} ) of the underlying field. The classical ways of bounding this quantity are to use either a rank bound observation due to Odlyzko or a vector anti-concentration inequality due to Halász. The former gives a stronger conclusion except when the number of equations is significantly smaller than the number of variables; even in such situations, the hypotheses of Halász’s inequality are quite hard to verify in practice. In this paper, using a novel approach to the anti-concentration problem for vector sums, we obtain new Halász-type inequalities that beat the Odlyzko bound even in settings where the number of equations is comparable to the number of variables. In addition to being stronger, our inequalities have hypotheses that are considerably easier to verify. We present two applications of our inequalities to combinatorial (random) matrix theory: (i) we obtain the first non-trivial upper bound on the number of n×n Hadamard matrices and (ii) we improve a recent bound of Deneanu and Vu on the probability of normality of a random {±1} matrix. 2022-10-18T17:14:04Z 2022-10-18T17:14:04Z 2022 2022-10-18T17:09:05Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/145894 Ferber, Asaf, Jain, Vishesh and Zhao, Yufei. 2022. "On the number of Hadamard matrices via anti-concentration." Combinatorics Probability and Computing, 31 (3). en 10.1017/S0963548321000377 Combinatorics Probability and Computing Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf Cambridge University Press (CUP) Cambridge University Press |
| spellingShingle | Ferber, Asaf Jain, Vishesh Zhao, Yufei On the number of Hadamard matrices via anti-concentration |
| title | On the number of Hadamard matrices via anti-concentration |
| title_full | On the number of Hadamard matrices via anti-concentration |
| title_fullStr | On the number of Hadamard matrices via anti-concentration |
| title_full_unstemmed | On the number of Hadamard matrices via anti-concentration |
| title_short | On the number of Hadamard matrices via anti-concentration |
| title_sort | on the number of hadamard matrices via anti concentration |
| url | https://hdl.handle.net/1721.1/145894 |
| work_keys_str_mv | AT ferberasaf onthenumberofhadamardmatricesviaanticoncentration AT jainvishesh onthenumberofhadamardmatricesviaanticoncentration AT zhaoyufei onthenumberofhadamardmatricesviaanticoncentration |