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?

  • 3
    $\begingroup$ 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. $\endgroup$ Mar 6, 2013 at 12:42
  • 2
    $\begingroup$ 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. $\endgroup$
    – Pedro M.
    Mar 6, 2013 at 12:53
  • 2
    $\begingroup$ 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. $\endgroup$
    – Pedro M.
    Mar 6, 2013 at 13:06
  • $\begingroup$ non negative constraint eliminates the other orthogonal matrix otherthan permutation matrix $\endgroup$
    – Learner
    Mar 6, 2013 at 14:23
  • $\begingroup$ 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.) $\endgroup$
    – passerby51
    Mar 6, 2013 at 14:44

1 Answer 1


Yes, $A$ must be a permutation matrix.

Suppose some rows have more than one positive element. Then by the pigeonhole principle, there must be one component which is positive in at least two rows, and this contradicts the orthogonality.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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