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

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 '14 at 13:18
  • $\begingroup$ Ah, ok, that makes more sense then. $\endgroup$ – Per Alexandersson Oct 23 '14 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 '14 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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