Skip to main content
MathOverflow

Return to Question

incorporated the OP’s clarification that m and n are also part of the things to find; fixed typo pointed out by Brendan McKay in a comment
Source Link
edit approved Oct 26, 2014 at 16:01
Tsuyoshi Ito
edit approved Oct 26, 2014 at 16:01
Tsuyoshi Ito
  • 2k
  • 16
  • 18

Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^m$$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.

Does there exist an $m \times n$ matrix $A$ and a vector $x \in \mathbb{R}^m$ 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.

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.

added 135 characters in body
Source Link
Daishisan
Daishisan
  • 388
  • 1
  • 9

Does there exist an $m \times n$ matrix $A$ and a vector $x \in \mathbb{R}^m$ 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.

Does there exist an $m \times n$ matrix $A$ and a vector $x \in \mathbb{R}^m$ 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.

Does there exist an $m \times n$ matrix $A$ and a vector $x \in \mathbb{R}^m$ 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.

Reworded question for less ambiguity.
Source Link
Daishisan
Daishisan
  • 388
  • 1
  • 9

Suppose we have aDoes there exist an (not necessarily square)$m \times n$ matrix $A$ whose entries are $\in \{0, 1\}$, and for all pairs of columns $x, y$ the entries of $x - y$ are never either all non-negative or all non-positive (i.e. there is a positive entry and a negative entry in $x - y$). Then is it possible that there exists a vector $x$$x \in \mathbb{R}^m$ such that $\sum_i x_i = 0$ and the entries of $Ax$ are all non-negative with at least one entry being strictly positive?:

  • 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.

Suppose we have a (not necessarily square) matrix $A$ whose entries are $\in \{0, 1\}$, and for all pairs of columns $x, y$ the entries of $x - y$ are never either all non-negative or all non-positive (i.e. there is a positive entry and a negative entry in $x - y$). Then is it possible that there exists a vector $x$ such that $\sum_i x_i = 0$ and the entries of $Ax$ are all non-negative with at least one entry being strictly positive?

Does there exist an $m \times n$ matrix $A$ and a vector $x \in \mathbb{R}^m$ 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.
My question was incorrectly worded before regarding the entries of $x - y$.
Source Link
Daishisan
Daishisan
  • 388
  • 1
  • 9
Source Link
Daishisan
Daishisan
  • 388
  • 1
  • 9