Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

O cone convexo gerado pelas colunas de uma matriz é um conjunto fechado?

+1 voto
169 visitas
perguntada Nov 8, 2016 em Matemática por Camila (31 pontos)  
editado Nov 13, 2016 por Camila

Considere o cone convexo dado por \(C=\{z \in \mathbb{R}^m: z=Ax,\ x\geq0\}\).

Compartilhe

1 Resposta

+1 voto
respondida Nov 8, 2016 por Camila (31 pontos)  
editado Dez 9, 2016 por Camila

Note que \(C\) é o cone convexo formado pelos vetores da matriz \(A=[a_1\ ...\ a_n]\), onde \(a_i \in \mathbb{R}^m\ \forall i\). Note, ainda, que qualquer elemento \(z \in C\) pode ser escrito como \(z=\sum_{i=1}^kx_ia_i,\ x_i>0\ \forall i,\ k\leq n\). Fixe \(z \in C\) qualquer.

Afirmação. Se \(k\) é o número mínimo de vetores de \(A\) tal que \(z\) pode ser escrito, a menos de reordenação, como \(z=\sum_{i=1}^kx_ia_i,\ x_i>0\ \forall i\), então \(a_1,...,a_k\) são linearmente independentes.

Demonstração da Afirmação. Suponha, por contradição, que \(a_1,...,a_k\) são linearmente dependentes. Então, existe \(\mu=(\mu_1,...,\mu_k)\neq (0,...,0)\) tal que \(\sum_{i=1}^k\mu_ia_i=0\). Como o número de vetores de \(A\) é finito, o número de elementos de \(\mu\) também é e, então, sem alterar a igualdade, podemos reordenar os elementos de \(\mu\) de forma que \(\mu_1 \leq \mu_2 \leq ... \leq \mu_k\). Assim, para algum \(i=s\) temos que \(\mu_i\leq 0\) se \(i< s\) e \(\mu_i>0\) se \(i\geq s\). Agora, para \(i\geq s\) considere a razão \(\frac{x_i}{\mu_i},\ i=s,...,k\), e ordene esses elementos de forma que \(\frac{x_1}{\mu_1}\leq \frac{x_2}{\mu_2}\leq ...\leq \frac{x_k}{\mu_k}\). Agora, note que

\[z=\sum_{i=1}^kx_ia_i-\frac{x_k}{\mu_k} \underbrace{\sum_{i=1}^k\mu_ia_i}_{\text{=0}}=\sum_{i=1}^k(x_i-\frac{x_k}{\mu_k}\mu_i)a_i.\]

Para \(i=k\) temos que \(x_i-\frac{x_k}{\mu_k}\mu_i=0\) e, caso contrário, \(x_i-\frac{x_k}{\mu_k}\mu_i\geq 0\). Portanto, \(z=\sum_{i=1}^{k-1}(x_i-\frac{x_k}{\mu_k}\mu_i)a_i\), o que é uma contradição com a hipótese de que \(k\) é mínimo. \(||\)

Podemos, então, reescrever \(C\) como uma união finita de conjuntos da forma \(K=\{z \in \mathbb{R}^m: z=Bx,\ x>0\)}, onde \(B=[a_{i_1},...,a_{i_k}]\) e \(\{a_{i_1},...,a_{i_k}\}\) é um conjunto de vetores linearmente independentes. Sabemos que a união de conjuntos fechados é um conjunto fechado. Logo, para mostrar que \(C\) é fechado precisamos apenas mostrar que cada elemento da união é um conjunto fechado. Como \(a_{i_1},...,a_{i_k}\) são linearmente independentes, então a matriz \(B\) possui uma inversa a esquerda \(L\). Tome uma sequência convergente \(z^n\rightarrow z\) tal que \(z^n=Bx^n\) e \(z^n \in K\ \forall n\). A convergência de \(z^n\) é equivalente à convergência de \(x^n\rightarrow x\), onde \(x\) é obviamente não negativo, pois \(x^n=Lz^n>0\ \forall n\). Portanto, \(z \in K\). \(\square\)

comentou Nov 13, 2016 por Mauro Patrão (71 pontos)  
Oi Camila, ficou bacana! Sugiro apenas que você altere a pergunta genérica por algo como "O cone convexo gerado pelas colunas de uma matriz é um conjunto fechado?" e passe a notação de conjunto para a pergunta detalhada, que deve vir logo abaixo da pergunta genérica. Além disso, sugiro mudar a notação de \(S\) para \(C\) de cone convexo.
comentou Nov 13, 2016 por Camila (31 pontos)  
Obrigada, Mauro! Segui as dicas. Concordo que ficou mais bonitinho!
...