Let x be a feasible solution to the linear system
Ax = c, x ≥ 0 … (23)
where A is an m × n matrix and c ∈ ℜm. Then
c = x1A1 + x2A2 + ... + xnAn
where Ai ∈ ℜm are the columns of A and and xi ≥ 0 for every i. Without loss of generality, assume that the first k components are positive and the rest are zero, that is,
c = x1A1 + x2A2 + ... + xkAk
with k ≤ n and xi > 0 for every a = 1, 2, . . . k.
1. The columns {A1, A2,..., Ak} are vectors in ℜm. If the columns {A1, A2,..., Ak} are linearly independent, then k < m and there exists a basic feasible solution.
2. If the vectors {A1, A2,..., Ak} are linearly dependent,
a. There exists a nonzero solution to the homogeneous system
y1A1 + y2A2 + ... + ykAk = 0
b. For t ∈ ℜ define  = x - ty.  is a solution to the non homogeneous system
Ax = c
c. Let


Then  = x - tx is a feasible solution, that is,  ≥ 0.
d. There exists h such that


 is a feasible solution with one less positive component.
3. If there exists a feasible solution, there exists a basic feasible solution.