Return to Question

Suppose there are 2n vectors $\{m_1,m_2,...,m_n\}$ and $\{\mu_1,\mu_2,...,\mu_n\}$. All vectors are in k-dimensional Euclid space $R^k$. The vectors satisfy: $$m_i \mu_j \leq 0, \quad \forall i\neq j $$ and $$ m_i \mu_i > 0, \quad \forall i.$$

What I want to prove: $n \leq 2k$.

Intuitively I think the bound $n \leq 2k$ is correct. It can be achieved by setting $m_i$ and $\mu_i$ to be the canonical base vectors and their negatives.

Suppose there are 2n vectors $\{m_1,m_2,...,m_n\}$ and $\{\mu_1,\mu_2,...,\mu_n\}$. All vectors are in k-dimensional Euclid space $R^k$. The vectors satisfy: $$m_i \mu_j \leq 0, \quad \forall i\neq j $$ and $$ m_i \mu_i > 0, \quad \forall i.$$

What I want to prove: $n \leq 2k$.

Intuitively I think the bound $n \leq 2k$ is correct. It can be achieved by setting $m_i$ and $\mu_i$ to be the canonical base vectors and their negatives.

As Saul points out, the upper bound actually does not exist in this simplified problem. I post my Orginal Problem in a new post.

Suppose there are 2n vectors $\{m_1,m_2,...,m_n\}$ and $\{\mu_1,\mu_2,...,\mu_n\}$. All vectors are in k-dimensional Euclid space $R^k$. The vectors satisfy: $$m_i \mu_j \leq 0, \quad \forall i\neq j $$ and $$ m_i \mu_i > 0, \quad \forall i.$$

What I want to prove: $n \leq 2k$.

Intuitively I think the bound $n \leq 2k$ is correct. It can be achieved by setting $m_i$ and $\mu_i$ to be the canonical base vectors and their negatives.

Edit: So the conjecture is wrong, as Saul RM pointed out, the number is unbounded. I derive this problem from a more cumbersome problem. Maybe it's worth asking directly the original one:

There exists (2n+1) vectors in $R^{k+1}$ $\{m_1,m_2,...,m_n\}$, $\{p_1,p_2,...,p_n\}$ and $p^*$.

$m_i$ are all weakly positive, $p_i$ and $p^*$ are probability vectors (namely they are weakly positive, and their coordinates sum to 1).

The vectors satisfy $$m_i p_j \geq m_i p^* = 1, \quad \forall i\neq j $$ and $$ m_i p_i = 0, \quad \forall i.$$

The question is what is the maximum number of $n$?

This number $n$ is at least bounded by $2^{k+1}-2$, which corresponds to non-trivial faces of the probability simplex. My feeling is that it might be much smaller. (For example, it is easy to show that the support of $m_i$ cannot be a subset of the support of $m_j$.

Suppose there are 2n vectors $\{m_1,m_2,...,m_n\}$ and $\{\mu_1,\mu_2,...,\mu_n\}$. All vectors are in k-dimensional Euclid space $R^k$. The vectors satisfy: $$m_i \mu_j \leq 0, \quad \forall i\neq j $$ and $$ m_i \mu_i > 0, \quad \forall i.$$

What I want to prove: $n \leq 2k$.

Intuitively I think the bound $n \leq 2k$ is correct. It can be achieved by setting $m_i$ and $\mu_i$ to be the canonical base vectors and their negatives.

Suppose there are 2n vectors $\{m_1,m_2,...,m_n\}$ and $\{\mu_1,\mu_2,...,\mu_n\}$. All vectors are in k-dimensional Euclid space $R^k$. The vectors satisfy: $$m_i \mu_j \leq 0, \quad \forall i\neq j $$ and $$ m_i \mu_i > 0, \quad \forall i.$$

What I want to prove: $n \leq 2k$.

Intuitively I think the bound $n \leq 2k$ is correct. It can be achieved by setting $m_i$ and $\mu_i$ to be the canonical base vectors and their negatives.

Edit: So the conjecture is wrong, as Saul RM pointed out, the number is unbounded. I derive this problem from a more cumbersome problem. Maybe it's worth asking directly the original one:

There exists (2n+1) vectors in $R^{k+1}$ $\{m_1,m_2,...,m_n\}$, $\{p_1,p_2,...,p_n\}$ and $p^*$.

$m_i$ are all weakly positive, $p_i$ and $p^*$ are probability vectors (namely they are weakly positive, and their coordinates sum to 1).

The vectors satisfy $$m_i (p_j-p^*) \geq 0, \quad \forall i\neq j $$ and $$ m_i p_i = 0, \quad \forall i.$$

The question is what is the maximum number of $n$? This number $n$ is at least bounded by $2^{k+1}-2$ (which corresponds to non-trivial faces of the probability simplex), but my feeling is that it might be much smaller.

Suppose there are 2n vectors $\{m_1,m_2,...,m_n\}$ and $\{\mu_1,\mu_2,...,\mu_n\}$. All vectors are in k-dimensional Euclid space $R^k$. The vectors satisfy: $$m_i \mu_j \leq 0, \quad \forall i\neq j $$ and $$ m_i \mu_i > 0, \quad \forall i.$$

What I want to prove: $n \leq 2k$.

Intuitively I think the bound $n \leq 2k$ is correct. It can be achieved by setting $m_i$ and $\mu_i$ to be the canonical base vectors and their negatives.

Edit: So the conjecture is wrong, as Saul RM pointed out, the number is unbounded. I derive this problem from a more cumbersome problem. Maybe it's worth asking directly the original one:

There exists (2n+1) vectors in $R^{k+1}$ $\{m_1,m_2,...,m_n\}$, $\{p_1,p_2,...,p_n\}$ and $p^*$.

$m_i$ are all weakly positive, $p_i$ and $p^*$ are probability vectors (namely they are weakly positive, and their coordinates sum to 1).

The vectors satisfy $$m_i p_j \geq m_i p^* = 1, \quad \forall i\neq j $$ and $$ m_i p_i = 0, \quad \forall i.$$

The question is what is the maximum number of $n$? 

This number $n$ is at least bounded by $2^{k+1}-2$, which corresponds to non-trivial faces of the probability simplex. My feeling is that it might be much smaller. (For example, it is easy to show that the support of $m_i$ cannot be a subset of the support of $m_j$.