7
$\begingroup$

Given a set of rank one matrices $A_1,..,A_n$, we need to find out if there exists $x \in \mathbb R^n$ with $x\gg 0$ (i.e, positive) such that

$$ \sum_{i=1}^n x_i A_i = x_1 A_1 + .... + 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 algorthim to do this?

$\endgroup$
  • $\begingroup$ Is the size of the $A_k$ somehow constrained by $n$? $\endgroup$ – Calle Apr 21 '15 at 19:32
  • $\begingroup$ No, but to have a meaningful situation we need to have $n \ge m$ (where the matrices are of size $m\times m$) $\endgroup$ – M.A Apr 21 '15 at 22:00
  • $\begingroup$ This is interesting (and I tried, but failed, to offer an answer) but to the best of my knowledge it is not convex optimization. $\endgroup$ – Michael Grant Apr 22 '15 at 12:48
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the insight. But a minor remark: the matrices are square. $\endgroup$ – M.A Apr 22 '15 at 13:34
  • $\begingroup$ That certainly simplifies things a bit. In particular, this means that both of the SVDs produce square U matrices. I do not believe however that it helps us get any closer to a solution. $\endgroup$ – Michael Grant Apr 22 '15 at 13:36
  • $\begingroup$ Of course, the fact that you were asking about singularity implies that A is square. I'll go ahead and edit my answer to correct that. $\endgroup$ – Michael Grant Apr 22 '15 at 13:47
  • $\begingroup$ A vague idea: since the matrices are of rank one, then their traces are nonzero. Assume now that they have mixed trace signs. For instance, let $tr(A_1)>0$ and $tr(A_2)<0$. therefore, for $x_1=[1,0,...,0]^T$ the resulting sum has a positive trace and a positive eigenvalue, and by continuity, the same holds for a neighborhood of $x_1$. For $x_2=[0,1,0,..0]^T$ and neighborhood the resulting sum has a negative trace and a negative eigenvalue. Since the set is connected, is it possible to have a straight line connecting them to conclude that the sum will be singular for some x (zero eigenvalue)? $\endgroup$ – M.A Apr 22 '15 at 14:39
  • $\begingroup$ No, because the trace is the sum of the eigenvalues. Just because the trace is zero doesn't mean that any of the eigenvalues are. $\endgroup$ – Michael Grant Apr 22 '15 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.