I'm reading Schrijver's Theory of Linear and Integer Programming, and I have a problem understanding cycling happens in the simplex method. The simplex is described as below:
Solving $\max\{cx\mid x \geq 0; Ax \leq b\}$ At each stage a set $C_k$ is maintained, which consists of $n$ linearly independent equalities from $Ax = b$, such that $x_k$ the current vertex is determined by $C_kx_k = b_C$.
$u$ is the unique vector $u_kA = c$ where $u$ is zero in the components corresponding to equalities outside $C_k$. if $u \geq 0$ then $x_k$ is optimal. Otherwise we choose an index $i^*$ where $u_{i^*} <0$, $y$ is the unique vector such that $C_ky$ is zero in all components except $i^*$. Then $\lambda$ is defined as $\min\{\frac {b_t - (Ax_k)_t}{(Ay)_t}, (Ay)_t > 0\}$, where $t^*$ is the index acquiring the minimum. Now $x_{k+1}$ is calculated from $x_k + \lambda y$ and $C_{k+1} = C_k + t^* \setminus i^* $. Also notice $cy = uAy = -u_{i^*} > 0$ so $cx_{k+1} > cx_k$.
So the book explains when choosing $i^*$ and $t^*$ and there are several options, there are different methods for breaking ties, some of which may cause cycling that is the algorithm wouldn't terminate. Here is what I don't understand: given there are finitely many vertices and $cx_{k+1} > cx_k$ how is it possible to visit the same vertex twice hence encountering cycling??
Later, when the average time of Simplex method is being analyzed due to Borgwardt, the book explains cycling can happen only if the LP problem is degenerate. And provides a condition for being non-degenerate there is no set of $n$ linearly dependent rows in the matrix $\begin{bmatrix}c\\A\end{bmatrix}$ and there is no set of $n+1$ linearly dependent rows in $\begin{bmatrix}A &b\end{bmatrix}$. can you please explain why is this?
