> sorting generators (of a group or algebra) may be more tricky than > you think. In case of the symmetric group, the `sign' is `-1' for a > transposition, > but a transposition can be elementary or not (changing adjacent or > distant generators [sic: indices]).
You are right. In my previous posts I used the word "transposition" with a meaning of elementary transpositions only exchanging neighbours. This may be a source of confusion. > If you work in a slight > generalization, say a Hecke algebra then you need to be more careful, > as the `sign' in this case is `q`, and an elementary (!) > transposition picks up a factor of 'q', while a general transposition > can have a more elaborate factor (in general q-polynomials). Ok. But a general transposition can still be composed of individual elementary ones and we can get the complicated factor by combining the simple factors, no? > Hence it is worth writing code which does count elementary > transpositions, My code already does this. For the bubble sort it is obvious. All, if any, operations done on the list are just swaps of neighbouring elements. Hence we count elementary transpositions. For the merge sort it may be less obvious. But we can get the correct number of elementary transpositions by incrementing the count not only by 1 but by a larger amount for each merge operation. Assume we are in the merge phase of the algorithm. We got two sorted lists La and Lb from the returned recursive calls. Now we concatenate both without doing the merge operation. Then we get a list L := [La, Lb] where both parts (but not necessarily L) are sorted. Denote the length of A by a. We start from the left and step through L item by item, with the current position beeing i. Then either the element L(i) at this place is correct and we go on or there is another element that should go at place i. This other element can be found in the Lb part of L. By iterative application of this procedure, it is always at the head of the currently remaining part of Lb. Therefore we have to move it a-i steps to the left and perform a-i elementary transpositions. (Or a-i+1 if we index L starting with with 1 instead of 0.) Combining the logic of this single merge step with induction in the list length we see that it is always correct. If I did not misunderstand you these sorting algorithms are perfectly valid even for the generalized cases. Maybe you have a simple example ready to try? > as it will yield in the case q=-1 the correct > symmetric group (q=1, just sorting) signs for transpositions > used to form antisymmetrizers. In teh q-case > you get q-symmetrizers as were used by Woronowicz in his definition > of matrix pseudo (quantum) groups. Thanks for your hints. -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/fricas-devel?hl=en.
