Mathematics, philosophy, programming, in-line skating and everything in between. More about me…

Matrix Multiplication in Galois Fields With Python

A few weeks ago I needed to quickly verify a result of matrix multiplication. Having only a few minutes, I had to resort to a DIY solution instead of finally learning how to use numpy (yeah, still on the TO DO list…)

There was an extra condition: the matrices were over a finite (Galois) field.

The code is pretty straightforward (matrices are represented as two-dimensional lists/tuples):

def multiplyMatrices(A, B, fieldSize = 0):
	if len(A[0]) != len(B):
	raise Exception, 'The number of columns of A must equal the number of rows of B'
	
	# Prepare an empty matrix with |rows(A)| rows and |columns(B)| columns. 
	C = [ [0] * len(B[0]) for i in range(len(A)) ]
	
	for ci in range(len(C)):
		for cj in range(len(C[ci])):
			C[ci][cj] = sum([ (A[ci][i] * B[i][cj]) for i in range(len(A[0])) ])
			if fieldSize > 0:
				C[ci][cj] %= fieldSize
	return C

Let’s add a simple function for printing the results:

def printMatrix(matrix):
	print '\n'.join([ ' '.join(map(lambda x: str(x).center(3), row)) for row in matrix ])

Of course, we could get far more creative :-)

def fancyPrint(matrix):
	for (i, row) in enumerate(matrix):
		if len(matrix) == 1: # for single-row matrices
		delim = '()'
		elif not i: # first row
			delim = '/\\'
		elif i == len(matrix) - 1: # last row
			delim = '\\/'
		else: # rows in the middle
			delim = '||'
		print delim[0], ' '.join(map(lambda x: str(x).center(3), row)), delim[1]

A Few Examples

First, let us have the following matrices:

A = (
	(10, 2, 9),
	(4, 8, 7),
	(3, 8, 0)
)

B = (
	(2, 10, 6),
	(2, 10, 2),
	(6, 5, 10)
)

If we multiply them in GF(11)…

M = multiplyMatrices(A, B, 11)
fancyPrint(M)

…we find out that B = A-1.

/  1   0   0  \
|  0   1   0  |
\  0   0   1  /

In the real domain, however…

N = multiplyMatrices(A, B)
fancyPrint(N)

…this is obviously not true.

/  78 165 154 \
|  66 155 110 |
\  22 110  34 /

Second, let’s create these two matrices:

C = (
	(4, 2, 1),
	(-1, 0, 1)
)

D = (
	(3, 1),
	(1, 1),
	(2, 5)
)

We multiply them in GF(7)…

O = multiplyMatrices(C, D, 7)
P = multiplyMatrices(D, C, 7)
fancyPrint(O)
print
fancyPrint(P)

…and show that matrix multiplication is indeed not commutative.

/  2   4  \
\  6   4  /

/  4   6   4  \
|  3   2   2  |
\  3   4   0  /

3 comments Add your own…

tarun I December 19, MMXI

this is owe some . this program helpful  to me  do many  programmes.

Évariste II April 15, MMXII

For fieldSize=q∈ℕ, your code does matrix multiplication over the ring ℤ∕qℤ, which is a field iff q is prime—in which case, of course, ℤ∕qℤ ≅ GF(q). So far, so good. But for q=pⁿ, with p prime and n≥2, there's a problem, since now ℤ∕qℤ isn't a field and so cannot be isomorphic to GF(q). (Recall that there is, up to isomorphism, exactly one finite field of each prime-power order.) In particular, ℤ∕4ℤ is not a field (because 2·2=0), and hence cannot be isomorphic to GF(4), so the code does not do matrix multiplication over GF(4) when fieldSize=4, even for 1×1 matrices.

Arithmetic (including matrix multiplication) in GF(pⁿ) usually begins by representing the field concretely as GF(p)[X]∕(f(X)), where (f(X)) is the principal ideal, in the polynomial ring GF(p)[X], generated by a monic irreducible polynomial f(X) of degree n over the prime subfield GF(p), itself represented as ℤ∕pℤ. Clearly, this requires a bit of work. Although there's undoubtedly value in working out the gory details for oneself, at least theoretically, for actual calculations it's certainly easier, and probably equally instructive, to work/experiment in a computer algebra system (CAS) where this has already been done. An excellent choice here is the Python-based open-source Sage system, which can even be used online at the Sage Notebook. (Sage and Sage Notebook also include LaTeX rendering and jsMath display.)

Note: Viewing the foregoing requires decent Unicode math font coverage; adequate fonts include the free DejaVu Sans, FreeSans, or FreeSerif.

Vita III April 16, MMXII

Wow. Thank you for the explanation. I admit algebra is my weak point and I was wondering about GF(pⁿ) a bit... Sage looks nice, I'll certainly give it a try if I ever fall out of love with Mathematica.

Speak your mind

Your name*

Your e-mail* (will not be displayed)

Your website (if you have one)

Please enter the current year (I hate spam)

Post Comment

Allowed HTML tags are a, blockquote, em, code, li, ol, p, pre, strong, ul. Links to other comments in the form “[IV]” or “[4]” are detected automatically.