Extremal Collections of k-Uniform Vectors

2018/01/29 by Joseph Briggs, Briggs, Joseph, Wesley Pegden +1
Mathematics · #05B35 #05C35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05B35 #msc:05C35

paper · pdf · doi:10.48550/arxiv.1801.09609

14 pages, major corrections to Theorem 1.6 and Corollary 3.7

arxiv created 2019/03/23 · arxiv updated 2019/03/26

Abstract

We show any matrix of rank r over \mathbbF_q can have ≤ \binomrk(q-1)^k distinct columns of weight k if k ≤ O_q(√(log r)) (up to divisibility issues), and ≤ \binomrk(q-1)^r-k distinct columns of co-weight k if k ≤ O_q(r^2/3). This shows the natural examples consisting of only r rows are optimal for both, and the proofs will recover some form of uniqueness of these examples in all cases.

Related

• Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness
• Ranks of matrices with few distinct entries
• Partitions of Matrix Spaces With an Application to q-Rook Polynomials
• On the Binary and Boolean Rank of Regular Matrices
• Matrix discrepancy and the log-rank conjecture