How to solve simple bilinear equations under extra linear constraints - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T17:20:37Z http://mathoverflow.net/feeds/question/84213 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84213/how-to-solve-simple-bilinear-equations-under-extra-linear-constraints How to solve simple bilinear equations under extra linear constraints Woland 2011-12-24T07:25:28Z 2011-12-24T08:04:52Z <p>Hello,</p> <p>This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy:</p> <p>$\lambda_i^T u_{ij} = 0$ for all $i,j$</p> <p>$\sum_{i=1}^n u_{ij} = u_j$ for all $j$</p> <p>$\sum_{j=1}^m (e p_j^T - e^T p_j I)u_{ij} \geq 0$ for all $i$</p> <p>$\lambda_i \geq 0$ for all $i$</p> <p>$e^T \lambda_i = 1$ for all $i$</p> <p>The variables are $\lambda_i$ and $u_{ij}$, the constants are $p_j$ and $u_j$, and $e$ is the vector of all ones. If the dimension of the $\lambda_i,u_{ij}$ is $k$, then the numbers of variables $m,n$ are related by $m=(n-1)^k$.</p> <p>Is solving this underdetermined bilinear system NP-hard or can one find a solution? Bilinear systems are NP-hard in general, but all proofs I have seen involve manipulating the matrix $A$ in $x^TAy$. I don't understand how extra linear constraints affect the complexity of the bilinear equations.</p> <p>Thank you in advance!</p>