Inverting a matrix in $\mathbb{Z}/n\mathbb{Z}$.

So in my Linear Algebra course I was shown that we cannot directly use row reduction to invert a matrix over a commutative ring in general because the algorithm requires elements to be invertible (which is not always the case in a ring). Inverting a matrix with the formula $A^{-1} = det(A)^{-1}C^T$ is guaranteed to work in every case.

However, it was also shown that in some rings we might still use row reduction in a way. For example, we can treat any matrix over $\mathbb{Z}$ as a matrix over $\mathbb{R}$ and invert it with row reduction - if the computed inverse only has elements in $\mathbb{Z}$, the matrix is invertible.

Knowing that I tried inverting matrices over $\mathbb{Z}/n\mathbb{Z}$ in a similar way. We can compute the inverse of $\begin{pmatrix}1 & 2 \\ 3 & 5\end{pmatrix}$ in $\mathbb{Z}/12\mathbb{Z}$ using the determinant and get $\begin{pmatrix}7 & 2 \\ 3 & 11\end{pmatrix}$. Inverting the same matrix over $\mathbb{R}$ yields $\begin{pmatrix}-5 & 2 \\ 3 & -1\end{pmatrix}$, which is the equivalent matrix modulo $12$, so this seems to work. In another case (matrix in $\mathbb{F}_7$), I was initially disheartened by seeing terms like $\frac{3}{2}$ in the inverse, but then my tutor reminded me that $\frac{3}{2}$ is really just $3\cdot2^{-1}$ which in $\mathbb{F}_7$ is equal to $3\cdot 4 = 12 = 5$.

My question is whether this is guaranteed to work in general. That is, will inverting a matrix in $\mathbb{R}$ and then taking inverses and modulos appropriately be successful exactly if the matrix is invertible in $\mathbb{Z}/n\mathbb{Z}$? It is clear that this is the case if $n$ is prime, because then $\mathbb{Z}/n\mathbb{Z}$ is a field, but what about the other cases? Is it possible that there is such a matrix that is invertible but whose inverse cannot be found by this method? Or conversely, that if such an "inverse" were to be found, it would not actually be an inverse of the matrix?

(As a related question: Are there rings over which matrices can only be inverted by using the determinant? Matrices over polynomials maybe? At least I haven't seen a technique for inverting these matrices with row reduction. But OTOH, I guess most of those matrices are probably not invertible anyway, since it would require the determinant to be of degree $0$).

• The answer to your question is yes. In any commutative ring, we have $$A \operatorname{adj}(A) = \det(A) I$$ where adj denotes the adjunct matrix. – Omnomnomnom Oct 26 '15 at 17:13
• I might be misunderstanding, but I think this doesn't actually answer the question or does it? My question was if the inverse can be found by using row reduction. – Fryie Oct 26 '15 at 17:14
• Well, you had several questions. What I've stated here is enough to say that $A$ has an inverse if and only if $\det(A)$ is an invertible element. – Omnomnomnom Oct 26 '15 at 17:18
• This talk of $\mathbb R$ seems a bit distracting -- we're talking about $\mathbb Q$ here, no? – joriki Oct 26 '15 at 17:36
• About $\mathbb R$ or $\mathbb Q$: You want to "translate" elements of the inverse over this field to the ring. We know how to do this translation from $\mathbb Q$ (as long as the denominators are invertible in the ring). Irrational numbers neither occur in the inverse, nor is there a notion of translating them to the ring, so they aren't playing any role here; including them in the field serves no purpose. – joriki Oct 26 '15 at 18:48

Inverting the matrix $A$ over the rationals $\mathbb Q$ will fail only if the matrix has determinant $0$ (over $\mathbb Q$). But in that case it also has determinant $0$ mod $n$ for any $n$, so it is not invertible over $\mathbb Z/n\mathbb Z$.

If you do find an inverse $B$ over $\mathbb Q$, and the denominator of some element of $B$ is divisible by some prime $p$ that also divides $n$, then the determinant of $A$ is divisible by $p$, which means $\det(A)$ is not a unit in $\mathbb Z/n\mathbb Z$, and again $A$ is not invertible over $\mathbb Z/n\mathbb Z$.

On the other hand, if all denominators of elements of $B$ are coprime to $n$, then $B$ corresponds to a matrix over $\mathbb Z/n\mathbb Z$ which is an inverse to $A$ there. Namely, if $d$ is the lcm of the denominators, $dB$ is a matrix of integers with $d A B = d I$ (over the integers), and thus $d A B = d I$ over $\mathbb Z/n\mathbb Z$ as well (using the homomorphism of rings $\mathbb Z \to \mathbb Z/n\mathbb Z$).

EDIT: The "standard" row reduction over $\mathbb Z/n \mathbb Z$ doesn't always work: consider the matrix $$\pmatrix{2 & 3\cr 3 & 5\cr}\ \text{over}\ \mathbb Z/6\mathbb Z$$ This matrix has determinant $1$ and thus is invertible. However, you're stuck right away trying to row reduce, because neither $2$ nor $3$ is invertible mod $6$. What you can do, though, is first add the second row to the first, making the top left matrix element invertible, and proceed from there.

Note that at any stage in the row reduction process, the entries in the next column that don't have leading $1$'s must have gcd coprime to $n$, otherwise the determinant would not be coprime to $n$. By Bezout's identity that gcd is some linear combination of these entries over the integers. Thus by some elementary row operations we can get a pivot entry that is coprime to $n$.

• Sure. The question seems to be, however: if the inverse of a matrix exists, can that inverse can be computed by row-reduction? – Omnomnomnom Oct 26 '15 at 17:46
• As for your example: The inverse of $\begin{pmatrix}2 & 3\\3 & 5\end{pmatrix}$ over $\mathbb{R}$ is $\begin{pmatrix}5 & -3\\-3 & 2\end{pmatrix}$, as can be computed by using row reduction. In $\mathbb{Z}/6\mathbb{Z}$, this is equivalent to $\begin{pmatrix}5 & 3\\3 & 2\end{pmatrix}$, which is indeed an inverse. So the method (invert the corresponding matrix over $\mathbb{R}$, then take the result modulo 6) actually works in this case. – Fryie Oct 26 '15 at 18:16
• Thanks for the answer. As far as I understand it, your answer proves that if $A$ is invertible over $\mathbb{Q}$ and if $A^{-1}$ corresponds to a matrix $B$ in $\mathbb{Z}/n\mathbb{Z}$, then $A$ is invertible over $\mathbb{Z}/n\mathbb{Z}$ with inverse $B$. This is one direction of the equivalence. What about the other way around? If $A$ is invertible over $\mathbb{Z}/n\mathbb{Z}$ with inverse $A^{-1}$, will $A^{-1}$ correspond to a matrix $B$ such that $B$ is an inverse of $A$ over $\mathbb{Q}$? – Fryie Oct 26 '15 at 18:27
• Yes. If $A$ is invertible over $\mathbb Z/n \mathbb Z$, its determinant over $\mathbb Z/n\mathbb Z$ is a unit in $\mathbb Z/n\mathbb Z$, and is the homomorphic image of the determinant over $\mathbb Q$. Therefore the latter is nonzero, and the matrix is invertible over $\mathbb Q$. As I showed, from this inverse over $\mathbb Q$ you get an inverse over $\mathbb Z/n\mathbb Z$. But inverses in any ring are unique, so the inverse you get is $A^{-1}$. – Robert Israel Oct 26 '15 at 18:39
• Okay, thanks. From I high level perspective, I get that this concludes the proof, so I will accept your answer. I cannot follow all the steps (I don't know all of the terms you use :)), so this indicates to me that I might have asked the question "too soon" (i.e. without learning all the relevant material to answer it). I hope I can come back to this answer when I have learned what homomorphic images are. :) PS: I sense that this question created some confusion so it would be very helpful to me if you could point out ways in which this question could be improved/clarified. – Fryie Oct 26 '15 at 18:49

If you have an integral domain $R$ you can do Row Reduction into its field of fractions.

As the inverse is given by the formula $\frac{1}{det(A)} adj(A)$, it follows that the answer we get by RR is a matrix with entries in $R$ (actually in the image of $R$ inside its field of fractions).

Next, if you have any factor $p:R \to R/I$ of an integral domain, then any matrix $A$ can be pulled back to a matrix $\tilde{A}$ with entries in $R$. You can do row reduction into the fields of fractions of $R$, and then the answer you get must be equal to $\frac{1}{\det(\tilde{A})} adj(\tilde{A})$. Note that $\det(\tilde{A})$ is not invertible in $R$ but is invertible in $R/I$. Therefore, every entry in $\tilde{A}^{-1}$ can be written as $a/b$ where $p(b)$ is invertible in $R/I$. This allows you to carry $\tilde{A}^{-1}$ through the mapping $p$ and get the inverse of $A$.

Added Lets say that we want calculate the inverse of $$A:=\begin{bmatrix} 3 & 4 \\ 2&5 \end{bmatrix}$$ in $\mathbb Z/12 \mathbb Z$. Now, if we calculate the inverse of $A$ in $\mathbb Q$ we get $$A^{-1} =\begin{bmatrix} \frac{5}{7} & -\frac{4}{7} \\ -\frac{2}{7} &\frac{3}{7} \end{bmatrix}$$

We write this as $$A^{-1} =\begin{bmatrix}7^{-1}5 & -7^{-1}4 \\ -7^{-1}2 &7^{-1}3 \end{bmatrix}$$

Now carry this into $\mathbb Z /12 \mathbb Z$. In here we have $7^{-1}=7$ thus $$A^{-1}=\begin{bmatrix}7\cdot5 & -7\cdot4 \\ -7\cdot2 &7\cdot3 \end{bmatrix}=\begin{bmatrix}-1 & -4 \\ -2 &-3 \end{bmatrix}$$

A simple checking shows that this is indeed right: $$\begin{bmatrix} 3 & 4 \\ 2&5 \end{bmatrix}\begin{bmatrix}-1 & -4 \\ -2 &-3 \end{bmatrix}=\begin{bmatrix}-11 & -24 \\ -12 &-23 \end{bmatrix}=I_2$$

Why does it work?

The reason is simple. We start calculating $A^{-1}$ in $\mathbb Q$. Now the formula $A^{-1} =\frac{1}{\det(A)} adj(A)$ tells us that if we multiply $A^{-1}$ by $\det(A)$ we get only matrices with integer coefficients.

[When we multiply $A \cdot A^{-1} =I_n$ by $\det(A)$ we actually get the relation $$A adj(A)=\det(A) I_n$$ which is well known.]

Since this is a relation which is true in $\mathbb Z$ it is also true in $\mathbb Z/12 \mathbb Z$. Then use the fact that the determinant is invertible in here.

In the above example, our reasoning was the following: Since $$A^{-1} =\begin{bmatrix} \frac{5}{7} & -\frac{4}{7} \\ -\frac{2}{7} &\frac{3}{7} \end{bmatrix}$$ in $\mathbb Q$ we know that $$\begin{bmatrix} 3 & 4 \\ 2&5 \end{bmatrix} \cdot \begin{bmatrix} \frac{5}{7} & -\frac{4}{7} \\ -\frac{2}{7} &\frac{3}{7} \end{bmatrix} =I_2$$ and hence $$\begin{bmatrix} 3 & 4 \\ 2&5 \end{bmatrix} \cdot \begin{bmatrix} 5 & -4 \\ -2 &3 \end{bmatrix} =7I_2$$

This is a relation which is true in $\mathbb Z$ and hence in $\mathbb Z/12 \mathbb Z$. Therefore in $\mathbb Z/12 \mathbb Z$ we have $$\begin{bmatrix} 3 & 4 \\ 2&5 \end{bmatrix} \cdot \begin{bmatrix} 5 & -4 \\ -2 &3 \end{bmatrix} =7I_2 \Rightarrow \\ \begin{bmatrix} 3 & 4 \\ 2&5 \end{bmatrix} \cdot 7^{-1}\begin{bmatrix} 5 & -4 \\ -2 &3 \end{bmatrix} =I_2$$ which is exactly the matrix we got, where the denominator is replaced by the inverse.

• Ah, but if i remember correctly, $\mathbb{Z}/n\mathbb{Z}$ is not generally an integral domain, right? Because in $\mathbb{Z}/4\mathbb{Z}$ it is the case that $2\cdot 2 = 4 = 0$, but $2 \neq 0$. – Fryie Oct 26 '15 at 18:29
• @Fryie But $\mathbb Z$ is. And $\mathbb Z/n \mathbb Z$ is a factor of an integral domain, read the second paragraph, the part which comes after "Next" ;) – N. S. Oct 27 '15 at 0:20
• @Fryie First part, you are in an integral Domain, and the assumption in your question is that $\det(A)$ is invertible in $R$. Thus you get fractions with invertible denominator, which are equivalent to elements of $R$. – N. S. Oct 29 '15 at 12:08
• @Fryie By pulling back yes I mean that. And yes det is not necessarily invertible. – N. S. Oct 29 '15 at 12:10
• @Fryie As for the first question, yes $A$ is invertible in $\,athbb Z/n \mathbb Z$ if and only if its determinant is.So yes, there is no danger. – N. S. Oct 29 '15 at 12:11