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?

Improve 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
    Commented Mar 1, 2012 at 18:25

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
$\begingroup$

The magic words are "Farkas' Lemma".

Improve this answer
$\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$
    – Anthony Quas
    Commented Mar 1, 2012 at 0:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .