Singularity of a conic combination of rank-$1$ matrices Given rank-$1$ square matrices $A_1, A_2, \dots, A_n$, determine if there exists $x \in \mathbb R_{>0}^n$ such that
$$ \sum_{i=1}^n x_i A_i = x_1 A_1 + \cdots + x_n A_n $$
is singular, or decide whether none exists (i.e., the positive linear combination is nonsingular for all positive $x$). Is there a well-known method or algorithm to do this?
 A: Here is a partial answer, and perhaps someone will be able to complete it.
Suppose that $A\in\mathbb{R}^{m\times m}$. Because each $A_i$ is rank 1, it can be written as a dyad $A_i=f_i g_i^T$, where $f_i$ and $g_i$ are vectors. Then
$$\sum_i x_i A_i = \sum_i x_i f_i g_i^T = F X G^T$$
where $X\triangleq\mathop{\textrm{diag}}(x)\in\mathbb{R}^{n\times n}$, and $F,G\in\mathbb{R}^{m\times n}$ collect the vectors $f_i$, $g_i$, respectively, as columns. Let 
$$r_F\triangleq\mathop{\textrm{rank}}(F)\leq\min\{m,n\}, \quad r_G\triangleq\mathop{\textrm{rank}}(G)\leq\min\{m,n\}.$$
Since $X$ is full rank, then we have
$$\mathop{\textrm{rank}}(FXG^T)\leq\min\{r_F,r_G\}\leq m$$
So if either $F$ or $G$ has a rank of less than $m$, you're done. In particular, this implies that $n\geq m$ if this is going to have a non-trivial answer.
If not, you have more work to do. And that's where I am personally stuck. 
Let $(U_F,\Sigma_F,V_F)$ and $(U_G,\Sigma_G,V_G)$ be economy-sized SVDs of $F$ and $G$, respectively. This means that 
$$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}$$
Then
$$FXG^T=U_F\Sigma_FV_F^TXV_G\Sigma_GU_G^T$$
It's not difficult to see that the unknown here is the rank of the $r_F\times r_G$ matrix $V_F^TXV_G$. Note that this is not an SVD, though it looks almost like one. Indeed, it is just a (possibly) reduced version of the very problem you began with!
I know this isn't a complete answer but I figured I shouldn't let the effort go to waste. If someone else can be inspired on this to finish the task, even the OP, then by all means, I look forward to voting them up.
A: Given matrices ${\rm A}_1, {\rm A}_2, \dots, {\rm A}_n \in \Bbb R^{d \times d}$, decide the existence of a vector $x \geq {\Bbb 0}_n$ such that
$$\mbox{rank} \left( \sum_{k=1}^n x_k {\rm A}_k \right) <  d$$

Since the nuclear norm is a convex proxy for the rank, we could solve the following convex program
$$\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}$$
Let ${\rm x}^{\min}$ denote the minimizer of the aforementioned convex program. If
$$\mbox{rank} \left( \sum_{k=1}^n x_k^{\min} {\rm A}_k \right) <  d$$
we are done. If not, we wasted a few minutes of our lives. Note that we did not require that the given matrices ${\rm A}_1, {\rm A}_2, \dots, {\rm A}_n$ be rank-$1$.
