061350/Class Notes for Thursday October 19

Matrix exponentiation is harder than you think
You think you know matrix exponentiation? OK, here's a question to test your knowledge. Fix a natural number . From here and on the word "matrix" means "an matrix with rational entries". Let be a linear combination of words whose letters are either matrices or meaningless symbols of the form . Say that if becomes when it is interpreted as a sum of products of formal power series of matrices and polynomials in formal variables , where is interpreted to mean . (Note that the number of formal parameters need not equal the number of matrices involved).
Thus for example, if the matrices and are known to commute (say and ), then . In fact, it is even true that .
Question. Provide a reasonable algorithm to decide if or not. In other words, provide a reasonable algorithm to decide if a certain equality between rational matrices and their exponentials holds or not.
Note that an unreasonable algorithm for this question is readily available. Over the algebraic closure of , exponentiations such as can be carried out explicitly using diagonalization, and then matrices can be multiplied or added as required, and the question is settled. The reason this is unreasonable is that the algebraic closure of is easy to speak of but very hard to work with. Many of you must have seen computer programs that manipulate rational numbers; this is easy. Have you ever seen a computer program that manipulates arbitrary algebraic numbers?
And of course, I could have asked the question about matrices with entries in some ring that doesn't have an algebraic closure. The question still makes sense, but the approach with explicit exponentiation does not.
In reality I care about an analog of this question in which the underlying algebra isn't necessarily a matrix algebra. For any algebra and any , makes sense within the algebra of formal power series in with coefficients in . Hence our question makes sense even if isn't a matrix algebra.
Note. As of the morning of October 19, I actually know how to solve this question. Whether my solution is useful or not, whether I will be able to use it or not, and if not useful, whether I will be able to make a precise sense of the way it is not useful, is yet to be seen. Drorbn 07:36, 19 October 2006 (EDT)