Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have $a^\intercal M b > 0$, where $\forall a_i > 0$, $\forall b_j > 0$, and M is known. I'd like to find a tight linear constraint on $b$ which is independent of $a$ (other than the positivity constraint on $a$). That is, I'd like to find a vector $v$ such that $v^\intercal b > 0$. (It's possible, of course, that such a vector may not exist for some $M$.)

Example: For the matrix $\left[\begin{matrix}9 & -2 \\ 8 & -2\end{matrix}\right]$, $v^\intercal = [4,-1]$ is a solution, because $[4,-1] b > 0$ implies $a^\intercal M b > 0$ for all positive $a$.

This feels like it should be reducible to a constrained linear optimization problem, but for the life of me I cannot figure out how. I'm not even sure how to typify $v$ as "tight"; for the example above, $v^\intercal = [5,-1]$ is also a solution but one which is weaker than $v^\intercal = [4,-1]$. For that matter, I wonder if there are multiple tight constraints when the size of $b$ grows beyond 2.

Incidentally, I'm not sweating $> 0$ versus $\geq 0$. Whichever makes the problem easier.

share|cite|improve this question
up vote 0 down vote accepted

Hmmm.... I'm not 100% certain of this, but it looks like $v^\intercal$ may just be composed of the minimum element from each column of $M$. As for "tight", that seems to mean "can't subtract a nonnegative vector from $v$ without violating the constraint". And there I was gearing up with the LCP...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.