|
LinearAlgebra[Modular][Inverse] - compute the Inverse of a square mod m Matrix
LinearAlgebra[Modular][Adjoint] - 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.
|
|
|
|
|
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.
|
>
|
![with(LinearAlgebra[Modular])](/support/helpjp/helpview.aspx?si=4515/file06074/math280.png)
|
|
>
|
|
|
| (1) |
|
>
|
![M := Mod(p, Matrix(3, 3, proc (i, j) options operator, arrow; rand() end proc), integer[])](/support/helpjp/helpview.aspx?si=4515/file06074/math291.png)
|
|
![M := Matrix([[77, 96, 10], [86, 58, 36], [80, 22, 44]])](/support/helpjp/helpview.aspx?si=4515/file06074/math294.png)
| (2) |
|
>
|
|
|
![Mi := Matrix([[16, 80, 72], [20, 20, 32], [5, 65, 89]])](/support/helpjp/helpview.aspx?si=4515/file06074/math301.png)
| (3) |
|
>
|
|
|
![Matrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]]), Matrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]])](/support/helpjp/helpview.aspx?si=4515/file06074/math308.png)
| (4) |
An example that fails with the LU and RET methods, but succeeds with RREF.
|
>
|
|
|
| (5) |
|
>
|
![M := Mod(m, [[3, 2], [2, 1]], float[8])](/support/helpjp/helpview.aspx?si=4515/file06074/math321.png)
|
|
![M := Matrix([[3., 2.], [2., 1.]])](/support/helpjp/helpview.aspx?si=4515/file06074/math324.png)
| (6) |
|
>
|
|
|
>
|
|
|
>
|
|
|
![Mi := Matrix([[5., 2.], [2., 3.]])](/support/helpjp/helpview.aspx?si=4515/file06074/math351.png)
| (7) |
|
>
|
|
|
![Matrix([[1., 0.], [0., 1.]]), Matrix([[1., 0.], [0., 1.]])](/support/helpjp/helpview.aspx?si=4515/file06074/math358.png)
| (8) |
An example where no inverse exists, but the adjoint does exist.
|
>
|
|
|
| (9) |
|
>
|
![M := Mod(m, [[2, 4], [4, 4]], float[8])](/support/helpjp/helpview.aspx?si=4515/file06074/math371.png)
|
|
![M := Matrix([[2., 4.], [4., 4.]])](/support/helpjp/helpview.aspx?si=4515/file06074/math374.png)
| (10) |
|
>
|
|
|
>
|
|
|
![Ma := Matrix([[4., 2.], [2., 2.]])](/support/helpjp/helpview.aspx?si=4515/file06074/math391.png)
| (11) |
|
>
|
|
|
![4, Matrix([[4., 0.], [0., 4.]]), Matrix([[4., 0.], [0., 4.]])](/support/helpjp/helpview.aspx?si=4515/file06074/math398.png)
| (12) |
An example where only the RET method succeeds at computing the adjoint.
|
>
|
|
|
| (13) |
|
>
|
![M := Mod(m, [[1, 1], [1, 1]], integer)](/support/helpjp/helpview.aspx?si=4515/file06074/math411.png)
|
|
![M := Matrix([[1, 1], [1, 1]])](/support/helpjp/helpview.aspx?si=4515/file06074/math414.png)
| (14) |
|
>
|
|
|
>
|
|
|
>
|
|
|
![Ma := Matrix([[1, 6], [6, 1]])](/support/helpjp/helpview.aspx?si=4515/file06074/math441.png)
| (15) |
|
>
|
|
|
![0, Matrix([[0, 0], [0, 0]]), Matrix([[0, 0], [0, 0]])](/support/helpjp/helpview.aspx?si=4515/file06074/math448.png)
| (16) |
|
|
