# $Ax=b$ has a solution over $\Bbb{F}_p$ for every prime $p~\implies$ existence of real solution??

$A$ be an $m\times n$ matrix and $b$ a $m\times1$ vector, both with integer entries. If $Ax=b$ has a solution over $\Bbb{F}_p$ for every prime $p$, is a real solution guaranteed?

I couldn't think of any easy way to begin this problem. Any hint please.

Bonus question: A matrix with all diagonal elements odd integers and all non diagonal elements even integers, is the identity matrix in $\Bbb{F}_2$. Does that imply it is invertible as a real matrix?

• Are all entries integers? May 3, 2018 at 6:23
• Yes...All integer entries
– QED
May 3, 2018 at 6:26

This is true. There will exist a rational solution.

Let $V\subseteq \Bbb{Q}^m$ be the column space of $A$. If there is no solution $x\in\Bbb{Q}^n$ this means that the column space of the augmented matrix $A'=(A|b)$ has higher dimension than $r=\dim_{\Bbb{Q}}V$. In other words, $A'$ has rank $r+1$ while $A$ has rank $r$ only.

This means that all the size $r+1$ minors of $A$ vanish, but there exists at least one non-vanishing minor $\Delta$ of $A'$ of the same size. Let $p$ be a prime that is not a factor of $\Delta$. If $\overline{A}$ and $\overline{A'}$ are the above matrices reduced modulo $p$ we see that $\overline{A'}$ has a non-vanishing minor $\overline{\Delta}$ of size $r+1$ whereas all the $(r+1)\times (r+1)$ minors of $A$ are equal to zero. This implies that $\overline{b}$ is not in the $\Bbb{F}_p$-span of the columns of $\overline{A}$. Therefore the system won't have a solution modulo $p$ either.

• I think that it suffices to assume that a solution mod $p$ exists for infinitely many primes $p$. May 3, 2018 at 6:50

For the bonus question, the condition implies the determinant is odd, hence not zero, hence the matrix is invertible over the reals (indeed, over the rationals).

• I was actually asking whether non singularity in $F_p$ guarantee non singularity in $\Bbb{R}$
– QED
May 3, 2018 at 7:32
• @AbishankaSaha It may be better to think about it over $\Bbb{Q}$ instead of $\Bbb{R}$. If all the matrix entries are integers then so are the determinants and you can reduce them mod $p$. Any matrix over rationals become an integer matrix if you multiply it with the lcm of the denominators. Over $\Bbb{R}$ those steps are not available. Of course, the invertibility of a matrix over any field is decided by looking at its determinant, so reals vs. rationals - no difference! May 3, 2018 at 9:16
• No, Abishanka, what you were actually asking, in your "bonus question", was whether an integer matrix, congruent modulo 2 to the identity, is invertible over the reals, and that's the question you actually asked that I actually answered. May 3, 2018 at 10:26