Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello,

I have the following problem:

Find a non-negative matrix $L$ (i.e. $L_{i,j} \geq 0$ for all $i,j$), $L \neq I$ so that $A(I-L)^{-1}y \geq 0$ (the inequality must hold for each component), where $A$ is a given matrix and $y$ is a known vector. Also, I would like the rows of $L$ to sum to one, but perhaps that condition can be dropped.

Is there a known way of approaching this problem, or is it NP-complete? Basically the issue is that I need both $L$ and $L^{-1}$ to satisfy a certain property. Surprisingly, I haven't found any results on optimization problems that involve a matrix and its inverse.

Thanks a lot!

share|improve this question
2  
If each row of $L$ sums to $1$, $I - L$ can't be invertible (the column vector of all $1$'s is in its null space). –  Robert Israel Dec 22 '11 at 8:14
    
Thank you, I should have seen that. Let's assume for now that there is no restriction on what the columns sum to. –  Woland Dec 22 '11 at 10:38
    
Although your question has already been answered, let me comment that you can impose constraints on a matrix and its inverse by semidefinite programming. See my answer in mathoverflow.net/questions/162100/… for an example. Or even better, have a look at the chapter 4 of the Ben-Tal & Nemirovski book (Lectures on Modern Convex Optimization). –  Cristóbal Guzmán Apr 9 at 14:05
    
I forgot to say in my comment above that this only works in the case your matrix variable is positive semidefinite. The tool you use is the Lemma on Schur complements, so you need your block diagonal parts to be psd. –  Cristóbal Guzmán Apr 9 at 14:57

1 Answer 1

up vote 1 down vote accepted

Leaving out for the moment the requirement that $I-L$ is invertible, write your inequality as $A u \ge 0$ where $Lu = u - y$.

Case 1: Suppose we can find a vector $u$ such that $A u \ge 0$ and $u$ has both positive and negative components: if possible, this can be done efficiently by linear programming. Then we can easily get $L u = u - y$ with $L \ge 0$, looking at each row of $L$ separately.

Case 2: Suppose case 1 does not hold, but there is a vector $u \ge 0$ with $A u \ge 0$ and $u_j > 0$ for those $j$ where $y_j > 0$. Again this can be found efficiently with linear programming. Multiplying be a suitable positive scalar, we can assume $u > y$. Then again we can easily get $L$ so $L u = u - y$.

Case 3: Suppose every vector $u$ with $A u \ge 0$ has $u \ge 0$, but case 2 does not hold: then there is a component $j$ such that $y_j > 0$ and every $u$ with $A u \ge 0$ has $u_j = 0$. Then $u_j - (L u)_j = y_j$ is impossible.

Similarly we can deal with the case where every vector $u$ with $A u \ge 0$ has $u \le 0$.

share|improve this answer
    
Thank you very much, that indeed solves the problem. Unfortunately I was a bit tired yesterday and I didn't state my question correctly. What I really have are $m$ matrices $A_j$ $1 \leq j \leq m$ and I am looking for a single positive matrix $L$ and vectors $u_j$ so that $\sum_j A_j u_j \geq 0$ and $Lu_j = u_j - y_j$, where $y_j$ is given. I'm not sure if I should post a new question or edit the one above. –  Woland Dec 22 '11 at 22:30

Your Answer

 
discard

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

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