Register to reply

Need help finding permutation matrix

by Samuelb88
Tags: matrix, permutation
Share this thread:
Samuelb88
#1
Jun19-11, 02:39 AM
P: 162
1. The problem statement, all variables and given/known data
What is the permutation matrix associated to the permutation of [itex]n[/itex] indices defined by [itex]p(i) = n - i + 1[/itex]? What is the cycle decomposition of [itex]p[/itex]? What is it's sign?

2. Relevant equations
Prop. A permutation matrix [itex]P[/itex] has a single 1 in each row and in each column, the rest of its entries being 0.

3. The attempt at a solution
I. So I'm a bit confused on how to find the matrix associated with [itex]p[/itex]. Here's my attempt:

Given [itex]p(i) = n - i + 1[/itex] defines a permutation of [itex]n[/itex] indices, then by our proposition, we know the associated matrix with [itex]p[/itex], say [itex]A[/itex], is an [itex]n \times n[/itex] matrix with a single 1 in each row and each column, the rest of its entries being 0. Therefore it is of the form:

[tex]A = \sum_i e_{p(i),i} = \sum_i e_{n-i+1,i}[/tex]

where [itex]e_{i,j}[/itex] denotes an [itex]n \times n[/itex] matrix with a single 1 in the ith row and jth column. From this we find that:

[tex]A = e_{n,1} + e_{n-1,2} + \cdots + e_{2,n-1} + e_{1,n}[/tex]

I guess I am a bit confused on whether I can deduce that [itex]A[/itex] is an [itex]n \times n[/itex] matrix from the fact that [itex]p[/itex] defines a permutation of [itex]n[/itex] indices. If so, does that mean I can sum [itex]i[/itex] from 1 to n in the formula above to find [itex]A[/itex]?

II. To find the cycle of decomposition of [itex]p[/itex], provided that my answer from I. is correct, would I just write:

[tex](n,1)(n-1,2) \cdots[/tex] ?

III. I'm not sure on how to determine the sign of [itex]A[/itex] seeing as it depends on the oddness or evenness of [itex]n[/itex].
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
HallsofIvy
#2
Jun19-11, 07:06 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,556
That function just reverses the order of the indices. The corresponding matrix has all 0s except that the diagonal from lower left to upper right is all 1s. It's sign is [itex](-1)^n[/itex].

Yes, it can be decomposed into cycles, (1, n)(2, n-1), ....
Samuelb88
#3
Jun19-11, 11:52 AM
P: 162
I'm confused about the sign being [itex](-1)^n[/itex]. Suppose that [itex]n=2[/itex]. Then:

[tex]A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}[/tex]

Then [itex]\det(A) = -1[/itex] and therefore the sign is -1. But according to your formula, the determinant of [itex]A[/itex] should be 1 and therefore the sign should be 1.

Here's what I think. After some investigation, I noticed that the sign of the determinant changes every [itex]2n[/itex]. We know that our permutation is a product of k transpositions [itex]\tau_1 \tau_2 \cdots \tau_k[/itex], where k equals either [itex]\frac{n-1}{2}[/itex], if [itex]n[/itex] is odd, or [itex]\frac{n}{2}[/itex], if [itex]n[/itex] is even. Thus the sign of the permutation is [itex](-1)^k[/itex], with [itex]k[/itex] defined as above.


Register to reply

Related Discussions
Powers of a permutation matrix. Calculus & Beyond Homework 2
Permutation matrix and PA = LDU Calculus & Beyond Homework 4
Conjugation of a permutation by a permutation in a permutation group Calculus & Beyond Homework 3
Matrix, making R2 to R3, finding standard matrix A! where did i mess up? Calculus & Beyond Homework 1
Finding the inverse and finding a matrix * A = 0 matrix Introductory Physics Homework 6