Matricea unimodulară - Unimodular matrix

În matematică , o matrice unimodulară M este o matrice pătrată întreagă având determinantul +1 sau -1. În mod echivalent, este o matrice întreagă care este inversabilă peste numerele întregi : există o matrice întreagă N care este inversă (acestea sunt echivalente sub regula lui Cramer ). Astfel, fiecare ecuație Mx = b , unde M și b au ambele componente întregi și M este unimodulară, are o soluție întreagă. N  ×  n matricele unimodulari formează un grup numit n  x  n gruparea liniară generală peste care este notat . ${\ displaystyle \ mathbb {Z}}$${\ displaystyle \ operatorname {GL} _ {n} (\ mathbb {Z})}$

Exemple de matrice unimodulare

Matricile unimodulare formează un subgrup al grupului liniar general sub multiplicarea matricei , adică următoarele matrice sunt unimodulare:

• Matrice de identitate
• Inversa unei matrice unimodular
• Produsul a două matrici unimodulari

Alte exemple includ:

• Matrici Pascal
• Matrici de permutare
• cele trei matrice de transformare din arborele ternar al triplelor pitagoreice primitive
• Anumite matrice de transformare pentru rotație , forfecare (ambele cu determinantul 1) și reflecție (determinantul -1).
• Matricea unimodulară utilizată (posibil implicit) în reducerea rețelelor și în forma normală a matricelor Hermite .
• Produsul Kronecker din două matrice unimodulare este, de asemenea, unimodular. Acest lucru rezultă din moment în care p și q sunt dimensiunile A și B , respectiv.${\ displaystyle \ det (A \ otimes B) = (\ det A) ^ {q} (\ det B) ^ {p},}$

Unimodularitate totală

O matrice total unimodulară ( matricea TU) este o matrice pentru care fiecare submatrică pătrată non-singulară este unimodulară. În mod echivalent, fiecare submatrică pătrată are determinantul 0, +1 sau −1. O matrice total unimodulară nu trebuie să fie în sine pătrată. Din definiție rezultă că orice submatrică a unei matrice total unimodulare este ea însăși total unimodulară (TU). Mai mult, rezultă că orice matrice TU are doar 0, +1 sau -1 intrări. Reciproca nu este adevărată, adică o matrice cu numai 0, +1 sau -1 intrări nu este neapărat unimodular. O matrice este TU dacă și numai dacă transpunerea sa este TU.

Matricile total unimodulare sunt extrem de importante în combinatorica poliedrică și optimizarea combinatorie, deoarece oferă o modalitate rapidă de a verifica dacă un program liniar este integral (are un optim integral, atunci când există orice optim). Mai exact, dacă A este TU și b este integral, atunci programele liniare de forme ca sau au optima integrală, pentru orice c . Prin urmare, dacă A este total unimodular și b este integral, fiecare punct extrem al regiunii fezabile (de exemplu ) este integral și astfel regiunea fezabilă este un poliedru integral . ${\ displaystyle \ {\ min cx \ mid Ax \ geq b, x \ geq 0 \}}$${\ displaystyle \ {\ max cx \ mid Ax \ leq b \}}$${\ displaystyle \ {x \ mid Ax \ geq b \}}$

Matrici comune unimodulare comune

1. Matricea de incidență neorientată a unui grafic bipartit , care este matricea coeficientului pentru potrivirea bipartită , este total unimodulară (TU). (Matricea de incidență neorientată a unui grafic non-bipartit nu este TU.) Mai general, în apendicele la o lucrare de Heller și Tompkins, AJ Hoffman și D. Gale demonstrează următoarele. Fie o matrice m de n ale cărei rânduri pot fi partiționate în două seturi disjuncte și . Apoi următoarele patru condiții împreună sunt suficiente pentru ca A să fie total unimodular: ${\ displaystyle A}$ ${\ displaystyle B}$${\ displaystyle C}$

• Fiecare intrare este 0, +1 sau −1;${\ displaystyle A}$
• Fiecare coloană de conține cel mult două intrări diferite de zero (adică, +1 sau −1);${\ displaystyle A}$
• Dacă două intrări diferite de zero într-o coloană au același semn, atunci rândul unuia este în interior, iar celălalt în ;${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle C}$
• Dacă două intrări diferite de zero într-o coloană au semne opuse, atunci rândurile ambelor sunt în sau ambele în .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle C}$

Ulterior s-a realizat că aceste condiții definesc o matrice de incidență a unui grafic semnat echilibrat ; astfel, acest exemplu spune că matricea de incidență a unui grafic semnat este total unimodulară dacă graficul semnat este echilibrat. Conversa este valabilă pentru grafice semnate fără jumătăți de margini (aceasta generalizează proprietatea matricei de incidență neorientată a unui grafic).

2. Constrângerile de debit maxim și minim de curgere al costurilor probleme rezulta o matrice de coeficienți cu aceste proprietăți (și cu gol C ). Astfel, astfel de probleme de flux de rețea cu capacități întregi mărginite au o valoare optimă integrală. Rețineți că acest lucru nu se aplică problemelor de flux cu mai multe mărfuri , în care este posibil să aveți o valoare optimă fracționată chiar și cu capacități întregi mărginite.

3. Proprietatea consecutivă a celor: dacă A este (sau poate fi permutat în) o matrice 0-1 în care pentru fiecare rând, 1 apare consecutiv, atunci A este TU. (Același lucru este valabil și pentru coloane, deoarece transpunerea unei matrice TU este, de asemenea, TU.)

4. Fiecare matrice de rețea este TU. Rândurile unei matrice de rețea corespund unui copac T = ( V , R ) , fiecare dintre ale cărui arcuri are o orientare arbitrară (nu este necesar să existe un vârf de rădăcină r astfel încât arborele să fie "înrădăcinat în r " sau " din r „) .Cele coloanele corespund alt set C de arce pe același set vârfuri V . Pentru a calcula intrarea la rândul R și coloana C = st , uite la s -to- t calea P în T ; atunci intrarea este:

• +1 dacă arcul R apare înainte în P ,
• −1 dacă arcul R apare înapoi în P ,
• 0 dacă arc R nu apare în P .

Vezi mai multe în Schrijver (2003).

5. Ghouila-Houri a arătat că o matrice este TU dacă pentru fiecare subset R de rânduri, există o atribuire de semne către rânduri astfel încât suma semnată (care este un vector de rând cu aceeași lățime ca matricea) să aibă toate intrările sale în (adică rândul-submatrică are discrepanță cel mult unul). Aceasta și câteva alte caracterizări dacă și numai dacă sunt dovedite în Schrijver (1998). ${\ displaystyle s: R \ to \ pm 1}$${\ displaystyle \ sum _ {r \ în R} s (r) r}$${\ displaystyle \ {0, \ pm 1 \}}$

6. Hoffman și Kruskal au demonstrat următoarea teoremă. Să presupunem că este un grafic direcționat fără 2-dicicluri, este setul tuturor dipatilor din și este matricea de incidență 0-1 a versus . Atunci este total unimodular dacă și numai dacă fiecare ciclu simplu orientat în mod arbitrar constă în alternarea arcurilor înainte și înapoi. ${\ displaystyle G}$${\ displaystyle P}$${\ displaystyle G}$${\ displaystyle A}$${\ displaystyle V (G)}$${\ displaystyle P}$${\ displaystyle A}$${\ displaystyle G}$

7. Să presupunem că o matrice are 0- ( 1) intrări și, în fiecare coloană, intrările nu sunt descrescătoare de sus în jos (deci toate −1 sunt în partea de sus, apoi 0, apoi 1 sunt în partea de jos). Fujishige a arătat că matricea este TU dacă fiecare submatrică 2 la 2 are determinant în . ${\ displaystyle \ pm}$${\ displaystyle 0, \ pm 1}$

8. Seymour (1980) a dovedit o caracterizare completă a tuturor matricilor TU, pe care le descriem aici doar informal. Teorema lui Seymour este că o matrice este TU dacă și numai dacă este o anumită combinație naturală a unor matrice de rețea și a unor copii ale unei anumite matrice TU de 5 la 5.

Exemple concrete

1. Următoarea matrice este total unimodulară:

${\ displaystyle A = \ left [{\ begin {array} {rrrrrr} -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 {array}} \ right].}$

Această matrice apare ca matricea coeficientului constrângerilor din formularea de programare liniară a problemei debitului maxim pe următoarea rețea:

2. Orice matrice a formei

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

nu este total unimodular, deoarece are o submatrică pătrată de determinant -2.

Algebră liniară abstractă

Algebra liniară abstractă consideră matrici cu intrări din orice inel comutativ , fără a se limita la numerele întregi. În acest context, o matrice unimodulară este una care este inversabilă peste inel; echivalent, al cărui determinant este o unitate . Acest grup este notat . Un dreptunghiular -by- matrice se spune ca unimodular dacă poate fi extins cu rânduri într - o matrice pătrată unimodular. ${\ displaystyle R}$${\ displaystyle \ operatorname {GL} _ {n} (R)}$${\ displaystyle k}$${\ displaystyle m}$${\ displaystyle mk}$${\ displaystyle R ^ {m}}$

Pe un câmp , unimodular are același sens ca non-singular . Unimodular aici se referă la matrici cu coeficienți într-un anumit inel (adesea numerele întregi) care sunt inversabile peste acel inel și se folosește matrice non-singular pentru a însemna care sunt inversabile pe câmp.

Vezi si

• Matrice echilibrată
• Matroid regulat
• Grup liniar special
• Integralitate totală duală
• Hermite formă normală

Note

Referințe

• Papadimitriou, Christos H .; Steiglitz, Kenneth (1998), „Secțiunea 13.2”, Combinatorial Optimization: Algorithms and Complexity , Mineola, NY: Dover Publications, p. 316, ISBN 978-0-486-40258-1
• Alexander Schrijver (1998), Teoria programării liniare și întregi . John Wiley & Sons, ISBN  0-471-98232-6 (matematic)
• Alexander Schrijver (2003), Optimizare combinatorie: poliedre și eficiență , Springer

linkuri externe

• Glosar de programare matematică de Harvey J. Greenberg
• Matricea Unimodulară din MathWorld
• Software pentru testarea unimodularității totale de M. Walter și K. Truemper