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

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

share|improve this question
add comment

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.