# rank of integer matrix reduced $\bmod p$ is at most that of the original matrix.

I am using a result in a problem but I am not sure how to write or support it correctly.

We have an integer matrix $$A$$ over the reals.

We can define a matrix $$A'$$ over $$\mathbb F_p$$ by just taking each entry $$\bmod p$$.

I want to say that the rank of $$A'$$ is less than or equal to the rank of $$A$$.

How do I justify this?

I am guessing the proof first tells us if there is a linear combination for $$0$$ in $$\mathbb R$$ for the rows of $$A$$ then that linear combination must also exist in $$\mathbb Q$$, and then we can probably multiply everything by the lcm of the denominators so our coefficients are in $$\mathbb Z$$.

So I guess what we can do is show that if a set of integer vectors not independant over $$\mathbb R$$ then they are not independent when reduced $$\bmod p$$ in $$\mathbb F_p$$. I think that constitutes a proof.

Does anyone have a reference of this result or thoughts on the proof? (I'm guessing something similar may also exist talking about some algebraic setting instead of specific fields and rings).

Many thanks and best regards.

• Yes. Clearly you can restrict yourself to combinations over $\mathbb{Q}$. Linear combinations can be expressed as multiplication on the left by a triangular matrix. Multiply every row by the lcm of its denominators and you get an integer matrix. May 19, 2021 at 19:51
• you already have all the ingredients. independent in $\mathbb F_p$ means independent over the reals, so get a set of #rank_in_p vectors that do not go to zero mod $p$, and the same will be independent and not go to zero on the reals. May 19, 2021 at 19:53
• Oh ok great, well I guess I can use this question as reference if no one finds a more "legit" source. I think this trick can sometimes be used to bound the rank of some matrices, where reducing $\bmod p$ gives nice matrices. May 19, 2021 at 19:55
• my suggestion would be to work this: math.stackexchange.com/questions/3777401/… backwards, noting that if $\phi$ is the ring homomophism $\mathbb Z\to \mathbb Z_p$ that is applied component-wise to a matrix (and technically we identify $1\times 1$ matrices to be equal to scalars) then $\phi\Big(\det\big(B\big)\Big) = \det\Big(\phi\big(B\big)\Big)$. Since determinants (and minors) are polynomials in the entries of a matrix they work very nicely with ring homomorphisms. May 19, 2021 at 21:12
• Oh, I think that makes a lot of sense ! The rank is the size of the largest non-zero minor right? Yeah that does the trick really well. May 19, 2021 at 21:25

The main ideas is to use the fact that a matrix has rank $$r$$ iff it has some $$r\times r$$ submatrix with nonzero determinant and for $$m\gt r$$ all $$m\times m$$ minors are zero.

Since $$A$$ is integer valued we can consider it as living in $$\mathbb Z^{n\times n}$$
(taken to be an abelian group )

Now consider the ring homomorphism $$\phi: \mathbb Z\longrightarrow \mathbb F_p$$
and the map $$\Phi:\mathbb Z^{n\times n}\longrightarrow \mathbb F_p^{n\times n}$$ which applies $$\phi$$ component-wise.

$$\det\big(B\big)= \sum_\sigma\text{sign}(\sigma) b_{1,\sigma(1)}...b_{n,\sigma(n)}\implies \det\Big(\Phi\big(B\big)\Big)=\phi\Big(\det\big(B\big)\Big)$$

So consider any $$m\times m$$ minor of $$A$$. Then in $$\mathbb F_p$$
$$\det\Big(\Phi\big(A_{m\times m}\big)\Big)=\phi\Big(\det\big(A_{m\times m}\big)\Big)=\phi\Big(0\Big)=0$$
$$\implies \text{rank}\Big(\Phi\big(A\big)\Big)\leq r =\text{rank}\Big(A\Big)$$

alternative proof:
using a bit more machinery: consider the Smith Normal Form $$A=Q^{-1}A'P$$ where all matrices are integer valued, $$A'$$ is diagonal and $$Q^{-1}$$ and $$P$$ each have determinants $$\in \big\{-1,+1\big\}$$.

Then $$\text{rank}\Big(A\Big)=\text{rank}\Big(A'\Big)$$ which is given by the number of non-zero components of $$A'$$. And $$\text{rank}\Big(\Phi\big(A\big)\Big)=\text{rank}\Big(\Phi\big(A'\big)\Big)$$ (since the determinants of $$\pm 1$$ are necessarily units modulo p). Because $$A'$$ is diagonal you need only check $$\phi\big(a'_{k,k}\big)$$ for $$1\leq k \leq n$$ and since $$\phi$$ maps zero to zero, the number of non-zero diagonal components on $$A'$$ -- i.e. its rank-- cannot increase under $$\Phi$$.

A few thoughts:

1. I would restrict the focus to either $$\mathbb{Q}^{n}$$ to start with. There is no need to consider linear combinations in $$\mathbb{R}^{n}$$, since $$\mathbb{Q}$$ is a perfectly valid field on its own.
2. I believe your proof is on the right track, but I would recommend writing out more of the details to be sure it works. One thing that might go wrong is that if you exhibit a nontrivial linear combination $$\sum a_{i} v_{i} = 0$$ over $$\mathbb{Z}^{n}$$ to show that the $$v_{i}$$ are dependent, then when passing to $$\mathbb{Z}_{p}$$ the $$a_{i}$$ could all become zero if they are divisible by $$p$$. That particular issue can be handled by dividing out the $$a_{i}$$ by their gcd, however.
3. Another approach to the proof would be to use an alternate definition the of rank, such as the rank being $$k$$ if the matrix is the sum of $$k$$ rank 1 matrices. That particular definition may not generalize well, however, but there are a few to choose from.
• Restricting to $\mathbb{Q}$ uses the fact that the ranks over $\mathbb{Q}$ and $\mathbb{R}$ are the same, a result in itself. But the gcd thing is very neat. May 19, 2021 at 23:59