3
$\begingroup$

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?

$\endgroup$
12
  • 1
    $\begingroup$ Put $a_{ij}=w_iw_j$ then the $a_{ij}$ satisfy a set of linear equations which can be solved. $\endgroup$ – Paul Apr 28 '16 at 20:05
  • $\begingroup$ 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! $\endgroup$ – Mario Krenn Apr 28 '16 at 20:10
  • 1
    $\begingroup$ Note that $a_{ii} = w_i^2$. $\endgroup$ – user26977 Apr 28 '16 at 21:10
  • $\begingroup$ wow! i wonder how i missed that cute trick. that's a really great technique! $\endgroup$ – Mario Krenn Apr 28 '16 at 21:13
  • $\begingroup$ 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. $\endgroup$ – Mario Krenn Apr 28 '16 at 21:27
3
+50
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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! $\endgroup$ – Mario Krenn May 2 '16 at 7:25
  • $\begingroup$ I used Maple to compute a Groebner basis. $\endgroup$ – Robert Israel May 2 '16 at 7:26
  • $\begingroup$ 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? $\endgroup$ – Mario Krenn May 2 '16 at 14:20
  • $\begingroup$ It certainly puts constraints on the kinds of "analytic" solution you could have. $\endgroup$ – Robert Israel May 2 '16 at 17:00
  • $\begingroup$ 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! $\endgroup$ – Mario Krenn May 4 '16 at 23:07
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.