Invertible matrices of natural numbers are permutations... why?

Question

I have heard the following statement several times and I suspect that there is an easy and elegant proof of this fact which I am just not seeing.

Question: Why is it true that an invertible nxn matrix with non-negative integer entries, whose inverse also has non-negative integer entries, is necessarily a permutation matrix?

The reason I am interested in this has to do with categorification. There is an important 2-category, the 2-category of Kapranov–Voevodsky 2-vector spaces, which in one incarnation has objects given by the natural numbers and 1-morphisms from n to m are mxn matrices of vector spaces. Composition is like the usual matrix composition, but using the direct sum and tensor product of vector spaces. The 2-morphisms are matrices of linear maps.

The above fact implies that the only equivalences in this 2-category are "permutation matrices" i.e. those matrices of vector spaces which look like permutation matrices, but where each "1" is replaced by a 1-dimensional vector space.

It is easy to see why the above fact implies this. Given a matrix of vector spaces, you can apply "dim" to get a matrix of non-negative integers. Dimension respects tensor product and direct sum and so this association is compatible with the composition in 2-Vect. Thus if a matrix of vector spaces is weakly invertible, then its matrix of dimensions is also invertible, and moreover both this matrix and its inverse have positive interger entries. Thus, by the above fact, the matrix of dimesnions must be a permutation matrix.

But why is the above fact true?

Answer 1

Proof: The condition that $M$ has nonnegative integer entries means that it maps the monoid $\mathbb{Z}_{\geq 0}^n$ to itself. The condition that $M^{-1}$ is likewise means that $M$ is an automorphism of this monoid.

The basis elements $(0,0,\ldots,0,1,0,\ldots, 0)$ in $\mathbb{Z}_{\geq 0}^n$ are the only elements which cannot be written as $u+v$ for some nonzero $u$ and $v$ in $\mathbb{Z}_{\geq 0}^n$. This description makes it clear that any automorphism of $\mathbb{Z}_{\geq 0}^n$ must permute this basis. So $M$ is a permutation matrix.

Answer 2

This is an easy consequence of the Perron-Frobenius theorem, but I'll desribe a proof without using that theorem.

A non-negative matrix is one that takes the positive orthant into the positive orthant. Whether integral or not, if the inverse is also positive, it follows that the linear map is a homeomorphism of the positive orthant to itself. The image of the orthant in projective space is an $n-1$-simplex; the induced map is a projective map that permutes the vertices, or in other words, any such matrix is a permutation matrix times a positive diagonal matrix. The only positive unit in $\mathbb Z$ is 1, so it's a permutation matrix.

Answer 3

Suppose $A$ and $B=A^{-1}$ have all coefficients in $\mathbb N$. Then the same is true for the symmetric matrix $AA^t$ and its inverse $B^t B$. Since every row (and column) of $A$ and $B$ contains at least one strictly positive coefficient, the products $AA^t$ and $B^tB$ can be written as $AA^t=I+a$ and $B^tB=I+b$ with $a$ and $b$ two symmetric (not necessarily invertible) matrices with coefficients in $\mathbb N$. Since $AA^tB^tB=I$, we get $a=b=0$ by considering the product $AA^tB^tB=(I+a)(I+b)=I+a+b+ab$.

The matrix $A$ is thus an orthogonal matrix with coefficients in $\mathbb N$, which implies that it has exactly one non-zero coefficient equal to $1$ in every row and column. It is thus a permutation matrix.

Answer 4

Here is a particularly simpleminded proof (which is probably the same as some of the others). Suppose that $A$ and $B$ are $n \times n$ matrices with non-negative entries and that $AB=D$ is a diagonal matrix. For each non-zero entry $a_{ij} \gt 0$ of $A$ we have $b_{j \ell}=0$ for all $\ell \ne i$ since $d_{i \ell} = 0$. Likewise, for each $b_{ji} \gt 0$ we have $a_{kj}=0$ for all $k \ne i.$

Now suppose that $D$ is invertible, then each row of A has a non-zero entry. We will now see that it is the only non-zero entry of its row and of its column. For each $i$ there is some $j$ with $a_{ij} \gt 0.$ Then $b_{ji} \gt 0$ since nothing else in its row is. Since $d_{mi}=0$ for $m \ne i$, $a_{ij}$ is the only non-zero entry in its column. And since no two rows of $B$ are dependent, for every $k \ne j$ there is an $m \ne i$ with $b_{km} \gt 0.$ Since $d_{im}=0$ it follows that $a_{ik}=0$ so indeed $a_{ij}$ is the only non-zero entry of its row and column. Similarly, $b_{ji} \gt 0$ is the only non-zero entry of its row and column.

Hence the non-zero entries of $A$ are the same as those of a permutation matrix $P$ and those of $B$ are the same as those of $P^t=P^{-1}$. If these non-negative matrices are integer matrices with $AB=I$ then the non-zero entries are all $1$ so $A=P.$