# Sufficient Conditions for a Bounded Feasible Region in the Linear Programming Problem

I am working on a problem where it would be nice to prove that the feasible region of a LP problem is bounded, but where it is not necessary to solve any particular problem.

In particular, given an NxN matrix $A$ and a non-negative vector $\vec{b}\in\mathbb{R}^N$, I would like to find a set of sufficient conditions to guarentee that the set of non-negative vectors $\vec{x}\in\mathbb{R}^N$ such that $A\vec{x}\leq\vec{b}$ is bounded.

Having no experience with linear programming, I am not sure where to even start and have been getting unnecessarily bogged down with details on the simplex algorithm - which aren't needed right now because I don't need a particular solution. Any references to literature focusing on this aspect of the LP problem would be very much appreciated!

Just in case anyone has a better idea of how to approach the problem I'm currently working, I'm trying to, given a N-dimensional quadratic form $Q:\mathbb{R}^N\rightarrow\mathbb{R}$, find a set of conditions guarenteeing that the set of non-negative vectors $\vec{x}\in\mathbb{R}^N$ such that the partial derivative of $Q$ in each direction is non-negative is bounded. This naturally turned into something like a LP problem, so I thought this would be the direction to head.

-

If $b \ge 0$, the feasible region is nonempty (because $0$ is feasible); the feasible region is unbounded iff the linear programming problem

P: maximize $e^T x$ subject to $A x \le b$, $x \ge 0$

is unbounded (where $e$ is the vector of all 1's), and this is true iff the dual problem

D: minimize $b^T y$ subject to $A^T y \ge e$, $y \ge 0$

is infeasible. This in turn is equivalent to: there is no linear combination of the rows of $A$ with all coefficients $\ge 0$ and all entries $> 0$.

-
I'm confused by your last sentence. Did you mean, that you take linear combinations of rows in the augmented matrix $[A|\vec{e}]$ and want the coefficients in the left-most N columns to be non-negative and those in the far-right column to be positive? If that is the case, does it follow that a sufficient condition (though weak one) would be that there is a non-negative vector $\vec{x}\in\mathbb{R}$ such that $A\vec{x}=\vec{e}$? – Chris M May 10 '11 at 5:47
Ideally, I am hoping for a statement concerning the eigenvalues or determinant of $A$ because I feel like this would tie in nicely with the known information of the quadratic form that I am working with. I have a hunch that if $A$ has a positive eigenvalue with an associated strictly positive eigenvector, then the feasible region is bounded, but I haven't had time to thoroughly think this through. – Chris M May 10 '11 at 7:00
I mean (if $A$ is $m \times n$) there do not exist $y_1, \ldots, y_m \ge 0$ such that $\sum_{i=1}^m A_{ij} y_i > 0$ for all $j = 1 \ldots n$. – Robert Israel May 10 '11 at 17:02
As for your hunch, it's almost right, except that you want an eigenvector of $A^T$ (or a left eigenvector of $A$) rather than an eigenvector of $A$. That is, if there exist $\lambda > 0$ and a vector $y > 0$ such that $A^T y = \lambda y$, in particular you have $A^T y > 0$, so my criterion says the feasible region is bounded. – Robert Israel May 10 '11 at 17:07
Thank you so much! I've actually been working with symmetric matrices so far, so I guess that's why I didn't think too hard about if it should be eigenvectors of $A$ or $A^T$. – Chris M May 10 '11 at 18:53