7
$\begingroup$

Let $A \in \mathbb{R}^{n \times n}$, with elements $a_{ij}$

What conditions on $A$ are required for the following to be true?

There exists some vector $x \in \mathbb{R}^n_+$, $x \neq 0$ such that for all $i=1\dots n$,

$$\sum_{j=1}^n x_j(a_{ij} - a_{ji}) \geq 0$$

Obviously if $A$ is symmetric this is true. I believe it may be true for all $A$ but I haven't been able to prove it.

(sorry really wasn't sure what to title this post)

I've tried the usual Farkas' Lemma-style trick but the problem is self-dual

$\endgroup$

2 Answers 2

7
$\begingroup$

Lawrence and Spingarn, On fixed points of non-expansive piecewise isometric mappings, Proc. London Math. Soc. (3) 55 (1987), no. 3, 605–624, MR0907234 (89d:58063), "obtain a constructive and simple new proof of Tucker's Theorem which states that for any antisymmetric real $n\times n$ matrix $A$, there exists $x\ge0$ such that $Ax\ge0$ and $x+Ax\gt0$." They also write, "This theorem is equivalent to the Farkas Lemma and the linear programming duality theorem in the sense that each may be easily derived from the other."

$\endgroup$
2
  • $\begingroup$ Interesting, thank you! Might you have any idea how the "easy" derivation from Farkas' lemma is done? I can't see it immediately $\endgroup$
    – Steven
    Oct 9, 2013 at 2:34
  • $\begingroup$ Sorry, I don't even know what Farkas' Lemma is. There might be something in the paper, or in the paper by Tucker, Dual systems of homogeneous linear relations, in Kuhn & Tucker, eds., Linear Inequalities and Related Systems, Annals of Math Studies 38 (1956) 3-18. $\endgroup$ Oct 9, 2013 at 2:38
3
$\begingroup$

The original question asks if we can find a nonzero vector $x \ge 0$ such that $(A-A^T)x \ge 0$, of equivalently, for a skew-symmetric (aka antisymmetric) matrix $M$, the claim is that there always exists an $0 \neq x \ge 0$ such that $Mx \ge 0$. Chasing Gerry Myerson's suggestion above, here is a link to a proof of this claim by invoking Farkas' Lemma.

Lemma 4.5 here.

$\endgroup$

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.