The Setting
Reduce the entries of an integer matrix modulo a prime and its rank can fall: the matrix with rows and has rank over the reals, while modulo its two rows coincide and its rank is . The question is how far the rank can fall when every row is short, in the sense that exceeds the sum of the squares of its entries.
Rows, Ranks and Reduction
Let and be finite sets. An integer matrix indexed by is a family of integers , one for each and , with rows indexed by and columns by ; it is square when , and an matrix when . Real matrices are indexed in the same way.
For a real number , a real or integer matrix indexed by has rows of squared norm at most when (1)
For a prime , the reduction of an integer matrix modulo is the matrix over the field , indexed by , whose entry at is the residue class of modulo . The real rank is the rank of as a matrix over , and is the rank of over . A square matrix is nonsingular when its determinant is not zero.
The Claim
Theorem 1. (a) Let be an integer matrix indexed by , for finite sets and , whose rows have squared norm at most a real number , and let be a prime. Then (2)✦
(b) Let be a nonsingular integer matrix whose rows have squared norm at most a real number , and let be a prime. Then (3)✦
(c) (Hadamard’s inequality.) Let be a real matrix whose rows have squared norm at most a real number . Then (4)✦
(d) Let be a square integer matrix indexed by , for a finite set , and let be a prime. Then (5)✦
In the paper, the result reads: for an integer matrix whose rows have Euclidean norm at most , where , and for every prime , .
What Is Checked
The claim is stated over matrices indexed by finite sets, integer in (2), (3) and (5) and real in (4): the squared norms of their rows as in (1), the real rank, the rank over of the reduction modulo a prime , and the determinant of a square matrix.