# Nonnegative orthogonal matrices

Assume that $A \in \mathbb{R}^{n \times n}$ has nonnegative entries and $AA^T = I_n$ where $I_n$ is the identity matrix. Is it true that $A$ should be a permutation matrix?

EDIT: I seem to have a proof for doubly stochastic matrices based on the Birkhoff theorem. Here is another related question: Is the set of nonnegative matrices the conic hull of permutation matrices?

• The columns have to be orthogonal so if you think about it each can have only a single nonzero entry and that entry must be $1$ for the column to be a unit vector. I don't know what a conic hull is. Mar 6, 2013 at 12:42
• Consider the $i$-th row of $A$, and let $J_i = \{j \in \{1,\ldots,n\} | a_{ij} > 0\}$. The $J_i$ are nonempty (since $A$ is invertible) and pairwise disjoint, therefore each of them must have exactly one element. Mar 6, 2013 at 12:53
• For the conic hull question, it is clearly false because if a matrix $M$ is a conic combination of permutation matrices, then the sums of the rows of $M$ (as well as the columns) are all equal. Mar 6, 2013 at 13:06
• non negative constraint eliminates the other orthogonal matrix otherthan permutation matrix Mar 6, 2013 at 14:23
• Gerry Myerson and Learner, that was my intuition too, thanks for confirming. Pedro M., thanks, your argument settles it (and also the conic hull question.) Mar 6, 2013 at 14:44

Yes, $A$ must be a permutation matrix.