This article was downloaded by: [University of Birmingham], [Peter Butkovic]On: 06 February 2012, At: 02:26Publisher: Taylor & FrancisInforma Ltd Registered in England and Wales Registered Number: 1072954 Registeredoffice: Mortimer House, 37-41 Mortimer Street, London W1T 3JH, UKLinear and Multilinear AlgebraPublication details, including instructions for authors andsubscription information:http://www.tandfonline.com/loi/glma20Z-matrix equations in max-algebra,nonnegative linear algebra and othersemiringsPeter Butkovi a , Hans Schneider b & Serge Sergeev ca School of Mathematics, University of Birmingham, Edgbaston,Birmingham B15 2TT, UKb Department of Mathematics, University of Wisconsin-Madison,Madison, WI 53706, USAc INRIA and CMAP Ecole Polytechnique, Palaiseau Cedex 91128,FranceAvailable online: 06 Feb 2012To cite this article: Peter Butkovi, Hans Schneider & Serge Sergeev (2012): Z-matrix equationsin max-algebra, nonnegative linear algebra and other semirings, Linear and Multilinear Algebra,DOI:10.1080/03081087.2012.656107To link to this article: http://dx.doi.org/10.1080/03081087.2012.656107PLEASE SCROLL DOWN FOR ARTICLEFull terms and conditions of use: http://www.tandfonline.com/page/terms-and-conditionsThis article may be used for research, teaching, and private study purposes. Anysubstantial or systematic reproduction, redistribution, reselling, loan, sub-licensing,systematic supply, or distribution in any form to anyone is expressly forbidden.The publisher does not give any warranty express or implied or make any representationthat the contents will be complete or accurate or up to date. The accuracy of anyinstructions, formulae, and drug doses should be independently verified with primarysources. The publisher shall not be liable for any loss, actions, claims, proceedings,demand, or costs or damages whatsoever or howsoever caused arising directly orindirectly in connection with or arising out of the use of this material.Linear and Multilinear Algebra2012, 1–20, iFirstZ-matrix equations in max-algebra, nonnegative linear algebra andother semiringsPeter Butkovicˇa*, Hans Schneiderband Sergeı˘SergeevcaSchool of Mathematics, University of Birmingham, Edgbaston, Birmingham B15 2TT,UK;bDepartment of Mathematics, University of Wisconsin-Madison, Madison,WI 53706, USA;cINRIA and CMAP Ecole Polytechnique,Palaiseau Cedex 91128, FranceCommunicated by C.-K. Li(Received 30 September 2011; final version received 6 January 2012)We study the max-algebraic analogue of equations involving Z-matricesand M-matrices, with an outlook to a more general algebraic setting. Weshow that these equations can be solved using the Frobenius trace-downmethod in a way similar to that in nonnegative linear algebra [G.F.Frobenius, U¨ber Matrizen aus nicht negativen Elementen. Sitzungsber.Ko¨n. Preuss. Akad. Wiss., 1912, in Ges. Abh., Vol. 3, Springer, 1968,pp. 546–557; D. Hershkowitz and H. Schneider, Solutions of Z-matrixequations, Linear Algebra Appl. 106 (1988), pp. 25–38; H. Schneider, Theinfluence of the marked reduced graph of a nonnegative matrix on the Jordanform and on related properties: A survey, Linear Algebra Appl. 84 (1986),pp. 161–189], characterizing the solvability in terms of supports and accessrelations. We give a description of the solution set as combination of theleast solution and the eigenspace of the matrix, and provide a generalalgebraic setting in which this result holds.Keywords: max-algebra; nonnegative linear algebra; idempotent semiring;Z-matrix equations; Kleene starAMS Subject Classifications: 15A80; 15A06; 15B481. IntroductionA Z-matrix is a square matrix of the form !I !A where ! is real and A is an(elementwise) nonnegative matrix. It is called an M-matrix if ! ""(A), where "(A) isthe Perron root (spectral radius) of A and it is nonsingular if and only if ! > "(A).Since their introduction by Ostrowski [28] M-matrices have been studied in manypapers and they have found many applications. The term Z-matrix was introducedby Fiedler–Pta´k [11].Results on the existence, uniqueness and nonnegativity of a solution x of theequation (!I !A)x ¼b for a given nonnegative vector b appear in many places(e.g. Berman-Plemmons [4] in the case of a nonsingular M-matrix or an irreduciblesingular M-matrix). Using the Frobenius normal form of A and access relation*Corresponding author. Email: [email protected] 0308–1087 print/ISSN 1563–5139 online! 2012 Taylor & Francishttp://dx.doi.org/10.1080/03081087.2012.656107http://www.tandfonline.comDownloaded by [University of Birmingham], [Peter Butkovic] at 02:26 06 February 2012defined by the graph of the matrix, Carlson [8] studied the existence and uniquenessof nonnegative solutions x of this equation in the case of a reducible singularM-matrix, and his results were generalized to all Z-matrices in Hershkowitz–Schneider [19].The purpose of this article is to prove corresponding results in the max-timesalgebra of nonnegative matrices, unifying and comparing them with the results in theclassical nonnegative linear algebra. We also notice that the basic proof techniquesare much more general. In particular, we exploit a generalization of the Frobeniustrace-down method [12,32]. This generalization is reminiscent of the universalalgorithms developed by Litvinov et al. [24,25,27], based on the earlier works onregular algebra applied to path-finding problems by Backhouse et al. [2,30].Following this line allows to include other examples of idempotent semirings, such asmax–min algebra [15] and distributive lattices [34]. A more general theoretic setup isdescribed in Section 4. It is very close to Cohen et al. [9] and Litvinov et al. [26].The main object of our study is Z-matrix equationAx þ b ¼ !x ð1Þover semirings. In the classical nonnegative algebra and max-plus algebra, any ! 6¼0is invertible, which allows to reduce (1) toAx þ b ¼ x: ð2ÞIn max-plus algebra, this equation is sometimes referred to as discrete Bellmanequation, being related to the Bellman optimality principle and dynamic program-ming [1,17,20]. In particular, it is very well-known that this equation has the leastsolution. However (to the authors’ knowledge) a universal and complete descriptionof solutions of !x ¼Ax þb or even x ¼Ax þb, which would cover both classicalnonnegative and max-plus algebra cases, is not found (surprisingly) in the keymonographs on max-plus algebra and related semirings. Such a description is