Max-plus algebra solution to twosides linear equation C⊗x=D⊗x
[x,x0,r] = maxplustslinsol(C,D)
Function returns a non unique solution x to equation C⊗x=D⊗x,
a random initial x0 and the number of iterating r. The existence of solution x depend on the initial x0. The solution exists if for every row i-th there is an index j0 such that cij0= dij0. If there exists a row i-th such that ci,j > di,j for all j then the solution does not exist,
and function returns r=1000, x=[].
For detailed, see : Cechlarova, K. (2005), "Eigenvectors of Interval Matrices over Max-Plus Algebra", Discrete Applied Mathematics, vol.150, 2-15.
Note that, if the equation C⊗x=D⊗x have solutions, then by running [x,x0,r] = maxplustslinsol(C,D) will gives x an
solution to C⊗x=D⊗x. Instead of if running [x,x0,r] = maxplustslinsol(D,C), then it possible that will gives x=[]. So
the solution does not exist. Furthermore, if D is a square matrix with an eigenvalue λ and C=λ⊗I with I identity matrix,
then the solution x to C⊗x=D⊗x exists and x is an eigenvector of D corresponding to eigenvalue λ.
c = [1. 2. 4. 8.; 6. 3. 9. 4.; 7. 3. 8. 0. ]; d = [0. 1. 4. 5.; 2. 3. 9. 2.; 7. 3. 7. 0.] ; [x,x0,r] = maxplustslinsol(c,d) // Check that x is the solution maxplusotimes(c,x)==maxplusotimes(d,x) // another solution [x,x0,r] = maxplustslinsol(c,d) // Check that x is the solution maxplusotimes(c,x)==maxplusotimes(d,x) // But by running [x,x0,r] = maxplustslinsol(d,c) [x,x0,r] = maxplustslinsol(d,c) // we get x=[], it means that the solution to d⊗x=c⊗x // does not exists. // The next example gives a solution does not exist. c = [10. 6. 13. 16. 6.; 17. 15. 9. 10. 9.; 2. 12. 18. 11. 11.; 4. 8. 5. 7. 8. ; 8. 11. 10. 14. 9. ]; d = [4. 6. 4. 7. 5.; 9. 7. 9. 3. 1.; 1. 9. 9. 5. 2.; 2. 5. 3. 3. 6.; 6. 3. 4. 5. 8.]; // Check that c≥d c >= d // observe that c(3,:)≠d(3,:) isequal(c(3,:),d(3,:)) // So, the equation c⊗x=d⊗x does not has a solution [x,x0,r]=maxplustslinsol(c,d) // this means that a solution does not exist. // Now we compute the eigenvalue of d mcm=maxplusmcm(d) // and let be c=(mcm)⊗(I) c=maxplusotimes(mcm,maxpluseye(5,5)) // and running [x,x0,r] = maxplustslinsol(c,d) [x,x0,r] = maxplustslinsol(c,d) // Check that x is an eigenvector of d // corresponding to the eigenvalue mcm [z] = maxplusisegv(d,x,mcm) | ![]() | ![]() |