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 for some prime , 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 .

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 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 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 . B is the multiplicative inverse of A mod .

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')
else
[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
end;

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.