Unimodulární matice

V matematice se čtvercová celočíselná matice s determinantem +1 nebo -1 nazývá unimodulární matice. Ekvivalentně je to celočíselná matice ${\boldsymbol {A}}$ , která je invertibilní v oboru celých čísel: existuje celočíselná matice ${\boldsymbol {B}}$ , která je k ní inverzní (tyto podmínky jsou ekvivalentní podle Cramerova pravidla). Každá soustava lineárních rovnic ${\boldsymbol {Ax}}={\boldsymbol {b}}$ , kde ${\boldsymbol {A}}$ i ${\boldsymbol {b}}$ mají celočíselné složky a ${\boldsymbol {A}}$ je unimodulární, má celočíselné řešení. Množina unimodulárních matic řádu $n$ tvoří vzhledem k maticovému součinu grupu zvanou obecná lineární grupa nad $\mathbb {Z}$ a označovanou $\operatorname {GL} _{n}(\mathbb {Z} )$ .

Definice

Čtvercová matice ${\boldsymbol {A}}\in \mathbb {Z} ^{n\times n}$ se nazývá unimodulární, jestliže pro její determinant platí:

\det {\boldsymbol {A}}\in \{1,-1\}

Ukázky

Matice

{\boldsymbol {A}}={\begin{pmatrix}2&1\\5&3\end{pmatrix}}\in \mathbb {Z} ^{2\times 2}

je unimodulární: Její determinant je $\det(A)=2\cdot 3-5\cdot 1=1$ . Inverzní matice

{\boldsymbol {A}}^{-1}={\begin{pmatrix}3&-1\\-5&2\end{pmatrix}}

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 $1$ , a monomiální matice, pro které je přesně jeden prvek v každém řádku a sloupci $+1$ nebo $-1$ . V obou uvedených typech matic jsou všechny ostatní prvky rovny $0$ .

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 $\det({\boldsymbol {A}}\otimes {\boldsymbol {B}})=(\det {\boldsymbol {A}})^{q}(\det {\boldsymbol {B}})^{p},$ kde $p$ a $q$ jsou rozměry ${\boldsymbol {A}}$ a ${\boldsymbol {B}}$ , 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 ${\boldsymbol {A}}$ je totálně unimodulární a ${\boldsymbol {b}}$ je celočíselné, pak lineární programy tvarů $\{\min {\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\mid {\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq 0\}$ nebo $\{\max {\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\mid {\boldsymbol {Ax}}\leq {\boldsymbol {b}}\}$ mají pro jakékoli ${\boldsymbol {c}}$ celočíselná optimální řešení, pokud je množina řešení neprázdná. Pokud je tedy ${\boldsymbol {A}}$ totálně unimodulární a ${\boldsymbol {b}}$ je celočíselné, každý krajní bod množiny přípustných řešení, např. $\{{\boldsymbol {x}}\mid {\boldsymbol {Ax}}\leq {\boldsymbol {b}}\}$ , je celočíselný, a proto je množina přípustných řešení mnohostěnem s vrcholy v bodech celočíselné mřížky $\mathbb {Z} ^{d}$ .

Ukázky

1. Následující matice je totálně unimodulární:

{\boldsymbol {A}}={\begin{pmatrix}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\end{pmatrix}}

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

{\boldsymbol {A}}=\left[{\begin{array}{ccccc}&\vdots &&\vdots \\\dotsb &+1&\dotsb &+1&\dotsb \\&\vdots &&\vdots \\\dotsb &+1&\dotsb &-1&\dotsb \\&\vdots &&\vdots \end{array}}\right].

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 $-1$
- 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ť ${\boldsymbol {A}}$ je matice typu $m\times n$ , jejíž řádky lze rozdělit do dvou disjunktních množin $B$ a $C$ . Potom následující čtyři podmínky společně postačují k tomu, aby ${\boldsymbol {A}}$ byla totálně unimodulární:

Každý prvek ${\boldsymbol {A}}$ je 0, +1 nebo -1.
Každý sloupec ${\boldsymbol {A}}$ obsahuje nejvýše dva nenulové prvky (tj. +1 nebo −1).
Pokud mají dva nenulové prvky ze stejného sloupce ${\boldsymbol {A}}$ stejné znaménko, pak řádek jednoho patří do $B$ a řádek druhého do $C$ .
Pokud mají dva nenulové prvky ze stejného sloupce ${\boldsymbol {A}}$ opačná znaménka, pak jejich řádky jsou oba v $B$ , nebo oba v $C$ .

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 $C$ ). 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 ${\boldsymbol {A}}$ přerovnat tak, že jedničky v každém řádku tvoří souvislý úsek, pak ${\boldsymbol {A}}$ 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 $T=(V,R)$ , 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ě $S$ orientovaných hran na stejné množině vrcholů $V$ . Je-li $s\in S$ hrana orientovaná z vrcholu $u$ do vrcholu $v$ a $P$ je cesta v $T$ z $u$ do $v$ , pak hodnota ve $s$ -tém sloupci a $r$ -tém řádku matice je:

+1, pokud se hrana $r\in R$ objeví ve směru cesty $P$ ,
−1, pokud se hrana $r$ objeví proti směru cesty $P$ ,
0, pokud hrana $r$ na cestě $P$ 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ů $R$ existuje přiřazení $s:R\to \pm 1$ znamének řádkům tak, že lineární kombinace $\sum _{{\boldsymbol {r}}\in R}s({\boldsymbol {r}}){\boldsymbol {r}}\in \{0,+1,-1\}^{n}$ (což je řádkový vektor, jehož délka $n$ je rovna šířce matice a má všechny své prvky v $\{0,\pm 1\}$ ). 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ť $G$ je orientovaný graf bez 2-dicyklů, $P$ je množina všech orientovaných cest v $G$ , a ${\boldsymbol {A}}$ je matice incidence vrcholů $V(G)$ v cestách z $P$ . Pak ${\boldsymbol {A}}$ je totálně unimodulární, právě když se každý jednoduchý cyklus v $G$ 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 $\pm 1$ .

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:

${\begin{pmatrix}-1&1&0&0&1\\1&-1&1&0&0\\0&1&-1&1&0\\0&0&1&-1&1\\1&0&0&1&-1\\\end{pmatrix}}$

Abstraktní lineární algebra

V abstraktní lineární algebře se studují matice s prvky z libovolného komutativního okruhu $R$ , 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čí $\operatorname {GL} _{n}(R)$ .^[8] Obdélníková matice typu $m\times n$ se nazývá unimodulární, pokud ji lze rozšířit $n-m$ řádky v $T^{n}$ 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.
↑ T. Zaslavsky (1982), "Signed graphs," Discrete Applied Mathematics 4, pp. 401–406.
↑ projecteuclid.org. Dostupné online.
↑ 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.
↑ 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

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.

[1] 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.

[2] 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.

[3] T. Zaslavsky (1982), "Signed graphs," Discrete Applied Mathematics 4, pp. 401–406.

[4] projecteuclid.org. Dostupné online.

[5] 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.

[6] 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)

[7] 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)

[8] LANG, Serge. Algebra. rev. 3rd ed. vyd. New York Berlin Heidelberg [etc.]: Springer (Graduate texts in mathematics). ISBN 978-0-387-95385-4.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]