Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a matrix $A$ I want to find a vector $\vec{x}$ such that every element of $A\vec{x}$ is strictly positive. Also, the columns of $A$ do not span the full space, so if I were to just naively pick some $\vec{y}$ with all positive entries, I could not in general find a solution for $A\vec{x} = \vec{y}$. Is there a method guaranteed to find a feasible point if one exists? Bonus points if it's a matrix-free method, so I only have to evaluate matrix-vector products, no pseudoinverses or factorizations. I suspect that this can be set up as a convex program, but I'm not sure how.

share|improve this question
    
Where does $A$ come from? Does it have any particular structure? –  Daryl Jul 25 '12 at 2:19
    
It's a system identification problem. Really $\vec{x}$ is a matrix $X$, which I right-multiply by another matrix $U$, and then apply the adjoint of the linear operator that constructs a block-Hankel matrix. If I can find $\vec{x}$ such that $XU$ is positive, then it should work. –  David Pfau Jul 25 '12 at 2:58
1  
Maybe try solving the linear program $\min_{\alpha,x} \{ \alpha | - \sum_{j=1}^n A_{i,j} x_j \leq \alpha , \ i=1,\cdots, n \}$? If the minimum is $<0$ then you have an answer, otherwise you know no such $x$ exists. –  copper.hat Jul 25 '12 at 3:11
    
Equivalently, you want a vector $x$ that has positive dot product with every row of the matrix. So it's a question of whether the intersection of open halfspaces determined by the row vectors is nonempty. –  user31373 Jul 26 '12 at 3:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.