from fractions import Fraction
import math

def isZero(x):
    return math.isclose(x, 0, abs_tol=1e-09)

def isZeroVector(v):
    return all(isZero(vi) for vi in v)

def addVector(v, w):
    return [vi + wi for vi, wi in zip(v, w)]

def subVector(v, w):
    return [vi - wi for vi, wi in zip(v, w)]

def mulScalarVector(alpha, v):
    return [alpha*vi for vi in v]

def equalVector(v, w):
    return isZeroVector(subVector(v, w))

def switchRow(A, i, k):    
    A[i], A[k] = A[k], A[i] #"di <-> dk"
    
def mulRow(A, i, num):  
    A[i] = mulScalarVector(num, A[i]) #"di = num*di"

def addRow(A, i, k, num):  
    A[i] = addVector(A[i], mulScalarVector(num, A[k])) #"di = di + num*dk"

def convertToFraction(A):
    if isinstance(A, list):
        return [convertToFraction(i) for i in A]
    else:
        return Fraction(A)
def printMatrix(A, sep=" "):
    if isinstance(A, list) and A:
        if isinstance(A[0], list):                  #list of list
            m, n = len(A), len(A[0])                #size of matrix
            widths = [max(len(str(di[j])) for di in A) for j in range(n)]
            rows = [sep.join(format(str(di[j]),  f">{widths[j]}") for j in range(n)) for di in A]

            print("[" + "\n".join((" [" if i > 0 else "[") + rows[i] + "]" for i in range(m)) + "]")
        else: #list
            print("[" + sep.join(str(q) for q in A) + "]")
    else:
        print(A)   

def createMatrixUnit(n):
    return [[1 if i == j else 0 for j in range(n)] for i in range(n)]

def inverse(A):
    tempM = A.copy()               
    n = len(tempM)
    ResultMatrix = createMatrixUnit(n) #Result 

    row = col = 0

    while row < n:
        #Step 1: Check if the terms on the column are zero or not
        for i in range(row, n):
            if all(isZero(tempM[row][j]) for j in range(n)):
                print("Ma trận không khả nghịch")
                return

        while col < n and all(isZero(tempM[i][col]) for i in range(row, n)):
            col += 1

        if col == n: #Echelon matrix
            break
        
        #Step 3: With the leading term from Step 2 being a≠0 , multiply the row containing it by 1/a
        a = 1/tempM[row][col]
        mulRow(tempM, row, a)
        mulRow(ResultMatrix, row, a)
        #mulScalarMatrix(ResultMatrix, 1/tempM[row][col])
            
        #Step 4: Add an appropriate multiple of the top line to each bottom line to turn the terms below the leading number into 0
        for i in range( n):

            multiplier = tempM[i][col] / tempM[row][col]
            if i == col:
                i+=1
            if i == n:
                break
            addRow(tempM, i, row, -multiplier)
            addRow(ResultMatrix, i, row, -multiplier)
                
    
        #Step 5: Repeat the steps until you get the echolon matrix.
        row += 1

    print("Ma trận nghịch đảo của A là: ")
    printMatrix(ResultMatrix)
    print("\n")