import copy from fractions import * def copyRationalMatrix(a): b = [] m = len(a) # Number of rows if m == 0: raise ValueError("Empty matrix") n = len(a[0]) # Number of columns if n == 0: raise ValueError("Empty matrix row") for i in range(m): if len(a[i]) != n: raise ValueError("Incorrect matrix row") row = [] for j in range(n): row.append(Fraction(a[i][j])) b.append(row) return b def copyRealMatrix(a): b = [] m = len(a) # Number of rows if m == 0: raise ValueError("Empty matrix") n = len(a[0]) # Number of columns if n == 0: raise ValueError("Empty matrix row") for i in range(m): if len(a[i]) != n: raise ValueError("Incorrect matrix row") row = [] for j in range(n): row.append(float(a[i][j])) b.append(row) return b def swapMatrixRows(a, i, k): if i == k: return assert(0 <= i and i < len(a)) assert(0 <= k and k < len(a)) assert(len(a[i]) == len(a[k])) n = len(a[i]) for j in range(n): (a[i][j], a[k][j]) = (-a[k][j], a[i][j]) def addMatrixLines(a, k, i, c): assert(0 <= i and i < len(a)) assert(0 <= k and k < len(a)) assert(len(a[i]) == len(a[k])) n = len(a[i]) for j in range(n): a[k][j] += c*a[i][j] def echelonFormOfRationalMatrix(a): '''For a matrix a, compute its row echelon matrix and the rank. Returns pair: (Echelon form of matrix, rank of matrix)''' b = copyRationalMatrix(a) m = len(a) # Number of rows n = len(a[0]) # Number of columns i = 0; j = 0 while i < m and j < n: # Find nonzero element in j-th column, starting # from line i imax = (-1) for k in range(i, m): if b[k][j] != 0: imax = k break if imax < 0: # Skip a zero column j += 1 continue assert(b[imax][j] != 0) # Swap rows i and imax and change a sign of one row if imax != i: swapMatrixRows(b, i, imax) r = b[i][j] for k in range(i+1, m): c = (-b[k][j])/r addMatrixLines(b, k, i, c) i += 1; j += 1 return (b, i) def showRationalMatrix(a): # First define a maximal size of matrix elements m = len(a) # Number of rows n = len(a[0]) # Number of columns assert(m > 0 and n > 0) maxSize = 0 for i in range(m): for j in range(n): s = str(a[i][j]) l = len(s) if l > maxSize: maxSize = l txt = "" # Print rows of matrix for i in range(m): if i > 0: txt += '\n' # Row delimiter # Print i-th row of matrix txt += '[' # Beginning of row for j in range(n): if j > 0: txt += ' ' # Element delimeter s = str(a[i][j]) l = len(s) if l < maxSize: txt += ' '*(maxSize - l) # Padding txt += s txt += ']' # End of row # txt += '\n' return txt def determinantOfRationalMatrix(a): (b, rank) = echelonFormOfRationalMatrix(a) d = Fraction(1) m = len(b) # Number of rows for i in range(m): d *= b[i][i] # Multiply d by diagonal element 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 def echelonFormOfRealMatrix(a, eps=1e-8): '''For a matrix a, compute its row echelon matrix and the rank. Returns pair: (Echelon form of matrix, rank of matrix)''' b = copyRealMatrix(a) m = len(b) # Number of rows n = len(b[0]) # Number of columns i = 0; j = 0 while i < m and j < n: # Find element with maximal absolute value in j-th column, starting # from line i imax = (-1) maxelem = 0.0; for k in range(i, m): if abs(b[k][j]) > maxelem: imax = k maxelem = abs(b[k][j]) if maxelem <= eps: # Clear and skip a zero column for k in range(i, m): b[k][j] = 0.0 j += 1 # Go to the next column continue assert(abs(b[imax][j]) > eps) # Swap rows i and imax and change a sign of one row if imax != i: swapMatrixRows(b, i, imax) r = b[i][j] for k in range(i+1, m): c = (-b[k][j])/r addMatrixLines(b, k, i, c) b[k][j] = 0.0 # replace very little element by strict zero i += 1; j += 1 return (b, i) def showRealMatrix(a): # First define a maximal size of matrix elements m = len(a) # Number of rows n = len(a[0]) # Number of columns assert(m > 0 and n > 0) maxSize = 0 for i in range(m): for j in range(n): # s = str(a[i][j]) s = "{0:12.4f}".format(a[i][j]) l = len(s) if l > maxSize: maxSize = l txt = "" # Print rows of matrix for i in range(m): if i > 0: txt += '\n' # Row delimiter # Print i-th row of matrix txt += '[' # Beginning of row for j in range(n): if j > 0: txt += ' ' # Element delimeter # s = str(a[i][j]) s = "{0:12.4f}".format(a[i][j]) l = len(s) if l < maxSize: txt += ' '*(maxSize - l) # Padding txt += s txt += ']' # End of row # txt += '\n' return txt def determinantOfRealMatrix(a): (b, rank) = echelonFormOfRealMatrix(a) d = 1.0 m = len(b) # Number of rows for i in range(m): d *= b[i][i] # Multiply d by diagonal element return d