The Cayley-Hamilton theorem (CHT) is a classic result in linear algebra over fields which states that a matrix satisfies its own characteristic polynomial. CHT has been extended from fields to com- mutative semirings by Rutherford in 1964. However, to the best of our knowledge, no result is known for noncommutative semirings. This is a serious limitation, as the class of regular languages, with finite automata as their recognizers, is a noncommutative idempotent semiring. In this paper we extend the CHT to noncommutative semirings. We also provide a simpler version of CHT for noncommutative idempotent semirings.
In Proc. of CIAA'10, the 15th International Conference on Implementation and Application of Automata, Winnipeg, Canada, August, 2010, pp. , Springer LNCS .
*This work was supported by the NSF Faculty Early Career
Development Award CCR01-33583 and the NSF CCF05-23863 Award.