Complex version of Farkas' lemma - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T13:01:56Z http://mathoverflow.net/feeds/question/61199 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61199/complex-version-of-farkas-lemma Complex version of Farkas' lemma Ewan Delanoy 2011-04-10T09:32:22Z 2011-04-10T12:01:34Z <p>It is well known result of linear optimization theory that, if a finite set $S$ of linear inequalities in real variables $x_1,x_2, \ldots ,x_n$ implies a linear inequality $i$ in $x_1,x_2, \ldots ,x_n$, then $i$ can be written as a positive linear combination of the inequalities in $S$.</p> <p>I wonder if an analogous property holds for moduluses of complex variables : let $A=(a_{ij}) (1 \leq i \leq p, 1 \leq j \leq n)$ be a matrix in ${\cal M}_{p,n}({\mathbb C})$ and $B=(b_1,b_2, \ldots b_p)^{T}$ be a column matrix in ${\cal M}_{p,1}({\mathbb R}^{+})$. Then we may denote by $|AZ| \leq B$ (where $Z=(z_1,z_2, \ldots z_n)^{T}$ is a column matrix in <code>${\cal M}_{n,1}({\mathbb C})$</code> ) the finite set of modulus constraints $\big| \sum_{j=1}^{n}a_{ij}z_j \big| \leq b_i$ for $1\leq i\leq p$. Suppose this set of constraints implies another modulus constraint (*), say $\big| \sum_{j=1}^{n}c_{j}z_j \big| \leq d$, with $c_j \in {\mathbb C}$ and $d \geq 0$.</p> <p>The question, then, is : can (*) be deduced linearly from $S$ ? In other words, are there scalars ${\lambda}_1, {\lambda}_2, \ldots ,{\lambda}_p$ in $\mathbb C$ with</p> <p>$$\sum_{i=1}^{p}\lambda_ia_{ij}=c_j \ ({\rm for} \ 1 \leq j \leq n), \ \ \sum_{i=1}^{p}|\lambda_i|b_i \leq d.$$</p> http://mathoverflow.net/questions/61199/complex-version-of-farkas-lemma/61201#61201 Answer by Fedor Petrov for Complex version of Farkas' lemma Fedor Petrov 2011-04-10T11:01:33Z 2011-04-10T11:01:33Z <p>I think, yes. Without loss of generality, all $b_i$'s and $d$ are equal to 1. Assume that the vector $c=(c_1,\dots,c_n)$ does not lie in a convex hull of vectors $(wa_{i,1},\dots,wa_{i,n})$ for all $i=1,\dots,n$ and all $|w|=1$. Then there is a linear real functional, which separates $c$ from this convex hull. It may be written as $F(c)= \Re(u_1c_1+\dots+u_nc_n)$. But if we maximize $F(wa)$ for fixed vector $a$ and various $w$ on the unit circle, we see that the maximum equals $|u_1a_1+\dots +u_na_n|$. So, this hypothetic separation is exactly the contrary to our assumption.</p>