1

Capitolul 1

NOŢIUNI DE ALGEBRĂ CONVENŢIONALĂ VS. ALGEBRĂ EXOTICĂ

Primul paragraf are ca scop principal introducerea unor structuri algebrice exotice (semiinel idempotent; semicorp idempotent, cunoscut sub numele de algebră max plus). În Paragraful 1.2 vom prezenta unele noţiuni de algebră liniară în algebra max plus ℝ .

1.1. Structuri algebrice exotice

În această secţiune ne vom ocupa de unele structuri algebrice exotice care se construiesc pornind de la structura de semiinel prin adăugarea unor proprietăţi (axiome) suplimentare.

Noţiunea de semiinel idempotent

Un monoid sau semigrup cu element neutru este un cuplu (푀,∗) unde ∗:푀 × 푀⟶

푀, (푥, 푦) ⟼ 푥 ∗ 푦 este o operaţie algebrică binară asociativă cu proprietatea că (∃)푒 ∈ 푀

astfel încât 푒 ∗ 푥 = 푥 ∗ 푒 = 푥, (∀)푥 ∈ 푀 ( adică 푒 ∈ 푀 este element neutru în raport cu

operaţia∗). Un monoid se va nota prin (푀,∗, 푒) sau (푀,∗) sau 푀.

Un monoid (푀,∗, 푒) se numeşte:

● comutativ, dacă ∗ este comutativă, adică 푥 ∗ 푦 = 푦 ∗ 푥, (∀)푥, 푦 ∈ 푀;

● idempotent, dacă operaţia ∗ este idempotentă, adică 푥 ∗ 푥 = 푥, (∀)푥 ∈ 푀.

Definiţia 1.1.1 Un semiinel (dioid) este un 5 uplu (푆,⊕,⊗, 휀, 푒) astfel încât sunt verificate

următoarele condiţii:

(i) (푆,⊕, 휀) este un monoid comutativ ( este element nul);

(ii) ),,( eS este un monoid ( e este element unitate);

(iii) operaţia este distributivă în raport cu operaţia , adică pentru orice Scba ,,

avem:

(1) )()()( cbcacba ;

(2) )()()( cabacba ;

(iv) aa ( este element absorbant pentru operaţia ). □

Un semiinel se numeşte:

2

● comutativ, dacă operaţia este comutativă;

● selectiv, dacă operaţia este selectivă, dacă bbasauaba pentru

orice Sba, .

Exemplul 1.1.1 (ℕ, +,∙ ,0,1) este un semiinel comutativ. □

Definiţia 1.1.2 Un semiinel (푆,⊕,⊗, 휀, 푒) cu proprietatea că operaţia ⊕ este idempotentă, se

numeşte semiinel idempotent sau dioid idempotent. Mai precis, un semiinel idempotent este un

5 uplu (푆,⊕,⊗, 휀, 푒) astfel încât sunt verificate următoarele condiţii:

(i) (푆,⊕, 휀) este un monoid idempotent comutativ ( este element nul), adică pentru

orice 푎,푏, 푐 ∈ 푆 avem:

(1) (푎 ⊕ 푏) ⊕ 푐 = 푎 ⊕ (푏 ⊕ 푐) (operaţia ⊕ este asociativă);

(2) 푎 ⊕ 휀 = 휀 ⊕ 푎 = 푎 (휀 este element nul în raport cu operaţia⊕);

(3) 푎 ⊕ 푏 = 푏 ⊕ 푎 (operaţia ⊕ este comutativă);

(4) 푎 ⊕ 푎 = 푎 (operaţia ⊕ este idempotentă);

(ii) (푆,⊗, 푒) este un monoid ( e este element unitate), adică pentru orice 푎, 푏, 푐 ∈ 푆

avem:

(1) (푎 ⊗ 푏) ⊗푐 = 푎 ⊗ (푏 ⊗ 푐) (operaţia ⊗ este asociativă);

(2) 푎 ⊗ 푒 = 푒 ⊗ 푎 = 푎 (푒 este element unitate în raport cu operaţia ⊗);

(iii) operaţia ⊗ este distributivă în raport cu operaţia⊕, adică pentru orice 푎, 푏, 푐 ∈ 푆 avem:

(1) (푎 ⊕ 푏) ⊗푐 = (푎 ⊗ 푐)⊕ (푏 ⊗ 푐);

(2) ⊗ (푏 ⊕ 푐) = (푎 ⊗ 푏) ⊕ (푎 ⊗ 푐);

(iv) 푎 ⊗ 휀 = 휀 ⊗ 푎 = 휀 (휀 este element absorbant pentru operaţia⊗). □

Un semiinel idempotent se numeşte comutativ, dacă operaţia ⊗ este comutativă.

Propoziţia 1.1.1 Fie (푆,⊕,⊗, 휀, 푒) un semiinel idempotent. Singurul element din 푆 care are un

simetric în raport cu operaţia ⊕ este elementul nul 휀.

Demonstraţie. Simetricul elementului nul 휀 este el însuşi, deoarece 휀 ⊕ 휀 = 휀. Fie acum

푥 ∈ 푆, 푥 ≠ 휀 care are un simetric 푥′ ∈ 푆, adică 푥 ⊕ 푥 = 푥 ⊕ 푥 = 휀. Aplicând

proprietăţile din definiţia unui semiinel idempotent, avem:

푥 = 푥 ⊕ 휀 = 푥 ⊕ (푥 ⊕ 푥 )) = (푥 ⊕ 푥) ⊕푥′ = 푥 ⊕ 푥′ = 휀 , contradicţie.

Prin urmare, singurul element care are un simetric este 휀 . □

3

Definiţia 1.1.3 Fie (푆,⊕,⊗, 휀, 푒) un semiinel idempotent. O submulţime nevidă 푆′ ⊆ 푆 este un

subsemiinel idempotent al semiinelului idempotent 푆, dacă sunt verificate următoarele condiţii:

(i) (∀)푥,푦 ∈ 푆 ⟹ 푥⊕ 푦, 푥 ⊗ 푦 ∈ 푆′; (ii) 휀 ∈ 푆′ şi 푒 ∈ 푆′ . □

Exemplul 1.1.2 (Exemple de semiinele idempotente). (i) Considerăm mulţimea ℝ =

{푎 ∈ ℝ | 푎 ≥ 0} înzestrată cu operaţiile de adunare şi înmultire a numerelor reale. Se verifică

uşor că (푃,⊕= +,⊗=∙, 휀 = 0, 푒 = 1) este un dioid comutativ care nu este idempotent. Acest

dioid nu este selectiv.

(ii) (ℕ,⊕=∨,⊗=∧, 휀 = 1, 푒 = 0) este un dioid idempotent, unde operaţiile algebrice ∨

şi ∧ sunt date prin:

푚 ∨ 푛 = cel mai mic multiplu comun al numerelor naturale m şi n ;

푚 ∧ 푛 = cel mai mare divizor comun al numerelor naturale m şi n .

Acest dioid nu este selectiv, deoarece 2 ⊕ 3 = 2 ∨ 3 = 6. □

Structura de semicorp idempotent ( algebră max-plus)

Definiţia 1.1.4. Un semiinel idempotent (핂,⊕,⊗, 휀, 푒) cu proprietatea că orice element nenul

푥 ∈ 핂, 푥 ≠ 휀 este inversabil, adică există 푥 ∈ 핂 astfel încât 푥 ⊗ 푥 = 푥 ⊗ 푥 = 푒, se numeşte

semicorp idempotent. Mai precis, un semicorp idempotent este un 5 uplu (핂,⊕,⊗, 휀, 푒) astfel

încât sunt verificate următoarele condiţii:

(i) (핂,⊕, 휀) este un monoid idempotent comutativ (휀 este element nul), adică pentru orice

푎, 푏, 푐 ∈ 푆 avem:

(1) (푎 ⊕ 푏) ⊕푐 = 푎 ⊕ (푏 ⊕ 푐) (operaţia ⊕ este asociativă);

(2) 푎 ⊕ 휀 = 휀 ⊕ 푎 = 푎 (휀 este element nul în raport cu operaţia ⊕);

(3) 푎 ⊕ 푏 = 푏 ⊕ 푎 (operaţia ⊕ este comutativă);

(4) 푎 ⊕ 푎 = 푎 (operaţia ⊕ este idempotentă);

(ii) (핂 ∖ {휀},⊗) este un grup (푒 este element unitate), adică pentru orice 푎, 푏, 푐 ∈ 핂

avem:

(1) (푎 ⊗ 푏) ⊗푐 = 푎 ⊗ (푏 ⊗ 푐) (operaţia ⊗ este asociativă);

(2) 푎 ⊗ 푒 = 푒 ⊗ 푎 = 푎 (푒 este element unitate în raport cu operaţia ⊗);

4

(3) (∀)푎 ∈ 핂 ∖ {휀} există 푎 ∈ 핂 astfel încât 푎 ⊗ 푎 = 푎 ⊗ 푎 = 푒 (푎 este inversul elementului

푎 în raport cu operaţia ⊗);

(iii) operaţia ⊗ este distributivă în raport cu operaţia ⊕, adică pentru orice 푎, 푏, 푐 ∈ 핂

avem:

(1) (푎 ⊕ 푏) ⊗푐 = (푎 ⊗ 푐)⊕ (푏 ⊗ 푐);

(2) 푎 ⊗ (푏 ⊕ 푐) = (푎 ⊗ 푏) ⊕ (푎 ⊗ 푐).

(iv) 푎 ⊗ 휀 = 휀 ⊗ 푎 = 휀 (휀 este element absorbant pentru operaţia ⊗). □

Într-un semicorp idempotent (핂,⊕,⊗, 휀, 푒), inversul 푥 ∈ 핂 al elementului 푥 ∈ 핂, 푥 ≠ 휀 se notează uneori cu 푥⊙ .

Un semicorp idempotent se numeşte comutativ, dacă operaţia ⊗ este comutativă. Observaţie (i) Un semicorp idempotent (핂,⊕,⊗, 휀, 푒) se mai numeşte algebră max - plus.

(ii) Dacă în Definiţia 1.2.5 se renunţă la condiţia (i)(3), se obţine structura de semicorp. □ Observaţia 1.1.1 Fie (핂,⊕,⊗, ε, e) un semicorp idempotent. Singurul element din 핂 care are un

simetric în raport cu operaţia ⊕ este elementul nul 휀. □ Definiţia 1.1.5. Fie (핂,⊕,⊗, 휀, 푒) un semicorp idempotent. O submulţime nevidă 핂′ ⊆ 핂 este

un subsemicorp idempotent sau subalgebră max - plus al semicorpului idempotent 핂, dacă sunt

verificate următoarele condiţii:

(i) (∀) 푥,푦 ∈ 핂′ ⟹ 푥⊕ 푦,푥 ⊗ 푦 ∈ 핂′;

(ii) 휀 ∈ 핂′;

(iii) (∀( 푥 ∈ 핂′ ∖ {휀} ⟹ 푥⊙ ∈ 핂′. □

Să observăm că, dacă 핂′ ⊆ 핂 este un subsemicorp idempotent al semicorpului

idempotent (핂,⊕,⊗, ε, e), atunci 푒 ∈ 핂′.

Algebra max-plus ℝ풎풂풙

În această secţiune vom da o un exemplu important de semicorp idempotent comutativ. Vom folosi termenul structură algebrică (convenţională) pentru a indica o mulţime de numere reale înzestrată cu un număr de operaţii uzuale cu numere reale. Termenul max-algebric şi prefixul max vor fi folosite pentru a indica conceptele şi proprietăţile care sunt valabile în algebra max-plus.

Elementele algebrei max-plus sunt numerele reale la care se adaugă elementul 휀 = −∞. Operaţiile de bază ale algbrei max-plus sunt:

5

푥 ⊕ 푦 = max{푥,푦} (maximul dintre 푥 şi 푦) 푥 ⊗ 푦 = 푥 + 푦 (suma dintre 푥 şi 푦)

pentru orice 푥, 푦 ∈ ℝ ∪ {−∞} . Motivul pentru care se utilizează aceste simboluri este acela că există o analogie între ⊕

şi adunare, respectiv ⊗ şi înmulţire. Multe concepte şi proprietăţi din algebra liniară convenţională pot fi transpuse în algebra max-plus prin înlocuirea simbolului + cu ⊕şi a simbolului × cu ⊗. De aceea vom numi operaţia ⊕ca fiindadunarea în max-algebra sau prescurtat, max-adunarea. Analog, operaţia ⊗va fi numită înmulţirea în max-algebra sau max-înmulţirea.

Considerăm mulţimea , înzestrată cu o operaţie aditivă , notată şi o operaţie

multiplicativă, notată , definite astfel:

(1.1.1) 푎 ⊕ 푏 = max{푎, 푏}; (1.1.2) 푎 ⊗ 푏 = 푎 + 푏, unde operaţiile binare ”max” şi ”+” au semnificaţia standard cunoscută.

Operaţia aditivă posedă următoarele proprietăţi:

1) legea internă:

2) comutativitatea:

3) asociativitatea:

4) existenţa elementului nul (neutru în raport cu ):

5) idempotenţa:

Operaţia multiplicativă posedă următoarele proprietăţi:

1) legea internă:

2) comutativitatea:

3) asociativitatea:

6

4) existenţa elemntului unitate(neutru în raport cu ):

5) existenţa elementului invers:

6) elementul nul este absorbant în raport cu :

De asemenea, operaţia este distributivă în raport cu operaţia aditivă , adică:

Conform proprietăţilor de mai sus, care se verifică prin calcul direct, se poate trage

concluzia enunţată în propoziţia următoare. Propoziţia 1.1.2. (ℝ ∪ {−∞},⊕= 푚푎푥,⊗= +, 휀 = −∞, 푒 = 0) are o structură algebrică de

semicorp idempotent comutativ. □

Semicorpul idempotent comutativ (ℝ ∪ {−∞},푚푎푥, +, 휀 = −∞, 푒 = 0) se notează cu ℝ şi se numeşte algebra max – plus ℝ .

Operaţia de înmulţire definită prin (1.1.2) permite introducerea operaţiei de ridicare la putere a unui element din mulţimea prin relaţia:

(1.1.3) 2, ,...... , , 10 jjjaaaaaaaaaaea j N .

Operaţia dată prin (1.1.3) poate fi apoi extinsă, în mod natural, la cazul:

(1.1.4) 2, ,/1 jjjaa j N .

Numărul real jaa j /1 se mai notează cu j a

(numit radical de ordinul j din

푎 ∈ ℝ ).

Propoziţia 1.1.3. (i) (ℤ ∪ {−∞},⊕= 푚푎푥,⊗= +, 휀 = −∞, 푒 = 0) are o structură algebrică de

semicorp idempotent comutativ.

(ii) (ℚ ∪ {−∞},⊕= 푚푎푥,⊗= +, 휀 = −∞, 푒 = 0) are o structură algebrică

de semicorp idempotent comutativ.

Demonstraţie. Se arată că (ℤ ∪ {−∞},⊕= 푚푎푥,⊗= +, 휀 = −∞, 푒 = 0) ( respectiv, (ℚ ∪

{−∞},⊕= 푚푎푥,⊗= +, 휀 = −∞, 푒 = 0) ) este un subsemicorp al semicorpului idempotent

comutativ ℝ . □

7

Semicorpul idempotent comutativ (ℤ ∪ {−∞},⊕= 푚푎푥,⊗= +, 휀 = −∞, 푒 = 0) (respectiv, (ℚ ∪ {−∞},⊕= 푚푎푥,⊗= +, 휀 = −∞, 푒 = 0)) se notează cu ℤ ( respectiv, ℚ ) şi se numeşte algebra m x- plus ℤ ( respectiv, ℚ ).

1.2. Algebra max-plus ℝ풎풂풙풏×풏 a matricelor peste ℝ풎풂풙. Proprietăţi

Operaţii cu matrice şi vectori definiţi pe algebra ℝ풎풂풙

Dacă 퐴 = (퐴 ) şi 퐵 = (퐵 ) sunt două matrice de aceeaşi dimensiune , ale căror

elemente aparţin mulţimii , definim matricea sumă în raport cu operaţia prin:

(1.2.1) 퐶 = 퐴 ⊕ 퐵 = (퐶 ), unde 퐶 = 퐴 ⊕ 퐵 = max 퐴 ,퐵 , 푖 = 1,푚, 푗 = 1,푛.

Dacă 퐴 = (퐴 ) şi 퐵 = (퐵 ) sunt două matrice de dimensiuni ( ) şi respectiv

( ), ale căror elemente aparţin mulţimii , definim matricea produs în raport cu operaţia prin:

(1.2.2) 퐷 = 퐴⊗ 퐵 = (퐷 ) , unde

(1.2.3) 퐷 = ⨁ 퐴 ⊗퐵 = max , 퐴 + 퐵 , 푖 = 1,푚, 푗 = 1,푝.

Să notăm prin 푀(푛;ℝ ) sau ℝ × mulţimea matricelor pătrate de ordin 푛 cu elemente din . Operaţia definită conform (1.2.1) pe mulţimea 푀(푛;ℝ ) are următoarele

proprietăţi:

1) Lege internă: (∀)퐴,퐵 ∈ 푀(푛;ℝ푚푎푥):퐴 ⊕ 퐵 ∈ 푀(푛;ℝ푚푎푥)

2) Comutativitate: (∀)퐴,퐵 ∈ 푀(푛;ℝ푚푎푥):퐴 ⊕ 퐵 = 퐵 ⊕ 퐴

3) Asociativitate: (∀)퐴,퐵,퐶 ∈ 푀(푛;ℝ푚푎푥): (퐴⊕ 퐵) ⊕퐶 = 퐴⊕ (퐵⊕ 퐶)

4) Existenţa matricei nule: (∃) ℰ ∈ 푀(푛;ℝ ): ℰ = 휀 = −∞: (∀)퐴 ∈ 푀(푛;ℝ ):퐴 ⊕ ℰ = ℰ ⊕ 퐴

5) Idempotenţa: (∀)퐴 ∈ 푀(푛;ℝ ):퐴⊕ 퐴 = 퐴

Observaţie. Proprietăţile 1) – 5) enumerate mai sus sunt valabile şi în cazul mai general al mulţimii matricelor de tipul nm . □ Operaţia definită conform (1.1.2.2) pe mulţimea푀(푛;ℝ ) are următoarele proprietăţi:

1) Lege internă: (∀)퐴,퐵 ∈ 푀(푛;ℝ푚푎푥):퐴⊗ 퐵 ∈ 푀(푛;ℝ푚푎푥)

2) Asociativitate: (∀)퐴,퐵,퐶 ∈ 푀(푛;ℝ푚푎푥): (퐴⊗ 퐵) ⊗퐶 = 퐴⊗ (퐵⊗ 퐶)

8

3) Existenţa matricei unitate:

(∃) 퐸 ∈ 푀(푛;ℝ ): 퐸 = 푒 = 0, 퐸 = 휀 = −∞, 푗 ≠ 푖:퐴 ⊗퐸 = 퐸 ⊗ 퐴 = 퐴

4) Matricea nulă ℰ este absorbantă în raport cu :

(∀)퐴 ∈ 푀(푛;ℝ ):퐴⊗ ℰ = ℰ ⊗ 퐴 = ℰ

Operaţia muliplicativă este distributivă în raport cu operaţia aditivă :

(∀)퐴,퐵,퐶 ∈ 푀(푛;ℝ ): 퐴 ⊕ 퐵 ⊗ 퐶 = 퐴⊗ 퐶 ⊕ 퐵⊗ 퐶

Pentru şi o matrice dreptunghiulară ale cărei elemente aparţin mulţimii definim operaţia (legea) externă:

(1.2.4) 퐵 = 훼 ⊗ 퐴, 퐵 = 훼 ⊗ 퐴 = 훼 + 퐴 , 푖 = 1, … ,푚, 푗 = 1, … ,푛

care poartă denumirea de înmulţire a matricei cu scalarul şi are următoarele proprietăţi:

1) (∀)훼 ∈ ℝ ∪ {−∞}, (∀)퐴 ∈ 푀(푛;ℝ ): 훼 ⊗퐴 ∈ ℝ ∪ {−∞}

2) (∀)훼,훽 ∈ ℝ ∪ {−∞}, (∀)퐴 ∈ 푀(푛;ℝ ): 훼 ⊗ 훽 ⊗ 퐴 = (훼 ⊗ 훽) ⊗퐴

3) (∀)훼,훽 ∈ ℝ ∪ {−∞}, (∀)퐴 ∈ 푀(푛;ℝ ): (훼 ⊕ 훽) ⊗퐴 = 훼 ⊗ 퐴⊕훽⊗ 퐴

4) (∀)훼 ∈ ℝ ∪ {−∞}, (∀)퐴,퐵 ∈ 푀(푛;ℝ ): 훼 ⊗ 퐴⊕ 퐵 = 훼 ⊗ 퐴⊕ 훼 ⊗퐵

5) (∀)퐴 ∈ 푀(푛;ℝ ): 푒 ⊗ 퐴 = 퐴

6) (∀)퐴 ∈ 푀(푛;ℝ ): ℰ ⊗ 퐴 = ℰ.

Observaţie. Proprietăţile 1) – 6) enumerate anterior sunt valabile şi în cazul mai general al

mulţimii matricelor de tipul nm . □ În baza proprietăţilor de mai sus, se poate afirma că mulţimea dotată cu operaţiile

interne şi respectiv, cu operaţia externă în raport cu , are o structură de algebră idempotentă. Observaţie. Pentru a simplifica notaţiile, vom renunţa la simbolurile şi vom utiliza următoarea convenţie de scriere: desemnează operaţia de adunare (1) din precum şi operaţia de adunare (1.1.2.1) din mulţimea matricelor; desemnează operaţia de înmulţire (2) din , operaţia de înmulţire (1.1.2.2) din mulţimea matricelor, precum şi operaţia (1.1.2.3) de înmulţire a unei matrice cu un scalar din

. □ Conform observaţiei precedente, operaţiile de max -adunare, max-înmulţire a matricelor

şi de max-înmulţire cu scalari a matricelor se definesc astfel:

9

● 퐶 = 퐴⊕ 퐵 = (퐶 ), unde

퐶 = (퐴⊕ 퐵) = 퐴 ⊕ 퐵 = max 퐴 ,퐵 , 푖 = 1,푚, 푗 = 1, 푛;

● 퐷 = 퐴 ⊗ 퐵 = (퐷 ) , unde

퐷 = (퐴⊗ 퐵) = ⨁ 퐴 ⊗퐵 = max , 퐴 + 퐵 , 푖 = 1,푚, 푗 = 1, 푝 ;

● 퐹 = 훼 ⊗ 퐴 = (퐹 ), unde

퐹 = (훼 ⊗ 퐴) = 훼 ⊗ 퐴 = 훼 + 퐴 , 푖 = 1,푚, 푗 = 1,푛.

Mulţimea 푀(푛;ℝ ) conţine două matrice speciale şi anume matricea max-nulă 푂⊙ şi matricea max-unitate 퐸⊙ , unde

푂⊙ =

⎝

⎜⎛휀 휀 ⋯ 휀 휀휀 휀 ⋯ 휀 휀⋮ ⋮ … ⋮ ⋮휀 휀 … 휀 휀휀 휀 … 휀 휀⎠

⎟⎞

,퐸⊙ =

⎝

⎜⎛

0 휀 ⋯ 휀 휀휀 0 ⋯ 휀 휀⋮ ⋮ … ⋮ ⋮휀 휀 … 0 휀휀 휀 … 휀 0⎠

⎟⎞

.

Matricele 푂⊙ şi 퐸⊙ se vor nota uneori cu ℰ respectiv 퐸 . Are loc propoziţia următoare.

Propoziţia 1.2.1. (푀(푛;ℝ ),⊕,⊗,푂⊙ ,퐸⊙ ) are o structură algebrică de semicorp

idempotent. □

Semicorpul idempotent (푀(푛;ℝ ),⊕,⊗,푂⊙ ,퐸⊙ ) este numit algebra max- plus a

matricelor de ordinul 푛 peste ℝ .