In the paper "Some NP-complete problems in linear programming" (https://doi.org/10.1016/0167-6377(82)90006-2), there are several proofs given to show that testing for degeneracy in LPs is NP-complete. I don't understand the proof in section 4. Are they saying that their reduction only produces binary y values? Or are they introducing a binary variable (and thus invalidating their proof)? The statement of "the standard trick..." -- what is this trick? Does it have a name? Is someone able to write out this "combined system (5)" for me? What does it look like?
