Butkovic Max-linear Systems: Theory and Algorithms

1. Auflage 2010
ISBN: 978-1-84996-299-5
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 274 Seiten

Recent years have seen a significant rise of interest in max-linear theory and techniques. Specialised international conferences and seminars or special sessions devoted to max-algebra have been organised. This book aims to provide a first detailed and self-contained account of linear-algebraic aspects of max-algebra for general (that is both irreducible and reducible) matrices.

Among the main features of the book is the presentation of the fundamental max-algebraic theory (Chapters 1-4), often scattered in research articles, reports and theses, in one place in a comprehensive and unified form. This presentation is made with all proofs and in full generality (that is for both irreducible and reducible matrices). Another feature is the presence of advanced material (Chapters 5-10), most of which has not appeared in a book before and in many cases has not been published at all.

Intended for a wide-ranging readership, this book will be useful for anyone with basic mathematical knowledge (including undergraduate students) who wish to learn fundamental max-algebraic ideas and techniques. It will also be useful for researchers working in tropical geometry or idempotent analysis.

Autoren/Hrsg.

Butkovic, Peter

Inhaltsverzeichnis

1;Preface;6
2;Contents;9
3;List of Symbols;13
4;Introduction;16
4.1;Notation, Definitions and Basic Properties;16
4.2;Examples;22
4.3;Feasibility and Reachability;24
4.3.1;Multi-machine Interactive Production Process: A Managerial Application;24
4.3.2;MMIPP: Synchronization and Optimization;25
4.3.3;Steady Regime and Its Reachability;26
4.4;About the Ground Set;27
4.5;Digraphs and Matrices;28
4.6;The Key Players;31
4.6.1;Maximum Cycle Mean;32
4.6.2;Transitive Closures;36
4.6.2.1;Transitive Closures, Eigenvectors and Subeigenvectors;36
4.6.2.2;Weak Transitive Closure;37
4.6.2.3;Strong Transitive Closure (Kleene Star);38
4.6.2.4;Two properties of subeigenvectors;41
4.6.2.5;Computation of Transitive Closures;42
4.6.3;Dual Operators and Conjugation;44
4.6.4;The Assignment Problem and Its Variants;45
4.7;Exercises;51
5;Max-algebra: Two Special Features;55
5.1;Bounded Mixed-integer Solution to Dual Inequalities: A Mathematical Application;55
5.1.1;Problem Formulation;55
5.1.2;All Solutions to SDI and All Bounded Solutions;56
5.1.3;Solving BMISDI;57
5.1.4;Solving BMISDI for Integer Matrices;59
5.2;Max-algebra and Combinatorial Optimization;62
5.2.1;Shortest/Longest Distances: Two Connections;62
5.2.2;Maximum Cycle Mean;63
5.2.3;The Job Rotation Problem;63
5.2.4;Other Problems;65
5.3;Exercises;66
6;One-sided Max-linear Systems and Max-algebraic Subspaces;67
6.1;The Combinatorial Method;67
6.2;The Algebraic Method;71
6.3;Subspaces, Generators, Extremals and Bases;73
6.4;Column Spaces;78
6.5;Unsolvable Systems;81
6.6;Exercises;83
7;Eigenvalues and Eigenvectors;85
7.1;The Eigenproblem: Basic Properties;85
7.2;Maximum Cycle Mean is the Principal Eigenvalue;88
7.3;Principal Eigenspace;90
7.4;Finite Eigenvectors;96
7.5;Finding All Eigenvalues;100
7.6;Finding All Eigenvectors;109
7.7;Commuting Matrices Have a Common Eigenvector;111
7.8;Exercises;112
8;Maxpolynomials. The Characteristic Maxpolynomial;116
8.1;Maxpolynomials and Their Factorization;118
8.2;Maxpolynomial Equations;124
8.3;Characteristic Maxpolynomial;125
8.3.1;Definition and Basic Properties;125
8.3.2;The Greatest Corner Is the Principal Eigenvalue;127
8.3.3;Finding All Essential Terms of a Characteristic Maxpolynomial;129
8.3.4;Special Matrices;136
8.3.5; Cayley-Hamilton in Max-algebra;137
8.4;Exercises;139
9;Linear Independence and Rank. The Simple Image Set;140
9.1;Strong Linear Independence;140
9.2;Strong Regularity of Matrices;143
9.2.1;A Criterion of Strong Regularity;143
9.2.2;The Simple Image Set;148
9.2.3;Strong Regularity in Linearly Ordered Groups;150
9.2.4;Matrices Similar to Strictly Normal Matrices;151
9.3;Gondran-Minoux Independence and Regularity;151
9.4;An Application to Discrete-event Dynamic Systems;157
9.5;Conclusions;159
9.6;Exercises;159
10;Two-sided Max-linear Systems;162
10.1;Basic Properties;163
10.2;Easily Solvable Special Cases;164
10.2.1;A Classical One;164
10.2.2;Idempotent Matrices;165
10.2.3;Commuting Matrices;165
10.2.4;Essentially One-sided Systems;166
10.3;Systems with Separated Variables-The Alternating Method;169
10.4;General Two-sided Systems;175
10.5;The Square Case: An Application of Symmetrized Semirings;177
10.6;Solution Set is Finitely Generated;182
10.7;Exercises;189
11;Reachability of Eigenspaces;192
11.1;Visualization of Spectral Properties by Matrix Scaling;194
11.2;Principal Eigenspaces of Matrix Powers;199
11.3;Periodic Behavior of Matrices;201
11.3.1;Spectral Projector and the Cyclicity Theorem;201
11.3.2;Cyclic Classes and Ultimate Behavior of Matrix Powers;206
11.4;Solving Reachability;209
11.5;Describing Attraction Spaces;215
11.5.1;The Core Matrix;216
11.5.2;Circulant Properties;217
11.5.3;Max-linear Systems Describing Attraction Spaces;219
11.6;Robustness of Matrices;225
11.6.1;Introduction;225
11.6.2;Robust Irreducible Matrices;226
11.6.3;Robust Reducible Matrices;228
11.6.4;M-robustness;233
11.7;Exercises;236
12;Generalized Eigenproblem;239
12.1;Basic Properties of the Generalized Eigenproblem;240
12.2;Easily Solvable Special Cases;242
12.2.1;Essentially the Eigenproblem;242
12.2.2;When A and B Have a Common Eigenvector;242
12.2.3;When One of A,B Is a Right-multiple of the Other;243
12.3;Narrowing the Search for Generalized Eigenvalues;245
12.3.1;Regularization;245
12.3.2;A Necessary Condition for Generalized Eigenvalues;246
12.3.3;Finding maper|C( lambda)|;247
12.3.4;Narrowing the Search;248
12.3.5;Examples;250
12.4;Exercises;253
13;Max-linear Programs;254
13.1;Programs with One-sided Constraints;254
13.2;Programs with Two-sided Constraints;256
13.2.1;Problem Formulation and Basic Properties;256
13.2.2;Bounds and Attainment of Optimal Values;258
13.2.3;The Algorithms;262
13.2.4;The Integer Case;264
13.2.5;An Example;266
13.3;Exercises;268
14;Conclusions and Open Problems;269
15;References;271
16;Index;278