from fractions import * def copyRationalMatrix(a): m = len(a) assert(m > 0) n = len(a[0]) assert(n > 0) b = [] for i in range(m): assert(len(a[i]) == n) row = [Fraction(a[i][j]) for j in range(n)] b.append(row) return b def showRationalMatrix(a): res = "" m = len(a) n = len(a[0]) maxLen = 0 for i in range(m): for j in range(n): txt = str(a[i][j]) l = len(txt) if l > maxLen: maxLen = l for i in range(m): if i > 0: res += '\n' # Line delimiter res += '[' for j in range(n): if j > 0: res += ' ' # Element delimiter txt = str(a[i][j]) l = len(txt) for k in range(maxLen - l): res += ' ' res += txt res += ']' return res def swapMatrixRows(a, i, k): assert(0 <= i and i < len(a) and 0 <= k and k < len(a)) if i == k: return n = len(a[i]) assert(n == len(a[k])) for j in range(n): (a[i][j], a[k][j]) = (a[k][j], -a[i][j]) def addMatrixRows(a, k, i, r): assert(0 <= i and i < len(a) and 0 <= k and k < len(a)) n = len(a[i]) assert(len(a[k]) == n) for j in range(n): a[k][j] += a[i][j]*r def echelonFormOfRationalMatrix(a): b = copyRationalMatrix(a) m = len(b) # number of rows n = len(b[0]) # number of columns i = 0 # number of rows processed j = 0 # number of columns processed while i < m and j < n: # 1. Looking for nonzero element in j-th column # starting from i-th row iMax = i for k in range(i, m): if b[k][j] != 0: iMax = k break if b[iMax][j] == 0: # Zero column j += 1 continue assert(b[iMax][j] != 0) if iMax != i: swapMatrixRows(b, i, iMax) assert(b[i][j] != 0) # 2. Annihilate elements of j-th column, # starting from i+1-th row c = b[i][j] for k in range(i+1, m): addMatrixRows(b, k, i, -b[k][j]/c) i += 1 j += 1 return (b, i) def copyRealMatrix(a): m = len(a) assert(m > 0) n = len(a[0]) assert(n > 0) b = [] for i in range(m): assert(len(a[i]) == n) row = [float(a[i][j]) for j in range(n)] b.append(row) return b def showRealMatrix(a): res = "" m = len(a) n = len(a[0]) maxLen = 0 for i in range(m): for j in range(n): # txt = str(a[i][j]) txt = "{0:.4f}".format(float(a[i][j])) l = len(txt) if l > maxLen: maxLen = l for i in range(m): if i > 0: res += '\n' # Line delimiter res += '[' for j in range(n): if j > 0: res += ' ' # Element delimiter # txt = str(a[i][j]) txt = "{0:.4f}".format(float(a[i][j])) l = len(txt) for k in range(maxLen - l): res += ' ' res += txt res += ']' return res def echelonFormOfRealMatrix(a, eps = 1e-8): b = copyRealMatrix(a) m = len(b) # number of rows n = len(b[0]) # number of columns i = 0 # number of rows processed j = 0 # number of columns processed while i < m and j < n: # 1. Looking for element in j-th column with maximal abs. value, # starting from i-th row iMax = i vMax = abs(b[i][j]) for k in range(i + 1, m): if abs(b[k][j]) > vMax: iMax = k; vMax = abs(b[k][j]) if vMax <= eps: # Zero column # Replace small numbers by zeroes for k in range(i, m): b[k][j] = 0.0 j += 1 continue assert(abs(b[iMax][j]) > eps) if iMax != i: swapMatrixRows(b, i, iMax) assert(abs(b[i][j]) > eps) # 2. Annihilate elements of j-th column, # starting from i+1-th row c = b[i][j] for k in range(i+1, m): addMatrixRows(b, k, i, -b[k][j]/c); b[k][j] = 0.0 i += 1 j += 1 return (b, i) def determinantOfRationalMatrix(a): if len(a) == 0 or len(a) != len(a[0]): raise ValueError("Determinant of non-square matrix") (b, rank) = echelonFormOfRationalMatrix(a) d = b[0][0] for i in range(1, len(b)): d *= b[i][i] return d def determinantOfRealMatrix(a, eps = 1e-8): if len(a) == 0 or len(a) != len(a[0]): raise ValueError("Determinant of non-square matrix") (b, rank) = echelonFormOfRealMatrix(a, eps) d = b[0][0] for i in range(1, len(b)): d *= b[i][i] return d def multiplyMatrices(a, b): if len(a) == 0 or len(a[0]) == 0: raise ValueError("Empty matrix a") if len(b) == 0 or len(b[0]) == 0: raise ValueError("Empty matrix b") rows_a = len(a) cols_a = len(a[0]) rows_b = len(b) cols_b = len(b[0]) if cols_a != rows_b: raise ValueError("Matrices cannot be multiplied") # Create a zero matrix of size rows_a * cols_b zeroLine = [0]*cols_b c = [ zeroLine.copy() for i in range(rows_a) ] for i in range(rows_a): for j in range(cols_b): for k in range(cols_a): c[i][j] += a[i][k]*b[k][j] return c