Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
Just a sidenote: the general term for quadrant, octant, etc. which applies for any $n$ is "orthant". –  Noah Stein Mar 1 '12 at 18:25
add comment

2 Answers

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.

share|improve this answer
add comment

The magic words are "Farkas' Lemma".

share|improve this answer
    
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. –  Anthony Quas Mar 1 '12 at 0:10
add comment

Your Answer

 
discard

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.