Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
$ AB = I $. Where do the zeros in $I$ come from? –  wj32 Oct 15 '12 at 20:07
3  
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
4  
@VPeric No... $\left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)$ –  xavierm02 Oct 15 '12 at 20:21
1  
@VPeric: No, there are plenty of matrices that have nonnegative entries and square to give the identity. –  wj32 Oct 15 '12 at 20:24

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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