LinearAlgebra[Modular]

 Inverse
 compute the Inverse of a square mod m Matrix
 compute the Adjoint of a square mod m Matrix

 Calling Sequence Inverse(m, A, det, B, meth) Adjoint(m, A, det, B, meth)

Parameters

 m - modulus A - mod m Matrix det - (optional) name to use for output determinant B - (optional) Matrix to use for output Inverse or Adjoint meth - (optional) method to use for computing Inverse or Adjoint

Description

 • The Inverse and Adjoint functions compute the inverse and adjoint, respectively, of a square mod m Matrix.
 • If det is specified, it is assigned the value of the determinant on successful completion.
 • If B is specified, it must have dimensions and datatype identical to A, and will contain the inverse or adjoint on successful completion. In this case the command will return NULL.
 • The default method for the inverse is LU, while the default method for the adjoint is RET, and these can be changed by specification of meth.
 Allowable options are:

 LU Obtain inverse or adjoint via LU decomposition. inplaceLU Obtain inverse or adjoint via LU decomposition destroying the data in A in the process. RREF Obtain inverse or adjoint through application of row reduction to an identity augmented mod m Matrix. RET Obtain inverse or adjoint through application of a row echelon transform to A. inplaceRET Obtain inverse or adjoint through application of a row echelon transform to A, replacing A with the inverse or adjoint.

 The LU and inplaceLU methods are the most efficient for small to moderate sized problems. The RET and inplaceRET methods are the most efficient for very large problems. The RREF method is the most flexible for nonsingular matrices.
 • For the inplaceRET method, B should never be specified, as the output replaces A. For this method, the commands always return NULL.
 • With the LU-based and RET-based methods, it is generally required that m be a prime, as mod m inverses are needed, but in some cases it is possible to obtain an LU decomposition or a Row-Echelon Transform for m composite.
 For the cases where LU Decomposition or Row-Echelon Transform cannot be obtained for m composite, the function returns an error indicating that the algorithm failed because m is composite.
 Note: There are cases with composite m for which the inverse and adjoint exist, but no LU decomposition or Row-Echelon Transform is possible.
 • If it exists, the RREF method always finds the mod m inverse.  The RREF method also finds the adjoint if the Matrix is nonsingular.
 • The RET method is the only method capable of computing the adjoint if the matrix is singular. The inplaceRET method cannot be used to compute the adjoint of a singular matrix, as this operation cannot be performed in-place.
 • These commands are part of the LinearAlgebra[Modular] package, so they can be used in the form Inverse(..) and Adjoint(..) only after executing the command with(LinearAlgebra[Modular]).  However, they can always be used in the form LinearAlgebra[Modular][Inverse](..) and LinearAlgebra[Modular][Adjoint](..).

Examples

Basic 3x3 Matrix.

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right):$
 > $p≔97$
 ${p}{≔}{97}$ (1)
 > $M≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(3,3,\left(i,j\right)↦\mathrm{rand}\left(\right)\right),\mathrm{integer}\left[\right]\right)$
 ${M}{≔}\left[\begin{array}{ccc}{77}& {96}& {10}\\ {86}& {58}& {36}\\ {80}& {22}& {44}\end{array}\right]$ (2)
 > $\mathrm{Mi}≔\mathrm{Inverse}\left(p,M\right)$
 ${\mathrm{Mi}}{≔}\left[\begin{array}{ccc}{16}& {80}& {72}\\ {20}& {20}& {32}\\ {5}& {65}& {89}\end{array}\right]$ (3)
 > $\mathrm{Multiply}\left(p,M,\mathrm{Mi}\right),\mathrm{Multiply}\left(p,\mathrm{Mi},M\right)$
 $\left[\begin{array}{ccc}{1}& {0}& {0}\\ {0}& {1}& {0}\\ {0}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {0}& {0}\\ {0}& {1}& {0}\\ {0}& {0}& {1}\end{array}\right]$ (4)

An example that fails with the LU and RET methods, but succeeds with RREF.

 > $m≔6$
 ${m}{≔}{6}$ (5)
 > $M≔\mathrm{Mod}\left(m,\left[\left[3,2\right],\left[2,1\right]\right],\mathrm{float}\left[8\right]\right)$
 ${M}{≔}\left[\begin{array}{cc}{3.}& {2.}\\ {2.}& {1.}\end{array}\right]$ (6)
 > $\mathrm{Mi}≔\mathrm{Inverse}\left(m,M\right)$
 > $\mathrm{Mi}≔\mathrm{Inverse}\left(m,M,'\mathrm{RET}'\right)$
 > $\mathrm{Mi}≔\mathrm{Inverse}\left(m,M,'\mathrm{RREF}'\right)$
 ${\mathrm{Mi}}{≔}\left[\begin{array}{cc}{5.}& {2.}\\ {2.}& {3.}\end{array}\right]$ (7)
 > $\mathrm{Multiply}\left(m,M,\mathrm{Mi}\right),\mathrm{Multiply}\left(m,\mathrm{Mi},M\right)$
 $\left[\begin{array}{cc}{1.}& {0.}\\ {0.}& {1.}\end{array}\right]{,}\left[\begin{array}{cc}{1.}& {0.}\\ {0.}& {1.}\end{array}\right]$ (8)

An example where no inverse exists, but the adjoint does exist.

 > $m≔6$
 ${m}{≔}{6}$ (9)
 > $M≔\mathrm{Mod}\left(m,\left[\left[2,4\right],\left[4,4\right]\right],\mathrm{float}\left[8\right]\right)$
 ${M}{≔}\left[\begin{array}{cc}{2.}& {4.}\\ {4.}& {4.}\end{array}\right]$ (10)
 > $\mathrm{Mi}≔\mathrm{Inverse}\left(m,M,'\mathrm{RREF}'\right)$
 > $\mathrm{Ma}≔\mathrm{Adjoint}\left(m,M,'\mathrm{det}','\mathrm{RREF}'\right)$
 ${\mathrm{Ma}}{≔}\left[\begin{array}{cc}{4.}& {2.}\\ {2.}& {2.}\end{array}\right]$ (11)
 > $\mathrm{det},\mathrm{Multiply}\left(m,M,\mathrm{Ma}\right),\mathrm{Multiply}\left(m,\mathrm{Ma},M\right)$
 ${4}{,}\left[\begin{array}{cc}{4.}& {0.}\\ {0.}& {4.}\end{array}\right]{,}\left[\begin{array}{cc}{4.}& {0.}\\ {0.}& {4.}\end{array}\right]$ (12)

An example where only the RET method succeeds at computing the adjoint.

 > $m≔7$
 ${m}{≔}{7}$ (13)
 > $M≔\mathrm{Mod}\left(m,\left[\left[1,1\right],\left[1,1\right]\right],\mathrm{integer}\right)$
 ${M}{≔}\left[\begin{array}{cc}{1}& {1}\\ {1}& {1}\end{array}\right]$ (14)
 > $\mathrm{Ma}≔\mathrm{Adjoint}\left(m,M,'\mathrm{RREF}'\right)$
 > $\mathrm{Ma}≔\mathrm{Adjoint}\left(m,M,'\mathrm{LU}'\right)$
 > $\mathrm{Ma}≔\mathrm{Adjoint}\left(m,M,'\mathrm{det}','\mathrm{RET}'\right)$
 ${\mathrm{Ma}}{≔}\left[\begin{array}{cc}{1}& {6}\\ {6}& {1}\end{array}\right]$ (15)
 > $\mathrm{det},\mathrm{Multiply}\left(m,M,\mathrm{Ma}\right),\mathrm{Multiply}\left(m,\mathrm{Ma},M\right)$
 ${0}{,}\left[\begin{array}{cc}{0}& {0}\\ {0}& {0}\end{array}\right]{,}\left[\begin{array}{cc}{0}& {0}\\ {0}& {0}\end{array}\right]$ (16)