11
$\begingroup$

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?

  • 6
    $ AB = I $. Where do the zeros in $I$ come from?2012-10-15
  • 3
    The English word you're looking for is "optimization".2012-10-15
  • 0
    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.2012-10-15
  • 0
    @wj32 Oh duh, I guess that means that A itself is also an identity matrix. That was easy. :)2012-10-15
  • 4
    @VPeric No... $\left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)$2012-10-15
  • 1
    @VPeric: No, there are plenty of matrices that have nonnegative entries and square to give the identity.2012-10-15

1 Answers 1

16

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

  • 0
    I need to usethis "theorem" in my publication, do you happen to have a reference for that?2017-10-02
  • 0
    @JürgMerlinSpaak Unfortunately, the above proof is my own, so I don't have any references for it.2017-10-02