""" Calcul le polynome caractéristique d'une matrice,
  codé avec la contrainte de ne pas utiliser numpy
  ne vérfie pas si la matrice envoyée est légale

  Adrien B. - 2017"""

def multiply(A, B): # Multiplication matricielle canonique

    R = [[0 for i in range(len(B[0]))] for j in range(len(A))]

    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(B)):
                R[i][j] += A[i][k] * B[k][j]

    return R

def delta(i, j): #symbole de Kronecker
    if i == j:
        return 1
    else:
        return 0

def id(n): # matrice identite de rang n
    return [[delta(i,j) for i in range(n)] for j in range(n)]

# l1 <- mu1 * l1 + mu2 <- l2
# effectue les operations sur un tableau de matrices en ligne
def opLigne(matriceLigne, l1, mu1, l2, mu2):

    for i in range(len(matriceLigne[0])):
        matriceLigne[l1][i] = mu1 * matriceLigne[l1][i] + mu2 * matriceLigne[l2][i]

def lineify(A): # transforme une matrice en tableau de nombres 1D
    R = []

    for i in range(len(A)):
        for j in range(len(A[0])):
            R.append(A[i][j])

    return R

def polMin(A): #calcul le polynome minimal d'une matrice

    n = len(A)
    M, compagnon, ligneNulle = id(n), id(n+1), [0] * n * n
    puissances = [lineify(M)]
    for i in range(n):
        M = multiply(M, A)
        puissances.append(lineify(M))

    i = 0
    while puissances[i] != ligneNulle:
        pivot = 0
        while puissances[i][pivot] == 0:
            pivot += 1

        for j in range(i + 1, n+1):
            opLigne(compagnon, j, puissances[i][pivot], i, - puissances[j][pivot])
            opLigne(puissances, j, puissances[i][pivot], i, - puissances[j][pivot])

        i += 1

    res = compagnon.pop()
    dom = res[len(res)-1]
    return [i / dom for i in res] # on renvoie la solution sous forme d'un polynome unitaire

def printPolynome(P): # affiche joliment(-ish) les polynomes
    res = ""

    for i in range(len(P)):
        tmp = ""
        if P[i] == 1:
            tmp = "+ "
        elif P[i] == -1:
            tmp = "- "
        elif P[i] > 0:
            tmp = "+ " + str(P[i])
        elif P[i] < 0:
            tmp = "- " + str(abs(P[i]))

        if tmp == "":
            continue

        if i == 1:
            res = tmp + "X " + res
        elif i == 0:
            res = " " + res
        elif i >= 2:
            res = tmp + "X^" + str(i) + " " + res

    return res

matrix = [
    [1, -1, 3],
    [2, 4,  4],
    [23, 12, 9]
]

print(printPolynome(polMin(matrix)))