# Prove a matrix is a generalized permutation matrix

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.
• 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. – hardmath Jan 24 '16 at 15:01