# An algebraic algorithm for finding inverses in the group algebra

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

-
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. –  Qiaochu Yuan Jan 30 '12 at 7:11
@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? –  DavidA Jan 30 '12 at 20:08
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)). –  Qiaochu Yuan Jan 30 '12 at 21:09
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. –  Jack Schmidt Jan 31 '12 at 0:55
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. –  Jack Schmidt Jan 31 '12 at 3:21