I working on the following exercise:
Suppose I have a linear program of the form
$$ \begin{matrix} \max c^T x \\ Ax \le b \end{matrix}$$
Whereas $Ax \le b$ doesn't contain any redundant constraints, the polyhedron it specifies is bounded and the dimension of the polyhedron is maximal for the ambient space.
Then suppose we look at each individual $A_i^T x \le b_i $ in this polyhedra, then the constraint $A_j$ such that $ c^T \cdot \frac{A_j}{||A_j||}$ is maximal over all $c^T \cdot \frac{A_i}{||A_i||}$, is TIGHT for the optimal solution to the linear programming problem.
My work:
This can be restated as:
The constraint $A_j$ such that $ \frac{c^T}{||c^T||} \cdot \frac{A_j}{||A_j||}$ is maximal over all $\frac{c^T}{||c^T||} \cdot \frac{A_i}{||A_i||}$, is TIGHT for the optimal solution to the linear programming problem.
From here by inspection if $\frac{A_i}{||A_i||} = \frac{c^T}{||c^T||}$ then this is maximal (namely 1) and its obvious that the optimal solution to $\max c^T$ will be tight for the constraints $c^Tx \le k$ if the latter constraint isn't redundant. So it's sort of intuitive why this must be true.
So now a fixed idea of attack:
Suppose there exists a point $p$ on the polyhedra that this constraint is not tight for. Then we need to show there exists another point for which this constraint is tight, that has higher (or equal) objective value.
The challenge here is that if I simply say consider a point $q$ where the constraint it is tight, I can only reason that
$$ q = p + X$$
where $X$ is non-zero in the signed direction normal to the constraint
thus $$c^Tq = c^Tp + c^TX$$
But is $c^TX \ge 0$? I'm not sure how to show this.