Bases in max-algebra. (English) Zbl 1059.15001

The authors consider bases for spaces of vectors over the semiring \((\mathbb R, \max, +)\). It is proved that all bases for a subset have the same cardinality; there exist subsets of \(\mathbb R^n\) having bases of arbitrary cardinality iff \(n\geq 3\); subsets have (finite) bases iff they are finitely generated, that \(\mathbb R^n\), \(n>1\) has no basis in this sense, and if bases were allowed to be infinite, under certain conditions bases would still not exist. One special feature of the definition is that in writing \(w\) as a linear combination of some set \(U\) of vectors, the linear combination is not allowed to involve \(w\) itself.


15A80 Max-plus and related algebras
15A03 Vector spaces, linear dependence, rank, lineability
Full Text: DOI


[1] Baccelli, F.L.; Cohen, G.; Olsder, G.-J.; Quadrat, J.-P., Synchronization and linearity, (1992), John Wiley Chichester, New York
[2] Carré, B.A., An algebra for network routing problems, J. inst. math. appl., 7, 273-294, (1971) · Zbl 0219.90020
[3] R.A. Cuninghame-Green, Minimax Algebra, Lecture Notes in Economics and Math. Systems, vol. 166, Springer, Berlin, 1979
[4] R.A. Cuninghame-Green, Minimax Algebra and Applications, in: Advances in Imaging and Electron Physics, vol. 90, Academic Press, New York, 1995, pp. 1-121
[5] S. Gaubert, Théorie des systèmes linéaires dans les dioı̈des, Thèse, Ecole des Mines de Paris, 1992
[6] M. Gondran, M. Minoux, L’indépendance linéaire dans les dioı̈des, Bulletin de la Direction Études et Recherches, EDF, Sé rie C, vol. 1, 1978, pp. 67-90
[7] Gondran, M.; Minoux, M., Linear algebra of dioı̈ds: a survey of recent results, Ann. discr. math., 19, 147-164, (1984) · Zbl 0568.08001
[8] Wagneur, E., Moduloids and pseudomodules 1. dimension theory, Discrete mathematics, 98, 57-73, (1991) · Zbl 0757.06008
[9] K. Zimmermann, Extremálnı́ algebra, Výzkumná publikace Ekonomicko - matematické laboratoře při Ekonomické m ústavě ČSAV, 46, Praha, 1976 (in Czech)
[10] U. Zimmermann, Linear and Combinatorial Optimization in Ordered Algebraic Structures. Ann. of Discrete Math., vol. 10, North Holland, Amsterdam, 1981 · 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.