0
$\begingroup$

**show that any n by n permutation matrix is a product of at most n exchange matrices.

Can anyone please help me with proving this one?

I am so confused... Thanks a lot!**

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Let $\sigma$ be an arbitrary permutation of $\{1,...,n\}$. You can achieve $\sigma$ by first swapping $1$ with $\sigma(1)$. Then swap 2 (which might be in position 1 now, but that's okay) with $\sigma(2)$, unless it was already in its final position. Proceed. After $n$ swaps, you can make sure that every number is in its proper final location.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .