1 MATRICI PǍTRATE DE ORDIN 2

I.    RIDICAREA LA PUTERE A UNEI MATRICI PǍTRATE DE ORDIN 2

٭ În  ceea ce urmează vom folosi următoarele notaţii :

     , S=a+d  ,   D=ad-bc  ,      ;  a,b,c,d C (am notat cu C mulţimea numerelor complexe).

Presupunem cunoscută identitatea:

A2=SA-DI        (R I.1)

Oricum, se poate verifica foarte uşor. În acest capitol vom da o generalizare a relatiei (R I.1) pentru puteri naturale ale lui A .

        ٭ Înmulţind relaţia (R I.1) cu An-1 obţinem An+1=SAn-DAn-1.
De aici rezultă că putem să considerăm identitatea
      (R I.2)       dacă definim produsul mixt

  unde x,y,z,w C iar M,N sunt matrici pătrate de ordin2.

Ceea ce e important pentru noi este că produsul acesta are proprietatea asociativităţii mixte următoare :
  unde x,y,z,w,x’,y’,z’,w’ C iar M şi N sunt matrici pătrate de ordin 2 cu elemente numere complexe.Aceasta se poate verifica direct prin calcul.

    ٭ Dacă notăm   din relaţia (R I.2) , prin iterare repetată  şi folosind asociativitatea mixtă , rezultă :

 
Deci avem relatia          n≥1        ;     (R I.3)
 care de altfel se poate verifica prin inducţie.

Ceea ce este remarcabil aici este că H are un element egal cu zero ; aceasta ne dă posibilitatea să calculăm Hn şi în cele din urmă An+1.

٭ Calculul lui Hn şi al lui An+1:
Notăm   ; atunci din relaţia    Hn+1=H Hn    rezultă :

  . De aici rezultă :
xn+1=Sxn-Dzn                                                               xn+1=Sxn - Dxn-1
yn+1=Syn-Dwn                                                      yn+1=Syn - Dyn-1            (R I.4)
zn+1=xn                                                                              zn+1=xn
wn+1=yn                                                                             wn+1=yn

Fie p şi q rădăcinile ecuaţiei   ; presupunem că p≠q .
Atunci  şirurile  xn=a1pn+b1qn     şi     yn= a2pn+b2qn       sunt soluţii pentru relaţiile (R I.4) , ceea ce se poate verifica direct prin calcul.
            Numerele a1,b1 şi a2,b2 rezultă din condiţiile iniţiale    şi   
   .    H0=I  deoarece presupunem    det H=D≠0 .
 Rezultă:   x0=1 , y0=0       şi      x1=S , y1= -D  . Aceasta permite să scriem relaţiile :

a1+b1=x0=1                         a2+b2=y0=0
a1p+b1q=x1=S                     a2p+b2q=y1= -D

De aici rezultă printr-un calcul simplu că:
   . De aici deducem :

                                                        
                           Folosind relaţia (R I.3) putem calcula An+1 ; din ea rezultă:
                                                
                    
                    An+1=xnA+ynI=       n≥1       (R I.5)
                     unde p,q sunt rădăcinile distincte ale ecuaţiei   .

II GENERALIZAREA RELAŢIEI :  An+1=    
       
        În determinarea relatiei (R I.5) am folosit faptul că p≠q şi că D≠0. În continuare vom găsi o formulă pentru An care este mai generală pentru că nu depinde de aceste condiţii .

    Notăm Xn=  ; p+q=S şi pq=D  deoarece p,q verifică ecuaţia   .
            Şirul Xn  verifică relaţia de recurenţă Xn+1=SXn – DXn-1 : Într-adevăr SXn – DXn-1= = =Xn+1.De aceea dăm o nouă definiţie pentru Xn

Definiţia 1: Xn+1=def=SXn – DXn-1  cu valorile iniţiale X1=1 şi X2=S  şi   n≥2   ;    (R II.1)

Observaţia1 : termenii X1, X2 , X3 , ... , Xn , ...sunt definiţi independent de relaţiile p≠q şi D≠0
Observaţia2 :putem defini cu aceeaşi relaţie de recurenţă termenii X0 , X -1 , X -2 , … dacă impunem condiţia suplimentară D≠0 . Într-adevăr :

n=1 implică X1+1=SX1 – DX0 adică S= S∙1 – D∙X0 de unde rezultă X0=0 deoarece D≠0 .
n=0 implică X0+1=SX0 – DX0-1adică 1=S∙0 - D∙X -1  de unde rezultă  deoarece D≠0.
n= -1implică X -1+1=SX -1 – DX -1-1  adică    deoarece D≠0.

   În general   .

Definiţia 2 :Fie      , S=a+d  ,   D=ad-bc  ,      ;  a,b,c,d C ; definim şirul de matrici :          An+1=def=Xn+1A- XnD I    n≥1 ;     (R II.2)    

    Dacă D≠0  atunci   An+1=def=Xn+1A- XnD I    Z       (R’II.2)   este un şir de matrici definit pentru orice întreg n (vezi obs.2 din def1).
                     Aici şirul Xn este cel din  Definiţia 1.

Vom demonstra ca An+1=An+1  în 2 etape : n≥1 si n≤0

Teorema 1 : An+1=An+1  pentru orice n≥1.
Demonstraţia o facem prin inducţie :
n=1 ; trebuie arătat că A2=A2 ;dar A2= A1+1=def2= X1+1A- X1D I=def1=SA-1∙D I =(R I.1)=A2

Presupunem că Ak+1=Ak+1 , unde k≥1  e fixat ; atunci  :
        
         Ak+2=Ak+1 A =Ak+1 A=def2= (Xk+1 A – Xk D I ) A = Xk+1 A2 – Xk D I A=(R I.1)=           
                              =Xk+1 (S A – D I) – Xk D A = (S Xk+1 – D Xk) A – Xk+1 D I =def1=
                   =Xk+2 A – Xk+1 D I=def2= Ak+2.
 Rezultă :Ak+2=Ak+2  şi demonstraţia este completă. Deci:
                  An+1=An+1=Xn+1A- XnD I , n≥1.       (R II.3)
Vom extinde teorema1 şi pentru exponenţi întregi negativi:

Teorema 2 : Dacă D≠0 atunci An+1=An+1  pentru orice întreg n.

Demonstraţia o facem prin inducţie descendentă pentru toate valorile întregi  n≤0 deoarece pentru n≥1 este deja făcută. Conform obs.2 din def1, Xn este definit şi pentru orice număr n≤0 deoarece D≠0. Reţinem valorile deja determinate:
 

Dacă n=0 atunci A1= A0+1=def2=X0+1A- X0D I=1∙A- 0∙D I=A=A1. Deci A1=A1.
Dacă n= -1 atunci A0=A -1+1=def2=X -1+1A- X -1D I= =I=A0 . Deci A0=A0
   Fie n= -2.
Deoarece det A=D≠0 există A-1.Atunci din relaţia A2=SA-DI  prin înmulţirea ei cu A-1 obţinem A=S I – DA-1 de unde rezultă că
                                       
Dar A -1=A -2+1=def2= X -2+1A- X -2D I=X -1A- X -2D I=
                          ; rezultă:

                                   (R II.4)
Presupunem Ak+1=Ak+1  unde k≤-2 este fixat.

Atunci Ak=A-1Ak+1=A-1Ak+1=(R II.4),def2=    
   
              Deci din Ak+1=Ak+1  rezultă Ak=Ak . Inducţia descendentă este probată şi teorema 2 este demonstrată.Deci :
             
 An+1=An+1=Xn+1A- XnD I oricare ar fi n Z , dar cu condiţia D≠0.  (R II.5)

TREBUIE REŢINUTǍ CONCLUZIA:
            Dacă      , S=a+d  ,   D=ad-bc , atunci rezultă că :
1)    An+1=Xn+1A - XnD I  pentru orice n≥1 , unde şirul Xn este definit de relaţia           
      Xn+1=SXn – DXn-1    cu valorile iniţiale X1=1 şi X2=S .
2)    Dacă D≠0 relaţia An+1=Xn+1A- XnD I  este valabilă pentru orice număr întreg n .
      Facem  precizarea că şirul Xn este definit acum pentru orice număr întreg n cu   
      aceeaşi relaţie  Xn+1=SXn – DXn-1   şi valorile iniţiale X1=1 şi X2=S.



III   STUDIUL ŞIRULUI Xn ŞI CÂTEVA APLICAŢII


٭Să vedem ce se întâmplă cu şirul Xn+1=SXn – DXn-1 dacă ecuaţia   are rădăcinile p şi q egale :
Teorema 1 : Dacă rădăcinile ecuaţiei   sunt egale (q=p≠0) atunci soluţia recurenţei Xn+1=SXn – DXn-1  este şirul Xn=nqn-1 , n≥1.

Demonstraţie:   Avem relaţiile S=2q şi D=q2 . Atunci rezultă că:
                         SXn – DXn-1=2q∙ nqn-1- q2∙(n-1)qn-2=(n+1)qn=Xn+1 .
                         În plus avem îndeplinite condiţiile iniţiale X1=1q1-1=1 şi  X2=2q2-1=2q=S .

Consecinţă : An+1=Xn+1A- XnD I=(n+1)qnA- nqn-1q2 I=qn[(n+1)A- nqI ] . Relaţia este valabilă şi pentru n≤0 deoarece D=q2≠0.

Exemplu:   , S=2 , D=1 ; ecuaţia  are soluţiile p=q=1 . Rezultă că
An+1= 1n[(n+1)∙A- n∙1∙I ]=  ; deoarece D=1≠0 putem considera valoarea   n= -2 ; atunci  obţinem :   .
٭Acum considerăm un exemplu în care S=0 . Fie   . Avem S=0 şi D=5.
Din Xn+1=SXn – DXn-1 rezultă :
Xn+1=0∙Xn – 5∙Xn -1 adică Xn+1= -5Xn -1 ; deoarece X1=1 şi X2=S=0 rezultă
X2k=0  şi X2k+1=(-5)k ; atunci  avem următoarele relaţii ce rezultă din (R II.5) :

A2k+1=X2k+1A- X2k5 I=(-5)kA    şi   A2k=X2kA- X2k -1∙ 5∙ I=(-5)kI  ,

ceea ce se poate scrie condensat astfel:
 

Relaţia este valabilă şi pentru n≤1 deoarece D≠0.
Generalizarea cazului S=0 este imediată şi o lăsăm pe seama cititorului.
٭Considerăm şi un exemplu în care D=0 . Fie   . Avem S=8 şi D=0.
Din Xn+1=SXn – DXn-1 rezultă Xn+1=8∙Xn – 0∙Xn-1 . Rezultă Xn+1=8n iar An+1=Xn+1A- XnD I implică      An+1=8n ∙A- 8n-1∙0∙ I=8n∙A.
Generalizarea cazului D=0 este imediată şi o lăsăm pe seama cititorului.
    
٭Dacă S=D=0 atunci din identitatea A2=SA-DI rezultă A2=0. Atunci dacă n≥3 rezultă
              An=A2∙An-2=0∙An-2=0

1 Din Xn+1=SXn – DXn-1 rezultă o formulă combinatorială pentru Xn+1 dacă observăm şi generalizăm următoarele relaţii :
X1=1
X2=S
X3=SX2- DX1=S2- D
X4=SX3- DX2=S3- 2SD
X5=SX4- DX3=S4- 3S2D+D2
X6=SX5- DX4=S5- 4S3D+3SD2
X7=SX6- DX5=S6- 5S4D+6S2D2- D3
X8=SX7- DX6=S7- 6S5D+10S3D2- 4SD3

Dacă citim triunghiul lui Pascal pe diagonală de jos în sus şi de la stânga la dreapta în sensul indicat de puncte vedem chiar coeficienţii dezvoltării lui Xn+1 :

 
De aceea putem presupune că termenul Sn-2iDi din dezvoltarea lui Xn+1
are coeficientul  . Intuiţia nu ne înşeală pentru că se poate demonstra :

Teorema 2 :
 Şirul Xn+1 din capitolul II Definiţia 1 în cazul n≥0 admite reprezentarea următoare :
 
                     Notăm relaţia de mai sus cu (R III.1).

Demonstraţie:
Se verifică faptul că şirul    satisface relaţia de recurenţă
Xn+1=SXn – DXn-1 şi că are aceeaşi termeni iniţiali X1=1 şi X2=S .  Verificarea recurenţei se face analizând cazurile când n este par şi când n este impar deoarece trebuie explicitată limita de sumare   =partea întreagă a numarului   .








    
٭Aplicaţia 1 .
Să se determine o matrice pătrată de ordin 2 , A , astfel încât şirul de matrici An+1 să fie periodic de perioadă n=3 .
Rezolvare : Fie   . Avem S= -1 şi D=1. Ecuaţia   are soluţiile
  şi   ; atunci folosind formula lui Moivre rezultă că

   este un şir periodic de perioadă n=3; rezultă din (R II.5) că
şi An+1=Xn+1A- Xn∙1∙ I este şir periodic de perioadă 3 ; avem că A3=X3A- X2I=0A- (-1)I=I ;
de aceea   A3k=I ; A3k+1=A ; A3k+2=A2.

De asemenea relaţia (R III.1) din teorema 2 implică
  ; de aici rezultă prin înmulţire cu (-1)n identitatea remarcabilă :

     , n≥0

٭Aplicaţia 2.    
Să se determine o matrice pătrată de ordin 2 , A , astfel încât şirul de matrici An+1 să fie periodic de perioadă n=10 .
Rezolvare: Fie  ;avem  şi D=1
iar ecuaţia   are soluţiile   şi  .
Rezultă folosind din nou formula lui Moivre că   ; aceasta ne arată că şirul Xn+1 este periodic de perioadă n=10 ; rezultă din (R II.5) că şi
An+1=Xn+1A- Xn∙1∙ I este şir periodic de perioadă n=10.Se verifică uşor că X10=0 şi X9= -1 ; atunci A10= X10A- X9∙1∙ I= 0∙A- (-1)∙1∙ I =I . De aceea  A10k+j=Aj unde 0≤j≤9 .
     



Relaţia (R III.1) din teorema 2 conduce la identitatea:
                      ,  n≥0         (R III.2)
    ٭Aplicaţia 3 .
Aici vom demonstra câteva proprietăţi ale şirului lui Fibonaci.
Şirul numerelor lui Fibonaci este definit de recurenţa Fn+1=Fn+Fn-1
şi de valorile iniţiale F1=F2=1 ; avem în tabelul de mai jos primii 18 termeni :
F1    F2    F3    F4    F5    F6    F7    F8    F9    F10    F11    F12    F13    F14    F15    F16    F17    F18
1    1    2    3    5    8    13    21    34    55    89    144    233    377    610    987    1597    2584

٭Considerăm matricea   ; vrem să calculăm An+1 cu relaţia An+1=Xn+1A- XnD I .
Avem S=1 , D= -1 ; relaţia Xn+1=SXn – DXn-1 devine Xn+1=Xn +Xn-1 , valorile iniţiale fiind
X1=1 şi X2=S=1 ; de aici rezultă că Xn+1=Fn+1 .
Atunci relaţia  (R II.5) devine :
An+1=Fn+1A- Fn(-1)I= ;(am utilizat relaţiaFn+2=Fn+1+Fn)  Ultima relaţie se mai poate scrie :
  ;

٭Deoarece det (An)=(det A)n obţinem relaţia :
 

٭Din An+m=An∙Am obţinem :
  ; de aici se pot deduce patru identităţi a căror scriere o lăsăm pe seama cititorului.

٭Relaţia (R III.1) devine :
  ; de aici deducem identitatea remarcabilă :

              n≥0           (R III.3)

٭Rădăcinile ecuaţiei   sunt   de unde rezultă că recurenţa Fn+1=Fn+Fn-1  cu condiţiile iniţiale F1=F2=1 este verificată de şirul
  ; de aici rezultă că

  ;


De aceea în relaţia (R III.2)     este interesant să vedem

ce obţinem dacă facem  înlocuirea          .

 Prin înlocuire obţinem şirul         .

Am calculat cu ajutorul unui calculator de buzunar primele 18 valori ale acestui şir :

Y1    Y2    Y3    Y4    Y5    Y6    Y7    Y8    Y9    Y10    Y11    Y12    Y13    Y14    Y15    Y16    Y17    Y18
0    1    1    0    0    0    -1    -1    0    0    0    1    1    0    0    0    -1    -1

În calcule am folosit valoarea F0=0.
Analizând aceste valori intuim că şirul Yn+1 este mărginit , ia doar valorile -1 , 0 , 1 şi este chiar periodic ( perioada este probabil n=10 ) .
Nu am demonstrat deocamdată nici una din aceste afirmaţii.
Propunem aceste probleme cititorului . (Sugerăm să folosim relaţia (R III.3) ; astfel reducem  totul la o problemă de combinări ) .
 
Aplicaţia 4 .
Vom prezenta în continuare fără detalii un sistem criptografic .
٭Chestiuni preliminare :
Considerăm aici că matricea A are elemente din corpul Zp , unde p este un număr prim mare.
Menţinem def 1 şi def 2 din cap. II ; în aceste condiţii au loc teoremele 1 şi 2 din cap. II adică
An+1=Xn+1A- XnD I    (R III.4)
٭Ideea de bază a cripto-sistemului :
-introducem textul pe care vrem să-l criptăm în elementele lui A sub formă binară
 (de exemplu fiecare caracter al textului poate fi reprezentat pe un octet iar câteva caractere alăturate formează un număr pe care îl atribuim elementului « a » al matricii A , etc. ) .
-criptarea matricii A constă în calcularea unei puteri An+1 ; An+1 reprezintă textul deja criptat sau criptotextul.
-cheia de decriptare este formată din perechea de numere (Xn+1, XnD)
    Cel care obţine în mod fraudulos criptotextul An+1, trebuie să-l ghicească pe A
(ştiindu-l doar pe An+1) , ca să ajungă la textul iniţial . Aceasta este extrem de improbabil fiindcă nu deţine cheia (Xn+1, XnD).
    Pentru cel care deţine cheia este foarte simplu să-l obţină pe A din (R III.4) :

A=(Xn+1)-1(An+1+XnD I)

٭Dacă avem de criptat un volum mare de date procedăm astfel :
    Presupunem că avem mai multe « sertare » fiecare cu cheia lui ; ca să nu purtăm după noi toate cheile încuiem în « sertarul 2 » cheia de la « sertarul 1 » , apoi încuiem în « sertarul 3 » cheia de la « sertarul 2 » şi aşa mai departe ; noi nu trebuie să păstrăm decât cheia de la ultimul « sertar ».
Sertarele conţin evident şi informatia pe care vrem să o protejăm.
    
Sertarele sunt un şir de matrici de forma :
                                   
Textul se introduce în elementele ai şi di iar cheia pentru decriptare a matricii precedente se introduce în elementele bi şi ci ; după aceste operaţiuni se criptează matricea A(i) iar cheia ei de decriptare se va introduce în matricea următoare A(i+1).
    ٭Trebuie evitate cazurile S=0 , D=0 , S2=4D deoarece atunci decriptarea poate deveni uşoară chiar fără cunoaşterea cheii ; de aceea vom folosi un caracter special w de un octet care nu are nici o semnificaţie în text dar prin introducerea căruia se modifică valoarea numerică a elementelor ai şi di până când obţinem îndeplinirea celor trei condiţii S≠0 , D≠0 , S2≠4D.
    ٭Toate calculele se fac modulo p ; de aceea numărul de caractere care formează elementele ai şi di este limitat de mărimea numărului prim p.
    ٭Putem oricând să adăugăm la text o continuare : caracterele noi vor fi introduse în matrici noi ;avantajul evident este că lungimea cheii ultimei matrici adăugate nu depinde deloc de lungimea textului pe care l-am criptat .
    ٭Numărul prim p trebuie să fie suficient de mare încât să descurajeze tentativa de a încerca toate cheile posibile.


Nota : Am utilizat o idee din cartea lui Isaac J. Shoenberg   « Privelisti matematice » ,
 Editura Tehnica -1989


                                                                             



                                                                     Prof.  VELCSOV GHEORGHE IOAN