corr-exam.sagews

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)$

A= $\displaystyle \left(\begin{array}{rrr} 4 & -1 & 2 \\ 2 & 1 & 4 \\ 2 & -5 & -8 \\ -3 & 3 & 3 \\ -1 & 4 & 7 \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)$

%md
**Fontions prédéfinies**

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(A,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))

matrix([[1,1],[3,4]])*matrix([[2,0],[0,3]])*matrix([[2,-3],[-1,2]])

[1 0] [0 6]

A=matrix([[4,2,2,-3,-1],[-1,1,-5,3,4],[2,4,-8,3,7]]).transpose()
transf(matrix.identity(5),[[2,2,3,-1],[2,4,5,-3],[2,1,3,-2],[2,3,5,2],[2,1,3,-3],[2,2,3,-2],[2,4,3,3],[4,1,5],[4,2,3],[2,1,2,-1]])

[ 0 0 -1 0 -1] [ 0 0 1 0 2] [ 0 1 -3 0 -4] [ 0 0 3 1 3] [ 1 0 -5 0 -6]

A

[ 4 -1 2] [ 2 1 4] [ 2 -5 -8] [-3 3 3] [-1 4 7]

l=fsmith(A)

A

[ 4 -1 2] [ 2 1 4] [ 2 -5 -8] [-3 3 3] [-1 4 7]