Minimax Algebra: (166 Lecture Notes in Economics and Mathematical Systems)

A number of different problems of interest to the operational researcher and the mathematical economist - for example, certain problems of optimization on graphs and networks, of machine-scheduling, of convex analysis and of approx- imation theory - can be formulated in a convenient way using the algebraic structure (R, $, @) where we may think of R as the (extended) real-number system with the binary combining operations x$y, x(R)y defined to be max(x, y), (x+y) respectively. The use of this algebraic structure gives these problems the character of problems of linear algebra, or linear operator theory. This fact hB.s been independently discovered by a number of people working in various fields and in different notations, and the starting-point for the present Lecture Notes was the writer's persuasion that the time had arrived to present a unified account of the algebra of linear transformations of spaces of n-tuples over (R, $, (R)), to demonstrate its relevance to operational research and to give solutions to the standard linear-algebraic problems which arise - e.g. the solution of linear equations exactly or approximately, the eigenvector- eigenvalue problem andso on.Some of this material contains results of hitherto unpublished research carried out by the writer during the years 1970-1977.

Table of Contents:
1 Motivation.- 1–1 Introduction.- 1–2 Miscellaneous Examples.- 1–3 Conclusion: Our Present Aim.- 2 The Initial Axioms.- 2–1 Some Logical Geography.- 2–2 Commutative Bands.- 2–3 Isotone Functions.- 2–4 Belts.- 2–5 Belt Homomorphisms.- 2–6 Types of Belt.- 2–7 Dual Addition.- 2–8 Duality for Belts.- 2–9 Some Specific Cases.- 3 Opening and Closing.- 3–1 The Operations ??,???,??,???.- 3–2 The Principle of Closing.- 3–3 The Principle of Opening.- 4 The Principal Interpretation.- 4–1 Blogs.- 4–2 The Principal Interpretation.- 4–3 The 3-element Blog ?.- 4–4 Further Properties of Blogs.- 5 The Spaces En and ?mn.- 5–1 Band-Spaces.- 5–2 Two-Sided Spaces.- 5–3 Function Spaces.- 5–4 Matrix Algebra.- 5–5 The Identity Matrix.- 5–6 Matrix Transformations.- 5–7 Further Notions.- 6 Duality for Matrices.- 6–1 The Dual Operations.- 6–2 Some Matrix Inequalities.- 7 Conjugacy.- 7–1 Conjugacy for Belts.- 7–2 Conjugacy for Matrices.- 7–3 Two Examples.- 8 AA* Relations.- 8–1 Pre-residuation.- 8–2 Alternating AA* Products.- 8–3 Modified AA* Products.- 8–4 Some Bijections.- 8–5 A Worked Example.- 9 Some Schedule Algebra.- 9–1 Feasibility and Compatibility.- 9–2 The Float.- 9–3 A Worked Example.- 10 Residuation and Representation.- 10–1 Some Residuation Theory.- 10–2 Residuomorphisms.- 10–3 Representation Theorems.- 10–4 Representation for Matrices.- 10–5 Analogy with Hilbert Space.- 11 Trisections.- 11–1 The Demands of Reality.- 11–2 Trisections.- 11–3 Convex Subgroups.- 11–4 The Linear Case.- 11–5 Two Examples.- 12 ? ø — Astic Matrices.- 12–1 ?ø — Asticity.- 12–2 The Generalised Question 2.- 13 / — Existence.- 13–1 / — Existence Defined.- 13–2 CompatibleTrisections.- 13–3 Dually ? ø — astic Matrices.- 13–4 / — Defined Residuomorphisms.- 13–5 Omn As Operators.- 13–6 Some Questions Answered.- 14 The Equation A ? x = b Over a Bldg.- 14–1 Some Preliminaries.- 14–2 The Principal Solution.- 14–3 The Boolean Case.- 15 Linear Equations over a Linear Bldg.- 15–1 All Solutions of (14–3).- 15–2 Proving the Procedure.- 15–3 Existence and Uniqueness.- 15–4 A Linear Programming Criterion.- 15–5 Left-Right Variants.- 16 Linear Dependence.- 16–1 Linear Dependence Over El.- 16–2 The A Test.- 16–3 Some Dimensional Anomalies.- 16–4 Strong Linear Independence.- 17 Rank of Matrices.- 17–1 Regular Matrices.- 17–2 Matrix Rank Over A Linear Blog.- 17–3 Existence of Rank.- 18 Seminorms on En.- 18–1 Column-Spaces.- 18–2 Seminorms.- 18–3 Spaces of Bounded Seminorm.- 19 Some Matrix Spaces.- 19–1 Matrix Seminorms.- 19–2 Matrix Spaces.- 19–3 The Role of Conjugacy.- 20 The Zero-Lateness Problem.- 20–1 The Principal Solution.- 20–2 Case of Equality.- 20–3 Critical Paths.- 21 Projections.- 21–1 Congruence Classes.- 21–2 Operations in Rang A.- 21–3 Projection Matrices.- 22 Definite and Metric Matrices.- 22–1 Some Graph Theory.- 22–2 Definite Matrices.- 22–3 Metric Matrices.- 22–4 The Shortest Distance Matrix.- 23 Fundamental Eigenvectors.- 23–1 The Eigenproblem.- 23–2 Blocked Matrices.- 23–3 ø-Astic Definite Matrices.- 24 Aspects of the Eigenproblem.- 24–1 The Eigenspace.- 24–2 Directly Similar Matrices.- 24–3 Structure of the Eigenspace.- 25 Solving the Eigenproblem.- 25–1 The Parameter ?(A).- 25–2 Properties of ?(A).- 25–3 Necessary and Sufficient Conditions.- 25–4 The Computational Task.- 25–5 An Extended Example.- 26 Spectral Inequalities.-26–1 Preliminary Inequalities.- 26–2 Spectral Inequality.- 26–3 The Other Eigenproblems.- 26–4 More Spectral Inequalities.- 26–5 The Principal Interpretation.- 27 The Orbit.- 27–1 Increasing Matrices.- 27–2 The Orbit.- 27–3 The Orbital Matrix.- 27–4 A Practical Case.- 27–5 More General Situations.- 27–6 Permanents.- 28 Standard Matrices.- 28–1 Direct Similarity.- 28–2 Invertible Matrices.- 28–3 Equivalence of Matrices.- 28–4 Equivalence and Rank.- 28–5 Rank of ?.- 29 References and Notations.- 29–1 Previous Publications.- 29–2 Related References.- 29–3 List of Notations.- 29–4 List of Definitions.