$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?

  • 2
    $\begingroup$ Are all entries integers? $\endgroup$ – Angina Seng May 3 '18 at 6:23
  • $\begingroup$ Yes...All integer entries $\endgroup$ – QED May 3 '18 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.

  • $\begingroup$ I think that it suffices to assume that a solution mod $p$ exists for infinitely many primes $p$. $\endgroup$ – Jyrki Lahtonen May 3 '18 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).

  • $\begingroup$ I was actually asking whether non singularity in $F_p$ guarantee non singularity in $\Bbb{R}$ $\endgroup$ – QED May 3 '18 at 7:32
  • $\begingroup$ @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! $\endgroup$ – Jyrki Lahtonen May 3 '18 at 9:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson May 3 '18 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.