7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.