Table of Contents
1 Introduction 1
1.1 Notation, Definitions and Basic Properties 1
1.2 Examples 7
1.3 Feasibility and Reachability 9
1.3.1 Multi-machine Interactive Production Process: A Managerial Application 9
1.3.2 MMIPP: Synchronization and Optimization 10
1.3.3 Steady Regime and Its Reachability 11
1.4 About the Ground Set 12
1.5 Digraphs and Matrices 13
1.6 The Key Players 16
1.6.1 Maximum Cycle Mean 17
1.6.2 Transitive Closures 21
1.6.3 Dual Operators and Conjugation 29
1.6.4 The Assignment Problem and Its Variants 30
1.7 Exercises 36
2 Max-algebra: Two Special Features 41
2.1 Bounded Mixed-integer Solution to Dual Inequalities: A Mathematical Application 41
2.1.1 Problem Formulation 41
2.1.2 All Solutions to SDI and All Bounded Solutions 42
2.1.3 Solving BMISDI 43
2.1.4 Solving BMISDI for Integer Matrices 45
2.2 Max-algebra and Combinatorial Optimization 48
2.2.1 Shortest/Longest Distances: Two Connections 48
2.2.2 Maximum Cycle Mean 49
2.2.3 The Job Rotation Problem 49
2.2.4 Other Problems 51
2.3 Exercises 52
3 One-sided Max-linear Systems and Max-algebraic Subspaces 53
3.1 The Combinatorial Method 53
3.2 The Algebraic Method 57
3.3 Subspaces, Generators, Extremals and Bases 59
3.4 Column Space 64
3.5 Unsolvable Systems 67
3.6 Exercises 69
4 Eigenvalues and Eigenvectors 71
4.1 The Eigenproblem: Basic Properties 71
4.2 Maximum Cycle Mean is the Principal Eigenvalue 74
4.3 Principal Eigenspace 76
4.4 Finile Eigenvectors 82
4.5 Finding All Eigenvalues 86
4.6 Finding All Eigenvectors 95
4.7 Commuting Matrices Have a Common Eigenvector 97
4.8 Exercises 98
5 Maxpolynnmials. The Characteristic Maxpolynomial 103
5.1 Maxpolynomials and Their Factorization 105
5.2 Maxpolynomiai Equations 111
5.3 Characteristic Maxpolynomial 112
5.3.1 Definition and Basic Properties 112
5.3.2 The Greatest Corner Is the Principal Eigenvalue 114
5.3.3 Finding All Essential Terms of a Characteristic Maxpolynomial 116
5.3.4 Special Matrices 123
5.3.5 Cayley-Hamilton in Max-algebra 124
5.4 Exercises 126
6 Linear Independence and Rank. The Simple Image Set 127
6.1 Strong Linear Independence 127
6.2 Strong Regularity of Matrices 130
6.2.1 A Criterion of Strong Regularit 130
6.2.2 The Simple Image Set 135
6.2.3 Strong Regularity in Linearly Ordered Groups 137
6.2.4 Matrices Similar to Strictly Normal Matrices 138
6.3 Gondran-Minoux Independence and Regularity 138
6.4 An Application to Discrete-event Dynamic Systems 144
6.5 Conclusions 146
6.6 Exercises 146
7 Two-sided Max-linear Systems 149
7.1 Basic Properties 150
7.2 Easily Solvable Special Cases 151
7.2.1 A Classical One 151
7.2.2 Idempotent Matrices 152
7.2.3 Commuting Matrices 153
7.2.4 Essentially One-sided Systems 153
7.3 Systems with Separated Variables-The Alternating Method 156
7.4 General Two-sided Systems 162
7.5 The Square Case: An Application of Symmetrized Semirings 164
7.6 Solution Set is Finitely Generated 169
7.7 Exercises 176
8 Reachability of Eigenspaces 179
8.1 Visualization of Spectral Properties by Matrix Scaling 181
8.2 Principal Eigenspaces of Matrix Powers 186
8.3 Periodic Behavior of Matrices 188
8.3.1 Spectral Projector and the Cyclicity Theorem 188
8.3.2 Cyclic Classes and Ultimate Behavior of Matrix Powers 193
8.4 Solving Reachability 196
8.5 Describing Attraction Spaces 202
8.5.1 The Core Matrix 203
8.5.2 Circulant Properties 204
8.5.3 Max-linear Systems Describing Attraction Spaces 206
8.6 Robustness of Matrices 212
8.6.1 Introduction 212
8.6.2 Robust Irreducible Matrices 213
8.6.3 Robust Reducible Matrices 215
8.6.4 M-robustness 220
8.7 Exercises 223
9 Generalized Eigenproblem 227
9.1 Basic Properties of the Generalized Eigenproblem 228
9.2 Easily Solvable Special Cases 230
9.2.1 Essentially the Eigenproblem 230
9.2.2 When A and B Have a Common Eigenvector 230
9.2.3 When One of A, B Is a Right-multiple of the Other 231
9.3 Narrowing the Search for Generalized Eigenvalues 233
9.3.1 Regularization 233
9.3.2 A Necessary Condition for Generalized Eigenvalues 234
9.3.3 Finding maper|C(λ) 235
9.3.4 Narrowing the Search 236
9.3.5 Examples 238
9.4 Exercises 241
10 Max-linear Programs 243
10.1 Programs with One-sided Constraints 243
10.2 Programs with Two-sided Constraints 245
10.2.1 Problem Formulation and Basic Properties 245
10.2.2 Bounds and Attainment of Optimal Values 247
10.2.3 The Algorithms 251
10.2.4 The Integer Case 253
10.2.5 An Example 255
10.3 Exercises 257
11 Conclusions and Open Problems 259
References 261
Index 269
