<wschlanger@[EMAIL PROTECTED]
> wrote in message
news:8e94f36d-8aaa-49f7-a8e7-ebac3a467cf8@[EMAIL PROTECTED]
> I am investigating permutation matrices. These are matrices made by
> beginning with the identity matrix I and then permuting its columns,
> until a new matrix M results. M has the effect of "scrambling" or
> permuting a vector x, and this is reversible: given y = Mx, M has an
> inverse.
>
> Let M^u = M * M * M, u times. Then it is an interesting fact that for
> all 4x4 permutation matrices (of which there are 4!=24 possible
> permutation matrices), M^(12+x) = M^x for non-negative integers x. Can
> any one shed some light on this phenomenon? Thus M^5=M^17=M^29 etc. It
> is also interesting that M^12=I, e.g. whatever this magic number 12
> is, M to that power yields the identity matrix.
I have not studied these permutation matrices, but it seems they have an
obvious correspondence with the group of permutations of 4 symbols (called
S4). Perhaps you could do some research into the area of permutation
groups
and group theory to gain understanding of the properties of these
matrices?
Here are some observations about permutation groups that may be of use...
The group of permutations of n symbols consists of the 1-1 mappings of the
symbols into themselves. Such mappings can obviously be combined to give
new permutations, and this is referred to as multiplying the permutations,
and with this operation of multiplication, the permutations form a
mathematical "Group". Notice that each of your permutation matrices
corresponds to a particular permutation, e.g.
|0 1 0 0| |a| |b|
|0 0 1 0| |b| = |c|
|0 0 0 1| |c| |d|
|1 0 0 0| |d| |a|
corresponding to the permutation T with
T: a-->b
b-->c
c-->d
d-->a
It is useful when representing permutations to break them down into
"disjoint cycles", e.g. for T above, we have just one cycle
a-->b-->c-->d-->a... and we represent this cycle like this:
T = (a,b,c,d) (also we have T = (b,c,d,a) = (c,d,a,b) = (d,a,b,c),
it doesn't matter where in the cycle we start
recording it!)
This is called a 4-cycle, as it "cycles" 4 elements.
Looking at another of your matrices:
|0 1 0 0| |a| |b|
|1 0 0 0| |b| = |a|
|0 0 0 1| |c| |d|
|0 0 1 0| |d| |c|
we see this corresponds to the permutation
U: a-->b
b-->a
c-->d
d-->c
we see U is the product of two disjoint 2-cycles
U = (a,b) * (c,d)
The key thing about disjoint cycles is that they commute and so are easy
to
multiply together, so for example:
U^2 = (a,b) * (c,d) * (a,b) * (c,d)
= (a,b) * (a,b) * (c,d) * (c,d)
= (a,b)^2 * (c,d)^2
= I * I
= I (identity permutation)
You see it is easy to find powers of permutations when they are written as
products of disjoint cycles? We just raise each cycle to the required
power
and multiply them all together.
Also it should be clear that a n-cycle c will have "order" n, i.e. c^n =
identity. I.e. if you apply an n-cycle n times, the elements will all be
cycled back to their original position... (and doing it less than n times
won't have this property.)
Now it should be possible to see the answers to your questions! You are
looking at 4x4 matrices which correspond to permutations of 4 elements,
and
you are looking at powers of these matrices, which correspond to the
powers
of the permutations. What can the "orders" of these permutations be?
We break them down into products of disjoint cycles. Hmmm, where I've
been
using a,b,c,d above, it's more usual notation to just use the symbols
1,2,3,4, and the possible permutations will look like this:
(1,2,3,4)
(1,2,3)(4) = (1,2,3), as (4) is the mapping that
just cycles 4-->4-->4... which is the identity
and can be omitted
(1,3,2)(4) = (1,3,2)
(1,3)(2,4)
(1)(2,3)(4) = (2,3)
etc.
The first permutation listed is a 4-cycle and has order 4. That means
that
applying the permutation 4 times leaves things unchanged. Obviously this
also implies that applying it any multiple of 4 times leaves things
unchanged. Going back to your matrices, this is saying the 4th power (and
8th, 12th, 16th etc.) of the corresponding matrix will be the identity I.
The second permutation is a 3-cycle, with order 3, so your corresponding
matrix will have order 3. I.e. it's matrix raised to the power of 3, 6,
9,
12, etc. will be I.
The 4th permuation listed above is the product of two 2-cycles, and each
2-cycle has order 2, and so the product also has order 2. Your
corresponding matrix will have order 2, and so the 2nd, 4th, ...12th,
14th...etc. powers of the matrix will be I.
So the answer to your question is that there are only so many "types" of
permutation of 4 symbols when we categorise them in terms of disjoint
cycles, i.e.
- 4-cycle
- 3-cycle (times 1-cycle)
- 2-cycle times 2-cycle
- 2-cycle (times 1-cycle times 1-cycle)
- Identity (= product of four 1-cycles)
The above permutations are easily seen to have orders 4, 3, 2, 2, and 1
respectively, and since 12 is a multiple of all these orders, we will have
T^12 = I for any permutation of 4 elements. (And so T^12 = I for any of
your permutation matrices.)
>
> Also I am interested in finding the set of permutation matrices M such
> that M ^ u = I for some non-negative integer u. I developed a program
> to do it, and it gives me M for u = 6 and u = 12 for instance. It
> works all right -- all possible answers have been multiplied by
> themselves to yield I after the requisite number of multiplications --
> although it is not exhaustive since we consider only permutation
> matrices. I found that M is a set -- there are for instance several
> possible permutation matrices M such that M ^ 2 = I (10 to be exact
> for a 4x4 matrix system).
Thinking in terms of permutations and disjoint cycles as above:
You want P ^ u = I, and if
P = P_1 * P_2 * ... P_n where these are disjoint, then
P^u = P_1^u * P_2^u * ... * P_n^u
= I,
and so you must have each of P_i^u = I (for i=1,2,...n)
i.e. u needs to be a multiple of the length of each of the cycles P_i.
E.g. taking u = 6, the disjoint cycles can be of lengths 1,2, or 3.
This allows us all permutations of types:
- 3-cycle (times 1-cycle)
- 2-cycle times 2-cycle
- 2-cycle (times 1-cycle times 1-cycle)
- Identity (= product of four 1-cycles)
and now you just have to identify the permutations above. E.g. to get the
3-cycles you first have to select the 3 elements involved (there are 4C3 =
4
ways to do this) and then list all the 3-cycles of these elements (there
will be (3-1)! = 2 possible cycles for each set of 3 elements, giving 4*2
=
8 3-cycles.
E.g. if we choose 3 elements 1,2,3 there are 2 3-cycles of these elements:
(1,2,3) [taking 1-->2-->3-->1..]
and (1,3,2) [taking 1-->3-->2-->1..]
....and so on...
For u=2, permutations can only consist of products of 1- and 2-cycles,
i.e.
permutations of types:
- 2-cycle times 2-cycle [there are 3 of these]
- 2-cycle (times 1-cycle times 1-cycle) [6 of these]
- Identity (= product of four 1-cycles) [1 of these]
and as you say, there are a total of 10 altogether (=3+6+1)
>
> Can anyone please help me figure out the meaning of M ^ (3 / 5) = I ?
Sorry I don't understand what you intend by this notation. Are you trying
to raise a matrix to the power of a non-integer? It is obvious that M^3 =
M*M*M, but what would M^(3/5) mean???
Anyway, hope my comments above are helpful!
Regards,
Mike.
> That is, I can compute M ^ 3 = I by brute force; it's a set of
> permutation matrices that when taken to the power of 3, yields I. But
> how to I proceed for that -SET- of matrices to a new set of matrices M
> ^ (3 / 5) ? I tried computing the cube of each element in the set and
> found the result is wrong (how do I know? I tried to compute I ^ (2 /
> 12) = M by first computing I ^ (1/12) and then finding the square of
> each element in that set. The results are in fact right -- taken to
> the 6th power they yield I, but they are not exhaustive -- if I
> compute I^(1/6) directly I find additional elements in the set not
> found by taking I ^ (1/12) elements squared).
>
> I also tried taking all permutation matrix M to the power of 3 and
> then computing that result to the power of (1/5), a set that, if it
> contiains only the identity matrix, was taken to be the M such that M
> ^ (3/5) = I. It got the same, wrong answer.
>
> I do not want to introduce negative numbers or imaginary numbers, or
> anything other than 0's and 1's in the permutation matrix.
>
> Your help greatly appreciated . . .
|
