8
$\begingroup$

Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^n$ such that:

  • The entries of $A$ are $\in \{0, 1\}$.
  • For all pairs of columns $u, v$ of $A$ the entries of $u - v$ are never either all non-negative or all non-positive (i.e. there is a positive entry and a negative entry in $u - v$).
  • $\sum_i x_i = 0$.
  • The entries of $Ax$ are all non-negative with at least one entry being strictly positive.

Edit: It turns out this is not true via a concrete counterexample found by my collaborator. I would list it, but it's rather large.

Improve this question
$\endgroup$
6
  • $\begingroup$ Is the question whether there exist any n,m, such that there is such a matrix? (in contrast to the way Per Alexandersson answered?) $\endgroup$
    – J Fabian Meier
    Commented Oct 23, 2014 at 13:15
  • $\begingroup$ Yes, I did mean whether there exists such an $n$ and $m$. I only said that to stress that $A$ need not be square. I guess it's still worded a bit unclearly. $\endgroup$
    – Daishisan
    Commented Oct 23, 2014 at 13:20
  • $\begingroup$ Have you done any computer searches for small m and n? $\endgroup$
    – Per Alexandersson
    Commented Oct 23, 2014 at 13:26
  • $\begingroup$ Not me personally, but my collaborator tried that. $\endgroup$
    – Daishisan
    Commented Oct 23, 2014 at 21:23
  • 1
    $\begingroup$ I'm also guessing your collaborator found an example rather than a counterexample. How large is it? $\endgroup$
    – Brendan McKay
    Commented Oct 26, 2014 at 5:25

2 Answers 2

Reset to default
1
$\begingroup$

Not if $n$ is too large compared to $m$: For a fixed number of rows, there is only a finite set of possible columns, $2^m$. Thus, if $n > 2^n$, some columns are identical. This contradicts property 2.

Using a finer reasoning about the second constraint, it should be easy to strengthen this observation.

As a related and easier problem: What is the maximal size of a subset of $\{0,1\}$-vectors of length $n$, such that all pairs satisfy property 2?

Improve this answer
$\endgroup$
2
  • $\begingroup$ The $n$ and $m$ were stated to just indicate that $A$ need not be rectangular --- they're numbers given to us. $\endgroup$
    – Daishisan
    Commented Oct 23, 2014 at 13:18
  • $\begingroup$ Ah, ok, that makes more sense then. $\endgroup$
    – Per Alexandersson
    Commented Oct 23, 2014 at 13:25
0
$\begingroup$

Unless I have misunderstood, here is a counterexample. Let $A$ be the $2\times 2$ identity matrix. This has your Pareto property on $x-y$, but if $x=[{a\atop b}]$, then $Ax=x$, and there is no way to have both $a+b=0$ and both $a$ and $b$ non-negative with at least one positive.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I guess my question was worded a bit poorly, but I was wondering if there ever exists such an $A$ and an $x$ pair. I've edited my question to reflect that now. $\endgroup$
    – Daishisan
    Commented Oct 23, 2014 at 2:17

You must log in to answer this question.

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