Igazából sejtettem, hogy a problémát nem én "találtam fel", de a nevét sem ismertem. Valóban, ilyen kis adatmennyiségnél a 'brutal force' is működik - de köszönöm, hogy az általánosságra is rávilágítottál.
Ez egy közismert NP-teljes probléma, lásd itt. Az NP-teljes azt jelenti a gyakorlatban, hogy valószínűleg nincs polinomiális algoritmus a megoldására.
Ha a városok száma legfeljebb néhány száz, akkor vannak hatékony algoritmusok (ezt nemrég hallottam egy kollegámtól, aki a gyakorlatban is használ ilyen algoritmusokat). A Te konkrét példádra a legegyszerűbb program is megtalálja a választ, hiszen összesen 720 lehetséges útvonal van.
Külföldi nyaralásra készülünk bérautóval. Meg szeretnénk nézni n várost, és ismert közülük bármely (i-edik) város bármely (j-edik) másiktól vett dij=dji távolsága (e szempontból a városok legyenek pontszerűek). Itthonról (az n közül) egy bizonyos A városba érkezünk (ott bérelünk autót) és ugyanonnan indulunk majd haza. Hogyan találjuk meg azt a legrövidebb útvonalat, amely A-ból indul, A-ba érkezik és amely mentén mind az n várost legalább egyszer érintjük?
(Az idő, az üzemanyag és egyéb erőforrások korlátlannak tekintendők.)
Legyen pl. n=7, az A város a 2-es és a dij=dji értékek az ábra szerintiek.
De engem éppen az érdekel, hogy a szignatúra mitől függ, mivel van/lehet még összefüggésben.
Mint mondtam, a szignatúra a valós szimmetrikus mátrixok egyetlen invariánsa, és azt írja le, hogy az általa definiált szimmetrikus bilineáris forma (azaz "skalárszorzat") mekkora altéren pozitív definit és mekkora altéren negatív definit. Megfogalmazhatjuk így is: ha A és B valós szimmetrikus mátrixok, akkor annak szükséges és elégséges feltétele, hogy A=MTBM legyen valamilyen valós invertálható M mátrixszal (ahol MT az M transzponáltja), az, hogy A és B szignatúrája megegyezzék. (Az A=MTBM reláció persze azt írja le, hogy A és B ugyanazt a szimmetrikus bilineáris formát határozza meg két különböző bázisban, amik között M az átmenő leképezés.)
Kérdés1: ez megőrzi még L sajátértékeinek a számát? Szerintem igen
Egy mátrix bármely konjugáltjának ugyanazok a sajátértékei (multiplicitással), mint az eredeti mátrixnak. Ez elég nyilvánvaló, hiszen egy mátrix és a konjugáltja ugyanazt a lineáris transzformációt írja le két különböző bázisban, a sajátértékek pedig a lineáris transzformáció tulajdonságai (bázisfüggetlen). Általánosabban, egy mátrixnak és a konjugáltjának ugyanaz a karakterisztikus polinomja (hasonló okból kifolyólag).
Kérdés2: G-1LH-nak még ugyanannyi sajátértéke van, mint L-nek?
Általában nem. Egy átlós mátrixszal való szorzás nem őrzi meg a sajátértékek számát (és nem is felel meg mértékegység-váltásnak: a mértékegység váltás is konjugálással írható le).
P.S. A fenti állításokat bármely lineáris algebra könyvben megtalálod.
Köszönöm szépen, hogy foglalkozol velem. Lehet, hogy egy kicsit túlságosan el vagyok merülve, és aludnom kellene rá egy párat, de az agyam most jár ezen.
Amit írsz, azt tegnap bebizonyítottam magamnak. Nem tanultam, de kiszámoltam, ezért értem is amit írsz. Tetszőleges metrikus tenzort írok fel (abban az értelemben ahogy én használom, bázisvektorok skalárszorzataként adom meg: ezeket kell megadnom, ha egy VxV-->R bilineáris függvényt akarok definiálni), tehát megadok egy tetszőleges (g1,g2,g2,g4) tenzort, akkor tudok olyan bázisváltást végezni, amiben ez diagonális lesz, és utána átskálázást (újabb bázisváltás) alkalmazva tudom a metrikus tenzort az (1,1) (0,1) vagy (-1,1) alakok valamelyikére hozni. Igen, a szignatúra nem változik meg, ezért tudom ezt megtenni. De engem éppen az érdekel, hogy a szignatúra mitől függ, mivel van/lehet még összefüggésben. (Aztán lehet, hogy semmivel)
Korábban, kb. 2 éve volt egy beszélgetésünk, amikor a specrel felépítéséről beszélgettünk. Akkor adtam egy levezetést, homogenitásokra, relativitás elvére építve. Talán emlékszel rá.
Akkor elhangzott részedről egy olyan kijelentés (zárásként), hogy a levezetés eredménye(i) szoros kapcsolatot mutat azzal, hogy SL(2,R)-ben 4 db. egyparaméteres részcsoport van a konjugálás erejéig: a forgatás, a Galilei, a Lorentz trafó és az átskálázás.
A konjugálás fontos szó most nekem. Ha van pl. a Lorentz-trafóm, ami K-ból K' bázisba visz ugyebár (tudjuk mik a bázisok: az ollószerűen összezáródó tengelyek) , akkor K bázis helyett egy K* másikat használva (amibe G-vel mehetek), valamint K' helyett egy K*'-t használva (amibe szintén G-vel mehetek K'-ből) a Lorentz transzformáció egyparaméteres csoportja így íródik át K*-->K*'-re: G-1LG. Ez SL-ben marad, minden G-re. Ezért volt fontos az, hogy konjugálás erejéig. Kérdés1: ez megőrzi még L sajátértékeinek a számát? Szerintem igen (nem számoltam ki, de úgy érzem.)
Ha most bonyolításként megengedem a mértékegységváltást K'-ra való áttérésnél, akkor már nem maradok SL-ben. Akkor már a Lorentz így íródik át: G-1LH. H ekkor még csakG-nek egy diagonális mátrixszal való szorzata, ha jól gondolom. Kérdés2: G-1LH-nak még ugyanannyi sajátértéke van, mint L-nek? Sztem igen.
Tehát ez a konjugálás + átskálázás még megőrzi a forgatás/Galilei trafó/Lorentz trafó sajátértékeinek a számát.
Ezért, az egymáshoz képest egyenletesen mozgó KR-ek között szállító trafók sajátértékei számának vizsgálatával azt hiszem mégiscsak meg tudom mondani a metrikus tenzor szignatúráját. Anélkül, hogy bármi egyebet is mondtam volna rá. Magyarán (könnyebb lenne, ha megoldanád a feladatot) a Lőrinc trafó sajátértékeinek a vizsgálatával meg tudom mondani, hogy valójában a Minkowski téridőben vagyok (vagy Galilei-téridőben, vagy euklidesziben forgattam...)
Elnézést, ha nehezen vagyok követhető, akkor majd letisztázom még magamban.
A metrikus tenzor (abban az értelemben, ahogy Te használod) nem más, mint a téren adott skalárszorzat koordinátái egy adott bázisra nézve, mátrixalakban elrendezve: (<i,i> <i,j> | <j,i> <j,j>). Ez egy szimmetrikus mátrix, ami tehát diagonizálható, és ha diagonizáljuk, akkor az átlóban a sajátértékek fognak állni. A sajátértékek előjeleit (a sorrendtől eltekintve) a mátrix szignatúrájának hívjuk, és ez csakis a kiindulási skalárszorzattól függ. Magyarán egy báziscsere nem változtatja meg a metrikus tenzor szignatúráját. Továbbá ez a metrikus tenzor egyetlen invariánsa a jelen szituációban, lásd itt.
Amúgy a bizonyítás nagyon egyszerű: a szignatúra azt adja meg (tetszőleges bázisban), hogy hány dimenziós a legnagyobb altér, amin a skalárszorzat pozitív definit (ez a pozitív sajátértékek száma), illetve negatív definit (ez a negatív sajátértékek száma).
Röviden: amin töprengsz, az egy egyszerű tény a lineáris algebrából: két valós szimmetrikus mátrix akkor és csak akkor írja le ugyanazt a szimmetrikus bilineáris formát két különböző bázisban, ha a szignatúrájuk megegyezik.
A metrikus tenzor az <i,i>, <i,j>, <j,i>, <j,j> skaláris szorzatokat tartalmazza, azaz a bázisvektorok önmagukkal és egymással vett skaláris szorzatát. Ugyebár vektortérben nincs metrika, de ha megadom ezeket az értékeket, akkor már van.
Ez amit itt feladtam, ez csak egy részfeladat. Ehhez kapcsolódik:
Magát az alapfeladatot már megoldottam évekkel ezelőtt. Viszont mostanában rájöttem, hogy több rétege van ám ennek, mélyebb értelme! Aminek utána akarok jobban járni.
Ha a Lorentz transzformációt (1+1 dimenzióban) nem a szokásos bázispárban írom fel, hanem esetleg egy-egy tengelyt forgatok, skálát változtatok, stb. akkor egészen más alakokat is ölthet. Ezzel párhuzamosan azonban a metrikus tenzor is változik...
Az euklideszi forgatás 0 sajátértékkel rendelkezik, a metrikus tenzora a térnek (ortonormált bázisban) +,+
A Galilei trafó 1 sajátértékkel rendelkezik, a Galilei téridő metrikus tenzora 0,+
A Lorentz trafó 2 sajátértékkel rendelkezik, metrikus tenzora -,+
Azt tudom, hogy 2 dimenzióban, ha a távolságot parabolikusan mérem, akkor csak 3 féle síkgeometria létezik, méghozzá a fentiek.
Be szeretném látni tehát, hogy akármilyen hülyén veszem fel az egyes bázisokat (megengedek forgatást, ferde szögű bázist, skálázást, stb.) , és ezért látszólag a fentiektől eltérő téridőt írok le, valójában mégsem. Méghozzá a sajátértékek száma az, ami nekem fontos. (Szerintem) Az fogja meghatározni a metrikát, ami pedig a metrikus tenzor determinánsának előjele szerint +,0,-, azaz Euklideszi, Galilei, Minkowski.
Ez az alapproblémám, de csak egy részét közöltem, és az lehet, hogy nem is elégséges rész... Még egy kicsit agyalok, köszi, hogy válaszoltál!
A metrika független az A-tól. Ez akkor is így van, ha végtelen sok A-t tekintesz egyszerre, amik egy egyparaméteres részcsoportot alkotnak. Ha a metrikáról akarsz megtudni valamit, akkor a metrikára vonatkozó feltételeket kell megadnod.
Lehet ám, hogy kevés ez az info, amit mondtam. Könnyen lehet, hogy másra is szükségünk van még.
Azt még hozzá tudom tenni a feladathoz, hogy az A mátrixok egyparaméteres részcsoportot alkotnak GL(2,R)-ben, a paraméter az a v szám. De ezt a feltételt igyekeztem volna elkerülni, hátha enélkül is megy... Viszont nem vagyok benne biztos, hgoy enélkül is meg lehet-e oldani.
Na mind1, egy kicsit még gondolkozom rajta, vannak még kiaknázatlan ötleteim. Ha nem jutok semmire, akkor átfogalmazva, pontosítva jelentkezem!
Nem igazán értem a kérdést, hiszen az A mátrix csak a két bázistól függ, a metrikától független. Az A-ra persze megadtál egy feltételt, de ez csak a két bázisra tesz megszorítást, a metrikára nem.
A metrika csupán egy szimmetrikus nemelfajuló bilineáris forma a téren: ez független minden bázistól, illetve a bázisok közötti átmenőleképezésektől.
Egy kis segítséget kérnék. Ha kicsit pontatlan a megfogalmazásom, akkor ne akadjatok fent rajta légyszi, azért remélem sikerül elmondanom a problémámat:
Van egy ismeretlen metrikájú 2 dimenziós vektorterem R fölött. (Sík geometria.) Van benne 2 bázisom: K(i,j) és K'(i',j'). A metrikus tenzort egyik bázisban sem ismerem.
K és K' között az A mátrix szállít. Egy K-ban felírt vektort az A mátrixszal tudok átszámolni K'-be: (x',y')=A(x,y).
K és K' között az alábbi kapcsolat van: Egy K-beli (vy,y) vektor K'-ben (0,y') koordinátákkal rendelkezik, minden y-ra. Tehát A(vy,y)=(0,y'). v egy valós szám.
Annyit tudok még mondani, hogy A-nak 2 különböző valós sajátértéke van.
Mit tudok mondani a metrikus tenzorról? A determinánsának az előjele érdekelne.
A matematikában a tenzor maga is egy vektor. Kissé elnagyoltan a következőről van szó.
Ha V egy m-dimenziós vektortér, és W egy n-dimenziós vektortér, akkor a V és W tenzorszorzata (jelölje V*W) egy mn dimenziós vektortér. Ha v1,...,vm a V egy bázisa, és w1,...,wn a W egy bázisa, akkor V*W bázisa a vi*wj szimbólumok, ahol i és j az összes lehetséges kombináción fut végig (amik száma ugye mn). A * műveletet ezek után kiterjeszthetjük egyértelműen egy VxW->V*W bilineáris leképezéssé. Tehát: ha v=sumi aivi a V egy tetszőleges eleme, és w=sumj bjwj a W egy tetszőleges eleme, akkor
Például: (v1+3v2)*(2w1-7w2) = 2(v1*w1)-7(v1*w2)+6(v2*w1)-21(v2*w2), hasonlóan ahogy a hagyományos szorzásnál minden tagot szorzunk minden taggal.
Nem nehéz belátni, hogy a kapott V*W vektortér és a VxW->V*W bilineáris leképezés független a bázistól, tehát csakis a V és W vektorterektől függ.
A V*W tenzorszorzatnak van egy nagyon fontos univerzális tulajdonsága: minden VxW->Z bilineáris leképezés (ahol Z tetszőleges vektortér) előáll egyértelműen mint egy V*W->Z lineáris leképezés és a fenti VxW->V*W bilineáris leképezés kompozíciója: VxW->V*W->Z. Úgy is mondhatnánk, hogy a tenzorszorzat segítségével a bilineáris leképezéseket felfoghatjuk speciális lineáris leképezésekként és viszont.
Minden fizikától és egyéb alkalmazástól elszakítva a tenzorszorzat (vektorterek között) egy egyszerű konstrukció, a közönséges szorzás általánosítása (az, amit fent leírtam). Először ezt értsd meg, mielőtt használni akarnád.
A tenzorok megértéséhez kérnék egy kis segítséget:
Én úgy tudom, hogy a tenzor a vektorok, vagy mátrixok kiterjszetése magasabb dimenziókra. Csak vektorterben lehet értelmezni. A tenzort úgy is fel lehet fogni, mint egy lineáris transzformáció, a transzformációs mátrixhoz hasonlítható csak magasabb dimenziókban.
Ha jól tudom létezik 3D-s transzformációs mátrix, ami azt jelentené, hogy pl. a 3 dimenziós térben egy vektorokkal leírt térbeli testet átalakít (át transzformál). Ha viszont 4 dimenziós vektortérben gondolkodunk, akkor egy 4 dimenziós objektumot is át tudunk transzformálni az "alap transzformációkkal" (ha jól tudom ezek azok: nyújtás, forgatás, eltolás) ezt az összetett műveletet a tenzorral tudjuk leírni.
Viszont van a tenzoroknak még egy jellemzőjük: a segítségükkel meghatározott többdimenziós testet (vagy valamilyen fizikai jelentéssel bíró erőteret) írhatunk le a vektortérben. Ha ezt a vektorteret egy sik lappal elmetszük, akkor kapunk egy két dimenziós teret. Itt már fel lehet írni egy mátrixot, ami ebben a síkban reprezentálja a tenzort.
Én úgy tudom, hogy így érthető meg a tenzor, de javítsatok ki ah tévedek.
Az L nem változó, hanem függvény, ezért a láncszabály miatt a -C/L2 kifejezést még szorozni kell az L ("a belső függvény") deriváltjával. Szóval amit Szelki Lata mondott, az helyes.
Mindenki tegye be a közösbe a rá eső részt forintban vagy kunában. Fizessetek mindent ebből, a nyaralása után pedig a megmaradt pénzt osszátok szét egyenlő arányban. :)
Hogy osszuk a nyaralási költséget, hogy mindenki egységesen fizessen bele?
5-en megyünk, fejenként 16800 Ft-ba kerül az út, ami 400Kn Uticél: Horvátország Deviza árfolyam: 42ft=1kn Nem adhat mindenki kunát, mert itthon is kell tankolni, matricát venni. 2 fő forintba adja, vagyis 2*16800 Ft. Hogyan is kellene ezt kiszámolni, hogy ne jöjjenek ki a Ft-ok mínuszba? Figyelembe véve azt is, hogy az autó tankja az indulásnál kb félig lesz, ami ugye még a sofőr benzinje, nem a "közös".
A bizonyításban használom, hogy Y eloszlásfüggvénye differenciálható c-ben, amihez mondjuk elég feltenni, hogy Y eloszlásfüggvénye folytonos c-ben. Valószínűleg más (esetleg gyengébb) feltételek mellett is található bizonyítás, pl. X és Y eloszlásfüggvénye differenciálható mindenhol, de ezen nem fogok gondolkodni.
