Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

share|improve this question

1 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.

share|improve this answer

Your Answer

 
discard

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.