38
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ I am not completely sure what the best tags are for this question. Feel free to add tags or retag as appropriate. $\endgroup$ Apr 18, 2011 at 14:17
  • 7
    $\begingroup$ (I suspect this question, if it wasn't given the highbrow categorical context, could have been closed as "too localized" or "homework"... BTW, I upvoted it) $\endgroup$
    – Qfwfq
    Apr 18, 2011 at 14:51
  • 2
    $\begingroup$ @unknowngoogle: Hmmm, I guess perhaps it could have been closed. More the lesson to include a little context in MO questions. If it were closed then I would never have learned of David Speyer's and Bill Thurston's beautiful proofs! $\endgroup$ Apr 18, 2011 at 15:53
  • 2
    $\begingroup$ What happens when you do the (high-school) multiplication? Doesn't it become apparent that the matrix must pe a permuation matrix if it is invertible with it and its inverse having all nonnegative integers for coefficients? Gerhard "Ask Me About System Design" Paseman, 2011.04.18 $\endgroup$ Apr 18, 2011 at 21:52

4 Answers 4

109
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks David. This proof is both elegant and simple. I couldn't have hoped for a more pleasing answer. $\endgroup$ Apr 18, 2011 at 15:44
  • 9
    $\begingroup$ Does this explains why ${\rm GL}_n({\bf F}_1)={\mathfrak S}_n$ !? $\endgroup$ Aug 2, 2011 at 3:40
48
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you for this proof which is also quite elegant. I like it a great deal. I like David's answer slightly more, so I am accepting his response, but it was a hard call to make. Again, thank you. $\endgroup$ Apr 18, 2011 at 15:48
  • 3
    $\begingroup$ I like David's proof (which was posted as I was writing mine) as well---it's really a simpler way to see this particular fact, I agree with your choice. BTW, there's another interesting MO question asking a related but deeper question, mathoverflow.net/questions/24131/… $\endgroup$ Apr 18, 2011 at 18:05
  • 3
    $\begingroup$ This proof (as well as the proof I propose below) gives a slightly stronger result: If $A$ is invertible and both matrices $A$ and $A^{-1}$ have only non-negative real coefficients, then $A$ is a permutation matrix times a diagonal matrix with strictly positive diagonal coefficients. $\endgroup$ Apr 19, 2011 at 6:42
21
$\begingroup$

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.

$\endgroup$
0
6
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Slightly less general, AB a diagonal matrix and BA another diagonal matrix (and no negative coefficients, etc.) should give at most one element in each row and column of both A and B. Then invertibility gives exactly one and that they are permutation matrices comes from the coefficients being nonnegative integers. However, I am glad you wrote up the proof I was thinking. Gerhard "Ask Me About System Design" Paseman, 2011.04.19 $\endgroup$ Apr 19, 2011 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.