MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

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 --



  • Prev by Date: Re: Multiplying permutations
  • Next by Date: RE: Quick "Random[]" question
  • Previous by thread: Re: Multiplying permutations
  • Next by thread: Re: Fw: Re: Multiplying permutations