A generalized permutation matrix is a matrix in which each row and each column contains exactly one nonzero entry.

I am trying to prove the following:

If a non-singular matrix and its inverse are both non-negative matrices (i.e. matrices with non-negative entries), then the matrix is a generalized permutation matrix.

So I need to prove that there exists a diagonal matrix $D$ with positive diagonal entries and a permutation matrix $P$ such that $A = DP$. I don't know how to start proving this, and I don't get how to use the non-negativity of $A^{-1}$. Please help me.


Let $A$ be $n \times n$.

Since $A^{-1}$ is non-singular and non-negative, there is a bijective function $f$ on $\{1, \dots, n\}$ such that $A^{-1}_{i,f(i)} > 0$, for each $i$.

Since $A$ is also non-negative, it is not difficult to see that the $f(i)$-th row of $A$ can only have a non-zero element in the $i$-th column. This is because the scalar product of the $i$-th row of $A^{-1}$ by the $j$-th column of $A$ must be zero, for $j \ne i$.

We have thus shown that $A$ is a permutation matrix.

  • 1
    $\begingroup$ Very nice. I might insert a remark that if bijectivity of $f$ were not possible, it would mean every traversal of $A^{-1}$ contains a zero, contradicting its non-singularity. $\endgroup$ – hardmath Jan 24 '16 at 15:01

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.