What is the relationship between basic vectors in Linear Algebra (Vector spaces) and basic variables in the Simplex method for linear programming?

Question

I suppose that basic vectors in Linear Algebra spanning a vector space and basic variables in the Simplex method (Variables that have a non zero value, where the basis represents a corner of the Simplex determined by the constraints) have to be somehow related, but I fail to see why and how...

Answer 1

I assume you mean basis vectors/variables. Here is one way of thinking about the connection:

In the normal form of the linear optimization problem, when you look at the system of equations given as constraints $Ax = b$ and you write the matrix-vector multiplication into the scheme vector-entry x matrix-column: $$x_1 \cdot a_1 + x_2 \cdot a_2 + ... + x_n \cdot a_n = b$$ (where $a_i$ is column $i$ of matrix $A$) then the basis variables of the linear program are multiplied with the basis vectors, which span the column space of A. To satisfy the system of equations we always need to have as many matrix columns in the basis as there are entries in the vecotr b. Otherwise we are able to describe b (where b is not zero). In the algorithm we kick variables from the basis (we set them to zero) and therefore must pick another variable to complete the basis (in reality this is done in reverse in the algorithm) again such that b may b represented or in other words a solution of Ax where a certain $_i$ has been set to zero. Following this line of thought the connection can be described as the basic variables are those variables wich pick a basis from the column vectors of A in which to describe b. This is possible, because in such problems there are more variables than necessesary to describe the right hand side of the equation $Ax = b$.