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.

  • $\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$ 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
    Oct 23, 2014 at 13:20
  • $\begingroup$ Have you done any computer searches for small m and n? $\endgroup$ Oct 23, 2014 at 13:26
  • $\begingroup$ Not me personally, but my collaborator tried that. $\endgroup$
    – Daishisan
    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$ Oct 26, 2014 at 5:25

2 Answers 2


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?

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

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.

  • $\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
    Oct 23, 2014 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.