Inverting a Matrix Over a Finite Field

Here we illustrate inverting a matrix of finite field elements. This file is the entire Scheme code necessary for the calculation but the links below leads you to some desultory code explanations as well.

Use code in this down to “------”. Use routines matpak and trnxx.

(define (Ffield T q) (let* ((f ((T 'gfip) q))(fops ((T 'fops) f))(i->p (T 'i->p))
               (f* (car fops))(f/ (cadr fops)) (zer (i->p 0)) (p+ (T 'p+)) (p- (T 'p-)))
        (matpak zer (lambda(x) (veq x zer)) (i->p 1) p+ (lambda (a b) (p+ a (p- b))) f* f/)))

Now (Ffield (gpa p) q) gives you the set of matrix tools over GF(p^q). Below (rm (gpa p) q n) provides a random n by n matrix over GF(p^q).

(define (rm T q n) (let ((i->p (T 'i->p))(sz (expt (T 'ch) q)))
   (DoL n (lambda (d) (DoL n (lambda (d) (i->p (inexact->exact
          (floor (* (random) sz))))))))))

We use tmz to test for the identity matrix. With these tools we invert and test a random matrix:

(define (mtt p q n) (let* ((T (gpa p))(m (rm T q n))(mt (Ffield T q))
    (minv (cadr mt))(mmul (car mt))(ic (mmul m (minv m cc))))
    (list (tmz ic) m ic)))

(mtt p q n) creates an n by n matrix over GF(p^q) and checks by multiplying the matrix by its inverse.

In the code above we use cc below which depends on the definitions of exit and mer.

(define cc (mer "Singular:"))