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

Matematika, filosofie, programování, in-line bruslení a vše mezi tím. Více o mně…

Násobení matic nad Galoisovými tělesy v Pythonu

Před pár týdny jsem potřeboval rychle ověřit výsledek násobení matic. Protože jsem měl jen pár minut, musel jsem se uchýlit k řešení udělej-si-sám, místo abych se konečně naučil používat numpy (ano, stále na seznamu úkolů…)

Byla zde ještě jedna okolnost: matice byly nad konečným (Galoisovým) tělesem.

Kód je poměrně přímočarý (matice jsou reprezentovány jako dvojrozměrné 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

Přidejme jednoduchou funkci pro vypisování výsledků:

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

Samozřejmě bychom mohli být o hodně kreativnější :-)

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]

Pár příkladů

Zaprvé, mějme následující matice:

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

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

Když je vynásobíme v GF(11)…

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

…zjistíme, že B = A-1.

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

Avšak v reálném oboru…

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

…to zcela zřejmě neplatí.

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

Zadruhé, vytvořme tyto dvě matice:

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

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

Vynásobíme je v GF(7)…

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

…a ukážeme tak, že násobení matic samozřejmě není komutativní.

/  2   4  \
\  6   4  /

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

RSS © MMXII Vita Smid