# 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?

-
$AB = I$. Where do the zeros in $I$ come from? – wj32 Oct 15 '12 at 20:07
The English word you're looking for is "optimization". – Robert Israel Oct 15 '12 at 20:11
Write the matrix multiplication for two arbitrary matrices and then, since you know the result ($I_n$), you'll be able to have some sums equal to either $0$ or $1$. And where it equals $0$, it means that every single operand is $0$ because all are positive. – xavierm02 Oct 15 '12 at 20:12
@VPeric No... $\left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)$ – xavierm02 Oct 15 '12 at 20:21
@VPeric: No, there are plenty of matrices that have nonnegative entries and square to give the identity. – wj32 Oct 15 '12 at 20:24

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