# Complex version of Farkas' lemma

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

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 ${\cal M}_{n,1}({\mathbb C})$ ) 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$.

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

$$\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.$$

• @Tony : thanks for "fixing the lambda". But how did you do it? The source text looks identical. Apr 10, 2011 at 11:40
• No problem. I think some of the lambdas where lambs before. Apr 10, 2011 at 11:51

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.