Abstract Nonsense

Crushing one theorem at a time

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.

Advertisements

October 27, 2010 - Posted by | Fun Problems, Linear Algebra | , , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: