2025/09/16 by Joseph Paat, Zach Walsh, Paat, Joseph +3
Computer Science · Mathematics · #05B35 #90C10 #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #Optimization and Control (math.OC) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2509.13463
openalex publication_date 2025/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An integer-valued matrix A is Δ-modular if each rank(A) × rank(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 ≤ 2 or Δ≤ 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 \binomr+12 + 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 \binomr+12 + (Δ-1)(r-1) pairwise non-parallel columns and pairwise non-isomorphic vector matroids is at least exponential in √Δ; previously only one matrix was known due to Lee et al.