Recently a colleague and I came across this unusual phenomenon.

Take $M\in\mathbb{R}^{n\times n}$ a singular irreducible M-matrix, and $b\in\mathbb{R}^{n}$ such that the system $Mx=b$ is solvable (so, in general, $b$ is going to contain both positive and negative entries). For each $i=1,2,\dots,n$, let $M^{(i)}\in\mathbb{R}^{n-1\times n-1}$ and $b^{(i)}\in\mathbb{R}^{n-1}$ be the matrices and vectors obtained by eliminating the $i$th row and column from $M$ and $b$. Then, at least one of the (nonsingular) systems $M^{(i)}x^{(i)}=b^{(i)}$ has a solution $x^{(i)}\geq 0$.

The proof in itself is quite easy: notice that the $x^{(i)}$ correspond to solutions of $Mx=b$ with one zero component; the solutions of this system can be written as $\alpha z +y$, with $z,y\geq 0$, and by minimality there is an $\alpha$ that makes one component zero and the rest positive.

However, I find this unusual because the typical argument in this field is finding out that a vector is nonnegative if it can be written as $A^{-1}c$, with $A^{-1}$ and $c$ nonnegative. Here we have a $c$ with mixed signs instead.

What I would be interested in is a better characterization of the entry(or entries) $i$ that has $x^{(i)}\geq 0$. I hope it satisfies some minimality property more meaningful than the obvious $i=\arg\min \min y_i/z_i$. The ideal for me would be finding a characterization that lets me operate on $M$ and $b$ only and be able to tell what is the "correct" entry to take.

Is this topic already studied? Maybe the magic $i$ corresponds to some special property of the graph associated to $M$.


Your Answer

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

Browse other questions tagged or ask your own question.