Question

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!

Answer 1

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$.