Singularidad de una combinación cónica de rango- $1$ matrices

Question

Dado el rango- $1$ matrices cuadradas $A_1, A_2, \dots, A_n$ determinar si existe $x \in \mathbb R_{>0}^n$ tal que

$$ \sum_{i=1}^n x_i A_i = x_1 A_1 + \cdots + x_n A_n $$

es singular, o decidir si no existe ninguna (es decir, la combinación lineal positiva es no singular para todas las $x$ ). ¿Existe algún método o algoritmo conocido para hacerlo?

Answer 1

He aquí una respuesta parcial, y quizás alguien pueda completarla.

Supongamos que $A\in\mathbb{R}^{m\times m}$ . Porque cada $A_i$ es de rango 1, se puede escribir como una díada $A_i=f_i g_i^T$ , donde $f_i$ y $g_i$ son vectores. Entonces $$\sum_i x_i A_i = \sum_i x_i f_i g_i^T = F X G^T$$ donde $X\triangleq\mathop{\textrm{diag}}(x)\in\mathbb{R}^{n\times n}$ y $F,G\in\mathbb{R}^{m\times n}$ recoger los vectores $f_i$ , $g_i$ respectivamente, como columnas. Sea $$r_F\triangleq\mathop{\textrm{rank}}(F)\leq\min\{m,n\}, \quad r_G\triangleq\mathop{\textrm{rank}}(G)\leq\min\{m,n\}.$$ Desde $X$ es de rango completo, entonces tenemos $$\mathop{\textrm{rank}}(FXG^T)\leq\min\{r_F,r_G\}\leq m$$ Así que si cualquiera de los dos $F$ o $G$ tiene un rango inferior a $m$ has terminado. En particular, esto implica que $n\geq m$ si esto va a tener una respuesta no trivial.

Si no es así, tienes más trabajo que hacer. Y ahí es donde estoy personalmente atascado.

Dejemos que $(U_F,\Sigma_F,V_F)$ y $(U_G,\Sigma_G,V_G)$ sean SVDs de tamaño económico de $F$ y $G$ respectivamente. Esto significa que $$U_F\in\mathbb{R}^{m\times r_F} \quad \Sigma_F\in\mathbb{R}^{r_F\times r_F} \quad V_F\in\mathbb{R}^{r_F\times n}$$ $$U_G\in\mathbb{R}^{m\times r_G} \quad \Sigma_G\in\mathbb{R}^{r_G\times r_G} \quad V_G\in\mathbb{R}^{r_G\times n}$$ Entonces $$FXG^T=U_F\Sigma_FV_F^TXV_G\Sigma_GU_G^T$$ No es difícil ver que la incógnita aquí es el rango del $r_F\times r_G$ matriz $V_F^TXV_G$ . Tenga en cuenta que esto es no un SVD, aunque casi parece uno. De hecho, ¡es sólo una versión (posiblemente) reducida del mismo problema con el que empezaste!

Sé que esto no es una respuesta completa, pero pensé que no debía desperdiciar el esfuerzo. Si alguien más puede inspirarse en esto para terminar la tarea, incluso el OP, entonces por todos los medios, espero votarlos.

Answer 2

Matrices dadas ${\rm A}_1, {\rm A}_2, \dots, {\rm A}_n \in \Bbb R^{d \times d}$ , decidir la existencia de un vector $x \geq {\Bbb 0}_n$ tal que

$$\mbox{rank} \left( \sum_{k=1}^n x_k {\rm A}_k \right) < d$$

---

Desde el norma nuclear es una representación convexa del rango, podríamos resolver el siguiente programa convexo

$$\begin{array}{ll} \underset{{\rm x} \in \mathbb R^n}{\text{minimize}} & \left\| \displaystyle\sum_{k=1}^n x_k {\rm A}_k \right\|_* \\ \text{subject to} & x \geq {\Bbb 0}_n\end{array}$$

Dejemos que ${\rm x}^{\min}$ denota el minimizador del mencionado programa convexo. Si

$$\mbox{rank} \left( \sum_{k=1}^n x_k^{\min} {\rm A}_k \right) < d$$

hemos terminado. Si no, hemos perdido unos minutos de nuestra vida. Tenga en cuenta que hicimos no requieren que las matrices dadas ${\rm A}_1, {\rm A}_2, \dots, {\rm A}_n$ ser rank- $1$ .