<p>Can I use Gaussian elimination to compute matrix inverse over the ring $\mathbb{Z}_{p^k}$ (ring of residues modulo $p^k$) where $p$ is prime and $k$ is an integer greater than $1$?</p>

<p>Such matrix is invertible if and only if its determinant is not congruent to zero modulo $p$. So we can check if it is invertible by constructing the second matrix &mdash; matrix of residues modulo $p$ of elements of the original matrix. The second matrix is over $\mathbb{Z}_p$ so we can use Gaussian elimination to compute its determinant. The determinant can be expressed as a polynomial formula (Laplace expansion) so the determinant of the second matrix is the determinant of the original one modulo $p$ and so the original matrix is invertible if and only if the determinant of the second one is not zero.</p>

<p>I think that using Gaussian elimination to compute the inverse in this case is correct and it is quite easy to prove. It uses exactly the same steps as inverting the aforementioned matrix over $\mathbb{Z}_p$. Gaussian elimination over the finite field $\mathbb{Z}_p$ fails if and only if the matrix is not invertible and it fails because all the elements under the pivot position are zero. It means that in the original matrix all these elements are congruent to zero modulo p so they are not invertible and Gaussian elimination fails over $\mathbb{Z}_{p^k}$. If the elimination succeeds over $\mathbb{Z}_p$ then it also succeeds over $\mathbb{Z}_{p^k}$ &mdash; if you can find nonzero pivot element in the matrix over $\mathbb{Z}_p$ then the equivalent element in the original matrix is invertible.</p>

<p>Moreover I have implemented it and it works. For invertible matrices it gives their inverses modulo $\mathbb{Z}_{p^k}$. For non-invertible it fails. I have conducted many tests for different matrix sizes, different $p$ and different $k$. </p>

<p>It is quite simple so there are two possibilities: either there is something wrong in my reasoning, or someone must have described it somewhere. However I could't find any reference for that fact. I've found some articles and books that discuss the computation of matrix inverses and determinants modulo integers (e.g. Pan, Stewart &mdash; Algebraic and numerical techniques for the computation of matrix determinants, von zur Gathen, Gerhard &mdash; Modern computer algebra) but I haven't found it there.</p>

<p>I would like to find some reference that clearly states that you can do Gaussian elimination over $\mathbb{Z}_{p^k}$ or some argument against it.</p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2014-07-11T20:45:40.287Z
This question should be migrated to Math.SE.
Niel de Beaudrap
CC BY-SA 3.0
2014-07-12T20:18:54.817Z
This may not directly answer the question, but it's pretty close. Buchmann and Neis (https://www-old.cdc.informatik.tu-darmstadt.de/reports/reports/papers/Finished/03b_TI-96-7.linear_algebra.pdf) show how to compute the inverse image of a point under a linear map over a principal ideal ring (which includes $\mathbb{Z}_{p^k}$).
Joshua Grochow
<reference-request><linear-algebra>
Gaussian elimination for inverting matrices modulo prime power
user26596
# Gaussian elimination for inverting matrices modulo prime power

(Asked by: username_0 on 2014-07-11)

Can I use Gaussian elimination to compute matrix inverse over the ring $\mathbb{Z}\_{p^k}$ (ring of residues modulo $p^k$) where $p$ is prime and $k$ is an integer greater than $1$?

Such matrix is invertible if and only if its determinant is not congruent to zero modulo $p$. So we can check if it is invertible by constructing the second matrix — matrix of residues modulo $p$ of elements of the original matrix. The second matrix is over $\mathbb{Z}\_p$ so we can use Gaussian elimination to compute its determinant. The determinant can be expressed as a polynomial formula (Laplace expansion) so the determinant of the second matrix is the determinant of the original one modulo $p$ and so the original matrix is invertible if and only if the determinant of the second one is not zero.

I think that using Gaussian elimination to compute the inverse in this case is correct and it is quite easy to prove. It uses exactly the same steps as inverting the aforementioned matrix over $\mathbb{Z}\_p$. Gaussian elimination over the finite field $\mathbb{Z}\_p$ fails if and only if the matrix is not invertible and it fails because all the elements under the pivot position are zero. It means that in the original matrix all these elements are congruent to zero modulo p so they are not invertible and Gaussian elimination fails over $\mathbb{Z}\_{p^k}$. If the elimination succeeds over $\mathbb{Z}\_p$ then it also succeeds over $\mathbb{Z}\_{p^k}$ — if you can find nonzero pivot element in the matrix over $\mathbb{Z}\_p$ then the equivalent element in the original matrix is invertible.

Moreover I have implemented it and it works. For invertible matrices it gives their inverses modulo $\mathbb{Z}\_{p^k}$. For non-invertible it fails. I have conducted many tests for different matrix sizes, different $p$ and different $k$.

It is quite simple so there are two possibilities: either there is something wrong in my reasoning, or someone must have described it somewhere. However I could't find any reference for that fact. I've found some articles and books that discuss the computation of matrix inverses and determinants modulo integers (e.g. Pan, Stewart — Algebraic and numerical techniques for the computation of matrix determinants, von zur Gathen, Gerhard — Modern computer algebra) but I haven't found it there.

I would like to find some reference that clearly states that you can do Gaussian elimination over $\mathbb{Z}\_{p^k}$ or some argument against it.

Thanks in advance.

**Tags:** reference-request, linear-algebra

> **Comments:**
> **username_1**: This question should be migrated to Math.SE.  
> **username_2**: This may not directly answer the question, but it's pretty close. Buchmann and Neis (https://www-old.cdc.informatik.tu-darmstadt.de/reports/reports/papers/Finished/03b_TI-96-7.linear_algebra.pdf) show how to compute the inverse image of a point under a linear map over a principal ideal ring (which includes $\mathbb{Z}_{p^k}$).  

---

## 0 answers

