def zero(n,p):
    """
    Renvoie la matrice nulle a n lignes et p colonnes
    """
    mat=[]
    for i in range(n):
        ligne=[]
        for j in range(p):
            ligne.append(0)
        mat.append(ligne)
    return mat
    
def identite(n):
    """
    Renvoie la matrice identite d'ordre n
    """
    mat = zero(n,n)
    for i in range(n):
        mat[i][i] = 1
    return mat
    
def taille(mat):
    """
    Renvoie le couple nombre de lignes/nombre de colonnes de la matrice
    """
    if not mat:
        return 0,0
    else:
        return len(mat), len(mat[0])
        
def somme(mat1,mat2):
    n1,p1 = taille(mat1)
    n2,p2 = taille(mat2)
    assert (n1,p1)==(n2,p2)
    result = zero(n1,p1)
    for i in range(n1):
        for j in range(p1):
            result[i][j] = mat1[i][j] + mat2[i][j]
    return result
    
def difference(mat1,mat2):
    n1,p1 = taille(mat1)
    n2,p2 = taille(mat2)
    assert (n1,p1)==(n2,p2)
    result = zero(n1,p1)
    for i in range(n1):
        for j in range(p1):
            result[i][j] = mat1[i][j] - mat2[i][j]
    return result
    
def prod_sc(x,mat):
    n,p=taille(mat)
    result = zero(n,p)
    for i in range(n):
        for j in range(p):
            result[i][j] = x*mat[i][j]
    return result
    
def transposee(mat):
    n,p=taille(mat)
    result = zero(p,n)
    for i in range(p):
        for j in range(n):
            result[i][j] = mat[j][i]
    return result
    
def produit(mat1,mat2):
    n1,p1 = taille(mat1)
    n2,p2 = taille(mat2)
    assert (p1 == n2)
    result = zero(n1,p2)
    for i in range(n1):
        for j in range(p2):
            coef=0
            for k in range(p1):
                coef += mat1[i][k] * mat2[k][j]
            result[i][j] = coef
    return result
    
def decoupe(mat):
    n,p=taille(mat)
    a11 = [[mat[i][j] for j in range(n//2)] for i in range(n//2)]
    a12 = [[mat[i][j+n//2] for j in range(n//2)] for i in range(n//2)]
    a21 = [[mat[i+n//2][j] for j in range(n//2)] for i in range(n//2)]
    a22 = [[mat[i+n//2][j+n//2] for j in range(n//2)] for i in range(n//2)]
    return a11,a12,a21,a22
    
def recolle(a11,a12,a21,a22):
    n,p = taille(a11)
    mat = zero(2*n,2*n)
    for i in range(n):
        for j in range(n):
            mat[i][j] = a11[i][j]
            mat[i][j+n] = a12[i][j]
            mat[i+n][j] = a21[i][j]
            mat[i+n][j+n] = a22[i][j]
    return mat
    
def strassen(a,b):
    n,p = taille(a)
    if n==1:
        return produit(a,b)
    else:
        a11,a12,a21,a22 = decoupe(a)
        b11,b12,b21,b22 = decoupe(b)
        m1 = strassen(somme(a11,a22),somme(b11,b22))
        m2 = strassen(somme(a21,a22),b11)
        m3 = strassen(a11,difference(b12,b22))
        m4 = strassen(a22,difference(b21,b11))
        m5 = strassen(somme(a11,a12),b22)
        m6 = strassen(difference(a21,a11),somme(b11,b12))
        m7 = strassen(difference(a12,a22),somme(b21,b22))
        c11 = somme(m1,somme(difference(m4,m5),m7))
        c12 = somme(m3,m5)
        c21 = somme(m2,m4)
        c22 = somme(difference(m1,m2),somme(m3,m6))
        c = recolle(c11,c12,c21,c22)
        return c
        
def affiche_naif(mat):
    for ligne in mat:
        for coef in ligne:
            print(coef,end=" ")
        print("")
        
def plus_long_coef(mat):
    longueur = 0
    for ligne in mat:
        for coef in ligne:
            n=len(str(coef))
            if n > longueur:
                longueur = n
    return longueur
    
def ajuste_taille(n,p):
    s= str(n)
    k=len(s)
    if k < p:
        if (p-k)%2 == 0:
            return " "*((p-k)//2)+s+" "*((p-k)//2)
        else:
            return " "*((p-k)//2)+s+" "*((p-k)//2)+" "
    else:
        return str(n)
            
def affiche_matrice(mat):
    longueur = plus_long_coef(mat)
    for ligne in mat:
        for coef in ligne:
            coefstr = ajuste_taille(coef,longueur)
            print(coefstr,end=" ")
        print("")
            
from math import *
from copy import deepcopy
def plus_grand_pivot(mat,k):
    pivot=0
    ligne=k
    n,p=taille(mat)
    for i in range(k,n):
        if abs(mat[i][k]) > pivot:
            pivot=mat[i][k]
            ligne=i
    return pivot,ligne
    
def colonne_pivot(mat,k):
    n,p =taille(mat)
    pivot,ligne = plus_grand_pivot(mat,k)
    mat2 = deepcopy(mat)
    for j in range(p):
        mat2[k][j],mat2[ligne][j] = mat2[ligne][j],mat2[k][j]
    for i in range(k+1,n):
        coef1 = mat2[i][k]
        for j in range(k,p):
            mat2[i][j] = mat2[i][j]*pivot - mat2[k][j]*coef1
    return(mat2)
    
def gauss(mat):
    n,p=taille(mat)
    mat2 = deepcopy(mat)
    for k in range(n):
        mat2 = colonne_pivot(mat2,k)
    return(mat2)
    
def gauss_ind(mat):
    def aux(mat,k):
        n,_ = taille(mat)
        if k==n:
            return(mat)
        else:
            return aux(colonne_pivot(mat,k),k+1)
    return aux(mat,0)
            
    
def rang(mat):
    echel = gauss(mat)
    n,p = taille(mat)
    rk = 0
    for i in range(n):
        if echel[i][i] != 0:
            rk+=1
    return rk