A non-negative matrix has a non-negative inverse. What other properties does it have?

This is homework for my mathematical optimization class. Here is the exact question:

Element-wise nonnegative matrix and inverse. Suppose a matrix $A \in\Bbb R^{n\times n}$ , and its inverse $B$, have all their elements nonnegative, i.e., $A_{ij}\geq 0$, $B_{ij}\geq 0$, for $i,j = 1,\dots,n$. What can you say must be true of $A$ and $B$? Please give your answer first, and then the justification. Your solution (which includes what you can say about $A$ and $B$, as well as your justification) must be short.

I have no idea what they are looking for; so far, I've got just the basic facts stemming from the fact that an inverse exists (it's square, the determinant is non-zero etc.). What can I deduce from the "non-negative" property?

Solution 1:

Suppose you have a non-negative matrix $A$ with a non-negative inverse $B$.

Since the entries are non-negative, if the $k$th entry of row $i$ is non-zero, i.e. $A_{ik}\neq 0$, then we must have $B_{kj} = 0$ for all $j$ except $j = i$. Otherwise, we would have $$I_{ij} = 0 = \sum_{\ell = 1}^n A_{i\ell}B_{\ell j} \ge A_{ik}B_{kj} > 0$$

Since we cannot have a zero row in an invertible matrix, this in-turn implies that $B_{ki} \neq 0$. Applying a symmetric argument now suggests $A_{ij} = 0$ for all $j$ except $j=k$. Thus each row of the matrix has precisely one non-zero entry. It follows that the matrix is the permutation of a positive diagonal matrix, i.e. there exists diagonal matrix $D > 0$ and permutation matrix $P$ such that $$A = PD$$ Such matrices if you are interested are called monomial matrices. You can easily check that the above condition is in fact necessary and sufficient:

Theorem: Let $A$ be a non-negative matrix. Then $A$ has a non-negative inverse if and only if $A$ is a positive monomial matrix (by positive monomial, I mean the non-zero entries are positive).