Eigenvalues and eigen-functionals of diagonally dominant endomorphisms in Min-Max analysis
✍ Scribed by M. Gondran; M. Minoux
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 715 KB
- Volume
- 282
- Category
- Article
- ISSN
- 0024-3795
No coin nor oath required. For personal study only.
✦ Synopsis
The so-called (Min, +) analysi.~ ,,Jay be viewed as an extension to the continuous case and to functional spaces of shortest path algebras in graphs. We investigate here (Min-Max) analysis which extends, in some similar way, minimum spanning tree problems and maximum capacity path problems in graphs. An endomorphism A of the functional Min-Max semi-module acts on any functional f to produce A I~ where, Vx:
Af(x) = Min{Max{A(x,y);fO,)} }. y
We present here a complete characterization of eigenvalues and eigen-functionals of diagonally dominant endomorphisms (i.e. such that Vx, Vy:A(x,x) = OA, A(x,y) >10A). It is shown, in particular, that any real value 2 > 0A is an eigenvalue, and that the associated eigen-semi-module has a unique minimal generator.