Using $\bar{A}$ ($A$ modulo $2$) to prove that $A$ is invertible

Question

Following this website, https://yutsumura.com/how-to-prove-a-matrix-is-nonsingular-in-10-seconds/:

Let $\bar{A}$ be the matrix whose $(i,j)$-entry is the $(i,j)$-entry of $A$ modulo $2$. That is

$\bar{A}=\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Since $\det(A)$ is a polynomial of entries of $A$, we have

$$\det(A)=\det(\bar{A}) (\text{mod} \ 2)= 1$$

I cannot see how we get the equality $\det(A)=\det(\bar{A}) (\text{mod} \ 2)$ just because $\det(A)$ is a polynomial of entries of $A$.

Answer 1

That is because you have a matrix in $\mathcal M_n(\bf Z)$ and the canonical map \begin{align} \pi:\mathbf Z&\longrightarrow \mathbf Z/2\mathbf Z \\ n&\longmapsto n\bmod 2 \end{align} is a ring homomorphism, i.e. it is compatible with addition and multiplication.

Some details:

Let's use the general formula for an $n\times n$ determinant,denoting $\overline x$ the reduction of $x\bmod2$ (or any modulus):

$$\overline{\det(a_{ij})}=\sum_{\sigma\in\mathfrak S_n}\varepsilon(\sigma)\overline{a_{\sigma(1),1} a_{\sigma(2),2}\dotsm a_{\sigma(n),n}}=\sum_{\sigma\in\mathfrak S_n}\varepsilon(\sigma)\overline{a_{\sigma(1),1}}\:\overline{a_{\sigma(2),2}}\dotsm \overline{a_{\sigma(n),n}}=\det(\overline{a_{i,j}}).$$

Answer 2

If $x \equiv y \pmod N$ and if $\{a_i\}_{i=0}^n \subseteq \mathbb Z$, then

$$\sum_{i=0}^n a_i x^i \equiv \sum_{i=0}^n a_i y^i \pmod N$$

An example should help.

Let $A = \left[\begin{array}{c} 11 & 13 \\ 17 & 19\end{array}\right]$.

Then $\det A = 11 \times 19 - 13 \times 17 = -12 \equiv 2 \pmod 7$

Also $\bar A = A \pmod 7 = \left[\begin{array}{c} 4 & 6 \\ 3 & 5 \end{array}\right]$

and $\det \bar A =4 \times 5 - 6 \times 3 \equiv 11 \times 19 - 13 \times 17 \equiv \det A \pmod 7$

Answer 3

For an integer $n$ ($2$ in your case) the application:

$$\begin{array}{l|rcl} \varphi : & \mathbb Z & \longrightarrow & \mathbb Z_n\\ & x & \longmapsto & \overline{x} \end{array}$$

is a ring homomorphism.

Hence for a multivariate polynomial $P(x_1, \dots, x_m)$ you have $\varphi(P) = \overline{P}$ where $\overline{P}$ is the polynomial obtained by taking the modulus of all coefficients.

Now $$\det A = \sum_{\sigma \in \mathcal S_n} (-1)^{\epsilon(\sigma)} a_{1 \sigma(1)} \dots a_{n \sigma(n)}$$ is a multivariate polynomial of the coefficients of $A$. Therefore the conclusion. See Wikipedia - determinant for above formula on the determinant.

Answer 4

If $\,f(x,y)\,$ is a polynomial with integer coefficients then by the polynomial congruence rule

$$\bmod 2\!:\,\ \ f(m,n)\,\equiv\, f(\overbrace{m\bmod 2}^{\large \overline{m}},\, \overbrace{n\bmod 2}^{\large\overline{n}})\qquad $$

So $\,f(m,n) = 0\,\Rightarrow\, f(\bar m,\bar n) \equiv 0\pmod{\!2}\ $ so contra+, $\ f(\bar m,\bar n) \not\equiv 0\pmod{\!2}\,\Rightarrow\, f(m,n)\neq 0$

i.e. any root $\,(m,n)\,$ of $f$ persists as a root $\!\bmod 2.\,$ OP is the special case when $f$ is the determinant function - which is indeed a polynomial function of its entries (with integer coefficients). Concretely

$$d = \left|\begin{array}{}\color{#c00}{11} & \color{#0a0}{22}\\ \color{#0a0}{33} & \color{#c00}{55}\end{array}\right| = \left\{\begin{align}&f(11,22,33,55) = \color{#c00}{11(55)}\!-\!\color{#0a0}{22(33)}\\ \ \equiv\ &f(\ \ 1,\ \ 0,\ \ 1,\ \ 1) \equiv \color{#c00}{\ \ 1(\ \ 1)}-\color{#0a0}{0(\ \ 1)}\equiv 1\!\!\!\pmod{\!2}\end{align}\right.\qquad$$

therefore $\,d\equiv 1\pmod{\!2},\,$ i.e. $\,d\,$ is odd, so $\,d\neq 0.$

Remark $ $ The same works for any modulus $\,m,\,$ e.g. we could use $\,m = 9\,$ ("casting out nines") exactly as above (or more generally as a check of any such polynomial computation), or we could compare unit digits $\bmod m\!=\!10\!:\ \,d\equiv \color{#c00}{1(5)}-\color{#0a0}{2(3)}\equiv -1\ $ so $\,d\neq 0.$

For motivation you might find instructive this post on the parity root test for polynomials. Such parity arguments are a prototypical way of solving ring (algebraic) problems via information gleaned from (simpler) modular images (an algebraic way of "dividing and conquering").

Answer 5

Here is perhaps the simplest answer to the specific question, avoiding the use of ring homomorphisms and residue classes. (Note: You should learn about ring homomorphisms and residue classes if you want to get anywhere in abstract algebra; you won't always be able to work as concretely as below.)

Fix a nonnegative integer $n$. We let $\left[n\right]$ denote the set $\left\{1,2,\ldots,n\right\}$.

Lemma 1. Let $A = \left(a_{i,j}\right)_{i, j \in \left[n\right]}$ and $B = \left(b_{i,j}\right)_{i, j \in \left[n\right]}$ be two $n\times n$-matrices of integers. Let $N$ be an integer. Assume that \begin{equation} a_{i,j} \equiv b_{i,j} \mod N \label{darij.eq.l1.1} \tag{1} \end{equation} for all $i, j \in \left[n\right]$. Then, $\det A \equiv \det B \mod N$.

Proof of Lemma 1. The Leibniz formula for determinants yields $\det A = \sum\limits_{\sigma \in S_n} \left(-1\right)^{\sigma} \prod\limits_{i=1}^n a_{i, \sigma\left(i\right)}$ and $\det B = \sum\limits_{\sigma \in S_n} \left(-1\right)^{\sigma} \prod\limits_{i=1}^n b_{i, \sigma\left(i\right)}$ (where $S_n$ denotes the set of all permutations of $\left[n\right]$, and where $\left(-1\right)^{\sigma}$ denotes the sign of a permutation $\sigma$). Thus, \begin{align} \det A & = \sum\limits_{\sigma \in S_n} \left(-1\right)^{\sigma} \prod\limits_{i=1}^n \underbrace{a_{i, \sigma\left(i\right)}}_{\substack{\equiv b_{i, \sigma\left(i\right)} \mod N \\ \left(\text{by \eqref{darij.eq.l1.1}}\right)}} \\ & \equiv \sum\limits_{\sigma \in S_n} \left(-1\right)^{\sigma} \prod\limits_{i=1}^n b_{i, \sigma\left(i\right)} = \det B \mod N \end{align} (here, we tacitly used the fact that everything in our expressions is an integer, and that congruences modulo $N$ can be multiplied). This proves Lemma 1. $\blacksquare$

Corollary 2. Let $A$ be an $n \times n$-matrix of integers such that all diagonal entries of $A$ are odd and all non-diagonal entries of $A$ are even. Then, $\det A$ is odd.

Proof of Corollary 2. Write the matrix $A$ as $A = \left(a_{i,j}\right)_{i, j \in \left[n\right]}$. Also, write the identity $n\times n$-matrix $I_n$ as $I_n = \left(b_{i,j}\right)_{i, j \in \left[n\right]}$. Then, it is easy to prove the congruence $a_{i,j} \equiv b_{i,j} \mod 2$ for all $i, j \in \left[n\right]$. (Indeed, if $i = j$, then $a_{i,j}$ is a diagonal entry of $A$, whereas $b_{i,j}$ is a diagonal entry of $I_n$ and thus equals $1$; hence, this congruence says that all diagonal entries of $A$ are odd. This is true by assumption. On the other hand, if $i \neq j$, then $a_{i,j}$ is a non-diagonal entry of $A$, whereas $b_{i,j}$ is a non-diagonal entry of $I_n$ and thus equals $0$; hence, this congruence says that all non-diagonal entries of $A$ are even. This is again true by assumption. Thus, the congruence holds in both cases $i = j$ and $i \neq j$.)

Thus, Lemma 1 (applied to $N=2$ and $B=I_n$) yields $\det A \equiv \det\left(I_n\right) = 1 \mod 2$. In other words, $\det A$ is odd. $\blacksquare$

Corollary 2 can be directly applied to your matrix $A$.