The column number for 3-modular matrices
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918142454792192 |
|---|---|
| author | Paat, Joseph Walsh, Zach Xu, Luze |
| author_facet | Paat, Joseph Walsh, Zach Xu, Luze |
| contents | An integer-valued matrix $\mathbf{A}$ is $Δ$-modular if each $\text{rank}(\mathbf{A}) \times \text{rank}(\mathbf{A})$ submatrix has determinant at most $Δ$ in absolute value. The column number problem is to determine the maximum number of pairwise non-parallel columns of a rank-$r$, $Δ$-modular matrix. Exact values for the column number are only known for $r \le 2$ or $Δ\le 2$. We prove that if $r$ is sufficiently large, then the maximum number of pairwise non-parallel columns of a rank-$r$, $3$-modular matrix is $\binom{r+1}{2} + 2(r-1)$. This settles a conjecture by Lee, Paat, Stallknecht, and Xu on the column number in the case $Δ= 3$. We complement this main result by showing that there are at least three $3$-modular matrices with pairwise non-isomorphic vector matroids that attain this upper bound. More generally, we show that if $r > Δ$, then the number of $Δ$-modular matrices with $\binom{r+1}{2} + (Δ-1)(r-1)$ pairwise non-parallel columns and pairwise non-isomorphic vector matroids is at least exponential in $\sqrtΔ$; previously only one matrix was known due to Lee et al. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_13463 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The column number for 3-modular matrices Paat, Joseph Walsh, Zach Xu, Luze Combinatorics Optimization and Control 05B35, 90C10 An integer-valued matrix $\mathbf{A}$ is $Δ$-modular if each $\text{rank}(\mathbf{A}) \times \text{rank}(\mathbf{A})$ submatrix has determinant at most $Δ$ in absolute value. The column number problem is to determine the maximum number of pairwise non-parallel columns of a rank-$r$, $Δ$-modular matrix. Exact values for the column number are only known for $r \le 2$ or $Δ\le 2$. We prove that if $r$ is sufficiently large, then the maximum number of pairwise non-parallel columns of a rank-$r$, $3$-modular matrix is $\binom{r+1}{2} + 2(r-1)$. This settles a conjecture by Lee, Paat, Stallknecht, and Xu on the column number in the case $Δ= 3$. We complement this main result by showing that there are at least three $3$-modular matrices with pairwise non-isomorphic vector matroids that attain this upper bound. More generally, we show that if $r > Δ$, then the number of $Δ$-modular matrices with $\binom{r+1}{2} + (Δ-1)(r-1)$ pairwise non-parallel columns and pairwise non-isomorphic vector matroids is at least exponential in $\sqrtΔ$; previously only one matrix was known due to Lee et al. |
| title | The column number for 3-modular matrices |
| topic | Combinatorics Optimization and Control 05B35, 90C10 |
| url | https://arxiv.org/abs/2509.13463 |