Finding Inverse of an array not working via sympy inverse Python-CodePudding

Can Someone explain why the inverse isn't working with this matrix but it is with the commented part?

from sympy import Matrix
list = []
print(self.get_key_secret())
key = np.array([7, 23, 21, 9, 19, 3, 15, 15, 12]).reshape(3, 3)
# key = np.array(
#     [[3, 10, 20],
#     [20, 9, 17],
#     [9, 4, 17]])
print(self.get_message_secret().shape)
encr = np.matmul(self.get_message_secret(), key)
encr = encr % 26
inverse_keyArray = Matrix(key).inv_mod(26)
print(inverse_keyArray)
inverse_keyArray = np.array(inverse_keyArray).astype(float)
print(inverse_keyArray)
decryption = np.matmul(encr, inverse_keyArray)
res = np.remainder(decryption, 26)
print(res)

I get the errors

ValueError: inverse of -3318 (mod 26) does not exist
sympy.matrices.common.NonInvertibleMatrixError: Matrix is not invertible (mod 26)

CodePudding user response：

I was going to complain about the missing items like self.get_key_secret(), but realized that the inv just involves the key array:

In [1]: key = np.array([7, 23, 21, 9, 19, 3, 15, 15, 12]).reshape(3, 3)
In [2]: key
Out[2]: 
array([[ 7, 23, 21],
       [ 9, 19,  3],
       [15, 15, 12]])

Ane make a sympy.Matrix from that:

In [3]: Matrix(key)
Out[3]: 
⎡7   23  21⎤
⎢          ⎥
⎢9   19  3 ⎥
⎢          ⎥
⎣15  15  12⎦

The full error, with traceback. Admittedly it doesn't add a lot. In part because I'm not familiar with this mod inverse.

In [4]: Matrix(key).inv_mod(26)
-----------------------------------------------------------------------
ValueError                            Traceback (most recent call last)
File /usr/local/lib/python3.8/dist-packages/sympy/matrices/inverse.py:176, in _inv_mod(M, m)
    175 try:
--> 176     det_inv = mod_inverse(det_K, m)
    177 except ValueError:

File /usr/local/lib/python3.8/dist-packages/sympy/core/numbers.py:551, in mod_inverse(a, m)
    550 if c is None:
--> 551     raise ValueError('inverse of %s (mod %s) does not exist' % (a, m))
    552 return c

ValueError: inverse of -3318 (mod 26) does not exist

During handling of the above exception, another exception occurred:

NonInvertibleMatrixError              Traceback (most recent call last)
Input In [4], in <cell line: 1>()
----> 1 Matrix(key).inv_mod(26)

File /usr/local/lib/python3.8/dist-packages/sympy/matrices/matrices.py:2199, in MatrixBase.inv_mod(self, m)
   2198 def inv_mod(self, m):
-> 2199     return _inv_mod(self, m)

File /usr/local/lib/python3.8/dist-packages/sympy/matrices/inverse.py:178, in _inv_mod(M, m)
    176     det_inv = mod_inverse(det_K, m)
    177 except ValueError:
--> 178     raise NonInvertibleMatrixError('Matrix is not invertible (mod %d)' % m)
    180 K_adj = M.adjugate()
    181 K_inv = M.__class__(N, N,
    182         [det_inv * K_adj[i, j] % m for i in range(N) for j in range(N)])

NonInvertibleMatrixError: Matrix is not invertible (mod 26)

So this error has nothing to do with the mix of numpy and sympy, since it is working with a sympy Matrix.

The common numeric matrix inverse works:

In [6]: np.linalg.inv(key)
Out[6]: 
array([[-0.05515371, -0.01175407,  0.0994575 ],
       [ 0.01898734,  0.06962025, -0.05063291],
       [ 0.04520796, -0.07233273,  0.02230259]])

and the equivalent fractions version

In [9]: Matrix(key).inv()
Out[9]: 
⎡-61    -13     55 ⎤
⎢────   ────   ─── ⎥
⎢1106   1106   553 ⎥
⎢                  ⎥
⎢        11        ⎥
⎢3/158  ───   -4/79⎥
⎢       158        ⎥
⎢                  ⎥
⎢  25   -40    37  ⎥
⎢ ───   ────  ──── ⎥
⎣ 553   553   1659 ⎦

Trying other mod:

In [15]: Matrix(key).inv_mod(5)
Out[15]: 
⎡4  2  0⎤
⎢       ⎥
⎢1  2  4⎥
⎢       ⎥
⎣0  0  3⎦

It also works for other powers of 5.

I don't think you need to convert sympy matrix objects to numpy, since sympy handles matrix multiplication (with the same @ operator), and you are only working with 2d Matrices - you don't need the 'batch' functionality of the numpy matmul.

So for example:

In [32]: M = Matrix(key)
In [33]: M1= M.inv_mod(5)
In [34]: M@M1
Out[34]: 
⎡51  60  155⎤
⎢           ⎥
⎢55  56  85 ⎥
⎢           ⎥
⎣75  60  96 ⎦

Sticking with sympy avoids the float issues of numeric inverse.

In [38]: [email protected]()
Out[38]: 
⎡1  0  0⎤
⎢       ⎥
⎢0  1  0⎥
⎢       ⎥
⎣0  0  1⎦

In [39]: [email protected](key)
Out[39]: 
array([[1.00000000e 00, 2.22044605e-16, 0.00000000e 00],
       [0.00000000e 00, 1.00000000e 00, 1.24900090e-16],
       [1.11022302e-16, 0.00000000e 00, 1.00000000e 00]])

CodePudding user response：

First of all, array and matrix are 2 different things.

What are the differences between numpy arrays and matrices? Which one should I use?

Second inv function takes a matrix(not array) as input and computes it's inverse.