Matricea degenerată

În matematică , se spune că o matrice pătrată reală este degenerată dacă unul dintre minorii săi majori este zero. O matrice pătrată reală care nu este degenerată este, prin urmare, o matrice a cărei minori principale sunt diferite de zero.

Aceste matrice intervin în studiul problemelor de complementaritate liniară .

Definiție

Pentru orice matrice M , acolo M IJ sub-matrice formată din elementele cu indicii în linia I și a coloanei de indici în J .

Matricea nedegenerată  -  Se spune că o matrice pătrată reală este nedegenerată dacă toți minorii săi majori sunt diferiți de zero: M∈Mnu⁡(R){\ displaystyle M \ in \ operatorname {M} _ {n} (\ mathbb {R})}

∀Eu⊂{1,...,nu}detMEuEu≠0{\ displaystyle \ forall I \ subset \ {1, \ ldots, n \} \ quad \ det M_ {II} \ neq 0}.

Prin urmare, matricea M este degenerată dacă și numai dacă, pentru un anumit vector diferit de zero , există I și J , complementare în , astfel încât și , care este echivalent cu unde denotă produsul Hadamard . tu∈Rnu{\ displaystyle u \ in \ mathbb {R} ^ {n}}{1,...,nu}{\ displaystyle \ {1, \ ldots, n \}}MEuEutuEu=0{\ displaystyle M_ {II} u_ {I} = 0}tuJ=0{\ displaystyle u_ {J} = 0}tu∘(Mtu)=0{\ displaystyle u \ circ (Mu) = 0}∘{\ displaystyle \ circ}

Complexitate

Verificarea faptului că o matrice dată nu este degenerată este o problemă completă a co-NP . Mnu⁡(Î){\ displaystyle \ operatorname {M} _ {n} (\ mathbb {Q})}

Rol în problemele de complementaritate

Nedenenerația unei matrice este legată de o noțiune de unicitate locală a soluțiilor problemei de complementaritate liniară , al cărei spațiu de soluție este notat . Acest spațiu este discret dacă și numai dacă o soluție este locală unică, adică izolată în . M∈Mnu⁡(R){\ displaystyle M \ in \ operatorname {M} _ {n} (\ mathbb {R})} LCP⁡(q,M){\ displaystyle \ operatorname {LCP} (q, M)}SOL⁡(q,M){\ displaystyle \ operatorname {SOL} (q, M)}SOL⁡(q,M){\ displaystyle \ operatorname {SOL} (q, M)}

Matrice nedegenerată și complementaritate  -  Pentru o matrice , următoarele proprietăți sunt echivalente: M∈Mnu⁡(R){\ displaystyle M \ in \ operatorname {M} _ {n} (\ mathbb {R})}

• M{\ displaystyle M} este nedegenerat;
• pentru orice , are cel mult elemente;q∈Rnu{\ displaystyle q \ in \ mathbb {R} ^ {n}}SOL⁡(q,M){\ displaystyle \ operatorname {SOL} (q, M)}2nu{\ displaystyle 2 ^ {n}}
• pentru tot , este terminat  ;q∈Rnu{\ displaystyle q \ in \ mathbb {R} ^ {n}}SOL⁡(q,M){\ displaystyle \ operatorname {SOL} (q, M)}
• pentru toate , este discret.q∈Rnu{\ displaystyle q \ in \ mathbb {R} ^ {n}}SOL⁡(q,M){\ displaystyle \ operatorname {SOL} (q, M)}

Note și referințe

1. Această echivalență este menționată în (en) P. Tseng, „  Co-NP-exhaustivitatea unor probleme de clasificare a matricii  ” , Mathematical Programming , vol.  88, n o  1,2000, p.  183-192.
2. (în) R. Chandrasekaran, SN Kabadi și KG Murty, „  Unele probleme NP-complete în programarea liniară  ” , Operations Research Letters , vol.  1, n o  1,1982, p.  101-104.
3. Murty 1988 , p.  179.
4. Cottle, Pang și Stone 2009 , p.  2.
5. Cottle, Pang and Stone 2009 , Teorema 3.6.3.

Anexe

Articole similare

• Algoritm Newton-min
• P-matrice

Bibliografie

 : document utilizat ca sursă pentru acest articol.

• (ro) RW Cottle, J.-S. Pang și RE Stone, The Linear Complementarity Problem , Philadelphia, PA, SIAM, al.  „Clasici în matematică aplicată” ( nr .  60),2009( citește online )
• (en) RA Horn și Ch. R. Jonhson, Topics in Matrix Analysis , New York, Cambridge University Press, 1991
• (ro) KG Murty, Complementaritate liniară , Programare liniară și neliniară , Berlin, Heldermann Verlag,1988