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')
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

 

Posted in Matlab program | Leave a comment

Lecture notes for ENGG2420

Some lecture notes I typed for the course ENGG2420B “Complex analysis and Differential Equations for Engineering”:

 

 

 

 

Posted in Mathematical notes | Leave a comment

ENGG2420B

I am currently teaching a math. course on complex analysis and differential equations.

This year, I adopt the Piazza e-learning platform. The Piazza page of the course is here.

 

 

 

 

Posted in Uncategorized | Leave a comment

What is dx?

Calculus teacher: It reminds you that x is the variable in the integration.

Private math. tutor: Points will be deducted if one forgets to write it down.

Engineer: It is an infinitesimally small \Delta x.

Teacher of advanced calculus: It is the differential of the function x.

Measure theorist: We usually write d \mu instead.

Differential geometer: It is a smooth function mapping a point P in a manifold to an element in the cotangent space at P.

Algebraic geometer: Let A be a k-algebra over a field k. dx is the equivalent class 1\otimes_k x + S in the quotient (A\otimes_k A )/ S, where S is the A-submodule of A\otimes_k A generated by elements of the form x \otimes_k yz - xy\otimes_k z - xz \otimes_k y. In general, f \,dx is f \otimes_k x + S.