non-zero variables are indexed by B, that is, for all . Properties 1. A BFS is determined only by the constraints of the LP (the matrix and the vector ); it does not depend on the optimization objective. 2. By definition, a BFS has at most m non-zero variables and at least n-m zero variables. A BFS can have less than m non-zero variables; in that case, it can have many different bases, all of which contain the indices of its non-zero variables. 3. A feasible solution is basic if-and-only-if the columns of the matrix are linearly independent, where K is the set of indices of the non-zero elements of . 4. Each basis determines a unique BFS: for each basis B of m indices, there is at most one BFS with basis B. This is because must satisfy the constraint , and by definition of basis the matrix is non-singular, so the constraint has a unique solution: The opposite is not true: each BFS can come from many different bases. If the unique solution of satisfies the non-negativity constraints , then B is called a feasible basis. 5. If a linear program has an optimal solution (i.e., it has a feasible solution, and the set of feasible solutions is bounded), then it has an optimal BFS. This is a consequence of the Bauer maximum principle: the objective of a linear program is convex; the set of feasible solutions is convex (it is an intersection of hyperspaces); therefore the objective attains its maximum in an extreme point of the set of feasible solutions. Since the number of BFS-s is finite and bounded by , an optimal solution to any LP can be found in finite time by just evaluating the objective function in all BFS-s. This is not the most efficient way to solve an LP; the simplex algorithm examines the BFS-s in a much more efficient way. Examples Consider a linear program with the following constraints: The matrix A is: Here, m=2 and there are 10 subsets of 2 indices, however, not all of them are bases: the set {3,5} is not a basis since columns 3 and 5 are linearly dependent. The set B={2,4} is a basis, since the matrix is non-singular. The unique BFS corresponding to this basis is . Geometric interpretation The set of all feasible solutions is an intersection of hyperspaces. Therefore, it is a