# Prove that a matrix is the permutation matrix of a permutation

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 permutaion matrix gives row rearrangments to the matrix in question. And multiplying on the right gives column rearrangments. And that if A and B are permutation matrices, their product does the rearrangments of B followed by A.

I would like the answer in sigma notation aswell 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.

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.