I have a question regarding feasibility checking. I need to check whether the system $\{ x: Ax=b , x \geq 0 \}$ has a feasible solution.
- What is the best worst case running time for this decision problem if it is considered as an LP?
- Is it possible to decide the feasibility using Gaussian elimination method or some other methods like this?
Note, however, that the entries of the matrix $A$ can be rational.