# Solving multilinear equations

Let $$N=\{1,2,\ldots,n\}$$. Suppose we are given $$n$$ equations, with each equation taking the form $$\sum_{A\subseteq N}\left(c_A \prod_{i\in A}x_i \right) = 0$$, where each $$c_A$$ is a real number constant. (So each equation contains at most $$2^n$$ terms.) An example for $$n=3$$ is:

$$2x_1x_2x_3 - 4x_1x_2+5x_3+2=0$$

$$7x_1x_3 - 6x_2-4=0$$

$$-x_1x_2x_3 + x_1 - 2x_2 +9 = 0$$

We want to find a solution $$(x_i)_{i\in A}$$ such that $$0\leq x_i\leq 1$$ for all $$i$$ (assuming we know such a solution exists).

Is there an algorithm that solves this in time bounded in $$n$$?

• This is as hard as solving general polynomial equations. – Emil Jeřábek May 28 at 11:49
• When you say "solve", are you asking for a numerical solution, or what? – Zach Teitler May 28 at 16:15
• @ZachTeitler Can we possibly solve this exactly (like we can do for linear equations), or is there some reason why this is impossible? – Alexi May 28 at 16:27
• @Alexi Exactly, no. With the trick in Vladimir Dotsenko's answer you can easily write a degree-5 polynomial equation in this form, by adding extra variables for $x^2, x^3, x^4$. Evil Abel foils our plans again. – Federico Poloni May 28 at 16:50
• In numerical practice, I would use something like Newton's method or homotopy continuation. – Federico Poloni May 28 at 16:51

Multilinear equations are hardly easier than general equations. For instance, the multilinear equations $$\begin{cases} x_0-x_1=0,\\ x_0x_1-x_2=0,\\ x_0x_2-x_3=0,\\ \ldots\\ x_0x_{n-1}-x_n=0 \end{cases}$$ simply tell you that $$x_k=x_0^k$$ for all $$k=1,\ldots,n$$. Using this, it is very easy to replace any system of polynomial equations by a system of multilinear ones, so I assume that the most standard method (Gröbner bases) would be the main tool to use.