CSR expansions of matrix powers in max algebra

Details CSR expansions of matrix powers in max algebra CSR expansions of matrix powers in max algebra

2009-12-13

arxiv.org/abs/0912.2534v2

Mathematics

Rings and Algebras

25 pages, minor corrections, added 3 illustrations

Scientific paper

We study the behavior of max-algebraic powers of a reducible nonnegative n by n matrix A. We show that for t>3n^2, the powers A^t can be expanded in max-algebraic powers of the form CS^tR, where C and R are extracted from columns and rows of certain Kleene stars and S is diadonally similar to a Boolean matrix. We study the properties of individual terms and show that all terms, for a given t>3n^2, can be found in O(n^4 log n) operations. We show that the powers have a well-defined ultimate behavior, where certain terms are totally or partially suppressed, thus leading to ultimate CS^tR terms and the corresponding ultimate expansion. We apply this expansion to the question whether {A^ty, t>0} is ultimately linear periodic for each starting vector y, showing that this question can be also answered in O(n^4 log n) time. We give examples illustrating our main results.

Affiliated with

Also associated with

No associations

Rating

CSR expansions of matrix powers in max algebra does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with CSR expansions of matrix powers in max algebra, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and CSR expansions of matrix powers in max algebra will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-557365