I said we would make two assumptions.
(i) The rows of $A$ are linearly independent and thus it has rank m. (If some rows are linearly dependent then a constraint can be removed without changing the feasible set).
(ii) Every set of $m$ columns of $A$ are linearly independent. (If some columns are linearly dependent then one of the corresponding variables can be removed.)
Thanks to a student query, I have thought more about this. What are we trying to achieve with these assumptions? Suppose $x$ is a BFS with support of size $m$, but the columns of this support are linearly dependent, so $Ay=0$ where $S(y)\subseteq S(x)$. Then by considering $x'=x+\epsilon y $ and increasing $\epsilon$ away from $0$ (in either the positive or negative direction) until some component of $x'$ becomes $0$, we see that it is possible to find a new feasible solution $x'$ such that $S(x') < m $. This is known as a "degenerate solution", i.e. there is a solution to the $m$ constraints $Ax=b$ in which strictly less than $m$ components of $x$ are nonzero. In the simplex tableau this would evidence itself by there being a $0$ in the rightmost column of the tableau. This is more than we can expect in general. Perturbing $A$ slightly, this should not happen. For the purposes of giving an algebraic explanation of the simplex algorithm we want $A_B$ to be non-singular. Degeneracy can also occur in dual solutions. This would be evidenced by a $0$ occurring in the bottom row of the tableau, in the column of a non-basic variable. It would be better to restate our assumptions as follows (and I will amend the notes.)
Degeneracy is not really a problem in practice, but it is with degeneracy that cycling can occur. In the example in lectures the pivot column is being chosen as the one with the most negative entry. One way to avoid cycling is to choose amongst pivot columns in a different way: by preferring the candidate whose variable has the smallest index (Bland's rule). You can check with that this pivot column selection rule the tableau considered in lectures does not cycle.
(i) The rows of $A$ are linearly independent and thus it has rank m. (If some rows are linearly dependent then a constraint can be removed without changing the feasible set).
(ii) Every set of $m$ columns of $A$ are linearly independent. (If some columns are linearly dependent then one of the corresponding variables can be removed.)
Thanks to a student query, I have thought more about this. What are we trying to achieve with these assumptions? Suppose $x$ is a BFS with support of size $m$, but the columns of this support are linearly dependent, so $Ay=0$ where $S(y)\subseteq S(x)$. Then by considering $x'=x+\epsilon y $ and increasing $\epsilon$ away from $0$ (in either the positive or negative direction) until some component of $x'$ becomes $0$, we see that it is possible to find a new feasible solution $x'$ such that $S(x') < m $. This is known as a "degenerate solution", i.e. there is a solution to the $m$ constraints $Ax=b$ in which strictly less than $m$ components of $x$ are nonzero. In the simplex tableau this would evidence itself by there being a $0$ in the rightmost column of the tableau. This is more than we can expect in general. Perturbing $A$ slightly, this should not happen. For the purposes of giving an algebraic explanation of the simplex algorithm we want $A_B$ to be non-singular. Degeneracy can also occur in dual solutions. This would be evidenced by a $0$ occurring in the bottom row of the tableau, in the column of a non-basic variable. It would be better to restate our assumptions as follows (and I will amend the notes.)
(i) The rows of $A$ are linearly independent and thus it has rank m.
(ii) Every set of $m$ columns of $A$ are linearly independent.
These assumptions rule out degeneracies of the following types: that we might have $Ax+z=b$ in the primal for some $(x,z)$ having less than $m$ non-zero components, or in the dual we might have
$\lambda^TA-w^T=c^T$ for some $(\lambda,w)$ having less than $n$ non-zero components.
Degeneracy is not really a problem in practice, but it is with degeneracy that cycling can occur. In the example in lectures the pivot column is being chosen as the one with the most negative entry. One way to avoid cycling is to choose amongst pivot columns in a different way: by preferring the candidate whose variable has the smallest index (Bland's rule). You can check with that this pivot column selection rule the tableau considered in lectures does not cycle.
