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!



Can one efficiently optimize over the inverse of matrix?
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$.


