Max-plus algebra eigenvalue and eigenvector
[l,v,d] = maxplusmaxalgol(A)
: a positve integer number that represents the period of vectors
x(q),x(q+1),⋯,x(p-1),x(p), where d = p-q and x(p) = l⊗x(q).
The function valid for both an irreducible and a reducible matrix A as long as the cycle time vector of matrix A contains all elements equal to the same constant, and returns eigenvector and a unique corresponding eigenvalue of matrix A. If the condition is not satisfied the function returns error. And if numerical error this function maxplusmaxalgol still work but A⊗v≠l⊗v and the norm of A⊗v - l⊗v given by norm(A⊗x - l⊗v)≤4.019D-14 .
For details see: Subiono and J.van der Woude (2000); "Power algorithms for (max,+)- and bipartite (min,max,+)-systems"; DEDS, vol.10, pp.369-389, 2000.
If the matrix A irreducible, instead of use function maxalgol, the time computation will more faster.
A =[-%inf 3. -%inf -%inf 7. -%inf; 2. -%inf 6. -%inf 7. 2.; -%inf 7. 8. 9. -%inf -%inf; -%inf -%inf -%inf 1. 2. -%inf; 8. -%inf 7. -%inf -%inf 2.; 0. -%inf -%inf 6. 5. -%inf]; // check strognly connected (irreducible) of A s=maxplusscg(A) s = T [l,v,d] = maxplusmaxalgol(A) d = 1. v = 15. 15. 17. 10. 16. 13. l = 8. // check v is the eigenvector of A with corresponding eigenvalue l z = maxplusisegv(A,v,l) z = T // or we can check as follows : isequal(maxplusotimes(A,v),maxplusotimes(l,v)) ans = T // instead of we can use maxalgol [l,v,d] = maxalgol(A) d = 1. v = 15. 15. 17. 10. 16. 13. l = 8. // Example reducible matrix A=[7 -%inf;0 3] A = 7. -Inf 0. 3. // Check matrix A is not irreducible s=maxplusscg(A) s = F [l,v,d] = maxplusmaxalgol(A) d = 1. v = 14. 7. l = 7. // check v is the eigenvector of A with the eigenvalue l z = maxplusisegv(A,v,l) z = T // Example reducible matrix but the cycle time vector at least contain two // difference elements, and returns an error massage. A=[8 -%inf;0 11] A = 8. -Inf 0. 11. // check cycle time vector of matix A and, run maxplusmaxalgol s=maxplusctv(A) s = 8. 11. // the cycle time vector contains difference elements [l,v,d]=maxplusmaxalgol(A) !--error 10000 The matrix does not has a unique eigenvalue at line 32 of function called by : [l,v]=maxplusmaxalgol(A) // Example if numerical error exists A = [12. -%inf -%inf 19. 13. 5. 15. -%inf -%inf -%inf; 11. 10. 16. 9. -%inf 13. 6. 8. 5. 18.; -%inf 8. -%inf -%inf 19. -%inf 8. -%inf 4. -%inf; 17. -%inf 16. -%inf -%inf 5. -%inf 17. 16. 19.; -%inf -%inf 4. -%inf 8. -%inf 20. -%inf 16. 14.; 6. 2. 7. -%inf -%inf -%inf -%inf -%inf 10. 19.; -%inf 1. -%inf -%inf 9. -%inf 14. 5. -%inf 1.; 19. -%inf 9. 19. 4. 20. 18. 10. 16. 11.; 5. -%inf 13. 15. -%inf -%inf -%inf 20. 3. -%inf; 18. 15. -%inf -%inf 7. -%inf 13. 9. 15. 6.]; [l,v,d]=maxplusmaxalgol(A); // this means that, the maxplusmaxalgol still work, returns A⊗v ≠ l⊗v, // but the norm of (A⊗v-l⊗v)≤4.019D-14 ~isequal(maxplusotimes(A,v),maxplusotimes(l,v)) ans = T // this is true that A⊗v ≠ l⊗v and the norm given by norm(maxplusotimes(a,v)-maxplusotimes(l,v)) ans = 4.019D-14 | ![]() | ![]() |