Sharedcorr-exam.sagewsOpen in CoCalc
Raw  Embed

L3 Alg. effective

Utilisation de la réduction de Smith programmée pour la correction de l'examen du 19dec17

Fonctions showop(), transf(), fsmith() définies en bas de la feuille

Ex4.

def f(l):
    if l==[]:return(l)
    elif len(l[0])==2:return(f(l[1:])+[l[0]])
    else:return(f(l[1:])+[[l[0][1],l[0][0],l[0][2]]])
l=[[4,2,1],[5,6],[1,3,-1],[2,1,-1],[2,1],[5,2,1],[4,5,2]]
print l
print f(l)
[[4, 2, 1], [5, 6], [1, 3, -1], [2, 1, -1], [2, 1], [5, 2, 1], [4, 5, 2]] [[5, 4, 2], [2, 5, 1], [2, 1], [1, 2, -1], [3, 1, -1], [5, 6], [2, 4, 1]]

Ex5.

l=[[2,2,1,3],[2,4,5,-1],[2,5,4,-2],[4,2,5],[2,6,2,-1],[4,2,3]]
print showop(l)
Q=transf(matrix.identity(6),l);show(Q)
print
show(matrix([[1,0,1,0,0,0]])*Q)
L2 + 3*L1 → L2 L4 + -1*L5 → L4 L5 + -2*L4 → L5 L2 ↔ L5 L6 + -1*L2 → L6 L2 ↔ L3
\displaystyle \left(\begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & -2 & 3 & 0 \\ 0 & 0 & 0 & 1 & -1 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & -3 & 1 \end{array}\right)
\displaystyle \left(\begin{array}{rrrrrr} 1 & 0 & 0 & -2 & 3 & 0 \end{array}\right)

Ex6.

M=matrix([[2,0],[0,3]]);show(M)
l=fsmith(M);print showop(l)
lc=[o for o in l if o[0]%2==1];print 'lc :\n',showop(lc)
ll=[o for o in l if o[0]%2==0];print 'll :\n',showop(ll)
P=transf(matrix.identity(2),ll);show('P=',P);print
Q=transf(matrix.identity(2),lc);show('Q=',Q);print
show('M=',M);print
show('transf(M,l)=',transf(M,l));print
show('P*M*Q=',P*M*Q)
\displaystyle \left(\begin{array}{rr} 2 & 0 \\ 0 & 3 \end{array}\right)
L2 + 0*L1 → L2 L1 + 1*L2 → L1 C2 + -1C1 → C2 C1 + -2C2 → C1 L2 + -3*L1 → L2 C1 ↔ C2 lc : C2 + -1C1 → C2 C1 + -2C2 → C1 C1 ↔ C2 ll : L2 + 0*L1 → L2 L1 + 1*L2 → L1 L2 + -3*L1 → L2
P= \displaystyle \left(\begin{array}{rr} 1 & 1 \\ -3 & -2 \end{array}\right)
Q= \displaystyle \left(\begin{array}{rr} -1 & 3 \\ 1 & -2 \end{array}\right)
M= \displaystyle \left(\begin{array}{rr} 2 & 0 \\ 0 & 3 \end{array}\right)
transf(M,l)= \displaystyle \left(\begin{array}{rr} 1 & 0 \\ 0 & -6 \end{array}\right)
P*M*Q= \displaystyle \left(\begin{array}{rr} 1 & 0 \\ 0 & -6 \end{array}\right)

Ex7.

A=matrix([[4,2,2,-3,-1],[-1,1,-5,3,4],[2,4,-8,3,7]]).transpose();show('matrice des coordonnées de u,v,w : A=',A)
l=fsmith(A)
print;J=transf(A,l);show('réduite de Smith de A :',J)
ll=[o for o in l if o[0]%2==0]
def inv(o): #cf corr int2
    n=len(o)
    if n==0:return(o)
    else:
        if o[n-1][0] in [3,4]:op=o[n-1]
        else:op=o[n-1][:3]+[-o[n-1][3]]
        return([op]+inv(o[:n-1]))
print 'll=',showop(ll)
print 'llinv=',showop(inv(ll))
P=transf(matrix.identity(5),ll)
Pinv=transf(matrix.identity(5),inv(ll))
show('test P*Pinv=',P*Pinv)
print;show('Pinv=',Pinv)
show('base de F:',Pinv[:,0],Pinv[:,1])
show('base de Im(A):',J[0,0]*Pinv[:,0],J[1,1]*Pinv[:,1])
show('coordonnées de (1,-1,-11,6,9) dans la base donnée de F ?',transf(matrix([[1,-1,-11,6,9]]).transpose(),ll))
print('(1,-1,-11,6,9) n\'est pas engendré par les deux premières colonnes de Pinv donc n\'est pas dans F')
show('coordonnées de (1,1,-1,0,1) dans la base donnée de F:',transf(matrix([[1,1,-1,0,1]]).transpose(),ll))
matrice des coordonnées de u,v,w : A= \displaystyle \left(\begin{array}{rrr} 4 & -1 & 2 \\ 2 & 1 & 4 \\ 2 & -5 & -8 \\ -3 & 3 & 3 \\ -1 & 4 & 7 \end{array}\right)
réduite de Smith de A : \displaystyle \left(\begin{array}{rrr} -1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right)
ll= L2 + 1*L1 → L2 L3 + -5*L1 → L3 L4 + 3*L1 → L4 L5 + 4*L1 → L5 L4 + -1*L2 → L4 L2 + -2*L4 → L2 L3 + 6*L4 → L3 L5 + -5*L4 → L5 L2 ↔ L4 llinv= L2 ↔ L4 L5 + 5*L4 → L5 L3 + -6*L4 → L3 L2 + 2*L4 → L2 L4 + 1*L2 → L4 L5 + -4*L1 → L5 L4 + -3*L1 → L4 L3 + 5*L1 → L3 L2 + -1*L1 → L2
test P*Pinv= \displaystyle \left(\begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array}\right)
Pinv= \displaystyle \left(\begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ -1 & 2 & 0 & 1 & 0 \\ 5 & -6 & 1 & 0 & 0 \\ -3 & 3 & 0 & 1 & 0 \\ -4 & 5 & 0 & 0 & 1 \end{array}\right)
base de F: \displaystyle \left(\begin{array}{r} 1 \\ -1 \\ 5 \\ -3 \\ -4 \end{array}\right) \displaystyle \left(\begin{array}{r} 0 \\ 2 \\ -6 \\ 3 \\ 5 \end{array}\right)
base de Im(A): \displaystyle \left(\begin{array}{r} -1 \\ 1 \\ -5 \\ 3 \\ 4 \end{array}\right) \displaystyle \left(\begin{array}{r} 0 \\ 6 \\ -18 \\ 9 \\ 15 \end{array}\right)
coordonnées de (1,-1,-11,6,9) dans la base donnée de F ? \displaystyle \left(\begin{array}{r} 1 \\ 9 \\ 38 \\ -18 \\ -32 \end{array}\right)
(1,-1,-11,6,9) n'est pas engendré par les deux premières colonnes de Pinv donc n'est pas dans F
coordonnées de (1,1,-1,0,1) dans la base donnée de F: \displaystyle \left(\begin{array}{r} 1 \\ 1 \\ 0 \\ 0 \\ 0 \end{array}\right)

Fontions prédéfinies

def showop(o): # affichage d'une liste d'opérations
    l=""
    for op in o:
        if op[0]==1:l=l+"C"+str(op[1])+" + "+str(op[3])+"C"+str(op[2])+" → C"+str(op[1])+"\n"
        elif op[0]==2:l=l+'L'+str(op[1])+' + '+str(op[3])+'*L'+str(op[2])+' → L'+str(op[1])+"\n"
        elif op[0]==3:l=l+'C'+str(op[1])+" ↔ C"+str(op[2])+"\n"
        elif op[0]==4:l=l+'L'+str(op[1])+" ↔ L"+str(op[2])+"\n"
    return(l)

import copy #B=copy.deepcopy(A)
def transf(A,o): #transformation d'une matrice A suivant la liste d'opération o
    B=copy.deepcopy(A) #sinon A est modifié
    for op in o:
        if op[0]==1:B[:,op[1]-1]=B[:,op[1]-1]+op[3]*B[:,op[2]-1]
        elif op[0]==2:B[op[1]-1,:]=B[op[1]-1,:]+op[3]*B[op[2]-1,:]
        elif op[0]==3:
            C=B[:,op[1]-1];B[:,op[1]-1]=B[:,op[2]-1];B[:,op[2]-1]=C
        elif op[0]==4:
            L=B[op[1]-1,:];B[op[1]-1,:]=B[op[2]-1,:];B[op[2]-1,:]=L
    return(B)

def fsmith(M,verif=false):
    A=copy.deepcopy(M) #sinon M est modifié
    if verif:show(A)
    p=A.nrows();q=A.ncols()
    L=[abs(A[i][j]) for i in range(p) for j in range(q)]
    if p*q==0 or max(L)==0:
        #print([]);
        return([])
    else:
        a=min(L[i] for i in range(p*q) if L[i]!=0)
        k=L.index(a);i0=k//q;j0=k%q;a=A[i0][j0] #a avec signe
        l=[i for i in range(p*q) if L[i]%a!=0]
        if verif:print '(verif) min,position =',[a,i0,j0]#verif
        if l==[]:  #pivot suivant a
            o=[[1,j+1,j0+1,-A[i0][j]/a] for j in [0..q-1] if j!=j0]\
                + [[2,i+1,i0+1,-A[i][j0]/a] for i in [0..p-1] if i!=i0]
            if j0!=0:o=o+[[3,1,j0+1]]
            if i0!=0:o=o+[[4,1,i0+1]]
            if verif:print '(verif) pivot',showop(o);show(transf(A,o))
            return(o+[[op[0],1+op[1],1+op[2]]+op[3:] for op in fsmith(transf(A,o).submatrix(1,1),verif)])#    
        else: #vers l'apparition du pgcd des coeff de A comme coeff de A
            k=min(l);i1=k//q;j1=k%q;b=A[i1][j1]
            if verif:print '(verif) coef non multiple de min, position =',[b,i1,j1]
            if A[i0][j1]%a != 0:
                o=[[1,j1+1,j0+1,-(A[i0][j1]//a)]]
            elif A[i1][j0]%a != 0:
                o=[[2,i1+1,i0+1,-(A[i1][j0]//a)]]
            else:
                o=[[2,i1+1,i0+1,-(A[i1][j0]//a)],[2,i0+1,i1+1,1],\
                   [1,j1+1,j0+1,-(((1-A[i1][j0]//a)*A[i0][j1]+b)//a)]] # Il y a une erreur [2,i0,i1,1] dans TP-smith-corr et dans int2 qui si elle n'est pas corrigée conduit à une réponse fausse pour l'ex6
            if verif:print '(verif) vers pgcd',showop(o);show(transf(A,o))
            return(o+fsmith(transf(A,o),verif))