2
$\begingroup$

I have $k$ linearly independent vectors in $\mathbb{R}^n$. I want to know if the span of these vectors (i.e. the set of points in $\mathbb{R}^n$ that can be described by linear combinations of these vectors) intersects the portion of $\mathbb{R}^n$ where all the axes are positive (e.g. the first quadrant in $\mathbb{R}^2$, the first octant in $\mathbb{R}^3$, etc.).

Is there a test I can run on my vectors that will answer this question?

$\endgroup$
1
  • 1
    $\begingroup$ Just a sidenote: the general term for quadrant, octant, etc. which applies for any $n$ is "orthant". $\endgroup$
    – Noah Stein
    Mar 1, 2012 at 18:25

2 Answers 2

3
$\begingroup$

In practice, the way to do this (where $n$ and $k$ may be large) is with linear programming software, since this is basically a linear programming feasibility problem: $A x \ge (1,\ldots, 1)^T$ where $A$ is the $n \times k$ matrix whose columns are your vectors.

$\endgroup$
2
$\begingroup$

The magic words are "Farkas' Lemma".

$\endgroup$
1
  • $\begingroup$ The specific form of the question (where the cone is exactly the positive orthant) shows up in option-pricing models. In Ross's textbook, An Elementary Introduction to Mathematical Finance, the exact question is called the Arbitrage Theorem. $\endgroup$ Mar 1, 2012 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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