Prove that a matrix is the permutation matrix of a permutation

Question

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.

Answer 1

Hint:

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.