# Are sums of 0-1 Pareto efficient vectors Pareto efficient?

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.

• Is the question whether there exist any n,m, such that there is such a matrix? (in contrast to the way Per Alexandersson answered?) – J. Fabian Meier Oct 23 '14 at 13:15
• 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. – Daishisan Oct 23 '14 at 13:20
• Have you done any computer searches for small m and n? – Per Alexandersson Oct 23 '14 at 13:26
• Not me personally, but my collaborator tried that. – Daishisan Oct 23 '14 at 21:23
• I'm also guessing your collaborator found an example rather than a counterexample. How large is it? – Brendan McKay Oct 26 '14 at 5:25

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.
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?
• The $n$ and $m$ were stated to just indicate that $A$ need not be rectangular --- they're numbers given to us. – Daishisan Oct 23 '14 at 13:18
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.
• 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. – Daishisan Oct 23 '14 at 2:17