Matematyka tropikalna
Tropikalnych matematyczny lub geometrii tropikalnych , to gałąź matematyki odpowiadających badań zmodyfikowanego układu poprzez przekształcenie do dodawania i mnożenia (a zatem innych operacji). Zdefiniowano dwie algebry tropikalne: algebrę min-plus zdefiniowaną przez minimum dla dodawania i dodawania dla mnożenia oraz algebrę max-plus , określoną przez maksimum dla dodawania i dodawania dla mnożenia.
Matematyka tropikalna została tak nazwana na cześć ich brazylijskiego wynalazcy , Imre Simona . Użycie przymiotnika tropikalny przypisuje Jean-Eric Pin Dominique'owi Perrinowi , podczas gdy sam Imre Simon przypisuje go Christianowi Choffrutowi. Termin tropikalny nie ma innego znaczenia niż odniesienie do Brazylii.
Połowa ciała max-plus
Zestaw R liczb rzeczywistych, o ile z operacjami maksymalnej i ponadto posiada przemienne pół - strukturę pola .
Operatory matematyczne
- Dodatek tropikalny definiuje się jako:
⊕{\ styl wyświetlania \ plus}
w⊕b=maks(w,b){\ displaystyle a \ oplus b = \ max (a, b)}
.
Wynik tropikalnego dodania dwóch liczb jest zatem ich maksimum. Więc ...
2⊕3=maks(2,3)=3{\ displaystyle 2 \ oplus 3 = \ max (2,3) = 3}![2 \ oplus 3 = \ max (2,3) = 3](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd44c75577741ef31dcb86840f2c7a3d403f1e78)
- Mnożenie tropikalne (lub produkt tropikalny) (lub ) jest zdefiniowane przez:
⊙{\ styl wyświetlania \ odot}
⊗{\ styl wyświetlania \ czasami}
w⊙b=w+b{\ styl wyświetlania a \ odot b = a + b}
.
Wynik tropikalnego mnożenia dwóch liczb jest więc zwykłą ich sumą. Więc ...
2⊙3=2+3=5{\ styl wyświetlania 2 \ odot 3 = 2 + 3 = 5}![2 \ odot 3 = 2 + 3 = 5](https://wikimedia.org/api/rest_v1/media/math/render/svg/c629d251eaabfbdcaf7589272cd741eb5f7563eb)
Właściwości operatora
Dodatek tropikalny , podobnie jak dodatek zwykły, przemienny i asocjacyjny . W ; jeśli pracujemy w , neutralnym elementem jest wtedy ; rzeczywiście . Nie ma elementu przeciwnego danemu elementowi: do tego konieczne jest, aby .
R{\ styl wyświetlania \ mathbb {R}}
R∪{-∞}{\ displaystyle \ mathbb {R} \ filiżanka \ {- \ infty \}}
-∞{\ styl wyświetlania - \ infty}
w⊕(-∞)=maks(w,-∞)=w{\ displaystyle a \ oplus (- \ infty) = \ max (a, - \ infty) = a}
w⊕x=maks(w,x)=(-∞){\ displaystyle a \ oplus x = \ max (a, x) = (- \ infty)}
w=x=(-∞){\ displaystyle a = x = (- \ infty)}![{\ displaystyle a = x = (- \ infty)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c1a11561a3a79fcbdd7efa8527e1bf209a91085)
Tropikalny mnożenie , podobnie jak mnożenie zwykle przemienne i asocjacyjne . Jest rozdzielczy w stosunku do dodatku tropikalnego . Liczba 0 jest neutralnym elementem mnożenia tropikalnego. Aby mieć element chłonny pracujemy w . Elementem chłonnym jest wtedy . Rzeczywiście . Każdy element ma odwrotność do mnożenia tropikalnego, ponieważ rzeczywiście .
⊕{\ styl wyświetlania \ plus}
R∪{+∞}{\ displaystyle \ mathbb {R} \ filiżanka \ {+ \ infty \}}
+∞{\ styl wyświetlania + \ infty}
w⊕(+∞)=maks(w,+∞)=+∞{\ displaystyle a \ oplus (+ \ infty) = \ max (a, + \ infty) = + \ infty}
w⊙(-w)=0{\ displaystyle a \ odot (-a) = 0}![a \ odot (-a) = 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/19d51787e667c5cb8c4beea69447d036209e84b6)
W strukturze brakuje elementu neutralnego dla pierwszego prawa i istnienia elementu symetrycznego dla pierwszego prawa, tak że struktura jest ciałem. Mówimy wtedy o półciele .
(R,⊕,⊙){\ styl wyświetlania (\ mathbb {R}, \ oplus, \ odot)}
(R,⊕,⊙){\ styl wyświetlania (\ mathbb {R}, \ oplus, \ odot)}![(\ mathbb {R}, \ oplus, \ odot)](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ebb91404e294024551489dd8d814420d5d811a9)
Moc tropikalna
Tropikalnych moc , zauważył , z pomocą liczby rzeczywistej a n jest liczbą naturalną odpowiada zwykłego mnożenia. W rzeczy samej,
w⊙nie{\ displaystyle a ^ {\ odot n}}![{\ displaystyle a ^ {\ odot n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b22b7f53176733e4deb050802fdda719f4db0dd8)
w⊙nie=w⊙⋯⊙w⏞nie czas=w+⋯+w⏞nie czas=nie×w{\ displaystyle a ^ {\ odot n} = \ nawias {a \ odot \ cdots \ odot a} ^ {n {\ tekst {razy}}} = \ nawias {a + \ cdots + a} ^ {n {\ tekst {razy}}} = n \ razy a}![{\ displaystyle a ^ {\ odot n} = \ nawias {a \ odot \ cdots \ odot a} ^ {n {\ tekst {razy}}} = \ nawias {a + \ cdots + a} ^ {n {\ tekst {razy}}} = n \ razy a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8449829a9e2fefcc1d6b0987b5ba3ee3785a49a2)
.
Zatem wielomian tropikalny w 2 zmiennych
w⊙x⊕b⊙tak⊕vs{\ displaystyle a \ odot x \ oplus b \ odot y \ oplus c}![{\ displaystyle a \ odot x \ oplus b \ odot y \ oplus c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab201b71b698847d599d1b3b92e0bc05573c43d6)
jest napisane, z bardziej zwykłymi zapisami,
maks(w+x,b+tak,vs){\ styl wyświetlania \ max (a + x, b + y, c)}![{\ styl wyświetlania \ max (a + x, b + y, c)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e8688143a33ab3f5b091ec2763321de75668cb8)
Połowa ciała min-plus
Inna struktura półciała jest zdefiniowana przez przyjęcie minimum zamiast maksimum jako pierwszego prawa.
Wielomiany tropikalne
Umieszczamy się w min-plus połowie ciała. Tropikalny wielomian jest funkcją , która może być wyrażona jako tropikalny sumy skończonej liczby terminów Jednomian. Każdy jednomian jest tropikalnym iloczynem stałej i zmiennych wziętych w zbiorze . Zatem wielomian tropikalny to F jest minimum skończonej rodziny afinicznych przekształceń liniowych, w których zmienne mają współczynniki liniowe; jest to funkcja wklęsła , ciągła i odcinkowo liniowa :
fa:Rnie→R{\ displaystyle F: \ mathbb {R} ^ {n} \ do \ mathbb {R}}
X1,...,Xnie{\ styl wyświetlania X_ {1}, \ ldots, X_ {n}}![{\ styl wyświetlania X_ {1}, \ ldots, X_ {n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac794f5521dcce89913085a6d566e7cdb615dbb0)
fa(X1,...,Xnie)=(VS1⊗X1⊗w11⊗⋯⊗Xnie⊗wnie1)⊕⋯⊕(VSs⊗X1⊗w1s⊗⋯⊗Xnie⊗wnies)=min{VS1+w11X1+⋯+wnie1Xnie,...,VSs+w1sX1+⋯+wniesXnie}.{\ displaystyle {\ początek {wyrównany} F (X_ {1}, \ ldots, X_ {n}) & = \ lewo (C_ {1} \ orazy X_ {1} ^ {\ orazy a_ {11}} \ orazy \ cdots \ otimes X_ {n} ^ {\ otimes a_ {n1}} \ po prawej) \ oplus \ cdots \ oplus \ po lewej (C_ {s} \ otimes X_ {1} ^ {\ otimes a_ {1s}} \ otimes \ cdots \ otimes X_ {n} ^ {\ otimes a_ {ns}} \ po prawej) \\ & = \ min \ {C_ {1} + a_ {11} X_ {1} + \ cdots + a_ {n1} X_ {n}, \; \ ldots, \; C_ {s} + a_ {1s} X_ {1} + \ cdots + a_ {ns} X_ {n} \}. \ end {wyrównany}}}![{\ displaystyle {\ początek {wyrównany} F (X_ {1}, \ ldots, X_ {n}) & = \ lewo (C_ {1} \ orazy X_ {1} ^ {\ orazy a_ {11}} \ orazy \ cdots \ otimes X_ {n} ^ {\ otimes a_ {n1}} \ po prawej) \ oplus \ cdots \ oplus \ po lewej (C_ {s} \ otimes X_ {1} ^ {\ otimes a_ {1s}} \ otimes \ cdots \ otimes X_ {n} ^ {\ otimes a_ {ns}} \ po prawej) \\ & = \ min \ {C_ {1} + a_ {11} X_ {1} + \ cdots + a_ {n1} X_ {n}, \; \ ldots, \; C_ {s} + a_ {1s} X_ {1} + \ cdots + a_ {ns} X_ {n} \}. \ end {wyrównany}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/945ef575435e334a50572e62d936493d81433199)
Zbiór punktów, w których wielomian tropikalny F jest nieróżniczkowalny, nazywa się jego hiperpowierzchnią tropikalną i jest oznaczony (analogicznie do rozmaitości algebraicznych . Równoważnie jest to zbiór punktów, w których minimum wyrazów F jest osiągane przez co najmniej 2 wyrazy.
V(fa){\ styl wyświetlania \ matematyka {V} (F)}
V(fa){\ styl wyświetlania \ matematyka {V} (F)}![{\ styl wyświetlania \ matematyka {V} (F)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/106b5230121985e2de94033b7aab7c1036ccb577)
Zastosowanie: obliczanie odległości na wykresie
Element jest dodawany do R i cała konstrukcja jest dostarczana min-plus; tak zdefiniowaną strukturę można wykorzystać do obliczenia najkrótszej odległości na grafie.
+∞{\ styl wyświetlania + \ infty}![+ \ infty](https://wikimedia.org/api/rest_v1/media/math/render/svg/bddbb0e4420a7e744cf71bd71216e11b0bf88831)
Reprezentujemy graf ważony na n wierzchołkach przez macierz, która podaje odległości między każdym wierzchołkiem: jeśli wierzchołek i jest połączony z wierzchołkiem j, to element jest równy wadze krawędzi ( i , j ), jeśli wierzchołki i a j nie są połączone to odpowiada nieskończoności (mamy ).
W=(wja,jot){\ styl wyświetlania A = (a_ {i, j})}
wja,jot{\ styl wyświetlania a_ {i, j}}
wja,jot{\ styl wyświetlania a_ {i, j}}
wja,ja=0{\ styl wyświetlania a_ {i, i} = 0}![a _ {{i, i}} = 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5b156d2a892ef1df345b080e4a52143e1d70a62)
Zatem odległość między i i j przechodzącymi przez co najwyżej jeden wierzchołek wynosi:
mink∈{1,⋯,nie}(wja,k+wk,jot)=⨁k∈{1,⋯,nie}wja,k⊙wk,jot{\ displaystyle \ min _ {k \ in \ {1, \ cdots, n \}} (a_ {i, k} + a_ {k, j}) = \ bigoplus _ {k \ in \ {1, \ cdots , n \}} a_ {i, k} \ odot a_ {k, j}}![\ min _ {{k \ in \ {1, \ cdots, n \}}} (a _ {{i, k}} + a _ {{k, j}}) = \ bigoplus _ {{k \ in \ { 1, \ cdots, n \}}} a _ {{i, k}} \ odot a _ {{k, j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb146a63c4ef5edba08891b5c28095fdfcc1d992)
Odpowiada to iloczynowi matrycy w strukturze min-plus. Więc obliczyć długość najkrótszej ścieżki z jednym wierzchołkiem do drugiego, mamy co najwyżej n krokach, na wykresie, wystarczy obliczyć moc n od A do tej struktury.
Bibliografia
-
To jest definicja matematyki tropikalnej autorstwa ich wynalazcy Imre Simona, online na Scientific Commons
-
Ilia Itenberg, „ Wprowadzenie do geometrii tropikalnej » ,P. 2
-
Jean- Eric Pin, „Tropical Semirings” , w J. Gunawardena, Idempotentność (Bristol, 1994) , Cambridge, Cambridge University Press,1998, s. 50-69.
-
Imre Simon, „Rozpoznawalne zbiory z krotnościami w tropikalnym półkolu” , w Mathematical Foundations of Computer Science (Carlsbad, 1988) , Springer, coll. "Lecture Notes in Computer Science" ( N O 324)
1988( czytaj online ) , s. 107–120.
-
Mathoverflow, 2011, Co jest tropikalnego w algebrze tropikalnej? na Mathoverflow
-
David Speyer i Bernd Sturmfels , „ Matematyka tropikalna ”, Magazyn Mathematics , tom. 82, n o 3,2009, s. 163–173 ( DOI 10.1080/0025570X.2009.11953615 , przeczytaj online ).
Zobacz również
Bibliografia
- Ilia Itenberg, „ Prawa tropikalne ”, Obrazy matematyki , CNRS,2011( przeczytaj online )
- (en) Diane Maclagan i Bernd Sturmfels, Wprowadzenie do geometrii tropikalnej , Providence (RI), Amerykańskie Towarzystwo Matematyczne, coll. " Studia matematyki " ( N O 161)kwiecień 2015, 363 s. ( ISBN 978-0-8218-5198-2 , czytaj online )
- Ilia Itenberg, Grigorij Michałkin i Eugenii Szustin, Tropikalna geometria algebraiczna , Bazylea, Birkhäuser, coll. "Oberwolfach Seminars" ( N O 35)2009( ISBN 978-3-0346-0047-7 , OCLC 310400815 )
- Dima Grigoriev, „ Tropikalne równania różniczkowe ”, Postępy w matematyce stosowanej , tom. 82,Javier 2017, s. 120–128 ( DOI 10.1016 / j.yam.2016.08.002 , arXiv 1502.08010.pdf )
- Dima Grigoriev , „ Tropikalne sekwencje rekurencyjne ”, Postępy w matematyce stosowanej , tom. 116,2020Artykuł N O 102012 ( DOI 10.1016 / j.aam.2020.102012 , arXiv 1807,10714 )
- Antoine Chambert-Loir , „ Gdy geometria staje tropikalny ” Pour La Science , n o 492,październik 2018, s. 26-33
- (de) Hannah Markwig , „Tropische Geometrie” w Katrin Wendland , Annette Werner (red.), Facettenreiche Mathematik , Wiesbaden, Vieweg + Teubner Verlag,2011( ISBN 978-3-8348-1414-2 )
Powiązane artykuły
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">