Matrix Representation of the Permutation Group
Matrix Representation of the Permutation Group
The set of all permutations of forms a group under the multiplication (composition) of permutations; that is, it meets the requirements of closure, existence of identity and inverses, and associativity. We can set up a bijection between and a set of binary matrices (the permutation matrices) that preserves this structure under the operation of matrix multiplication. The bijection associates the permutation with the matrix , with zeros everywhere except for ones at row, column , for .
S
n
{1,2,…,n}
S
n
n×n
p=
1 | 2 | … | n |
p 1 | p 2 | … | p n |
P
p
i
p
i
i=1,2,…,n