spyked bricks in the wall — cu cofunctori și matrice inversabile

cu cofunctori și matrice inversabile

duminică, 19 feb. 2012, 15:37

Articolul despre atom ne-a lăsat în pom cu o particularitate destul de neplăcută (și care dă spre inconsistență) a sistemului prezentat: toate reprezentările abstracte din cadrul acestuia sunt cu precădere duale, deci binare [i], pe când abordarea categorială e una ternară. Cu alte cuvinte, categoria ca construcție naturală a matematicii e formată din obiecte (notate de obicei ), săgeți între obiecte (notate de obicei ) și o operație de compunere a săgeților care respectă două axiome [ii].

Definiția o generalizează pe cea a monoidului, care-i în fapt și la urma urmei o categorie cu un singur obiect care-i de fapt o mulțime $M$ , ale cărei elemente sunt săgeți în categoria dată, iar compunerea e operația binară de compunere a monoidului. Definiția generală a monoidului dă de fapt un triplet format dintr-un obiect și două morfisme, într-un mod analog cu monadele, dar astea nu-s legate de discuția noastră.

Tot în despre atom sugeram functorul ca operator de abstractizare. Abstractizarea asta e de fapt o trecere dintr-o categorie $\mathcal{C}$ într-o categorie $\mathcal{D}$ , care poate fi uneori echivalentă cu $\mathcal{C}$ , caz în care vom folosi termenul de endofunctor. Functorii sunt interesanți prin aceea că pot fi văzuți drept constructori de date. De exemplu dacă notăm cu $L\;A$ constructorul pentru liste cu obiecte de tipul $A$ , vom putea (1) să construim șiruri de elemente din mulțimea $A$ , și (2) să aplicăm funcții $f : A \to B$ pe structura de listă, obținând $L\;B$ , adică liste de forma [iii]. Drept urmare, functorii se comportă civilizat atât în raport cu operația de compunere cât și cu săgeata identitate, adică $F(f \circ g) = F\;f \circ F\;g$ , respectiv .

Functorii de mai sus mai sunt numiți și functori covarianți, deoarece prezervă sensul săgeților. Putem defini și functor contravarianți (sau cofunctori), care inversează sensul acestora, adică pentru o săgeată $f : A \to B$ , vom avea $F\;f : F\;B \to F\;A$ , pe obiecte cofunctorii aplicându-se identic cu cazul functorilor. În acest caz, legea asociativității devine $F(f \circ g) = F\;g \circ F\;f$ . În particular, ne putem lovi de problema existenței cofunctorilor într-un context dat, după cum vom vedea în cele ce urmează.

Elementele de mai sus ar trebui să fie suficiente pentru a putea ilustra problema dată, cu condiția să fi absolvit liceul sau să fim olimpici la matematici sau ceva. Așadar dacă ne întoarcem la perioada noastră de elevi silitori de clasa a XII-a, ne amintim că putem defini structura de vector $n$ -dimensional drept un șir ordonat de $n$ elemente dintr-o mulțime dată și structura de matrice $m$ -dimensională drept un șir de $m$ vectori din mulțimea fixată. Dat fiind faptul că pentru noi $m = n$ , deci lucrăm cu matrice pătratice, nu ne interesează care-s linii, care-s coloane și alte asemenea detalii. Important e faptul că matricele au o structură bine definită.

Ne mai interesează aspectul că matricele pătratice împreună cu operația de înmulțire formează o structură algebrică de monoid, în virtutea faptului că (1) înmulțirea matricelor pătratice e închisă și asociativă și (2) există un element identitate, care-i chiar matricea identitate. Putem observa astfel destul de ușor că determinantul unei matrice $M^{n \times n}$ este în mod natural un functor care „uită” structura acesteia, deci duce în monoidul lui $M$ împreună cu operația de înmulțire asociată. Verificarea e imediată, pentru că știm că $\text{det}(I) = 1$ , care e element neutru în raport cu înmulțirea [iv], iar $\text{det}(AB) = \text{det}(A)\text{det}(B)$ .

Bun, dar care-i rolul functorilor contravarianți în toată povestea asta? Cel mai „natural” cofunctor în categoria dată pare a fi operația de inversare a matricelor, cofunctor care întâmplător este și endofunctor. Inversarea matricelor e în mod evident un cofunctor, deoarece inversa matricei unitate este ea însăși, iar $(AB)^{-1} = B^{-1}A^{-1}$ . Mai știm și că $A^{-1} A = I$ (care e de fapt definiția matricei inverse), ceea ce ne duce cu gândul la izomorfisme și dualitate, dacă ținem cont de faptul că functorii contravarianți sunt o expresie a categoriei duale într-o categorie dată. În același timp știm că spațiul dual algebric al unei matrice e dat de transpusă, iar $A^T \equiv A^{-1}$ dacă și numai dacă $A$ e ortogonală, însă firul ăsta de gândire îl lăsăm deschis.

Revenind la problema de mai sus, știm că nu toate matricele sunt inversabile. Mai exact, doar matricele având determinantul nenul sunt inversabile, astfel că în mulțimea $M$ de mai sus trebuie să găsim și un element $0$ [v] (sau putem să nu, asta în cazul cel mai fericit). Asta înseamnă și că existența celui de-al doilea functor prezentat e cumva determinată de felul în care cel dintâi acționează în cadrul monoidului, însemnând automat că aceștia nu pot fi definiți independent când vorbim de matrice.

Soluția cea mai elegantă ar fi bineînțeles să impunem ca monoidul nostru să fie grup, rezultând că toate săgețile sunt izomorfisme (deci toate matricele sunt inversabile), moment în care discuția a luat sfârșit. Întrebarea e totuși dacă fenomenul de mai sus poate fi generalizat și abstractizat într-o clasă de triplete monoid-functor-cofunctor (sau dacă clasa respectivă e chiar structura de grup sau poate avea restricții mai lejere), întrebare la care nu am un răspuns încă, dar poate o voi face cândva.

Post Scriptum: Undeva mai aproape de viața reală și mai jos de sferele abstracte, problema se poate constitui în exemple precum cel al transformatei fourier discrete, unde trecerea inversă (din domeniul frecvență în cel timp) presupune inversarea de matrice. Mai aproape de calculatoare și de ingineria software se dorește conceperea unor modele care să garanteze anumite proprietăți (securitatea și performanța sunt primele care-mi vin în minte), pentru care toată poliloghia matematică din spate s-ar putea dovedi a fi utilă. Așadar gândiți-vă de două ori înainte să caracterizați articolele de genul ăsta drept pură masturbare intelectuală.

Și iată cum am comis și erezia de a folosi numere în cadrul unor teorii care fac abstracție de acestea la un nivel fundamental. [↩]
Mai exact asociativitatea operației și existența unui element neutru [↩]
Această „aplicare” a funcțiilor pe structuri e exact operația map din programarea funcțională. Atât map cât și fold/reduce sunt formalizate în teoria categoriilor, dar asta-i o cu totul altă discuție. [↩]
Am particularizat la numere, dar de fapt nu prea ne interesează natura elementelor din $M$ în cadrul monoizilor dați, iar $1$ e un element fixat din $M$ , nu musai un număr. [↩]
La o primă vedere ar părea că putem defini un functor de „înmulțire cu zero”, functor constant care schimbă operația binară și elementul neutru al monoizilor dați și duce mereu în zero. Operația nouă ar fi adunarea matricelor, respectiv a elementelor din $M$ , unde zeroul nostru e element neutru. Nu am verificat pe foaie afirmațiile astea din pură lene, motiv pentru care le las drept exercițiu cititorului. [↩]

Publicat de spyked în misc stuff, algebra, category theory, cofunctor, division by zero, functor, math, monoid

Comments

spyked bricks in the wall — dinamica traficului, un model spune:

august 5, 2012 la 17:31

[…] facem abstracție de argumentul asociat timpului, putem spune că este o funcțională, adică un functor. […]

spyked bricks in the wall — naturalețea în matematici spune:

august 19, 2012 la 19:39

[…] natural în matematică trebuie să aibă corespondent în teoria categoriilor – de exemplu matricele și functorii. Iară numerele naturale și principiul inducției sunt de fapt expresii naturale ale […]

Comentariile sunt dezactivate.

« Acasă