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](http://ncatlab.org/nlab/show/2-vector+space#kapranovvoevodsky_2vector_spaces_15), 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?



Invertible matrices of natural numbers are permutations... why?
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.


