5

While looking at something related to game theory, I came across this problem.

Given an antisymmetric matrix $\mathbf A$, show that there is a vector $\mathbf t \ne \mathbf 0$ with only nonnegative entries such that $\mathbf{At}$ has only nonpositive entries.

I've managed to prove some things about $\mathbf t$. In particular, for all $i$, at most one of $t_i$ and $[At]_i$ can be nonzero. However, I can't seem to prove that $\mathbf t$ necessarily exists. Any tips on how I might prove this? Or, for that matter, is there a counterexample?

eyeballfrog
  • 22,485

1 Answers1

1

Your conjecture is true. Here is a proof by contradiction. Let $P$ be the positive cone $\mathbb R_{\ge0}^n$. Suppose the contrary that $Av\not\le0$ for every $v\in P\setminus0$. Then $AP$ and $-P\setminus0$ are two disjoint nonempty convex sets. Therefore, by separating hyperplane theorem, there exists a nonzero vector $v$ such that:

  1. $\langle v,x\rangle\ge0$ for every $x\in AP$,
  2. $\langle v,y\rangle\le0$ for every $y\in-P\setminus0$.

Now (1) implies that $v^TA=(v^TAe_1,\ldots,v^TAe_n)\ge0$. Since $A$ is anti-symmetric, we get $Av=-(v^TA)^T \le 0$. However, (2) implies that $v\ge0$. Hence our initial assumption that $Av\not\le0$ for every $v\in P\setminus0$ cannot be true.

user1551
  • 139,064
  • Interesting. When using the separating hyperplane theorem (in the form given in the Wiki article), how do we know we can take $c = 0$? – eyeballfrog Jun 16 '17 at 19:00
  • @eyeballfrog That's because both $-P$ (as the closure of $-P\setminus0$) and $AP$ contain the origin. – user1551 Jun 16 '17 at 19:02
  • Makes sense. I will say that proofs of the form "Assume the statement is false. This implies the statement is true. Therefore the statement is true" bother me. I realize that $(\neg p\rightarrow p) \equiv p$ but it always seems like there should be a direct way. – eyeballfrog Jun 16 '17 at 19:44