1
$\begingroup$

I'm a little stuck into a question of the book "Linear Programming and Network Flows":

Let $B$ be an invertible matrix with nonnegative entries. Show that every row of $B^{-1}$ has at least one positive entry.

I tried to show that the elements in the diagonal should be positive in $B^{-1}$ when doing elementary operations into $B$. But I was not able to go very far...

$\endgroup$
3
$\begingroup$

Hint: if it were not to be the case, we would have a row with all negative entries.

Suppose that this occurs at row $j$. Then we must have $1 = I_{jj} = (B^{-1}B)_{jj} = \sum_{s}B^{-1}_{js}B_{js},$ which is absurd since the right hand side is negative (recall that by hypotehsis it is $B_{js}^{-1}B_{js} \leq 0$ for all $s$).

$\endgroup$
1
$\begingroup$

Seeking a contradiction, suppose that $B^{-1}$ has a row $r$ whose entries are nonpositive. The equation $B^{-1}B$ implies that $r\cdot b=1$ for one of the columns $b$ of $B$. Since each entry in $r$ is $\leq 0$ and each entry in $b$ is $\geq 0$, it follows that each term in $r\cdot b$ is $\leq 0$. Thus $1=r\cdot b\leq 0$, a contradiction.

$\endgroup$

Your Answer

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

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