Unimodulární matice
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7c/Unimodular_product.svg/220px-Unimodular_product.svg.png)
V matematice se čtvercová celočíselná matice s determinantem +1 nebo -1 nazývá unimodulární matice. Ekvivalentně je to celočíselná matice , která je invertibilní v oboru celých čísel: existuje celočíselná matice , která je k ní inverzní (tyto podmínky jsou ekvivalentní podle Cramerova pravidla). Každá soustava lineárních rovnic , kde i mají celočíselné složky a je unimodulární, má celočíselné řešení. Množina unimodulárních matic řádu tvoří vzhledem k maticovému součinu grupu zvanou obecná lineární grupa nad a označovanou .
Definice
Čtvercová matice se nazývá unimodulární, jestliže pro její determinant platí:
Ukázky
Matice
je unimodulární: Její determinant je . Inverzní matice
je opět celočíselná a unimodulární. Důležitými třídami celočíselných unimodulárních matic jsou permutační matice, pro které je přesně jeden prvek v každém řádku a sloupci roven , a monomiální matice, pro které je přesně jeden prvek v každém řádku a sloupci nebo . V obou uvedených typech matic jsou všechny ostatní prvky rovny .
Vlastnosti
Unimodulární matice tvoří podgrupu obecné lineární grupy vzhledem k násobení matic, tj. následující matice jsou unimodulární:
- Jednotková matice
- Inverze unimodulární matice
- Součin dvou unimodulárních matic
Mezi další příklady patří:
- Pascalovy matice,
- permutační matice,
- tři transformační matice v ternárním stromu primitivních pythagorejských trojic,
- některé transformační matice pro rotaci, zkosení (obě s determinantem 1) a symetrii (determinant −1),
- unimodulární matice používaná (implicitně) při redukci mřížky a v Hermitově normálním tvaru matic,
- Kroneckerův součin dvou unimodulárních matic je rovněž unimodulární. Toto následuje od kde a jsou rozměry a , v tomto pořadí.
Některé unimodulární matice lze získat součinem trojúhelníkových unimodulárních matic a permutačních matic jako na obrázku výše. Jde jen o výpočet matice z daného LUP rozkladu.
Totálně unimodulární matice
Totálně unimodulární matice[1] je matice, pro kterou je každá čtvercová nesingulární podmatice unimodulární. Ekvivalentně, determinant každé čtvercové podmatice je roven -1, 0 nebo +1. Totálně unimodulární matice sama o sobě nemusí být čtvercová. Z definice vyplývá, že jakákoli podmatice totálně unimodulární matice je sama o sobě totálně unimodulární.
Totálně unimodulární matice jsou extrémně důležité v polyedrické kombinatorice a kombinatorické optimalizaci, protože poskytují rychlý způsob, jak ověřit, že lineární program je celočíselný (má celočíselné optimum, pokud nějaké existuje). Z Cramerova pravidla bezprostředně vyplývá, že pokud je totálně unimodulární a je celočíselné, pak lineární programy tvarů nebo mají pro jakékoli celočíselná optimální řešení, pokud je množina řešení neprázdná. Pokud je tedy totálně unimodulární a je celočíselné, každý krajní bod množiny přípustných řešení, např. , je celočíselný, a proto je množina přípustných řešení mnohostěnem s vrcholy v bodech celočíselné mřížky .
Ukázky
1. Následující matice je totálně unimodulární:
Tato matice vzniká jako matice koeficientů omezení ve formulaci lineárního programování problému maximálního toku v následující síti:
2. Jakákoli matice ve tvaru
není totálně unimodulární, protože má čtvercovou podmatici s determinantem −2.
Vlastnosti
- V unimodulární matici se mohou vyskytovat pouze čísla -1,0 a 1. Protože i determinanty jednotlivých prvků matice musí být -1,0 nebo 1, může se matice skládat pouze z těchto čísel. Ovšem ne každá matice skládající se z těchto čísel je totálně unimodulární.
- Totálně unimodulární matice jsou uzavřené na:
- permutaci řádků
- transpozici
- vynásobení řádku koeficientem
- přidání/vynechání řádku s jediným nenulovým prvkem
- přidání/vynechání nulového řádku
- Incidenční matice orientovaného grafu je totálně unimodulární
- Incidenční matice neorientovaného grafu je totálně unimodulární právě když je graf bipartitní
- Dvě polynomiální matice odpovídajících rozměrů jsou nesoudělné, když všechny jejich největší společní dělitelé jsou unimodulární matice.
Použití
Velký význam má v úlohách celočíselného programování, kde pro výpočet řešení umožňuje použít jednodušší algoritmy obecného lineárního programování.
Konstrukce totálně unimodulárních matic
1. Neorientovaná incidenční matice bipartitního grafu, která je koeficientovou maticí pro bipartitní párování, je totálně unimodulární. (Neorientovaná incidenční matice nebipartitního grafu totálně unimodulární není.) A. J. Hoffman a D. Gale dokazují v příloze článku Hellera a Tompkinse [2] následující zobecnění: Nechť je matice typu , jejíž řádky lze rozdělit do dvou disjunktních množin a . Potom následující čtyři podmínky společně postačují k tomu, aby byla totálně unimodulární:
- Každý prvek je 0, +1 nebo -1.
- Každý sloupec obsahuje nejvýše dva nenulové prvky (tj. +1 nebo −1).
- Pokud mají dva nenulové prvky ze stejného sloupce stejné znaménko, pak řádek jednoho patří do a řádek druhého do .
- Pokud mají dva nenulové prvky ze stejného sloupce opačná znaménka, pak jejich řádky jsou oba v , nebo oba v .
Později bylo zjištěno, že tyto podmínky určují incidenční matici vyváženého signed grafu, neboli grafu, kde každá hrana má přiřazeno znaménko a přitom součin znamének podél každého cyklu je kladný. Uvedená ukázka znamená, že incidenční matice signed grafu je totálně unimodulární, pokud je graf vyvážený. Uvedený vztah platí i obráceně pro signed grafy bez půlhran.[3]
2. Omezení problémů maximálního toku a toku minimálního nákladu dávají matici koeficientů s těmito vlastnostmi (a s prázdným ). Uvedené tokové problémy s omezenými celočíselnými kapacitami mají celočíselné optimální řešení. Zobecnění ovšem neplatí pro problémy multikomoditních toků, ve kterých je možné mít jednoznačné racionální optimální řešení i s omezenými celočíselnými kapacitami.
3. Vlastnost po sobě jdoucích jedniček: pokud lze řádky a sloupce 0-1 matice přerovnat tak, že jedničky v každém řádku tvoří souvislý úsek, pak je totálně unimodulární. (Totéž platí pro sloupce, protože transpozice zachovává totální unimodularitu.) [4]
4. Každá matice sítě je totálně unimodulární. Řádky matice odpovídají libovolně zorientovanému stromu , přičemž není nutné, aby všechny hrany směřovaly k nějakému kořeni nebo od něj. Sloupce odpovídají jiné množině orientovaných hran na stejné množině vrcholů . Je-li hrana orientovaná z vrcholu do vrcholu a je cesta v z do , pak hodnota ve -tém sloupci a -tém řádku matice je:
- +1, pokud se hrana objeví ve směru cesty ,
- −1, pokud se hrana objeví proti směru cesty ,
- 0, pokud hrana na cestě neobjeví.
Více viz Schrijver (2003).
5. Ghouila-Houri ukázal, že matice je totálně unimodulární, pokud pro každou podmnožinu řádků existuje přiřazení znamének řádkům tak, že lineární kombinace (což je řádkový vektor, jehož délka je rovna šířce matice a má všechny své prvky v ). Uvedená charakterizace a několik dalších jsou dokázány v Schrijver (1998).
6. Hoffman a Kruskal[5] dokázali následující větu: Nechť je orientovaný graf bez 2-dicyklů, je množina všech orientovaných cest v , a je matice incidence vrcholů v cestách z . Pak je totálně unimodulární, právě když se každý jednoduchý cyklus v skládá ze střídavě orientovaných hran.
7. Předpokládejme, že prvky matice jsou v každém sloupci uspořádány neklesajícím způsobem, čili všechny −1 jsou nahoře, potom 0 a spodní úsek tvoří 1. Fujishige[6] ukázal, že matice je totálně unimodulární, když každá regulární podmatice řádu 2 má determinant .
8. Úplnou charakterizaci všech totálně unimodulárních matic podal Seymour v roce 1980.[7] Seymourova věta neformálně říká, že matice je totálně unimodulární, právě když je určitou přirozenou kombinací některých matic sítě a případně kopií následující totálně unimodulární matice:
Abstraktní lineární algebra
V abstraktní lineární algebře se studují matice s prvky z libovolného komutativního okruhu , t.j. nejen celočíselné. V tomto kontextu je unimodulární matice ta, která je invertibilní nad okruhem; ekvivalentně, jejímž determinantem je jednotkový prvek. Tato grupa se značí .[8] Obdélníková matice typu se nazývá unimodulární, pokud ji lze rozšířit řádky v na unimodulární čtvercovou matici.
Nad tělesem má termín unimodulární stejný význam jako regulární. Unimodulární značí matice s koeficienty v nějakém okruhu (často celá čísla), které jsou invertibilní v tomto okruhu, přičemž těleso je speciální případ okruhu.
Odkazy
Reference
V tomto článku byly použity překlady textů z článků Unimodular matrix na anglické Wikipedii a Ganzzahlige unimodulare Matrix na německé Wikipedii.
- ↑ Termín zavedl Claude Berge, viz HOFFMAN, Alan J.; KRUSKAL, Joseph B. Introduction to Integral Boundary Points of Convex Polyhedra. Příprava vydání Michael Jünger, Thomas M. Liebling, Denis Naddef, George L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, Laurence A. Wolsey. Berlin, Heidelberg: Springer Dostupné online. ISBN 978-3-540-68279-0. DOI 10.1007/978-3-540-68279-0_3. S. 49–50. (anglicky) DOI: 10.1007/978-3-540-68279-0_3.
- ↑ HELLER, I.; TOMPKINS, C. B. Linear Inequalities and Related Systems. Redakce Kuhn H. W.. Princeton (NJ): Princeton University Press, 1956. (Annals of Mathematics Studies; sv. 38). Kapitola An Extension of a Theorem of Dantzig's, s. 247–254. Je zde použita šablona
{{Citation}}
označená jako k „pouze dočasnému použití“. - ↑ T. Zaslavsky (1982), "Signed graphs," Discrete Applied Mathematics 4, pp. 401–406.
- ↑ projecteuclid.org. Dostupné online. Je zde použita šablona
{{Cite journal}}
označená jako k „pouze dočasnému použití“. - ↑ HOFFMAN, A. J.; KRUSKAL, J. B. Linear Inequalities and Related Systems. Redakce Kuhn H. W.. Princeton (NJ): Princeton University Press, 1956. (Annals of Mathematics Studies; sv. 38). Kapitola Integral Boundary Points of Convex Polyhedra, s. 223–246. Je zde použita šablona
{{Citation}}
označená jako k „pouze dočasnému použití“. - ↑ FUJISHIGE, Satoru. A system of linear inequalities with a submodular function on {0,±1}; vectors. Linear Algebra and its Applications. 1984-12, roč. 63, s. 253–266. Dostupné online [cit. 2023-12-25]. DOI 10.1016/0024-3795(84)90147-2. (anglicky)
- ↑ SEYMOUR, P.D. Decomposition of regular matroids. Journal of Combinatorial Theory, Series B. 1980-06, roč. 28, čís. 3, s. 305–359. Dostupné online [cit. 2023-12-25]. DOI 10.1016/0095-8956(80)90075-1. (anglicky)
- ↑ LANG, Serge. Algebra. rev. 3rd ed. vyd. New York Berlin Heidelberg [etc.]: Springer (Graduate texts in mathematics). ISBN 978-0-387-95385-4.
Literatura
- PAPADIMITRIOU, Christos H.; STEIGLITZ, Kenneth. Combinatorial optimization: algorithms and complexity. 6. pr. vyd. Englewood Cliffs, N.J: Prentice-Hall, 1982. 496 s. Dostupné online. ISBN 978-0-13-152462-0.
- SCHRIJVER, Alexander. Theory of linear and integer programming. Nachdr.. vyd. Chichester Weinheim: Wiley, 1998. 471 s. (Wiley-Interscience series in discrete mathematics and optimization). ISBN 978-0-471-98232-6.
- SCHRIJVER, Alexander. Combinatorial optimization: polyhedra and efficiency. Berlin Heidelberg: Springer, 2003. (Algorithms and combinatorics). ISBN 978-3-540-44389-6.
Související články
- Vyvážená matice
- Regulární matroid
- Speciální lineární grupa
Externí odkazy
- Unimodulární matice z MathWorld (angl.)
- Mathematical Programming Glossary Archivováno 9. 11. 2023 na Wayback Machine. (angl.)
- Software pro testování úplné unimodularity od M. Waltera a K. Truempera.