# zbMATH — the first resource for mathematics

Simple image set of (max,+) linear mappings. (English) Zbl 0976.15013
By defining an addition $$a\oplus b=\max(a,b)$$ and a multiplication $$a\otimes b =a+b$$ for any $$a,b\in\mathbb{R}$$, one can construct a max-algebra of real numbers. Then these operations can be extended to matrices and vectors in the same way as in conventional linear algebra. If $$A$$ is a real $$n\times n$$ matrix, then the mapping $$x\mapsto A\otimes x$$ from $$\mathbb{R}^n$$ to $$\mathbb{R}^n$$ ($$n>1$$) is neither surjective nor injective. However, for some of such mappings (called strongly regular) there is a nonempty subset (called the simple image set) of the range, each element of which has a unique pre-image. In this paper, a description of simple image sets is presented, from which criteria for strong regularity are obtained. It is also proved that the closure of the simple image set of a strongly regular mapping $$f$$ is the image of the $$k$$-th iterate of $$f$$ after normalization for any $$k\geq n-1$$ or, equivalently, the set of fixed points of $$f$$ after normalization.

##### MSC:
 15A30 Algebraic systems of matrices 15A04 Linear transformations, semilinear transformations
##### Keywords:
max-algebra; strong regularity; eigenproblem; assignment problem
Full Text:
##### References:
  Baccelli, F.L.; Cohen, G.; Olsder J.-P. Quadrat, G.-J., Synchronization and linearity, (1992), Wiley New York  Butkovic, P., Strong regularity of matrices – a survey of results, Discrete appl. math., 48, 45-68, (1994) · Zbl 0804.06017  Butkovic, P.; Cuninghame-Green, R.A., On the regularity of matrices in MIN algebra, Linear algebra appl., 145, 127-139, (1991) · Zbl 0731.15012  Butkovic, P.; Hevery, F., A condition for the strong regularity of matrices in the minimax algebra, Discrete appl. math., 11, 209-222, (1985) · Zbl 0602.90136  Cuninghame-Green, R.A., Describing industrial processes with interference and approximating their steady-state behaviour, Oper. res. quart., 13, 95-100, (1962)  Cuninghame-Green, R.A., Minimax algebra, Lecture notes in economics and mathematical systems, Vol. 166, (1979), Springer Berlin  R.A. Cuninghame-Green, Minimax Algebra and Applications in: Advances in Imaging and Electron Physics, Vol. 90, Academic Press, New York, 1995.  S. Gaubert, Théorie des systèmes linéaires dans les dioı̈des, thèse, Ecole des Mines de Paris, 1992.  M. Gavalec, Private communication, 1999.  M. Gondran, M. Minoux, Valeurs propres et vecteurs propres dans les dioı̈des et leur interprétation en théorie des graphes. EDF Bulletin de la Direction des Études et Recherches, Série C-Math. Info. #2, 1977, pp. 25-41.  Gondran, M.; Minoux, M., Linear algebra of dioı̈ds: a survey of recent results, Ann. discrete math., 19, 147-164, (1984) · Zbl 0568.08001  Karp, R.M., A characterization of the minimum cycle Mean in a digraph, Discrete math., 23, 309-311, (1978) · Zbl 0386.05032  Prou, J.M.; Wagneur, E., Controllability in the MAX-algebra, Kibernetika, 35, 13-24, (1999) · Zbl 1274.93036  Wagneur, E., Moduloids and pseudomodules. I: dimension theory, Discrete math., 98, 57-73, (1991) · Zbl 0757.06008  K. Zimmermann, Extremálnı́ algebra (Výzkumná publikace Ekonomicko-matematické laboratore pri Ekonomickém ústave CSAV, 46, Praha, 1976) (in Czech).  Zimmermann, U., Linear and combinatorial optimization in ordered algebraic structures, Annals of discrete mathematics, Vol. 10, (1981), North-Holland Amsterdam · Zbl 0466.90045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.