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

Question

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$).

Answer 1

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

Answer 2

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.