Forma scara redusa a unei matrici. Transformari matricialeelementare. Descompunerea LU a unei matrici patratice

2.1 Metoda Gauss–Jordan

Metoda transformarilor elementare pe linie numita si metoda eliminarii a lui Gauss poate firafinata, prin metoda Gauss-Jordan. Si anume metoda Gauss-Jordan are ın plus doua caracter-istici:

i. In fiecare etapa, elementul pivot este fortat sa devina 1. Mai precis daca s-a fixat pivotulpe linia i ca fiind aij 6= 0, atunci transformarea Li/aij → Li conduce la pivot 1.

2. Pe langa zerouri sub pivot se creeaza prin transformari elementare pe linie, zerouri sideasupra pivotului.

O matrice scara obtinuta prin metoda Gauss-Jordan din matricea A se numeste matrice ınforma scara redusa (reduced row echelon form, prescurtat rref).

Exemplul 1. Matrici scara ın forma redusa:

1 0 −20 1 50 0 0

1 −2 0 00 0 1 00 0 0 10 0 0 0

1 0 0 −6 50 1 0 −1 20 0 1 3 −4

Observatia 2.1.1 Se poate demonstra ca forma scara redusa a unei matrici este unica, adicaindiferent de transformarile elementare pe linie aplicate obtinem aceeasi matrice redusa. Notamprin S0

A, forma scara redusa a matricii A.

Forma scara redusa este fundamentala ın algebra liniara deoarece asa cum vom arata ın cursurileurmatoare ea codifica proprietati importante ale matricii initiale, foarte utile ın rezolvarea anumeroase probleme.

Sa ilustram cateva avantaje ale reducerii matricii unui sistem de ecuatii liniare la formascara redusa. Aplicand metoda Gauss–Jordan de reducere a unui sistem liniar si neomogen de

1

2

n ecuatii cu n necunoscute, compatibil determinat:

a11 a12 . . . a1n

a21 a22 . . . a2n...

... . . ....

an1 an2 . . . ann

x1

x2...

xn

=

b1

b2...bn

⇔ Ax = b,

obtinem la sfarsitul procedurii, aplicata matricii prelungite a sistemului:

A =

a11 a12 . . . a1n

a21 a22 . . . a2n...

... . . ....

an1 an2 . . . ann

∣∣∣∣∣∣∣∣∣

b1

b2...bn

matricea echivalenta cu ea:

S0A

= [A′|s] =

1 0 · · · 00 1 · · · 0...

... · · · ...0 0 · · · 1

∣∣∣∣∣∣∣∣∣

s1

s2...

sn

= [In|s] (2.1)

Motivul pentru care forma scara redusa a matricii prelungite arata astfel este ca rangul matriciiA este n (sistemul fiind compatibil determinat) si deci forma scara redusa are n pivoti, adica nde 1 pe diagonala principala si 0 deasupra si dedesubtul pivotilor.

Sistemul de ecuatii initial Ax = b este echivalent cu sistemul definit de matricea S0A

( auaceleasi solutii). Si anume, sistemul echivalent este sistemul de matrice In si coloana termenilorliberi de elemente s1, s2, . . . , sn:

In

x1

x2...

xn

=

s1

s2...

sn

Deci solutia acestui sistem (precum si a celui initial) este:

x1 = s1

x2 = s2...

xn = sn,

(2.2)

Cu alte cuvinte solutia sistemului este ınregistrata ın ultima coloana a matricii scara redusa, S0A

.Observam ca ın deducerea solutiei din forma scara redusa am pornit de la ipoteza ca sistemul

este compatibil determinat. In realitate ınsa nu stim la ınceputul procedurii de reducere laforma scara redusa daca un sistem de n ecuatii cu n necunoscute (cu n foarte mare) este sau nu

3

compatibil determinat. Reducand ınsa matricea prelungita la forma scara redusa, dupa ultimaetapa deducem din analiza matricii reduse daca sistemul este compatibil sau nu si daca da citimsolutia ca mai sus. Si anume:

• Daca ın forma scara redusa S0A

= [A′|s], matricea A′ este matricea unitate, In, adicanumarul pivotilor din A′ este egal cu n, atunci rezulta ca rangul matricii A este n, si decisistemul Ax = b este compatibil determinat si solutia sistemului se poate citi pe ultima coloanaa formei scara redusa S0

A.;

• Daca numarul pivotilor ın submatricea formata din primele n coloane ale matricii reduseeste mai mic decat n, adica A′ 6= In, sistemul poate fi incompatibil sau compatibil nedeterminat,ın functie de relatia dintre rangul acestei matrici si al matricii prelungite.

Exemplul 2. Consideram sistemul neomogen de 5 ecuatii cu 5 necunoscute, avand matriceaprelungita:

A =

2 −1 0 5 8−5 3 3 1 −1

0 −4 1 −3 31 2 −2 0 23 6 7 2 0

∣∣∣∣∣∣∣∣∣∣

02

−451

Forma sa scara redusa este (Verificati!)

1 0 0 0 00 1 0 0 00 0 1 0 00 0 0 1 00 0 0 0 1

∣∣∣∣∣∣∣∣∣∣

−0.23321.3578

−0.8287−0.3233

0.4301

Avand 5 pivoti plasati ın submatricea matricea formata din primele 5 coloane, rezulta ca ma-tricea sistemului are are rangul 5, deci determinantul matricii sistemului este nenul si sistemuleste compatibil determinat, iar solutia lui este data de ultima coloana:

(x1 = −0.2332, x2 = 1.3578, x3 = −0.8287, x4 = −0.3233, x5 = 0.4301)

Exemplul 3. Sistemul neomogen de 5 ecuatii cu 5 necunoscute avand matricea prelungita:

A =

5 8 19 2 −11 −1 20 −5 3

−3 3 −15 0 −40 2 −3 1 22 0 1 3 6

∣∣∣∣∣∣∣∣∣∣

1−7

04

−3

are forma scara redusa:

1 0 0 1.6667 00 1 0 00 0 1 −0.3333 00 0 0 0 10 0 0 0 0

∣∣∣∣∣∣∣∣∣∣

00001

4

Observam ca numarul de pivoti ın submatricea formata din primele 5 coloane este 4, decirangul matricii sistemului este 4 iar rangul matricii prelungite este egal cu numarul de pivoti dinforma scara redusa a cesteia, adica 5. Deci sistemul este incompatibil.

Un sistem de 5 ecuatii cu 5 necunoscute a carui matrice prelungita are forma scara redusa:

1 0 0 2 00 1 0 11 00 0 1 −3 00 0 0 0 10 0 0 0 0

∣∣∣∣∣∣∣∣∣∣

1−7

3−4

0

este compatibil nederminat deoarece rangul matricii sistemului coincide cu rangul matricii pre-lungite, dar acest rang nu este maxim, adica 5.

Aceasta particularitate este exploatata la calculul inversei unei matrici patratice nesingulare.Conform definitiei inversa unei matrici patratice nesingulare, A ∈ Kn×n, este o matrice

X ∈ Kn×n, cu proprietatea caAX = In,

adica

X:,1 X:,2 X:,n

a11 a12 · · · a1n

a21 a22 · · · a2n...

... · · · ...an1 an2 · · · ann

x11 x12 . . . x1n

x21 x22 . . . x2n...

... . . ....

xn1 xn2 . . . xnn

=

1 0 . . . 00 1 . . . 0...

... . . ....

0 0 . . . 1

(2.3)

Determinarea inversei X , este echivalenta cu rezolvarea a n sisteme de ecuatii:

X:,j

a11 a12 · · · a1n

a21 a22 · · · a2n...

... · · · ...an1 an2 · · · ann

x1j

x2j...x1nj

= ej =

0...1...0

← j

(2.4)

avand drept necunoscute elementele din coloana j a inversei, j = 1, n. Folosind metoda Gauss-Jordan de rezolvare a sistemului compatibil determinat, (2.4), vom obtine ca matricea prelungita[A|ej] este echivalenta cu matricea ın forma scara redusa, [I|A−1

:,j ] unde prin A−1:,j am notat

coloana j din matricea inversa, adica solutia X:,j . Pentru reducerea matricii A la forma scararedusa, In, deci si a matricii prelungite [A|ej] se aplica o succesiune de transformari elementare.Dar ın loc sa rezolvam n ecuatii AX:,j = ej , j = 1, n, ce au aceeasi matrice A, adica sa repetam

5

de n ori aplicarea transformarilor elementare ce reduc pe A la In si pe [A|ej] la [In|A−1:,j ], putem

aplica aceleasi transformari elementare pe linie (Gauss-Jordan) matricii:

[A|e1|e2| · · · |en]

si vom obtine la ın final matricea echivalenta:

[In|A−1:,1 |A−1

:,2 | · · · |A−1:,n ] = [In|A−1]

In concluzie, daca stim ca o matrice A ∈ Kn×n este inversabila, atunci pentru a afla inversasa, constituim matricea extinsa: Ae = [A|In], pe care o transformam ın forma scara redusa[In|M ] si matricea M va fi inversa A−1.

In realitate ınsa nu stim ın prealabil daca o matrice patratica (de dimensiuni mari) este saunu singulara. Exploatand modul de mai sus de calcul al inversei, se procedeaza astfel:

• se bordeaza matricea patratica A ∈ Kn×n cu matricea unitate In si obtinem matriceaextinsa Ae = [A|In];

• se reduce matricea extinsa la forma scara redusa (Gauss-Jordan) [A|In] ↔ [A′|M ];? Daca prima jumatate a formei scara redusa, A′ (adica submatricea constituita din liniile

1, n si coloanele 1, n) este matricea unitate adica forma scara redusa este de forma:

1 0 . . . 00 1 . . . 0...

... . . ....

0 0 . . . 1

∣∣∣∣∣∣∣∣∣

a′11 a′12 . . . a′1n

a′21 a′22 . . . a′2n...

... . . ....

a′n1 a′n2 . . . a′nn

atunci matricea A este inversabila si inversa ei este:

a′11 a′12 . . . a′1n

a′21 a′22 . . . a′2n...

... . . ....

a′n1 a′n2 . . . a′nn

¥ Daca numarul pivotilor din prima jumatate a formei scara reduse este mai mic decatn (adica rangul matricii A este mai mic decat n) atunci matricea este singulara si nu admiteinversa.

De exemplu pentru matricea extinsa asociata unei matrici A ∈ R4×4:

Ae =

2 −3 7 33 5 1 −5

−4 2 −10 −25 −1 11 1

∣∣∣∣∣∣∣∣

1 0 0 00 1 0 00 0 1 00 0 0 1

forma scara redusa calculata numeric (folosind un program ce implementeaza algoritmul decalcul al formei scara) este:

6

1 0 2 00 1 −1 −10 0 0 00 0 0 0

∣∣∣∣∣∣∣∣

0 0 0.1667 0.33330 0 0.8333 0.66671 0 2.1667 1.33330 1 −4.6667 −4.3333

Submatricea formata din cele patru linii si primele patru coloane are doi pivoti, deci rangulmatricii A este 2, adica este o matrice singulara si submatricea formata din ultimele 4 coloanenu este inversa ei!

Sa parcurgem algoritmul de calcul al rangului matricii si ilustrare a inversei ın caz de matricenesingulara prin calcul direct:

Exemplul 4. Consideram matricea:

A =

1 1 11 2 21 2 3

Matricea extinsa asociata este:

Ae =

1 1 11 2 21 2 3

∣∣∣∣∣∣

1 0 00 1 00 0 1

↔

1 1 10 1 10 1 2

∣∣∣∣∣∣

1 0 0−1 1 0−1 0 1

↔

1 0 00 1 10 0 1

∣∣∣∣∣∣

2 −1 0−1 1 0

0 −1 1

↔

1 0 00 1 00 0 1

∣∣∣∣∣∣

2 −1 0−1 2 −1

0 −1 1

Deoarece forma scara redusa a matricii A este matricea unitate, ea are rangul 3, deci esteinversabila si inversa ei este:

A−1 =

2 −1 0−1 2 −1

0 −1 1

Observatia 2.1.2 Cele trei transformari elementare pe linie se pot exprima matricial.

Si anume:¥ interschimbarea a doua linii Lj ↔ Lk a unei matrici A ∈ Km×n este echivalenta cu

ınmultirea matricii A la stanga cu matricea permutare Pπ, unde π este permutarea:

π =

1 2 . . . j . . . k . . . m↓ ↓ . . . ↓ . . . ↓ . . . ↓1 2 . . . k . . . j . . . m

7

Matricea permutare corespunzatoare este matricea notata Pjk:

j k

j

k

1...

.

.

.

. . ....

.

.

. 01

.

.

....

. . . . . . . . . 0 . . . . . . . . . 1

.

.

. 1...

.

.

.. . .

.

.

.

.

.

. 1...

. . . . . . . . . 1 . . . . . . . . . 0

1

0 . . .

1

¥ ınmultirea liniei Lk cu numarul nenul a este echivalenta cu ınmultirea matricii A lastanga cu matricea urmatoare:

k

1...

. . .... 0

1 0

. . . . . . 0 a 0

0 1

0 . . . 0

0 1

¥ transformarea elementara aLj + Lk → Lk, a 6= 0, j 6= k, efectuata asupra matricii A,este echivalenta cu ınmultirea lui A la stanga cu matricea:

j

k

1...

.

.

.

. . ....

.

.

. 0. . . . . . 1 . . . 0

.

.

.. . .

.

.

.

. . . . . . a . . . 1

. . .0

1

Numim ın continuare cele trei tipuri de matrici, matrici elementare de tip 1, 2, 3, si lenotam generic cu E. Remarcam ca matricile elementare se obtin efectuand transformarile core-spunzatoare asupra matricii unitate.

Fie A o matrice de tip m × n asupra careia se efectueaza transformari elementare pe linie,reprezentate de matricile Pjk, de tipul 1, Ej(a) - tipul 2 si respectiv Ejk(a)- tipul 3.

8

Observatia 2.1.3 O matrice de tipul 3, Ejk(a) = (eIJ), este, pentru j < k, o matrice inferiortriunghiulara (adica eIJ = 0, pentru orice I < J) si respectiv o matrice superior triunghiularadaca j > k (superior triunghiulara ınseamna ca eIJ = 0 pentru orice I > J).

Definitia 2.1.1 O matrice inferior (superior) triunghiulara care are toate elementele de pe di-agonala principala egale cu 1, se numeste matrice inferior (superior) triunghiulara, diagonalunitara.

Exemplul 5.

E13(7) =

1 0 00 1 07 0 1

, iar E32(−5) =

1 0 00 1 −50 0 1

Matricea E13(7), cu 1 < 3 este inferior triunghiulara, diagonal unitara, iar matricea E32, cu3 > 2, este superior triunghiulara diagonal unitara.

Forma generala a unei matrici, L, inferior triunghiulara, diagonal unitara, respectiv a uneimatrici U , superior triunghiulara, diagonal unitara, este:

L =

1 0 0 . . . 0`21 1 0 . . . 0`31 `32 1 . . . 0...

...... . . .

...`n1 `n2 `n3 . . . 1

, U =

1 u12 u13 . . . u1n

0 1 u23 . . . u2n

0 0 1 . . . u3n...

...... . . .

...0 0 0 . . . 1

Se poate verifica, folosind definitia produsului a doua matrici patratice ca:

a) Produsul a doua matrici inferior (superior) triunghiulare, diagonal unitare este o matricecu aceeasi proprietate;

b) inversa unei matrici inferior (superior) triunghiulare, diagonal unitara este si ea inferiortriunghiulara, diagonal unitara.

Proprietati ale matricilor elementare:

a) Matricile elementare sunt inversabile si inversa fiecareia este de acelasi tip ca si matricea

9

directa, deoarece transformarile elementare pe linie sunt reversibile:

1 : ALj↔Lk−→ A′ L′j↔L′k−→ A,

adica PjkA = A′ si PjkA′ = A ⇔ PjkPjkA

′ = A′ ⇔ PjkPjk = Im ⇔ P−1jk = Pjk

2 : AaLj→Lj−− −→ A′

(1/a)L′j→L′j−− −→ A, a 6= 0. Exprimand aceste transformari matricial, avem:Ej(a)A = A′si Ej(1/a)A′ = A ⇔ Ej(a)Ej(1/a)A′ = A′ ⇔ Ej(a)Ej(1/a) = Im ⇔⇔ (Ej(a))−1 = Ej(1/a) .

3 : AaLj+Lk→Lk−−−− −→ A′

(−a)L′j+L′k→L′k−−−− −→ A, a 6= 0, si la fel ın eprimarea matriciala :Ejk(a)A = A′ iar Ejk(−a)A′ = A ⇔ Ejk(a)Ejk(−a)A′ = A′ ⇔ Ejk(a)Ejk(−a) = Im ⇔(Ejk(a))−1 = Ejk(−a)

b) Produsul a doua matrici permutare Pπ, P ′σ este tot o matrice permutare, si anume (TEMA):

PπPσ = Qπ◦σ

c) Produsul a doua matrici de tip 3, Eij(a), Ekl(b), cu i < j, k < l este matrice inferiortriunghiulara, diagonal unitara.

Deoarece forma scara (redusa) SA (S0), a unei matrici A, se obtine printr-o succesiune detransformari elementare pe linie, reprezentate de matricile elementare E1, E2, . . . , EN , rezultaca forma scara se exprima ca un produs:

SA = ENEN−1 · · ·E1A

unde E1, E2, . . . , EN sunt matrici elementare de tip 1, 2 si 3. Procedura de calcul a inversei uneimatrici nesingulare prin metoda reducerii Gauss-Jordan conduce la o proprietate importanta amatricilor inverse ce se exploateaza ın numerosi algoritmi de calcul numeric. Si anume:

Propozitia 2.1.1 Orice matrice patratica A, inversabila, poate fi exprimata ca un produs dematrici elementare de forma 1,2,3.

Demonstratie: Fie E1, E2, . . . , EN matricile elementare ce reprezinta transformarile elementareaplicate matricii extinse Ae = [A|In] pentru a fi dusa la forma scara redusa [In|A−1]. Astfelavem ca:

EN · · ·E2E1A = In

Notand cu E := EN · · ·E2E1 rezulta ca EA = In, adica A = E−1 = E−11 E−1

2 · · ·E−1N

(deoarece ın general (M · N)−1 = N−1 ·M−1.) Dar am demonstrat ca inversele unor matricielementare de tipul 1, 2, respectiv 3 sunt tot matrici elementare de tipul 1, 2, respectiv 3. Decimatricea A, inversabila, se poate exprima ca un produs de matrici elementare. Exprimarea nueste ınsa unica. Doua persoane care reduc matricea extinsa la forma scara redusa pot alege ınordine diferita tipurile de transformari elementare!

10

Pe baza acestei proprietati rezulta si:

Propozitia 2.1.2 Calculul produsului A−1B dintre inversa unei matrici patratice de tip n × nsi o matrice B de tip n × p se poate realiza prin reducerea la forma scara redusa a matriciiextinse [A|B].

Demonstratie: Fie E1, E2, . . . , EN matricile elementare ce reprezinta transformarile ce se aplicamatricii extinse pentru a o reduce la forma redusa: [In|X]. Transformarile E1, E2, . . . , EN ac-tioneaza simultan si asupra matricii A si a matricii B. Din EN . . . E2E1A = In si EN . . . E2E1B =X rezulta ca EN . . . E2E1 = A−1 si deci X = A−1B.

2.2 Determinarea compatibilitatii/incompatibilitatii unui sistem din anal-iza formei scara a matricii sale prelungite

Problemele legate de existenta solutiilor unui sistem de ecuatii liniare pot fi rezolvate analizandpivotii ın forma scara a matricii prelungite a sistemului.

Propozitia 2.2.1 Un sistem de m ecuatii liniare cu n necunoscute AX = b este incompatibil,daca si numai daca forma scara a matricii prelungite A = [A|b] are ultima linie nenula deforma:

L =[

0 0 . . . 0 | c], c 6= 0

Demonstratie: Presupunem ca ultima linie nenula a formei scara este de tipul precizat. Atunciecuatia corespunzatoare este:

0x1 + 0x2 + . . . + 0xn = c 6= 0

si evident nu are solutie, deci sistemul initial nu are solutie (este incompatibil).Reciproc, daca sistemul este incompatibil atunci rangul matricii prelungite este diferit de

rangul matricii sistemului si prin urmare daca rangul matricii sistemului este r, atunci ultimalinie nenula din forma scara a matricii sistemului este linia r, iar ın forma scara a matriciiprelungite este linia r + 1:

Lr+1 =[

0 0 . . . 0 | c], c 6= 0

In concluzie forma scara a unei matrici are urmatoarele aplicatii:I Calculul rangului unei matrici: numarul pivotilor din forma scara a unei matrici A ∈

Km×n este egal cu rangul matricii;I Determinarea compatibilitatii sau incompatibilitatii unui sistem de m ecuatii cu n ne-

cunoscute AX = b; notand [A′|b′] forma scara a matricii prelungite a sistemului, [A|b], extragemurmatoarele informatii:

11

• daca forma scara a matricii prelungite are ultima linie nenula de forma:

L =[

0 0 . . . 0 | c], c 6= 0

atunci sistemul este incompatibil;• daca numarul de pivoti ın forma scara a matricii prelungite coincide cu numarul

de pivoti ın forma scara A′, a matricii A, sistemul este compatibil (deoarece cele doua matriciau acelasi rang).

Forma scara redusa are aplicatii suplimentare:I Reducand matricea prelungita [A|b] a unui sistem de n ecuatii cu n necunoscute, AX =

b, la forma scara redusa [A′|b′] extragem urmatoarele informatii:• Daca [A′|b′] = [In|s] atunci sistemul este compatibil determinat si unica solutie a

sistemului este plasata pe ultima coloana a formei scara reduse, adica colana notata s.• Daca forma scara redusa este [A′ 6= In|b′] atunci sistemul nu este compatibil

determinat, ci este compatibil nedeterminat daca numarul de pivoti din A′ coincide cu numarulde pivoti din [A′|b′], si respectiv este incompatibil daca ultima linie nenula din [A′|b′] este deforma:

L =[

0 0 . . . 0 | c], c 6= 0

I Daca A ∈ Kn×n este o matrice patratica atunci reducand matricea extinsa Ae = [A|In]la forma scara redusa concluzionam ca:

• matricea A este inversabila daca forma scara redusa a matricii Ae este de forma[In|M ] si ın plus inversa A−1 = M ;

• Matricea A este o matrice singulara daca forma scara redusa a matricii extinseeste de forma [A′ 6= In|M ].

I Pentru a calcula un produs de forma A−1B, unde A este matrice patratica de tip n×n,iar B este o matrice de tip n×p se constituie matricea extinsa, M = [A|B], asociata celor doua.Daca forma scara redusa a lui M este de forma [In|C], atunci C = A−1B, iar daca forma scararedusa este [A′ 6= In|D] atunci matricea A este singulara si D nu reprezinta produsul A−1B.

Observatia 2.2.1 Toate consideratiile si proprietatile formei scara, respectiv a formei scararedusa asociate unei matrici cu elemente ın corpul comutativ K = R sau K = C ramanvalabile pentru matrici cu valori ın corpul comutativ Zp, p numar prim, al claselor de resturimodulo p.

Matricile cu elemente ın Zp, p numar prim, au numeroase aplicatii ın criptografie.

2.3 Descompunerea LU a unei matrici patratice

Definitia 2.3.1 Fie A ∈ Kn×n o matrice patratica nesingulara. Daca exista o matrice L,inferior triunghiulara, diagonal unitara si o matrice superior triunghiulara U , astfel ıncat A =LU , atunci aceasta factorizare a matricii A se numeste descompunerea LU.

12

A =

1 0 0 . . . 0`21 1 0 . . . 0`31 `32 1 . . . 0...

...... . . .

...`n1 `n2 `n3 . . . 1

u11 u12 u13 . . . u1n

0 u22 u23 . . . u2n

0 0 u33 . . . u3n...

...... . . .

...0 0 0 . . . unn

Observatie. Daca A = LU , determinantul matricii A este det(A) = det(L)det(U) = 1 ·det(U).Deoarece matricea A este nesingulara, rezulta ca det(U) 6= 0 si deci uii 6= 0, ∀ i = 1, n.

Teoretic o matrice patratica nesingulara se poate descompune ıntr-un produs LU, daca Aeste transformata ın forma scara SA, doar prin transformari de tipul 3, Eij(a), cu i < j. Sianume, daca EN · · ·E2E1A = SA, unde E1, E2, . . . , EN sunt inferior triunghiulare, diagonalunitare, atunci si produsul lor EN · · ·E2E1 este inferior triunghiular, diagonal unitar, si la fel siinversa (EN · · ·E2E1)

−1. Notam L = (EN · · ·E2E1)−1. Cum forma scara generala, SA a unei

matrici patratice nesingulare este o matrice nesingulara, superior triunghiulara, notam U = SA.Cu aceste notatii avem:

EN · · ·E2E1A = SA ⇔ A = (EN · · ·E2E1)−1U = LU

Exemplul 6. Sa se ıncerce reducerea matricii

A =

1 −2 32 −5 120 2 −10

la forma scara aplicand doar transformari elementare aLi + Lj → Lj , cu i < j si daca esteposibil sa se determine descompunerea LU a matricii A.

A =

1 −2 32 −5 120 2 −10

−2L1+L2→L2←→

1 −2 30 −1 60 2 −10

2L2+L3→L3←→

1 −2 30 −1 60 0 2

= U

Prin urmare am obtinut forma scara a matricii A aplicandu-i transformarile:

E23(2)E12(−2)A = U ⇔ A = (E12(−2))−1(E23(2))−1U ⇔ A = E12(2)E23(−2)︸ ︷︷ ︸L

U

Astfel

L = E12(2)E23(−2) =

1 0 02 1 00 0 1

1 0 01 1 00 −2 1

=

1 0 02 1 00 −2 1

si deci A admite descompunerea LU:

A =

1 −2 32 −5 120 2 −10

=

1 0 02 1 00 −2 1

1 −2 30 −1 60 0 2

13

Descompunerea LU are aplicatii ın rezolvarea sistemelor de n ecuatii liniare si neomogene,compatibile determinate.

Presupunem ca sistemul Ax = b, A ∈ Kn×n, este compatibil determinat si ca matriceaA = LU . Atunci sistemul se scrie:

(LU)x = b

Notand y = Ux, rezolvam mai ıntai sistemul auxiliar, Ly = b:

1 0 0 . . . 0`21 1 0 . . . 0`31 `32 1 . . . 0...

...... . . .

...`n1 `n2 `n3 . . . 1

y1

y2

y3...

yn

=

b1

b2

b3...

bn

prin metoda substitutie directe: y1 = b1, din ecuatia 2, rezulta y2 si ın final ın etapa n, rezultayn. Cunoscand acum pe y1, y2, . . . , yn, se rezolva sistemul Ux = y:

1 u12 u13 . . . u1n

0 1 u23 . . . u2n

0 0 1 . . . u3n...

...... . . .

...0 0 0 . . . 1

x1

x2

x3...

xn

=

y1

y2

y3...

yn

prin metoda substitutiei inverse.Daca o matrice nesingulara, A are ın una sau mai multe pozitii de pe diagonala principala

elemente nule, atunci reducerea matricii A la forma scara, nu se poate efectua doar aplicandu-itransformari elementare pe linie, de tipul 3.

Exemplul 7. Fie sistemul

A =

0 1 −3−1 −2 2

5 4 1

x1

x2

x3

=

−1

57

Se poate rezolva sistemul prin descompunerea matricii A ıntr-un produs LU?

Pentru a putea reduce matricea A, la forma scara, mai ıntai trebuie aplicata o permutare a liniilor1 cu 2, pentru a avea element nenul ın pozitia (1,1), a pivotului. Astfel matricea P12A va fi:

A′ =

−1 −2 2

0 1 −35 4 1

Daca ınmultim sistemul Ax = b la stanga cu matricea P12 obtinem sistemul:

P12A︸ ︷︷ ︸A′

x = P12b︸︷︷︸b′

14

Daca A′ admite descompunerea LU, A′ = LU , atunci se rezolva sistemul LUx = b′, rezolvandsuccesiv, Ly = b′ si Ux = y.

Exemplul 8. Sa se arate ca matricea

A =

1 2 −12 4 00 1 −1

nu admite o descompunere LU.

Alegem pe linia ıntai, pivotul 1. Transformarea elementara −2L1 + L2 → L2, conduce lazerouri sub pivot:

A ↔

1 2 −10 0 20 1 −1

Pentru a alege pivotul pe linia a 2-a ar trebui sa interschimbam liniile L2, L3, dar aceasta inter-schimbare nu este o transformare de tip 3, ci o permutare, deci nu este reprezentata de o matriceinferior triunghiulara si diagonal unitara. Prin urmare matricea A nu admite descompunere LU(desi este matrice nesingulara). Cauza generarii unui element 0 ın pozitia (2,2) este faptul ca ınmatricea A, determinantul de ordin 2, constituit din

∣∣∣∣a11 a12

a21 a22

∣∣∣∣ =

∣∣∣∣1 22 4

∣∣∣∣ = 0

Matricile patratice care sigur admit descompunere LU sunt descrise ın:

Propozitia 2.3.1 Fie A ∈ Kn×n o matrice, ce are toti minorii de nord vest, adica minorii:

∆1 = |a11|, ∆2 =

∣∣∣∣a11 a12

a21 a22

∣∣∣∣ , . . . , ∆j =

∣∣∣∣∣∣∣

a11 . . . a1j... . . .

...aj1 . . . ajj

∣∣∣∣∣∣∣, . . . , ∆n = det(A)

nenuli. Atunci exista o unica matrice, L, inferior triunghiulara, diagonal unitara si o unicamatrice, U = (uij), superior triunghiulara, astfel ıncat A = LU si det(A) = u11u22 · · ·unn.

2.4 Metoda reducerii la forma scara ın virgula mobila.OPTIONAL, dar foarte util pentru un student la CTI

Rezolvarea sistemelor de ecuatii liniare avand matricea sistemului de dimensiuni mari serezolva nu prin calcul manual, ci implementand metoda reducerii la forma scara (redusa) amatricii prelungite, precum si alte metode pe care le pune la dispozitie algebra liniara. Intimp ce rezolvarea manuala implica folosirea aritmeticii exacte, ın rezolvarea cu calculatoruleste implicata aritmetica ın virgula mobila, cunoscuta ın CS ca si floating point arithmetic. In

reducerea la forma scara a unei matrici prin metoda ”manuala” folosim fractii de forma 5/3,7/9, etc pentru a ınmulti, de exemplu, elementele unei linii. Intr-o reprezentare ın calculator cear stoca de exemplu 15 cifre zecimale, numarul 5/3 = 1.6666666666666666... ar fi reprezentatde numarul ce se obtine din 1.66666666..... printr-o trunchiere, urmata eventual de o rotunjire.Aceste reprezentari nu sunt exacte si ele introduc erori de aproximare si rotunjire. In problemeleın care sunt implicate mii de calcule eroarea se poate cumula semnificativ. Cum ın reducereamatricilor de dimensiuni mari la forma scara intervin ın calcule numeroase astfel de reprezentaritrunchiate si rotunjite discutam modalitatea de a evita cumularea unor erori semnificative.

Multimea numerelor reale de forma:

f = ±.c1c2 . . . cp × be, c1 6= 0,

unde b si p sunt fixate, iar e este un numar ıntreg ce ia doar valori ıntre ıntregii emin, emax, adicaemin ≤ e ≤ emax, se numesc numere ın virgula flotanta ın baza b. c1, c2, . . . , cp sunt cifre ınbaza b, adica c1, c2, . . . , cp ∈ {0, 1, . . . , b− 1}. e se numeste exponent, iar p, precizie.

0.c1c2 . . . cp se numeste mantisa numarului f .

Sistemele de calcul (computers) folosesc reprezentarea numerelor reale ın virgula mobila,ın baza 2, ın timp ce calculatoarele de buzunar, ın baza 10 .

Notam cu F(b, p, emin, emax) multimea numerelor ın baza b, avand precizia p si exponentule ıntre cele doua limite. Evident ca aceasta este o multime finita.

Fie fmin, fmax cel mai mic, respectiv cel mai mare numar din F(b, p, emin, emax). Deci nuorice numar real poate fi exprimat exact printr-un numar din aceasta multime si mai mult nu-merele reale care nici macar nu pot fi reprezentate ın calculator prin astefl de numere, deci nupot fi implicate ın calcule.

Daca x ∈ R este un numar real arbitrar si el intra ın datele cu care lucreaza un program ınlimbajul X, ce foloseste reprezentarea ın virgula mobila definita de F(b, p, emin, emax), atunciel este reprezentat ın calculator prin numarul fl(x) care este cel mai apropiat numar de x dinmultimea finita F(b, p, emin, emax).

Pentru a ıntelege mai rapid problematica pe care o discutam dam exemple ın baza b = 10.Sa determinam de exemplu, aproximarea fl(x) ın baza 10, cu precizia p a unui numar real

x ∈ [(fmin, fmax]. In acest scop se exprima numarul x ın forma zecimala±0.c1c2 . . . cpcp+1...10k,cu prima cifra dupa virgula nenula: c1 6= 0. Pentru a determina cel mai apropiat numar de xdin F(10, p, emin, emax) se procedeaza astfel:

fl(x) =

{ ±0.c1c2 . . . cp × 10k daca cp+1 < 5±((0.c1c2 . . . cp) + 10−p)× 10k daca cp+1 ≥ 5

Exemplul 9. a) Sa determinam reprezentarea numarului x = 5/3. 5/3 = 1.66666666... =0.166666666...×101 ın virgula mobila cu precizia p=4. Trunchiem numarul 0.166666666666...la p + 1 = 5 zecimale: 0.16666 .

Dupa trunchiere se efectueaza rotunjirea, adica se determina numarul dinF cel mai apropiatde x:

Deoarece zecimala a 5-a ın cazul exemplului nostru este mai mare decat 5 rotunjim numarultrunchiat adunand la 0.1666 pe 10−4 = 0.0001 si avem fl(x) = 0.1667 × 101. Remarcam case patreaza exponentul din exprimarea numarului real ca un numar zecimal cu prima cifra dupapunctul zecimal diferita de zero.

b) Sa reprezentam numarul x = −95/7 = −13.571428571428... = −0.13571428571428...102

tot cu precizia 4. Cifra a 5-a a dupa punctul zecimal este 1, deci fl(−95/7) = −0.1357× 102.c) Reprezentarea numarului −327/53 cu precizia p = 4: exprimam numarul ın forma

zecimala −327/53 = −6.1698113207... = −0.61698113207... × 101. Zecimala a 5-a estec5 = 8 > 5. Prin urmare adunam mantisei fara semn 0.c1c2c3c4 = 0.6169 pe 10−4 = 0.0001 siavem, 0.6169 + 0.0001 = 0.617. Astfel fl(−327/53) = −0.6170× 101

Subliniem ca aproximarea numerelor reale x prin numere fl(x) dintr-un sistem datF(b, p, emin, emax) prezinta, ın general, anomaliile urmatoare:

fl(x + y) 6= fl(x) + fl(y), si fl(xy) 6= fl(x)fl(y)

De exemplu daca x = 9/7 = 1.28571... si y = 17/7 = 2.42857..., atunci ın sistemul dereprezentare ın virgula mobila de 4 zecimale precizie, ın baza 10 avem:

fl(x) = 0.1286× 101, f l(y) = 0.2429× 101, f l(x) + fl(y) = 0.3715× 101

iarx + y = 3.714285... f l(x + y) = 0.3714× 101 6= fl(x) + fl(y)

Exemplul 10. Verificati ca fl(2/3)+fl(fl(2/3)−fl(1/3)) 6= fl((fl(2/3)+fl(2/3))−fl(1/3)folosind precizia p = 8.

Pentru a ilustra un caz ın care erorile de rotunjire cresc semnificativ, luam urmatorul exempludin multimea numerelor ın virgula flotanta, de precizie p=4, baza zece:

presupunem ca avem de efectuat operatiile 100000(25.743 + 0.3162) ın sistemul de numereın virgula flotanta specificat. Notam x = 25.743, y = 0.3162. Atunci:

fl(x) = 0.2574× 102, f l(y) = 0.3162× 100

Pentru a efectua adunarea fl(x) + fl(y) exprimam cele doua cu acelasi exponent, 2 si avem ınaritmetica uzuala

fl(x) + fl(y) = 0.2574× 102 + 0.003162× 102 = 0.260562× 102

dar ın reprezentarea ın sistemul fixat suma este0.2606× 102. Prin urmare s-a introdus o eroarede 0.0037.

Produsul 100000(25.743 + 0.3162) este reprezentat de

fl((0.1× 106)(0.2606× 102)) = fl(0.02606× 108) = 0.0260× 108

Deci rezultatul ınmultirii ın sistemul ın virgula mobila este 2600000, ın timp ce rezultatulınmultirii manuale este: 100000(25.743 + 0.3162) = 2605920. Acest exemplu ilustreaza caınmultirea cu numere foarte mari sau echivalent ımpartirea la numere mici poate cauza erorimari. Aceste erori mari se datoreaza faptului ca rezultatul ınmultirii cu un numar ”mare” (maimare decat 10p ın cazul nostru) conduce la o trunchiere ce implica renuntarea la multe zecimalepentru a obtine reprezentantul dintr-o multime cu precizia p.

Sa luam acum un exemplu de sistem pe care sa-l rezolvam prin metoda reducerii la formascara a matricii prelungite folosind aritmetica exacta si aritmetica ın virgula flotanta, de preciziespecificata. Pentru a sublinia diferentele lucram cu precizie redusa, de exemplu de 3 zecimale.

Un exemplu de sistem care ilustreaza diferentele ıntre cele doua ”aritmetici” este:

−10−4x + y = 1x + y = 2

Solutia sistemului este x = 1/1.0001 ≈ 0.9999, y = 1.0002/1.0001 ≈ 1.00009999Rezolvam acum sistemul sistemul prin reducerea la forma scara a matricii prelungite, folosind

aritmetica ın virgula mobila cu 3 zecimale a:[ −10−4 1

1 1

∣∣∣∣12

]104L1+L2→L2−−−−− −→

[ −0.1× 10−3 0.1× 101

0 0.1× 105

∣∣∣∣0.1× 101

0.1× 105

]

deoarece:

fl(104 + 1) = fl(10001) = fl(0.10001× 105)3 zecimale

= 0.100× 105

sifl(104 + 2) = fl(10002) = fl(0.10002× 105)

3 zecimale= 0.100× 105

Astfel obtinem solutia x = 0, y = 1. x = 0 este departe de valoarea exacta x = 1/1.0001 ≈0.9999, ın timp ce y este suficient de aproape.

Cauza acestei erori mari se datoreaza alegerii unui pivot mic, −10−4 = −0.0001, ceea ceconduce la ınmultirea liniei L1 cu numar mare 1/0.0001 = 104. Intr-adevar daca schimbamliniile ıntre ele pentru a avea pivot mare, reducerea la forma scara conduce la:

[ −10−4 11 1

∣∣∣∣12

]L1↔L2−−−−− −→

[1 1

−10−4 1

∣∣∣∣21

]−→

10−4L1+L2→L2−−−−− −→[

1 10 1

∣∣∣∣21

]

deoarecefl(10−4 + 1) = fl(0.10001× 101)

3 zecimale= 0.100× 101 = 1

sifl(2× 10−4 + 1) = fl(0.10002× 101)

3 zecimale= 0.100× 1 = 1

si obtinem solutia x = y = 1, care este foarte apropiata de cea exacta.

18

Strategia de schimbare a liniilor astfel ıncat pivotul din linia ”ın lucru” sa fie cel mai mareelement ın valoare absoluta de pe coloana sa, se numeste pivotare partiala.

Mai precis daca ın procedura de reducere la forma scara pe linii am ajuns ın etapa ın caretrebuie sa alegem pivotul de pe linia i, si primul element nenul pe aceasta linie este ın pozitia(i, j), n ≥ j ≥ i, chiar daca elementul aij este nenul, nu-l alegem neaparat ca pivot:

s11 s12 . . . s1j s1 j+1 . . . s1n

0 s22 . . . s2j s2 j+1 . . . s2n...

... . . ....

... . . ....

0 0 . . . aij ai j+1 . . . ain

0 0 . . . ai+1 j ai+1 j+1 . . . ai+1 n...

... . . ....

... . . ....

0 0 . . . amj am j+1 . . . amn

ci alegem pivotul sij = max{aij, ai+1 j, . . . , amj}, adica cel mai mare element din coloana j,liniile i, i + 1, . . . ,m.

Reducerea la forma scara (redusa) folosind pivotarea partiala este implementata ın progra-mul C inclus ın arhiva postata.

Pivotarea partiala ınlatura o parte din efectele aproximarii numerelor reale prin numere ınvirgula flotanta de precizie fixata.

La prima vedere am fi tentati sa credem ca daca crestem precizia anomaliile ilustrate seatenueaza. Partial este adevarat, dar crescand precizia, putem da din nou alte exemple care ınprecizia respectiva conduc la aceleasi erori de aproximare.

2.5 Aplicatii ale calculului matricial pe Zp ın criptografie. Optional

2.5.1 Problematica criptografiei

In ultimul deceniu comunicatiile si tranzactiile prin internet au impus si condus la dez-voltarea a numeroase metode matematice destinate asigurarii securitatii informatiei. Stiinta carese ocupa cu dezvoltarea unor astfel de metode se numeste criptografie. Mai precis, criptografiaeste stiinta codificarii informatiei ın scopul securizarii comunicarii ei catre un destinatar. Nu-mele vine din limba greaca: cryptos ınseamna ascuns, iar grafie- scriere.

In literatura de specialitate orice metoda dezvoltata ın scopul asigurarii securitatii informatieieste prezentata ın urmatorul context:

Alice trimite sau intentioneaza sa-i trimita un mesaj lui Bob printr-un canal de comunicatienesigur. Insecuritatea transmiterii se datoreaza unui adversar, numit generic Oscar, care poateintercepta si modifica informatia (mesajul transmis printr-un canal de comunicatie poate fieronat sau perturbat si datorita unor cauze de ordin fizic: zgomotul ce interfera cu informatiatransmisa, stergerea unor biti etc; studiul detectarii si corectarii erorilor de transmitere a infor-matiei se bazeaza de asemenea pe tehnici de algebra liniara si va fi abordat ıntr-un alt curs).

Pentru a asigura confidentialitatea mesajului, Alice ıl transforma, secretizeaza, ın asa felıncat Oscar, adversarul, daca l-ar intercepta ar avea nevoie teoretic de un timp foarte ındelungat

19

pentru a-l descifra, chiar daca are resurse de calcul foarte mari. Oscar, (the evil), intentioneazafie doar sa citeasca mesajul, fie sa-l modifice sau sa-i trimita lui Alice propriul sau mesaj, pentrua o induce ın eroare, facand-o sa creada ca Bob i l-a transmis. Pentru a preveni acest al doileacomportament al adversarului, pe langa confidentialitate mai trebuie asigurata si autenticitateamesajului, astfel ıncat Bob sa fie sigur ca mesajul primit a fost expediat de Alice.

Vocabularul specific criptografiei:• mesajul original se numeste plaintext;• mesajul codificat se numeste ciphertext (text cifrat);Procesul de transformare a plaintextului ın ciphertext se numeste criptare, iar procesul

invers se numeste decriptare.O schema sau metoda folosita pentru criptare se numeste sistem criptografic sau cifru.Bob, destinatarul primeste mesajul criptat si ıl decripteaza exploatand metoda de criptare.

Se presupune ca Alice si Bob au stabilit ın prealabil detaliile modalitatii de criptare si decriptare.Tehnicile folosite de catre Oscar pentru decriptarea mesajului, fara a cunoaste detaliile

metodei de criptare, constituie domeniul numit criptanaliza. Criptanaliza are drept scop spar-gerea codului.

Criptografia si criptanaliza sunt subdomenii ale criptologiei.Formalizat matematic, un sistem de criptare este constituit din:1. multimea P a plaintextelor, adica a mesajelor originale pe care expeditorul intentioneaza

sa le transmita. Un mesaj este un sir de caractere dintr-un alfabet fixat sau un sir de biti.2. Multimea textelor cifrate, C, la fel constituite din siruri de caractere dintr-un acelasi

alfabet sau siruri de biti.3. O multime de elemente, K, (deocamdata neprecizate) numite chei. Fiecare cheie K

defineste o metoda de criptare (care este o aplicatie eK : P → C ce asociaza fiecarui plaintextP , textul cifrat C = eK(P )) si una de decriptare dK (care este o aplicatie dK : C → P ceasdociaza unui text cifrat C, plaintextul P din care provine: dK(C) = P . Daca dK = e−1

K ,sistemul de criptare se numeste sistem simetric.

2.5.2 Cifrul Hill

Cifrul Hill este un sistem de criptare simetric, cu cheie secreta, bazat pe matrici cu elementedin Zp, inelul claselor de resturi modulo p. Pentru a aplica rezultatele de algebra liniara relativ lareducerea unei matrici la forma scara, consideram ın continuare ca p este un numar prim si deciZp este un corp comutativ. Hill a definit initial cifrul ce-i poarta numele, pentru Z26. DeoareceZ26 nu este corp (nu orice element nenul admite invers modular) apar o serie de diferente deabordare care vor fi subliniate la sfarsitul prezentarii cifrului ın Z29.

Cifrul Hill este un cifru de substitutie poligrafica, adica un cifru care se defineste astfel:• se considera alfabetul limbii engleze format din 26 de litere majuscule, la care se adauga

caracterele punct ·, semnul ıntrebarii ? si blank:

A B C D E F G H I J K L M N O P Q R0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

20

S T U V W X Y Z · ? blank18 19 20 21 22 23 24 25 26 27 28

In procesul de criptare/ decriptare, reprezentam aceste caractere prin ”alfabetul”Z29 = {0, 1, 2, . . . , 28}, corespondenta dintre caracterele alese pentru a exprima mesaje si nu-merele din Z29 fiind ilustrata ın tabelul de mai sus.

I Fiecare mesaj exprimat ın alfabetul Z29 este divizat ın grupuri adiacente de cate nelemente din Z29. Numarul n este ales, fixat, de comun acord de catre Alice si Bob. Un astfelde grup se numeste grup n-poligrafic. Daca ultimul grup are doar k < n elemente, atuncise completeaza restul de pozitii pana la n cu 28 (adica cu blank). Fie m numarul grupurilorpoligrafice constituite din mesajul original.

I Alice constituie o matrice A de m linii si n coloane cu elemente din Z29: pe linia iincluzand codurile din Z29 pentru cel de-al i-lea grup poligrafic.

I Multimea cheilor K, este multimea matricilor patratice de tip n × n, inversabile, cuelemente din Z29.

I Alice alege o cheie K conform unei ıntelegeri prealabile cu Bob (care ısi noteaza cheiasi o pastreaza ın secret). Cheia K se foloseste pentru a cripta un grup n-poligrafic exprimatın alfabetul Z29 astfel: se ınmulteste matricea K cu matricea coloana a elementelor din Z29 cecodifica grupul respectiv. De exemplu daca un grup de n caractere consecutive din mesaj estecodificat de numerele z1, z2, . . . , zn ∈ Z29, atunci criptarea grupului

z1

z2...

zn

este constituita din setul de n numere din Z29, c1, c2, . . . , cn, unde:

c1

c2...cn

= K

z1

z2...

zn

Pentru a cripta ıntregul mesaj format din m grupuri n-poligrafice se ınmulteste transpusalui A la stanga cu matricea K si se obtine B = KAT = [KAT

:,1|KAT:,2| · · · |KAT

:,m]. Inmultireacelor doua matrici se efectueaza modulo 29. Astfel pe coloana j, j = 1,m, a matricii B esteplasata cifrarea celui de-al j-lea grup poligrafic din mesajul original.

IPentru a transmite mesajul criptat, Alice concateneaza coloanele matricii B (transcriindcoloana dupa coloana) rezultand un text cifrat exprimat ın alfabetul Z29. Transforma acest textconform tabelului de mai sus, ıntr-un text ın alfabetul

A,B, C, . . . , X, Y, Z, ·, ?, blank

si ıi transmitem lui Bob mesajul astfel rezultat.

21

I Pentru a decripta mesajul, Bob rescrie ciphertextul ın alfabetul Z29 reconstituie B sipentru ca B = KAT , calculeaza inversa lui K (mod 29) si ınmulteste matricea B la stanga cuK−1, obtinand AT . Constituie apoi matricea A si ıi concateneaza liniile pentru a citi mesajultransmis.

Remarcam ca o problema fundamentala este alegerea cheii K ın asa fel ıncat sa avem cer-titudinea ca este o matrice inversabila. Cum Z29 este corp, orice matrice de determinant nenuleste inversabila. In loc sa definim la ıntamplare o matrice K de tip n × n cu elemente dinZ29 si apoi sa-i calculam determinantul pentru a vedea daca este inversabila sau nu, se geneazamatricea inversabila, ca produs de matrici elementare de tipul 1,2,3, cu elemente din Z29.

Pentru exemplul urmator generam o cheie K, ca produs de matrici elementare de tip 3.Presupunem ca cheia este destinata cifrului Hill, ce actioneaza asupra unui grup 3–poligrafic

(adica mesajul este divizat ın frupuri adiacente de trei caractere) Astfel definim cheia K ∈ Z3×329 :

K = E13(18)E23(5)E12(11)E32(17)E31(9)E21(27) =

22 27 1818 28 54 17 1

Subliniem ca ın acest produs am luat matrici de tip Ejk(a) ∈ Z3×329 , corespunzatoare atat

unor perechi (j,k) cu j < k cat si j > k. Daca luam doar matrici corespunzatoare la indicij < k, produsul lor era o matrice inferior triunghiulara, care se inverseaza rapid (deci ar usuramunca lui Oscar!).

Deoarece inversa unei matrici Eij(a) este Eij(−a (mod 29)) si ın general (AB)−1 = B−1A−1

avem ca:

K−1 = E21(−27)E31(−9)E32(−17)E12(−11)E23(−5)E13(−18)= E21(2)E31(20)E32(12)E12(18)E23(24)E13(11) =

=

1 18 82 8 11

20 24 14

Prin urmare cunoscand transformarile elementare ce definesc matricea K, nu este nevoie sainversam matricea K printr-o anume procedura, ci simplu exprimam inversa tot ca un produsde matrici elementare, care implica calcule mai simple si mai rapide decat orice metoda deinversare (care ar implica calculul x−1 (modulo 29), pentru diverse elemente nenule x ∈ Z29;algoritmul de calcul al inversului modular consuma mult timp, ori ın criptanaliza timpul este”pretios”!).

Exemplul 11. Alice doreste sa ıi transmita lui Bob mesajul:

LIPSESC LA ALGEBRA.

Pentru a-l cripta folosind cheia K de mai sus, codifica ın prealabil mesajul cu elemente dinalfabetul Z29, constituind o matrice linie::

M =[

11 8 15 18 4 18 2 28 11 0 28 0 11 6 4 1 17 0 26]

22

apoi divide mesajul codificat ın grupuri 3-poligrafice pe care le insereaza pe liniile1 unei matrici:

A =

11 8 1518 4 182 28 110 28 0

11 6 41 17 0

26 28 28

Deoarece ultima linie nu contine decat un element o completeaza cu doi de 28, adica 2 blankuri.Efectuand ınmultirea modulo 29, B = KAT , obtine matricea B:

B =

3 16 12 2 12 17 54 4 5 1 9 1 0

21 13 2 12 5 3 28

Prin urmare fiecare 3-grup poligrafic este cifrat pe cate o coloana a matricii B. De exemplutextul cifrat pentru grupul LIP este 3, 4, 21, pentru SES este 16,4, 13, etc. Transcriind coloanadupa coloana, dar inlocuind numerele din Z29 cu litere rezulta urmatorul mesaj cifrat transmisde Alice lui Bob:

DEVQENMFCCBMMJFRBDFA

Bob reconstituie matricea B din textul cifrat si calculeaza

K−1B (mod 29) =

11 18 2 0 11 1 268 4 28 28 6 17 28

15 18 11 0 4 0 28

Concatenand coloana dupa coloana, si ınlocuind elementele din Z29 cu caracterele pe care lecodifica poate citi mesajul:

LIPSESC LA ALGEBRA.

Oride cate ori se lanseaza un nou sistem de criptare, se ıncearca si sa se demonstreze cat dedificila este problema spargerii cifrului, adica se efectueaza criptanaliza sistemului.

Provocare! Ce demersuri trebuie sa faca Oscar pentru a descoperi cheia cifrului Hill?

END Optional

1Inserarea ıntr-o matrice a grupurilor 3-poligrafice se poate face si pe coloane, alegerea pe linii sau pe coloaneramanand la latitudinea lui Alice si Bob!