A Saddlepoint Theorem for Self-Dual Linear Systems
Abstract
A finite class of skew coefficient matrices over an ordered field can be associated with a self-dual linear system. Pivot techniques enable one to transform a given matrix of the class into another while maintaining the same sets of solutions. The exchange of two independent variables in the system for two corresponding dependent ones maintains skewsymmetry. The main theorem says that in a finite number of pivot steps one can transform any skew matrix into a skew matrix with a saddlepoint - that is, a non-negative row and corresponding nonpositive column. A tableau form introduced by A. W. Tucker permits an immediate translation of this result about matrices into a statement about types of solutions that must occur in the associated self-dual linear system. This theorem and its corollaries yield an elementary proof of the Minimax Theorem for symmetric games.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1973
- Accession Number
- AD0764564
Entities
People
- Marjorie L. Stein
Organizations
- University of Wisconsin–Madison