Víťa Šmíd a.k.a. Zephyrus

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  /

Get my articles by RSS © MMXII Vita Smid