Max-linear Systems: Theory and Algorithms (eBook)

Preface 6
Contents 9
List of Symbols 13
Introduction 16
Notation, Definitions and Basic Properties 16
Examples 22
Feasibility and Reachability 24
Multi-machine Interactive Production Process: A Managerial Application 24
MMIPP: Synchronization and Optimization 25
Steady Regime and Its Reachability 26
About the Ground Set 27
Digraphs and Matrices 28
The Key Players 31
Maximum Cycle Mean 32
Transitive Closures 36
Transitive Closures, Eigenvectors and Subeigenvectors 36
Weak Transitive Closure 37
Strong Transitive Closure (Kleene Star) 38
Two properties of subeigenvectors 41
Computation of Transitive Closures 42
Dual Operators and Conjugation 44
The Assignment Problem and Its Variants 45
Exercises 51
Max-algebra: Two Special Features 55
Bounded Mixed-integer Solution to Dual Inequalities: A Mathematical Application 55
Problem Formulation 55
All Solutions to SDI and All Bounded Solutions 56
Solving BMISDI 57
Solving BMISDI for Integer Matrices 59
Max-algebra and Combinatorial Optimization 62
Shortest/Longest Distances: Two Connections 62
Maximum Cycle Mean 63
The Job Rotation Problem 63
Other Problems 65
Exercises 66
One-sided Max-linear Systems and Max-algebraic Subspaces 67
The Combinatorial Method 67
The Algebraic Method 71
Subspaces, Generators, Extremals and Bases 73
Column Spaces 78
Unsolvable Systems 81
Exercises 83
Eigenvalues and Eigenvectors 85
The Eigenproblem: Basic Properties 85
Maximum Cycle Mean is the Principal Eigenvalue 88
Principal Eigenspace 90
Finite Eigenvectors 96
Finding All Eigenvalues 100
Finding All Eigenvectors 109
Commuting Matrices Have a Common Eigenvector 111
Exercises 112
Maxpolynomials. The Characteristic Maxpolynomial 116
Maxpolynomials and Their Factorization 118
Maxpolynomial Equations 124
Characteristic Maxpolynomial 125
Definition and Basic Properties 125
The Greatest Corner Is the Principal Eigenvalue 127
Finding All Essential Terms of a Characteristic Maxpolynomial 129
Special Matrices 136
Cayley-Hamilton in Max-algebra 137
Exercises 139
Linear Independence and Rank. The Simple Image Set 140
Strong Linear Independence 140
Strong Regularity of Matrices 143
A Criterion of Strong Regularity 143
The Simple Image Set 148
Strong Regularity in Linearly Ordered Groups 150
Matrices Similar to Strictly Normal Matrices 151
Gondran-Minoux Independence and Regularity 151
An Application to Discrete-event Dynamic Systems 157
Conclusions 159
Exercises 159
Two-sided Max-linear Systems 162
Basic Properties 163
Easily Solvable Special Cases 164
A Classical One 164
Idempotent Matrices 165
Commuting Matrices 165
Essentially One-sided Systems 166
Systems with Separated Variables-The Alternating Method 169
General Two-sided Systems 175
The Square Case: An Application of Symmetrized Semirings 177
Solution Set is Finitely Generated 182
Exercises 189
Reachability of Eigenspaces 192
Visualization of Spectral Properties by Matrix Scaling 194
Principal Eigenspaces of Matrix Powers 199
Periodic Behavior of Matrices 201
Spectral Projector and the Cyclicity Theorem 201
Cyclic Classes and Ultimate Behavior of Matrix Powers 206
Solving Reachability 209
Describing Attraction Spaces 215
The Core Matrix 216
Circulant Properties 217
Max-linear Systems Describing Attraction Spaces 219
Robustness of Matrices 225
Introduction 225
Robust Irreducible Matrices 226
Robust Reducible Matrices 228
M-robustness 233
Exercises 236
Generalized Eigenproblem 239
Basic Properties of the Generalized Eigenproblem 240
Easily Solvable Special Cases 242
Essentially the Eigenproblem 242
When A and B Have a Common Eigenvector 242
When One of A,B Is a Right-multiple of the Other 243
Narrowing the Search for Generalized Eigenvalues 245
Regularization 245
A Necessary Condition for Generalized Eigenvalues 246
Finding maper|C( lambda)| 247
Narrowing the Search 248
Examples 250
Exercises 253
Max-linear Programs 254
Programs with One-sided Constraints 254
Programs with Two-sided Constraints 256
Problem Formulation and Basic Properties 256
Bounds and Attainment of Optimal Values 258
The Algorithms 262
The Integer Case 264
An Example 266
Exercises 268
Conclusions and Open Problems 269
References 271
Index 278