Max-plus代数中analogy-transitive矩阵及其本征问题

The Analogy-transitive Matrix and Its Eigenproblem in Max-plus Algebra

定义一类analogy-transitive矩阵,讨论其基本性质,给出判定一个矩阵是否为analogytransitive矩阵的判定定理及算法,最后讨论关于analogy-transitive矩阵的本征问题.对于analogytransitive矩阵,存在一个O(n2)的算法计算其唯一本征值λ(A)和所有本征向量x=(x1,…,xn)使得max j=1,…,n(aij+xj)=λ+xi(i=1,…,n).该结果较一般情况下O(n3)的算法有所改进.

The eigenproblem for analogy-transitive matrices in max-plus algebra is shown to be solved.For an analogy-transitive matrix A =（aij）,there exists an O（n^2） algorithm to find the unique eigenvalue λ （A） and all eigenvectors x =（x1,x2,…,xn） such that max j=1,…,n（aij ＋ xj） =λ ＋ xi （i =1,…,n）.The results improve the standard O（n3） algorithms in general case.