Degenerovat matici

V matematice se říká , že skutečná čtvercová matice je zdegenerovaná, pokud je jeden z jejích hlavních nezletilých nulový. Skutečná nedegenerovaná čtvercová matice je tedy matice, jejíž hlavní nezletilí jsou všichni nenuloví.

Tyto matice zasahují do studia problémů lineární komplementarity .

Definice

U každé matice M , zde M IJ dílčí matrice skládající se z prvků s indexy v souladu I a sloupců indexy J .

Nedegenerovaná matice  -  Skutečná čtvercová matice je považována za nedegenerovanou, pokud jsou všechny její hlavní nezletilé osoby nenulové: M∈Mne⁡(R){\ displaystyle M \ in \ operatorname {M} _ {n} (\ mathbb {R})}

∀Já⊂{1,...,ne}detMJáJá≠0{\ displaystyle \ forall I \ podmnožina \ {1, \ ldots, n \} \ quad \ det M_ {II} \ neq 0}.

Matice M je proto zdegenerovaná právě tehdy, když pro určitý nenulový vektor existují I a J , komplementární v takovém, že a , který je ekvivalentní kde označuje Hadamardův produkt . u∈Rne{\ displaystyle u \ in \ mathbb {R} ^ {n}}{1,...,ne}{\ displaystyle \ {1, \ ldots, n \}}MJáJáuJá=0{\ displaystyle M_ {II} u_ {I} = 0}uJ=0{\ displaystyle u_ {J} = 0}u∘(Mu)=0{\ displaystyle u \ circ (Mu) = 0}∘{\ displaystyle \ circ}

Složitost

Ověření, že zadaná matice je nedegenerovaná, je problémem s úplnou spoluprací . Mne⁡(Q){\ displaystyle \ operatorname {M} _ {n} (\ mathbb {Q})}

Role v otázkách doplňkovosti

Nedenenerace matice souvisí s představou lokální jedinečnosti řešení problému lineární komplementarity , jehož prostor řešení je označen . Tento prostor je diskrétní, právě když je nějaké řešení lokálně jedinečné, to znamená izolované v . M∈Mne⁡(R){\ displaystyle M \ in \ operatorname {M} _ {n} (\ mathbb {R})} LCP⁡(q,M){\ displaystyle \ operatorname {LCP} (q, M)}PŘÍZEMNÍ⁡(q,M){\ displaystyle \ operatorname {SOL} (q, M)}PŘÍZEMNÍ⁡(q,M){\ displaystyle \ operatorname {SOL} (q, M)}

Nedegenerovaná matice a komplementarita  -  U matice jsou ekvivalentní následující vlastnosti: M∈Mne⁡(R){\ displaystyle M \ in \ operatorname {M} _ {n} (\ mathbb {R})}

• M{\ displaystyle M} je nedegenerovaný;
• za všechno , má u většiny prvků;q∈Rne{\ displaystyle q \ in \ mathbb {R} ^ {n}}PŘÍZEMNÍ⁡(q,M){\ displaystyle \ operatorname {SOL} (q, M)}2ne{\ displaystyle 2 ^ {n}}
• za všechno , je hotový  ;q∈Rne{\ displaystyle q \ in \ mathbb {R} ^ {n}}PŘÍZEMNÍ⁡(q,M){\ displaystyle \ operatorname {SOL} (q, M)}
• za všechno , je diskrétní.q∈Rne{\ displaystyle q \ in \ mathbb {R} ^ {n}}PŘÍZEMNÍ⁡(q,M){\ displaystyle \ operatorname {SOL} (q, M)}

Poznámky a odkazy

1. Tato ekvivalence je zmíněna v (en) P. Tseng, „  Co-NP-úplnost některých problémů s klasifikací matic  “ , Mathematical Programming , sv.  88, n o  1,2000, str.  183-192.
2. (in) R. Chandrasekaran, SN Kabadi a KG Murty, „  Some NP-complete problems in linear programming  “ , Operations Research Letters , sv.  1, n o  1,1982, str.  101-104.
3. Murty 1988 , s.  179.
4. Cottle, Pang and Stone 2009 , str.  2.
5. Cottle, Pang and Stone 2009 , Theorem 3.6.3.

Dodatky

Související články

• Newton-minův algoritmus
• P-matice

Bibliografie

 : dokument použitý jako zdroj pro tento článek.

• (en) RW Cottle, J.-S. Pang a RE Stone, The Linear Complementarity Problem , Philadelphia, PA, SIAM, al.  "Classics aplikované matematiky" ( n °  60),2009( číst online )
• (en) RA Horn a Ch. R. Jonhson, Topics in Matrix Analysis , New York, Cambridge University Press, 1991
• (en) KG Murty, Lineární komplementarita, Lineární a nelineární programování , Berlín, Heldermann Verlag,1988