# TP 15 correction : Matrices
# BCPST1B 2025-2026
# Lycée Hoche, Versailles
# L.-C. LEFÈVRE

#%% fonctions données
# exécuter une fois pour toute la cellule

from random import randint
import numpy as np # pour tricher

# matrice nulle de taille (n, p)
def matrice_nulle(n, p):
    return [[0 for _ in range(p)] for _ in range(n)]

# matrice de coefficients au hasard entre -9 et 9, de taille (n, p)
def matrice_hasard(n, p):
    return [[randint(-9, 9) for _ in range(p)] for _ in range(n)]

# affiche la matrice, bien mise en forme, en trichant
def matrice_print(A):
    print(np.array(A))

#%% exercice 1

def taille(A):
    n = len(A)
    p = len(A[0])
    return (n, p)

# test
A = [[8, -1, 7, 4], [6, -2, 5, -3], [7, 2, 0, 7]]
matrice_print(A)
print(taille(A))

#%% exercice 2

def identité(n):
    A = matrice_nulle(n, n)
    for i in range(n):
        A[i][i] = 1
    return A

# test
A = identité(5)
matrice_print(A)

#%% exercice 3

def diagonale(L):
    n = len(L)
    A = matrice_nulle(n, n)
    for i in range(n):
       A[i][i] = L[i]
    return A

# test
L = [1, 3, 5, 7]
A = diagonale(L)
matrice_print(A)

#%% exercice 4

def somme(A, B):
    (n, p) = taille(A)
    (n2, p2) = taille(B)
    assert n == n2 and p == p2, "ça ne marche pas, revois ton cours"
    S = matrice_nulle(n, p)
    for i in range(n):
        for j in range(p):
            S[i][j] = A[i][j] + B[i][j]
    return S

# test
A = matrice_hasard(4, 5)
B = matrice_hasard(4, 5)
matrice_print(A)
matrice_print(B)
S = somme(A, B)
matrice_print(S)

#%% exercice 5

def produit_constante(A, a):
    (n, p) = taille(A)
    B = matrice_nulle(n, p)
    for i in range(n):
        for j in range(p):
            B[i][j] = a * A[i][j]
    return B

# test
A = matrice_hasard(4, 5)
a = randint(-9, 9)
matrice_print(A)
print("a = ", a)
B = produit_constante(A, a)
matrice_print(B)

#%% exercice 6

def coeff_produit(A, B, i, j):
    (n, p) = taille(A)
    (p2, q) = taille(B)
    assert p == p2, "aïe, tu devrais revoir ton cours"
    c = 0
    for k in range(p):
        c = c + A[i][k] * B[k][j]
    return c

def produit(A, B):
    (n, p) = taille(A)
    (p2, q) = taille(B)
    assert p == p2, "il faut VRAIMENT que tu revoies ton cours"
    P = matrice_nulle(n, q)
    for i in range(n):
        for j in range(q):
            P[i][j] = coeff_produit(A, B, i, j)
    return P

# test
A = matrice_hasard(2, 3)
B = matrice_hasard(3, 4)
matrice_print(A)
matrice_print(B)
P = produit(A, B)
matrice_print(P)

#%% variante
# pas besoin d'une fonction auxiliaire

def produit(A, B):
    (n, p) = taille(A)
    (p2, q) = taille(B)
    assert p == p2, "il faut VRAIMENT que tu revoies ton cours"
    P = matrice_nulle(n, q)
    for i in range(n):
        for j in range(q):
            for k in range(p):
                P[i][j] = P[i][j] + A[i][k] * B[k][j]
    return P

#%% exercice 7

# version récursive
def puissance(A, N):
    (n, p) = taille(A)
    assert n == p, "non mais sérieusement, encore ???"
    if N == 0:
        return identité(n)
    else:
        return produit(A, puissance(A, N-1))

# version itérative
def puissance_itératif(A, N):
    (n, p) = taille(A)
    assert n == p
    P = identité(n)
    for k in range(N):
        P = produit(A, P)
    return P

# test, voir cours et programme de colle
A = [[2, 1, 0], [0, 2, 1], [0, 0, 2]]
for N in range(6):
    print("N = ", N)
    P = puissance(A, N)
    matrice_print(P)

#%% exercice 8

def est_diagonale(A):
    """ renvoie True si la matrice A est diagonale, False sinon """
    (n, p) = taille(A)
    if n != p:
        return False # ou assert ; les matrices diagonales sont carrées
    for i in range(n):
        for j in range(p):
            if i != j and A[i][j] != 0:
                return False
    return True

# test
A = [[1, 0, 0], [0, 3, 0], [0, 0, 5]]
matrice_print(A)
print(est_diagonale(A))
B = [[1, 2, 0], [0, 3, 0], [0, 0, 5]]
matrice_print(B)
print(est_diagonale(B))
C = [[0, 0, 0], [0, 3, 0], [0, 0, 5]]
matrice_print(C)
print(est_diagonale(C))
D = [[0, 0, 0], [-1, 3, 0], [0, 0, 5]]
matrice_print(D)
print(est_diagonale(D))
E = [[1, 0, 0], [0, 3, 0], [0, 1, 5]]
matrice_print(E)
print(est_diagonale(E))

#%% exercice 9

def est_triangulaire_supérieure(A):
    """ renvoie True si la matrice A est triangulaire supérieure, False sinon """
    (n, p) = taille(A)
    if n != p:
        return False # les matrices triangulaires sont carrées
    for i in range(n):
        for j in range(p):
            if i > j and A[i][j] != 0:
                return False
    return True

A = [[1, 2, 3], [0, 3, -2], [0, 0, 5]]
matrice_print(A)
print(est_triangulaire_supérieure(A))
B = [[0, 2, 1], [0, 3, -2], [0, 0, 5]]
matrice_print(B)
print(est_triangulaire_supérieure(B))
C = [[1, 2, 3], [-7, 3, 0], [0, 0, 5]]
matrice_print(C)
print(est_triangulaire_supérieure(C))
D = [[1, 0, 0], [0, 3, 4], [0, 2, 5]]
matrice_print(D)
print(est_triangulaire_supérieure(D))

#%% exercice 10

def échange(A, i, j):
    (n, p) = taille(A)
    for k in range(p):
        x = A[i][k]
        A[i][k] = A[j][k]
        A[j][k] = x

def combinaison(A, a, i, b, j):
    (n, p) = taille(A)
    for k in range(p):
        A[i][k] = a * A[i][k] + b * A[j][k]

def dilate(A, a, i):
    (n, p) = taille(A)
    for k in range(p):
        A[i][k] = a * A[i][k]

#%% exercice 11

# C'est une fonction pour chercher un coefficient non-nul !
def cherche_pivot(A, r, j):
    (n, p) = taille(A)
    for i in range(r, n):
        if A[i][j] != 0:
            return i
    return None

#%% exercice 12

def échelonne(A):
    (n, p) = taille(A)
    # indice du pivot actuel
    r = 0
    # boucle sur les colonnes
    for j in range(p):
        i = cherche_pivot(A, r, j)
        # si on a trouvé un pivot : opérations comme d'habitude
        if i != None:
            échange(A, r, i)
            for k in range(r+1, n):
                combinaison(A, A[r][j], k, -A[k][j], r)
            # passer au pivot suivant
            r = r + 1
        # sinon la colonne est nulle en dessous de la ligne r :
        # on passe simplement à la colonne suivante (sans incrémenter r)
    print("Rang", r)
    return A

# 4x4 inversible
print("A1")
A1 = [[1, -1, 1, -2], [2, -1, 0, -2], [-1, 1, 0, 0], [-1, 0, 1, 1]]
matrice_print(A1)
matrice_print(échelonne(A1))
print()

# 4x4 rang 2
print("A2")
A2 = [[1, 3, 4, 1], [-1, -2, -3, 0], [0, 3, 3, 3], [1, 2, 3, 0]]
matrice_print(A2)
matrice_print(échelonne(A2))
print()

# 4x5 rang 3
print("A3")
A3 = [[-2, -4, -7, 0, 1], [1, 0, -1, 3, 1], [-1, -1, -1, -2, 0], [1, -1, -3, 4, 2]]
matrice_print(A3)
matrice_print(échelonne(A3))
print()

# 3x5 rang 2
print("A4")
A4 = [[1, -2, -1, 0, 1], [2, -4, 1, 3, -1], [-1, 2, 3, 2, -3]]
matrice_print(A4)
matrice_print(échelonne(A4))
print()

#%% exercice 13

def inverse(A):
    (n, p) = taille(A)
    assert n == p, "pffffffffff"
    # B est une copie de A et I est l'identité
    B = [[A[i][j] for j in range(n)] for i in range(n)]
    I = identité(n)
    # tout pareil au début, mais on opère sur B et sur I en même temps
    r = 0
    for j in range(n):
        i = cherche_pivot(B, r, j)
        # on *doit* trouver un pivot dans chaque colonne, sinon…
        assert i != None, "La matrice n'est pas inversible."
        échange(B, r, i)
        échange(I, r, i)
        a = B[r][j]
        for k in range(r+1, n):
            b = B[k][j]
            combinaison(B, a, k, -b, r)
            combinaison(I, a, k, -b, r)
        r = r + 1
    # ici la matrice est échelonnée et inversible
    # on remonte, en s'intéressant à la ligne n-i-1 pour i de 0 à n-1
    for i in range(n):
        a = B[n-1-i][n-1-i]
        # éliminer, dans la colonne i, les coefficients au-dessus de a
        for k in range(0, n-i-1):
            b = B[k][n-1-i]
            combinaison(B, a, k, -b, n-i-1)
            combinaison(I, a, k, -b, n-i-1)
        # puis mettre à 1 les coefficients diagonaux de B
        dilate(B, 1/a, n-1-i)
        dilate(I, 1/a, n-1-i)
    return I

# test avec la matrice 4x4 inversible
print("A1")
A1 = [[1, -1, 1, -2], [2, -1, 0, -2], [-1, 1, 0, 0], [-1, 0, 1, 1]]
B1 = inverse(A1)
matrice_print(A1)
print("inverse")
matrice_print(B1)
# test : on doit avoir l'identité
print("produit")
matrice_print(produit(A1, B1))