Computing matrix inverse mod p in Matlab

The command “inv" in Matlab compute the inverse of a matrix over the real numbers or complex numbers. If we need to compute the inverse of a matrix, whose entries are drawn from GF(p) for some prime p, then certainly we cannot apply the function inv directly. The result obtained by Matlab command inv is a matrix over real numbers, but we want a matrix whose entries are integers between 0 to p-1.

Instead, we can obtain the adjugate matrix, or the adjoint of a matrix, provided that the determinant of the matrix does not cause any integer overflow. For a matrix \mathbf{A} with integer entries, the adjoint is defined as the transpose of the cofactor matrix, and the entries of it are all integers. I cannot find a Matlab command for calculating the adjoint of a matrix, but we can calculate it indirectly by inv(A)*det(A). Here, det(A) is the determinant of matrix \mathbf{A} and is an integer.

The correct answer is simply the product of  inv(A)*det(A) and the multiplicative inverse of det(A) mod p.

The following program illustrate the procedure. A is a random matrix with entries between 0 and p-1. B is the multiplicative inverse of A mod p.

p = 11; % a prime number
A = floor(rand(4,4)*p)  % a randomly generated integer matrix

determinant = round(mod(det(A),p));

if determinant == 0
   disp('matrix is singular')
    [d r s] = gcd(determinant,p);
    B =  mod(round(inv(A)*det(A)*r),p)  % B is the inverse of A mod p
    mod(A*B,p)  % check that B times A mod p is the identity matrix

The sample output is

A =

     3     5     6     6
     6     8     2     9
     5     1     6     5
     7     5     0     4

B =

    10     0     1     3
     2     3     8     5
     8     4     0     1
     2    10     2     8

ans =

     1     0     0     0
     0     1     0     0
     0     0     1     0
     0     0     0     1


This entry was posted in Matlab program. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *