Representing the space of linear programs as the Grassmann manifold

Abstract

Each linear program (LP) has an optimal basis. The space of linear programs can be partitioned according to these bases, so called the basis partition. Discovering the structures of this partition is our goal. We represent the space of linear programs as the space of projection matrices, i.e., the Grassmann manifold. A dynamical system on the Grassmann manifold, first presented in Sonnevend et al. (Math Program 52:527-553), is used to characterize the basis partition as follows: From each projection matrix associated with an LP, the dynamical system defines a path and the path leads to an equilibrium projection matrix returning the optimal basis of the LP. We will present some basic properties of equilibrium points of the dynamical system and explicitly describe all eigenvalues and eigenvectors of the linearized dynamical system at equilibrium points. These properties will be used to determine the stability of equilibrium points and to investigate the basis partition. This paper is only a beginning of the research towards our goal. © 2008 Springer-Verlag.