From: Joe Rieo To: sci-math-research@uunet.uu.net Subject: Powers of an algebraic element Date: 30 Sep 1998 21:26:00 -0700 Newsgroups: sci.math.research Let x be an element in an algebra. If x^2 = b*x + a*Id, where a and b are scalars and Id is the identity element in the algebra, then, for n a positive integer x^n = f_{a,b}(n)*x + g_{a,b}(n)*Id Are there closed form expressions for the functions f_{a,b} and g_{a,b}? Thanks, Joe Riel -- joer@k-online.com ============================================================================== From: Dave Rusin Date: Thu, 1 Oct 1998 09:41:19 -0500 (CDT) To: joer@k-online.com Subject: Re: Powers of an algebraic element [deletia -- djr] [...] this is fairly easy unless I'm overlooking some special context involved. If this is an associative algebra over a commutative ring R (e.g. a field) then let S = R*1 + R*x, the rank-2 free module over R spanned by 1 and x, which we may view as a formal indeterminate if we wish. Then your assumption x^2=a+bx implies that S is an additive subset closed under multiplication by x. The action of x is given in this basis by the 2x2 matrix A = [ 0 a ] [ 1 b ] that is, x sends 1 to 1*x and sends x to a*1+b*x. Then the algebra element you seek, x^n, can be computed as x^n times 1, which in turn is the element of S whose coordinates are in the first column of A^n. So your whole question boils down to, is there a closed form expression for the n-th power of A ? The answer is more or less yes: diagonalize A, raise the eigenvalues to a power, then change basis back. You can also view the sought-after coefficients as terms in a recurrence relation. As you may know from the Fibonacci sequence, the terms in such a sequence are given by formulas of the form c r^n + d s^n for some numbers c,d,r,s; in fact, r and s are precisely the eigenvalues I just mentioned, namely the roots of the equation X^2=bX+a. (You can determine c and d from the two initial values of the sequence.) The situation is a little different if a=-(b/2)^2, in which case there is a double root to the quadratic and the matrix need not diagonalize. If this is unclear I can post your message, although it would be more in keeping with the nature of the newsgroup if you were to ask a question which went beyond these ideas in some way. dave ============================================================================== From: "Joe Riel" To: "Dave Rusin" Subject: Re: Powers of an algebraic element Date: Thu, 1 Oct 1998 11:18:31 -0700 Dave, [deletia -- djr] Does it matter, in this context, whether the ring is commutative? I suspect not. My motivation is to compute the exponential of a multivector in a Clifford algebra. The general method I use (for a computer algebra system) is to convert to a matrix representation and then compute the exponential of the matrix via a Jordan canonical form. That is a somewhat expensive process, typical problems often can be handled on an ad-hoc basis by exploiting special properties (one of which was my original submission). Your explanation made me realize that the computation of the exponential can still be done via matrix conversion, but that I can use a smaller matrix, one that represents the multivector in a subalgebra of the full algebra. I'll have to think about that a bit. I wonder how difficult/expensive it is to determine an appropriate subalgebra for an arbitrary multivector? Finally, could you recommend a good book for self study (interesting problems, applications, good index, informal style, not just theorem/proof) on abstract algebra? Thanks again Joe Riel -- joer@k-online.com ============================================================================== From: Dave Rusin Date: Thu, 1 Oct 1998 23:14:20 -0500 (CDT) To: joer@k-online.com Subject: Re: Powers of an algebraic element > Does it matter, in this context, whether the ring is commutative? Well, yes and no. If you continue to assume associativity and the distributive laws but drop commutativity, you'll get similar but more complicated answers. If x^n = b_n x + a_n then x^(n+1) = x^n x = b_n x^2 + a_n x = (b_n b + a_n) x + (b_n a) so you can readily compute the new pair of coefficients with a matrix multiplication [ b a ] [ b a ] ^ n [ b_(n+1) a_(n+1) ] = [ b_n a_n ] [ ] = [ 1 0 ][ ] [ 1 0 ] [ 1 0 ] The problem is that matrix algebra over non-commutative rings is a real chore; AFAIK there is no guaranteed diagonalization over extension rings and so on. But I suspect perhaps you didn't mean that: I only had to assume that the subring of _constants_ (the subring containing a and b ) is central (commutes with all elements of R). The larger ring R containing x need not be commutative, since we never multiplied anything but powers of x (and constants from Z[a,b]) together. So if R is contained in a matrix algebra _over the real field_, then the techniques I mentioned in an earlier letter are fine. >I can use a smaller matrix, one that represents the multivector >in a subalgebra of the full algebra. I'll have to think about >that a bit. I wonder how difficult/expensive it is to determine >an appropriate subalgebra for an arbitrary multivector? I'm not entirely sure I understand you but perhaps you're just looking for the subalgebra generated by x. If your ring is a subalgebra of a real matrix algebra, this subalgebra will be isomorphic as an algebra to a direct sum of rings isomorphic to either the reals or the complexes -- certainly fairly simple, ring-theoretically. >Finally, could you recommend a good book for self study >(interesting problems, applications, good index, informal style, >not just theorem/proof) on abstract algebra? There's probably a Schaum's outline kind of book but I don't deal with that approach much. We use a textbook by two colleagues here for our undergraduate course (Beachy/Blair) which is fairly unintimidating, but certainly a true math text. You could try the algebra section of welcome.html It sounds like you're interested in Associative Ring Theory index/16-XX.html or (for Clifford algebras and so on) in Linear Algebra, index/15-XX.html I've included a number of pointers to texts and so on in those pages. dave ============================================================================== From: "Joe Riel" To: "Dave Rusin" Subject: Re: Powers of an algebraic element Date: Thu, 1 Oct 1998 23:42:21 -0700 Dave, Thanks again. Yes, the constants commute with all elements. Thanks for the site pointers. I see that Abstract Algebra II, by Beachy is on the web. I'll download the intro and if it seems reasonable purchase it and the companion volume, Joe -- joer@k-online.com