Matrix not consistent with multiplication

[dlfivefifty]

This behaviour is inconsistent:

julia> using Permutations

julia> P = Permutation([4,2,1,3])
(1,4,3)(2)

julia> a,b,c,d = Permutation([2,1,3,4]),Permutation([1,2,4,3]),
                   Permutation([1,3,2,4]),Permutation([2,1,3,4]);

julia> a*b*c*d == P
true

julia> Matrix(a)*Matrix(b)*Matrix(c)*Matrix(d) ==
               Matrix(P)
false

Changing the order of multiplication fixes this (that is, swap p and q in *(::Permuation, ::Permutation).

[scheinerman]

I'm not 100% sure I agree with this change and will do some checking. I understand the beauty of having the Permutation --> Matrix transformation being covariant. My setup has it as contravariant; that is, Matrix(a*b)==Matrix(b)*Matrix(a). I found one example on the web that I think confirms my choice. See http://planetmath.org/exampleofpermutationmatrix . My linear algebra books are silent on this matter.

It boils down to this. Suppose π is a permutation and A is its associated permutation matrix. Which do we prefer: A[k,π(k)]=1 or A[π(k),k]=1? I'll ask some of my math buddies. If the answer is a resounding "it doesn't matter", then I'm OK with the change. But if there's a standard, I'd prefer to go with that.

[scheinerman]

OK. Now I've seen what you've done, and I regret that I cannot accept the change as you've set it up. We can debate the transformation from permutation to matrix, but the operation for permutations should be function composition. That is p[q[k]] must equal `(pq)[k]`:

julia> p = RandomPermutation(10)
(1,6,9,10,3,2,7)(4,5,8)

julia> q = RandomPermutation(10)
(1,3,6,5)(2)(4,9)(7,8,10)

julia> (p*q)[2]
7

julia> p[q[2]]
7

[dlfivefifty]

I think overriding * to be defined this way is misleading: any representations of the Symmetric group should act consistently with multiplication. You should override ∘ if you want function composition.

[dlfivefifty]

See for example: https://en.wikipedia.org/wiki/Representation_theory_of_finite_groups#Definition

The current definition is not consistent with the desire for ρ(p*q) == ρ(p)*ρ(q) where ρ is any representation.

[scheinerman]

I understand what you want, but I think the better solution is to change the definition of Matrix, and not of *. Let me think it over.

[dlfivefifty]

You can just change Matrix to return the transpose of the current result.

Both choices of definition of * are valid definitions of the symmetric group. It's just important to make sure the representation (and Matrix(::Permutation) should be a representation) is consistent.

[scheinerman]

Agreed, unless there's a strong reason not to. I plan to ask a few folks if there's a standard. I expect there isn't and I'll then change Matrix.

[dlfivefifty]

I asked a colleague of mine in representation theory and he said:

For multiplication one usually takes (12)(23)=(123)

This is consistent with your definition of *, so I concede that point.

I'll submit another PR to transpose Matrix(::Permutation) to make it behave like a representation.