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)



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.


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.