(RGS 4/5) Inverting matrices modulo m Task

Given an integer matrix M and a modulus m, find an inverse of M modulo m. If the matrix M is not invertible modulo m, the behaviour is left unspecified.

Matrix inverse

If M is a square matrix, its inverse exists if and only if its determinant is not 0. Similarly, when we are talking about matrices modulo m, the inverse of M will exist if and only of the determinant of M is invertible modulo m, which happens when the determinant is coprime with m.

The inverse of M is a square matrix inv(M) such that M*inv(M) = inv(M)*M = I, where

$$I = \begin{bmatrix}
1 &amp; 0 &amp; 0 &amp; \cdots &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; \cdots &amp; 0 \\
\vdots &amp; \ddots &amp; \ddots &amp; \ddots &amp; \vdots \\
0 &amp; 0 &amp; \cdots &amp; 0 &amp; 1
\end{bmatrix}$$

has the same shape of M and is called the identity matrix. As an example, consider the first test case, where [[22, 43], [29, 37]] is the inverse of [[26, 16], [38, 41]] mod 45:

$$\begin{bmatrix}
26&amp;16\\38&amp;41
\end{bmatrix} \cdot \begin{bmatrix}
22&amp;43\\29&amp;37
\end{bmatrix} = \begin{bmatrix}
1036&amp;1710\\2025&amp;3151
\end{bmatrix} \equiv \begin{bmatrix}
1 &amp; 0 \\ 0&amp;1
\end{bmatrix} \mod 45$$

Input

A square matrix M with integer values between 0 and m-1, inclusive, and a positive integer m &gt; 1. The matrix may be given in any sensible format, including


a list of lists, where the inner lists encode the rows, like M = [[1, 2], [3, 4]], or a flattened version, like M = [1, 2, 3, 4]
a list of lists, where the inner lists encode the columns, like M = [[1, 3], [2, 4]], or a flattened version, like M = [1, 3, 2, 4]


where these encode the matrix

\$\$\begin{bmatrix}
1 &amp; 2 \\ 3 &amp; 4
\end{bmatrix}\$\$

The integer m giving the modulus.

You may also accept the size of the matrix as input.

The inputs can be given in any order.

Output

A matrix representing the inverse of M modulo m. You may assume such an inverse exists. Preferable format is for each matrix entry \$a_{i,j}\$ to satisfy \$0 \leq a_{i,j} &lt; m\$ but this is just to make it easier to compare with the test cases.

Test cases

45, [[26, 16], [38, 41]] -&gt; [[22, 43], [29, 37]]

39, [[29, 50], [29, 1]] -&gt; [[16, 19], [4, 35]]

35, [[24, 14], [48, 45]] -&gt; [[5, 7], [4, 33]]

53, [[43, 20], [15, 8]] -&gt; [[5, 14], [37, 7]]

49, [[15, 11, 30], [20, 12, 40], [33, 25, 2]] -&gt; [[33, 28, 23], [25, 18, 0], [25, 48, 13]]

37, [[8, 9, 22, 17], [24, 30, 30, 19], [39, 8, 45, 23], [5, 30, 22, 33]] -&gt; [[18, 17, 26, 20], [29, 36, 23, 1], [19, 0, 9, 3], [30, 23, 14, 21]]


This is code-golf so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!



This is the fourth challenge of the RGS Golfing Showdown. If you want to participate in the competition, you have 96 hours to submit your eligible answers. Remember there is still 300 reputation in prizes! (See 6 of the rules)

Also, as per section 4 of the rules in the linked meta post, the "restricted languages" for this third challenge are only Jelly, V (vim) and 05AB1E so submissions in these languages are not eligible for the final prize. But they can still be posted!!

Otherwise, this is still a regular code-golf challenge, so enjoy!
R, 68 bytes



function(M,m,n,A=M){while(any(A%*%M%%m!=diag(n)))A[]=rpois(n^2,9)
A}


Try it online!

Strikingly slow. Will most likely time out for all test cases on TIO, but is guaranteed to give an answer eventually.

Works by rejection sampling: generates random matrices A, with each value taken from a \$Poisson(9)\$ distribution, until a solution is found.

Note that to get A of the correct dimensions, it is 6 bytes shorter to initialize it as A=M and then replace all the values with A[]=rpois(n^2,9) than to create it directly with A=matrix(rpois(n^2,9),n).