Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that a matrix is the permutation matrix of some permutation just when

1 its entries are all 0’s or 1’s and

2 it has exactly one 1 in each column and

3 it has exactly one 1 in each row.

My attempt is that I kinda of "know" this is true because of the definition of a permutation matrix but I do not know how to describe this or prove it. I have also used the search function on this site.

I know multiplying on the left by a permutation matrix gives row rearrangements to the matrix in question. And multiplying on the right gives column rearrangements. And that if $A$ and $B$ are permutation matrices, their product does the rearrangements of $B$ followed by $A$.

I would like the answer in sigma notation as well as the capital letter notation. If I could see this worked out I believe I can make progress on the rest of the problems I want to do. Right now, I am completely lost.

(I have already asked through normal channels in my university which was unbelievably unhelpful)

share|cite|improve this question


In the $i$th row there is a single entry which is one. Lets say that this is $ij$. Define $\sigma(i)=j$.

This way you get a function $\sigma: \{ 1,2,.., n\} \to \{1,2,..,n\}$. Use now (2) to prove that $\sigma$ is one to one. Conclude that $\sigma$ is a permutation which gives exactly your matrix.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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