Matriz P0

Em matemática , uma matriz P0 é uma matriz quadrada real cujos menores maiores são positivos . Essas matrizes intervêm no estudo de problemas de complementaridade linear . Uma noção relacionada é a de P-matrizes .

Definição

Notamos abaixo a sub-matriz formada por seus elementos com índices de linha em e índices de coluna em $M _ {{I, J}}$ $M$ $eu$ ${\ displaystyle J.}$

Matriz P0 - Dizemos que uma matriz quadrada real é uma matriz P0 se uma das seguintes propriedades equivalentes for válida: $M \ in \ mathbb {R} ^ {{n \ vezes n}}$

todos os principais menores de positivo: para todos os não-vazios , $M$ $I \ subset \ {1, \ ldots, n \}$ ${\ displaystyle \ det M_ {I, I} \ geqslant 0}$
para qualquer vetor diferente de zero, podemos encontrar um índice tal que e , $x \ in \ mathbb {R} ^ {n}$ $eu$ ${\ displaystyle x_ {i} \ neq 0}$ ${\ displaystyle x_ {i} (Mx) _ {i} \ geqslant 0}$
para qualquer não vazio, os autovalores reais de são positivos, $I \ subset \ {1, \ ldots, n \}$ ${\ displaystyle M_ {I, I}}$
para qualquer matriz diagonal definida positiva , é invertível. $D$ ${\ displaystyle M + D}$

Denotamos o conjunto de matrizes P0 de qualquer ordem. Chamamos de P0-matricidade a propriedade de uma matriz à qual pertencemos . ${\ mathbf {P_ {0}}}$ ${\ mathbf {P_ {0}}}$

O nome dessas matrizes foi proposto por Fiedler e Pták (1966), que também mostraram a equivalência entre as definições 1 e 2. A expressão 4 da matriz P0 deve-se a Chen e Harker (1993).

Propriedades imediatas

Da definição 1, deduzimos que

${\ displaystyle M \ in \ mathbf {P_ {0}}}$ se e somente se , ${\ displaystyle M ^ {\ top \!} \ in \ mathbf {P_ {0}}}$
se for simétrico, então se e somente se for semi-definido positivo , $M$ ${\ displaystyle M \ in \ mathbf {P_ {0}}}$ $M$
${\ displaystyle \ mathbf {P_ {0}} \ cap \ mathbb {R} ^ {n \ vezes n}}$ é um fechado de , ${\ displaystyle \ mathbb {R} ^ {n \ vezes n}}$
se for semi-definido positivo , então ${\ displaystyle M + M ^ {\! \ top \!}}$ ${\ displaystyle M \ in \ mathbf {P_ {0}}.}$

Complexidade

Verificar se uma matriz dada em é uma matriz P0 é um problema co-NP-completo . ${\ displaystyle \ mathbb {Q} ^ {n \ vezes n}}$

Apêndices

Observação

(em) Sr. Fiedler, Pták V. (1966). Algumas generalizações de definição positiva e monotonicidade. Numerische Mathematik , 9, 163-172. doi
(en) B. Chen, PT Harker (1993). Um método de continuação não interior para problemas de complementaridade linear. SIAM Journal on Matrix Analysis and Applications , 14, 1168–1190. doi
(em) P. Tseng (2000). Co-NP-completude de alguns problemas de classificação de matrizes. Mathematical Programming , 88, 183-192.

Obras gerais

(en) RW Cottle, J.-S. Pang, RE Stone (2009). O problema da complementaridade linear . Clássicos em Matemática Aplicada 60. SIAM, Filadélfia, PA, EUA.
(en) RA Horn, Ch. R. Jonhson (1991). Tópicos em Análise de Matriz . Cambridge University Press, Nova York, NY, EUA.