# Abstract Nonsense

## Interesting Trick To Remember

Point of Post: Often problems like:

” Determine whether the matrix

$\begin{bmatrix} 54401 & 57668 & 15982 & 103790\\ 33223 & 26563 & 23165 & 71489\\ 39799 & 37189 & 16569 & 46152\\ 21689 & 55538 & 79922 & 51237\end{bmatrix}$

is invertible.”

This post gives a trick, which when applicable, can make monstrosities like the above into simple calculations.

So, as the above motivated we are looking for easy to check conditions which will tell us when a matrix, like the above, is invertible. We could check the rank, the span of the columns etc., the spectrum (multiset of eigenvalues), etc. But, in a time-oriented setting (e.g. a math competition) these conditions aren’t so feasible. But, even given all the time in the world checking the column space of a matrix is not often easy, and it would be preferable to consider another means. So, we fall back on our old friend, the determinant. The quantitative measure of whether a matrix is invertible. But, this in itself may be a herculean task if the numbers are as “messy” as those in the above matrix. But, when we are considering matrices with integer entries, there is a neat “trick” one can check that can often (not always) make our lives easier. It stems from two observations: first

Observation: An integer $z_0$ is zero if and only if $n\mid z_0$ for every $n\in\mathbb{N}$

Put differently, $z_0=0$ if and only if $z_0\equiv 0\text{ mod }n$ for all $n\in\mathbb{N}$. And the second

Observation: If $\gamma_n(z)$ is defined to be the remainder of $z$ upon division by $n$,

then $\gamma_n(z_1\cdot z_2\cdots z_m)=\gamma_n\left(z_1\cdot\gamma_n(z_2)\cdots\gamma_n(z_n)\right)$ and

$\gamma_n\left(z_1+\cdots+z_m\right)=\gamma_n\left(\gamma_n(z_1)+\cdots+\gamma_n(z_m)\right)$

The second of these observations is clear, but the first may require some explaining. What this $\gamma_n$ really means is that every integer $z$ can be uniquely represented as $qn+r$ where $q\in\mathbb{Z}$ and $r\in\{0,\cdots,n-1\}$ (this is really just the division algorithm) and so we’re saying that $\gamma_n(z)=\gamma_n(qn+r)=r$. So, with this definition we can prove the above by noticing that if $z_j=q_jn+r_j$ that

\begin{aligned} \gamma_n\left(z_1\cdots z_m\right) &= \gamma_n\left( (q_1 n+r_1) (q_1 n + r_2) \cdots (q_m n+ r_m)\right)\\ &= \gamma_m\left( q_1n(q_2 n +r_2)\cdots (q_m n+r_m)+r_2(q_2 n +r_2)\cdots(q_m n +r_m)\right)\\ &=\gamma_n\left(q_1n(q_2n+r_2)\cdots(q_mn+r_m)\right)+\gamma_n\left(r_1(q_1n+r_2)\cdots(q_mn+r_m)\right)\\ &=\gamma_n\left((q_2nr_1+r_1r_2)\cdots(q_mn+r_m)\right)\\ &\quad \vdots \text{ applying the same logic }m\text{ times}\\ &=\gamma_n(r_1\cdots r_m)\end{aligned}

but,

\displaystyle \begin{aligned}\gamma_n\left(z_1 \gamma_n(z_2)\cdots\gamma_n(z_m)\right) &= \gamma_n\left((q_1n+r_1)\gamma_n\left(q_2n+r_2\right)\cdots\gamma_n\left(q_mn+r_m\right)\right)\\ &= \gamma_n\left((q_1n+r_1)r_2\cdots r_m\right)\\ &=\gamma_n\left(q_1nr_1\cdots r_m+r_1\cdot r_2\cdot r_m\right)\\ &=\gamma_n\left(q_1nr_2\cdots r_m\right)+\gamma_n\left(r_1\cdots r_m\right)\\ &= \gamma_n\left(r_1\cdots r_m\right)\end{aligned}

from where it becomes clear. But, with this definition of $\gamma_n$ we may restate the first observation as ” $z_0=0$ if and only if $\gamma_n(z_0)=0$ for all $n\in\mathbb{N}$“.

So now, with these observations made we may begin our hunt for easier (in a sense) conditions for when an integer entried matrix is invertible. We begin by recalling that if  $A\in \mathcal{M}_m\left(\mathbb{Z}\right)$ (where $\mathcal{M}_m\left(\mathbb{Z}\right)$ is the ring of matrices with entries in  $\mathbb{Z}$)

$A=\begin{bmatrix} a_{1,1} & \cdots & a_{1,m}\\ \vdots & \ddots &\vdots\\ a_{m,1} & \cdots & a_{m,m}\end{bmatrix}$

that $\det:\mathcal{M}_n\left(\mathbb{Z}\right)\to\mathbb{Z}$ is defined by

$\displaystyle \det A=\sum_{\pi\in S_m}\text{sgn}\left(\pi\right)a_{1,\pi(1)}\cdots a_{m,\pi(m)}$

And a necessary and sufficient condition for $A$ to be invertible is that $\det A\ne 0$. But, note that since $\det A\in\mathbb{Z}$ our observations tell us that $A$ is not invertible if and only if $\gamma_n\left(\det A\right)=0$ for all $n\in\mathbb{N}$. But,

\displaystyle \begin{aligned}\gamma_n\left(\det A\right) &= \gamma_n\left(\sum_{\pi\in S_m}\text{sgn}(\pi)a_{1,\pi(1)}\cdots a_{m,\pi(m)}\right)\\ &= \gamma_n\left(\sum_{\pi\in S_m}\gamma_n\left(\text{sgn}(\pi)a_{1,\pi(1)}\cdots q_{m,\pi(m)}\right)\right)\\ &= \gamma_n\left(\sum_{\pi\in S_m}\gamma_n\left(\text{sgn}\left(\pi\right)\gamma_n\left(a_{1,\pi(1)}\right)\cdots\gamma_n\left(a_{m,\pi(m)}\right)\right)\right)\\ &= \gamma_n\left(\sum_{\pi\in S_m}\text{sgn}\left(\pi\right)\gamma_n\left(a_{1,\pi(1)}\right)\cdots\gamma_n\left(a_{m,\pi(m)}\right)\right)\\ &= \gamma_n\left(\det\begin{bmatrix}\gamma_n\left(a_{1,1}\right) & \cdots & \gamma_n\left(a_{1,1}\right)\\ \vdots & \ddots & \vdots\\ \gamma_n\left(a_{m,1}\right) & \cdots & \gamma_n\left(a_{m,m}\right)\end{bmatrix}\right)\end{aligned}

So that if we define

$\Gamma_n\left(A\right)=\left[\gamma_n(a_{i,j})\right]$

then what we’ve really shown is that $A$ is not  invertible if and only if $\gamma_n\left(\det\left(\Gamma_n\left(A\right)\right)\right)=0$ for all $n\in\mathbb{N}$. At this point you’re probably asking “And this is easier than just taking the determinant…how?”

Well, let me show you how. Consider the matrix we had in the motivation, call it $M$. Then,

$\displaystyle \Gamma_2\left(M\right)=\begin{bmatrix} 1 & 0 & 0 & 0\\ 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 1\end{bmatrix}$

and with this it is much easier to find that

$\det\left(\Gamma_2\left(M\right)\right)=-1$

and thus

$\gamma_2\left(\det\left(\Gamma_2\left(M\right)\right)\right)=1$

But, this means that $M$ must be invertible!

Thus, the use of this is mostly when one wants to prove that something is invertible. If one can find any $m\in\mathbb{N}$ for which if one reduces the entires of a matrix $\text{ mod }m$, takes the determinant, and then reduces the result $\text{ mod }m$ that one doesn’t get $0$ then the matrix must be invertible. Probably the most applicable (as in the above example) case is the following corollary

Corollary: If a matrix $A\in\mathcal{M}_m\left(\mathbb{Z}\right)$ has the quality that $\det \Gamma_2\left(A\right)$ is odd, then $A$ is invertible.

References: I haven’t found a book that explicitly states this theorem, but for more information on the determinant see

1.  Horn, Roger A., and Charles R. Johnson. Matrix Analysis. Cambridge [u.a.: Cambridge Univ., 2009. Print.