5
$\begingroup$

This is an extension to my earlier question.

Is there a purely algebraic algorithm to find inverses in the group algebra? For example, in the group algebra $\mathbb{C}S_{4}$, how would one go about finding an inverse for $(1 2 3) + 2(1 2)(3 4)$.

By a purely algebraic algorithm, I mean one that avoids, if possible, the use of representation theory. (So if possible, it shouldn't require that I know the irreps of the group, and it shouldn't require that I switch to matrices.)

The answer to my earlier question pointed out that $(1 2 3) + 2(1 2)(3 4) = (1 2 3) (1 + 2(1 4 3))$ so it is sufficient to find an inverse for $1 + 2(1 4 3)$

Now, after a little experimentation, I've worked out how to do examples like this by inspection. The inverse is 1/9 of $1 - 2(1 4 3) + 4(1 3 4)$.

This is by analogy with the fact that the inverse of $1+x$ is $1-x+x^{2}-...$. Given $g$ of order $n$, then $(1+ag)(1-ag+a^{2}g^{2}-...\pm a^{n-1}g^{n-1}) = 1\pm a^{n}g^{n} = 1\pm a^{n}$, which is a scalar.

(Of course, some elements of the group algebra are zero divisors, and hence don't have inverses. For example $(1+(1 2)) (1-(1 2)) = 0$.)

Okay, so to get to the point. I'm stuck on how to proceed for elements of the form $1+ag+bh$, for example $1+2(1 2)+3(3 4)$. It's not clear that $ag+bh$ will be of finite order, so the above trick won't work.

Is there some analogue of Moebius inversion or principle of inclusion-exclusion that might be used?

EDIT: I think I have figured out how to do this (though I'm still curious whether there are other methods). It's easiest to explain with an example.

Suppose we want to invert $1+(1 2)+(3 4)$. It's clear that the answer, if it exists, will be of the form $a+b(1 2)+c(3 4)+d(1 2)(3 4)$. Multiplying these two expressions together, we get $a+a(1 2)+a(3 4)+b(1 2)+b+b(1 2)(3 4)+c(3 4)+c(1 2)(3 4)+c+d(1 2)(3 4)+d(3 4)+d(1 2)$. Now, identify coefficients with $1+0(1 2)+0(3 4)+0(1 2)(3 4)$, and we get a linear system in a, b, c, d. Solving the linear system gives us our inverse: 1/3 of $1+(1 2)+(3 4)-2(1 2)(3 4)$

  • 0
    If your ultimate goal is just to be able to write efficient code to do this, it makes more sense to me to write down a faithful matrix representation of the group algebra and work in that instead. In this case we can use $4 \times 4$ matrices, where elements of $S_4$ get sent to permutation matrices. Inverting $1 + ag$ is in some sense an abelian problem, since you are working in the commutative subalgebra generated by $g$, while inverting $1 + ag + bh$ is a nonabelian problem if $g, h$ don't commute and I don't see any reason to expect that it has a straightforward algebraic answer.2012-01-30
  • 0
    @QiaochuYuan - Unless I am mistaken, the permutation matrix representation is faithful on the group, but not on the group algebra. For example, I believe it sends $(1 2) + (3 4)$ to the same matrix as $1 + (1 2)(3 4)$. Hence although I could go from the group algebra to the matrix, and then invert the matrix, I couldn't then get back to the group algebra. Or am I misunderstanding?2012-01-30
  • 0
    Ah, you're right. Okay, then I guess you have to take the direct sum of the irreducible representations (this is still more efficient than using the regular representation, especially for "highly non-abelian" groups (that is, groups with irreps of large dimension)).2012-01-30
  • 0
    Something similar to what you've already done is to consider the minimal polynomial of x=1+g+h+… If its constant term is nonzero, then it gives an expression for the inverse as a polynomial in x, and if the constant term is 0, then it witnesses x as a zero divisor. The minimal polynomial is found by checking when x^k is dependent on {1,x,x^2,...,x^(k-1)} and then finding the dependence relation. This is linear algebra very similar to the equations you solved for when x^3 was dependent on {1,x,x^2}. If the support of x lies in a small subgroup, then this should be very effective.2012-01-31
  • 0
    GAP appears to just use your method (write down the system of equations corresponding to xy=1 and solve) as QuotientFromSCTable, but this is a fairly ridiculous method in general for group rings since the dimension of the regular module is so large. However, my method also appears to be pretty dumb, so I'm not sure how to do this (or if it is doable) for larger groups.2012-01-31
  • 0
    So here is a simple sounding question I can't answer: what is the inverse of 1 + (1,2) + (1,2,3,4,5,6,7,8,9,10,11)? Coefficients are complex numbers (or without loss, rational numbers). Will the coefficients have any pattern? Can one find any of the coefficients? I think all methods suggested would choke on this question.2012-01-31
  • 0
    @JackSchmidt - As it happens, I suspect that your example is a zero divisor. I've now implemented the code, and I find that $1+(1 2)+(1 2 3 4)$ and $1+(1 2)+(1 2 3 4 5)$ are zero divisors, for example - but as you anticipated, the algorithm is too slow for larger groups. I also observe that the inverses typically involve almost all the group elements. I still think that there might be some analogue of Moebius inversion in the incidence algebra, but I haven't managed to figure it out yet.2012-02-01
  • 0
    @DavidA: thanks! I'd be interested in anything you figure out. I wouldn't have expected division to be so hard.2012-02-01

0 Answers 0