# Closed-Form solution for system of simple nonlinear equations

I am interested in analytical solutions for a system of nonlinear equations.

Motivation: The source of the question is a very convinient method to create random matrices with special properties. Mathematica can give me solutions up to certain sizes of the linear system, but I would like to have it for arbitrary size N. I can also use numerical algorithms (which I am doing at the moment), but for N in the order of $N\approx10.000$, they are quite slow.

System of nonlinear equations:

$$(w_i \cdot \sum_{j=1}^N w_j) - w_i^2 = d_i$$ for $i=1...N$, and $w$ and $d$ are vectors with $N$ dimensions, and $w_i$ and $d_i$ is the $i$-th component of the vector. Both $d_i$ and $w_i \in \mathbb{R_+}$. I am providing the vector $d$ (i.e. N real non-negative numbers), and want to solve for $w_i$. Is there a way to solve this system analytically for arbitrary N?

Edit: For clarification, if N=3 we have the following system of equations:

$$w_1 \cdot (w_2 + w_3) = d_1 \\ w_2 \cdot (w_1 + w_3) = d_2 \\ w_3 \cdot (w_1 + w_2) = d_3$$

with $w_i, d_i \in \mathbb{R}$. For a given vector $d=(d_1,d_2,d_3)$, I want to get $w=(w_1,w_2,w_3)$.

Edit2: I think I see a way how it could be solved, but I'm not certain:

Let's set $c=\sum_{j=1}^N w_j$, which is the sum of all weights. What we have now:

$$c \cdot w_i - w_i^2 = d_i \\ w_i^2 - c \cdot w_i + d_i = 0$$ which has two solutions:

$$w_{i_{1,2}} = \frac{c}{2} \pm \sqrt{ \left(\frac{c}{2}\right)^2 - d_i}$$ and the normalisation constant $c$ can be calculated by the sum of all weights:

$$\sum_{j=1}^N w_j = \sum_{j=1}^N \left(\frac{c}{2} \pm \sqrt{ \left(\frac{c}{2}\right)^2 - d_j} \right) = c$$

Is this correct? Do you know an analytical solution for c?

• Put $a_{ij}=w_iw_j$ then the $a_{ij}$ satisfy a set of linear equations which can be solved. – Paul Apr 28 '16 at 20:05
• Thank you, that is correct. But how can one go from $a_{ij}$ to the actual $w_i$? Is it simpler than the original problem? I can not see how one could do it at the moment. Thanks! – Mario Krenn Apr 28 '16 at 20:10
• Note that $a_{ii} = w_i^2$. – user26977 Apr 28 '16 at 21:10
• wow! i wonder how i missed that cute trick. that's a really great technique! – Mario Krenn Apr 28 '16 at 21:13
• But actually, $a_{ii}$ is never mentioned in the equation system, so i only get values for $a_{i,j}$, right? It feels like i'm missing some simple final step. – Mario Krenn Apr 28 '16 at 21:27

$n=3$ is rather easy: $w_i$ satisfies a quadratic polynomial.

For $n=4$, each $w_i$ satisfies a rather nasty polynomial of degree $8$ (but involving only even powers). Thus there is a solution in terms of radicals, but it won't be pleasant.

For $n=5$, it seems each $w_i$ satisfies a polynomial of degree $22$. A solution in radicals is not to be expected. Thus with $d_1 = -7, d_2 = 3, d_3 = 9, d_4 = 7, d_5 = 8$, $w_5$ satisfies $$81\,{w_{{5}}}^{22}+7074\,{w_{{5}}}^{20}+198792\,{w_{{5}}}^{18}+2887764 \,{w_{{5}}}^{16}+23487600\,{w_{{5}}}^{14}+99587008\,{w_{{5}}}^{12}+ 69082752\,{w_{{5}}}^{10}-1402988992\,{w_{{5}}}^{8}-6995300352\,{w_{{5} }}^{6}-14191984640\,{w_{{5}}}^{4}-13095665664\,{w_{{5}}}^{2}- 4492099584 = 0$$

EDIT: This is an irreducible polynomial of degree $11$ in $x = w_5^2$. Maple doesn't do Galois groups of polynomials of degree $11$, but GAP does, and confirms that its Galois group is $S_{11}$. In particular, there is no solution in radicals.

• Thank you Robert, very interesting. Could you please mention how you get to the 8 and 22 degree polynomial equation for $w_i$, I can not see it unfortunatly. It seems my Edit2 already nearly has a solution within a quadratic polynomial equation - could you maybe point out why it is actually much more complicated? Thanks a lot! – Mario Krenn May 2 '16 at 7:25
• I used Maple to compute a Groebner basis. – Robert Israel May 2 '16 at 7:26
• Thank you! I'm surprised that this scales in such a bad way. 2, 8, 22 (oeis.org/search?q=2%2C8%2C22). Do you think this is a no-go for an analytic solution, or could there be a different method to attack that problem? – Mario Krenn May 2 '16 at 14:20
• It certainly puts constraints on the kinds of "analytic" solution you could have. – Robert Israel May 2 '16 at 17:00
• I find your answer wonderful (and the result unfortunate of course :) ). I wonder what how to interpret it? Does it mean that one can not find a solution using your approach, or does it say more such as "very likely there is no analytical solution with known methods, as it would solve high-order polynomials - which is known to be very difficult"? I'm asking as I want to know whether it would make sense to transfer the question to MO. I would be interested in your opinion, thank you! – Mario Krenn May 4 '16 at 23:07

For $$c^2\gt 4d_j$$

$$\sqrt{c^2-4d_j}=c\sqrt{1-\frac{4d_j}{c^2}}\approx c\left(1-\frac{2d_j}{c^2}\right)=c-\frac{2d_j}c,$$ with a relatively good approximation.

Summing,

$$\sum_{j=1}^N\left(c\pm\left(c-\frac{2d_j}c\right)\right)=2c.$$

With $M$ positive signs,

$$Mc-\frac{d}c=c,\\c=\pm\sqrt{-\frac{d}{M-1}},$$

where $d=\sum_{j=1}^N\pm d_j$.

This might give you reasonable approximations to start Newton's iterations or maybe just fixed-point.