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®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,$,®),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.

Inhalt

1 Motivation.- 1-1 Introduction.- 1-2 Miscellaneous Examples.- 1-2.1 Schedule Algebra.- 1-2.2 Shortest Path Problems.- 1-2.3 The Conjugate.- 1-2.4 Activity Networks.- 1-2.5 The Assignment Problem.- 1-2.6 The Dual Transportation Problem.- 1-2.7 Boolean Matrices.- 1-2.8 The Stochastic Case.- 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 Compatible Trisections.- 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.