# permutation matrix

• May 24th 2009, 11:17 AM
manjohn12
permutation matrix
Prove that permutation matrices can be written as the product of transpositions.

So geometrically, we can represent transpositions as lines between two "poles" or sticks. And completing the cycle defines a permutation?
• May 24th 2009, 02:15 PM
NonCommAlg
Quote:

Originally Posted by manjohn12
Prove that permutation matrices can be written as the product of transpositions.

So geometrically, we can represent transpositions as lines between two "poles" or sticks. And completing the cycle defines a permutation?

for any $\displaystyle \alpha, \beta \in S_n,$ let $\displaystyle P_{\alpha}, P_{\beta}$ be the corresponding permutation matrices. then $\displaystyle P_{\alpha}P_{\beta}=P_{\beta \alpha }.$ now use this fact that every $\displaystyle \sigma \in S_n$ is a product of transpositions.
• May 24th 2009, 02:44 PM
manjohn12
because every transposition matrix is a permutation?
• May 24th 2009, 02:50 PM
NonCommAlg
Quote:

Originally Posted by manjohn12

because every transposition matrix is a permutation?

ok, how do you basically define a transposition matrix?
• May 24th 2009, 10:27 PM
Swlabr
Quote:

Originally Posted by NonCommAlg
for any $\displaystyle \alpha, \beta \in S_n,$ let $\displaystyle P_{\alpha}, P_{\beta}$ be the corresponding permutation matrices. then $\displaystyle P_{\alpha}P_{\beta}=P_{\beta \alpha }.$ now use this fact that every $\displaystyle \sigma \in S_n$ is a product of transpositions.

Is there not a neat way of showing the result for permutation matrices without going back into $\displaystyle S_n$?
• May 25th 2009, 01:12 PM
manjohn12
Quote:

Originally Posted by NonCommAlg
ok, how do you basically define a transposition matrix?

by interchanging two rows of the identity matrix
• May 25th 2009, 11:30 PM
NonCommAlg
Quote:

Originally Posted by manjohn12

by interchanging two rows of the identity matrix

right! and when you interchange the rows $\displaystyle i,j,$ you exactly get the permutation matrix $\displaystyle P_{\sigma},$ where $\displaystyle \sigma=(i \ j).$ so, every transposition matrix is a permutation.