Note on Degeneracy

Given a linear program in standard form, Min cx s.t. Ax b, x or 0, where A is an m x n matrix with rational coefficients, one technique used to resolve degeneracy in the simplex algorithm is the lexicographic rule. This rule adjoins to b a non-singular m x m square matrix M. the appended columns of M are updated along with b on each iteration. When the ratio test for determining the pivot row results in a tie, the ratio test is applied to the corresponding elements of the updated columns of M in turn, from left to right, until the tie is resolved. In this note we prove that it is only necessary instead, to adjoin to b a single column d whose ith component is d sub i pi sub i, or preferably the fractional part of pi sub i in order that d sub i 1. Any transcendental number can be used instead of pi 3.14.... The proof exploits the fundamental property of a transcendental number namely, it can never be a root of a polynomial equation Alpha sub 1 x alpha sub 2 squared .... alpha sub p sub x to the p power 0 when alpha sub 1, alpha sub 2,...., alpha sub p are rational and not all zero.