Re: Re: Multiplying permutations
- To: mathgroup at smc.vnet.net
- Subject: [mg41857] Re: [mg41837] Re: Multiplying permutations
- From: gauer at ras.sk.ca
- Date: Sat, 7 Jun 2003 00:08:46 -0400 (EDT)
- References: <bbhvu4$75u$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
> Thank you all very much for you interesting contributions.
<snip>
> 3) Using the idea of Kai's matrix approach I tried to define an nxn
> matrix P corresponding to a permutation p by (e = {1,2,...,n})
A couple of years back in a differential equations class I used a similar
idea to quickly pop off a solution. I may still have the .nb on my
platform at home (I'll check tonight if anyone's interested) for the
correct syntax that I used. Go ahead and polish up the syntax if the group
theory setting is an alternate approach.
Here's the (slightly modified) original message I sent Wolfgang in private
(and a quick guess that turned out to be another accurate answer for Jay's
purposes - All this posting may get to be contagious):
" I had on previous occasions converted p and q as vectors and wrote
A.p==q as a Matrix and done my work from there.
If p has n elements, A will look like an nxn matrix with a "1" if "3->2"
in the (3,2)th position and "0" otherwise for that row (if "3-/->2"). Next
step is to repeat for each row and build your arithmetic table that way. A
quick check for necessary conditions for validity of a good operation, A,
is:
A will have precisely n ones and n(n-1) zeroes, and, no one row and no one
column should have more than 1 one pop up.
<this paragraph slightly edited>
Interesting, this "simple command" (matrix arithmetic) could also allow for
inverses of products to be found easily enough as well, and it also allows
to run tests such as For[] conditions against the matrix operator. For
instance, if the matrix is nxn, then run at most n loop iterations to
check to see that matrix^n==Identity(nxn), and furthermore, test that no
other 0<k<n first returns matrix^k==Identity(nxn) as being true. If so,
matrix^(n-1) should return the inverse permutation (if I can accurately
recall a group theory interpretation of a similar exercise I once had to
prove).
<end editing>
The case might be that your vectors are unordered. In that case, I might
choose to say {{0,0,1},{1,0,0},{0,1,0}}.{{a,b,c}}->p={a=3,b=1,c=2} in your
example. Note that if a->a ever and you run into large matrices, you can
shrink the size of your matrix by a dimension (so n drops to (n-1) or
less)."
> Solve[P.p == e, P]
>
> but it didn't work. Any hints if there is a way to find P along this
> line would be helpful.
[
On another completely different note, an alternate solution for only
positive roots:
"Will
Solve[{x^2==1,Abs[x]==x},x]
do the trick? I'm not in front of a Mathematica terminal right now."
> Hello,
> Consider the following equation.
>
> Solve[x^2 ==1, x]
>
> Mathematica will output 1 and -1 for x. However, I only want
> Mathematica to output the positive solution (i.e., x -> 1), so I can use
> this conveniently in a subsequent equation. Is there a way to force the
> output to produce only the positive solution? Thanks, Jay
]
> Wolfgang
>
> Dr. Wolfgang Hintze wrote:
>
>> Is there a simple command in Mathematica to multiply two permutations,
>> i.e. to carry out one after the other?
>>
>> I looked at the packages DiscreteMath`Permutations` and
>> DiscreteMath`Combinatorica` but couldn't find it.
>>
>> Example
>>
>> p = {3,1,2} mapping: 1->3, 2->1, 3->2
>> q = {2,1,3} mapping: 1->2, 2->1, 3->3
>> p.q = mappings (p first, then q)
>> [1-p->3-q->3, 2-p->1-q->2, 3-p->2-q->1]
>> = {3,2,1}
>>
>> Any help appreciated
>>
>> Wolfgang
>>
>>
-- Kai G. Gauer, B. Sc. (Mathematics) --
Alumnus, Luther College, University of Regina
Royal Astronomy Society of Canada Regina Centre
www.rasc.ca www.reginachessclub.com www.ras.sk.ca
-- Regina Cathedral Centre Chess Club --