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$ Commented Apr 28, 2016 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$ Commented Apr 28, 2016 at 20:10
  • 1
    $\begingroup$ Note that $a_{ii} = w_i^2$. $\endgroup$ Commented Apr 28, 2016 at 21:10
  • $\begingroup$ wow! i wonder how i missed that cute trick. that's a really great technique! $\endgroup$ Commented Apr 28, 2016 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$ Commented Apr 28, 2016 at 21:27

2 Answers 2

Reset to default
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$ Commented May 2, 2016 at 7:25
  • $\begingroup$ I used Maple to compute a Groebner basis. $\endgroup$ Commented May 2, 2016 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$ Commented May 2, 2016 at 14:20
  • $\begingroup$ It certainly puts constraints on the kinds of "analytic" solution you could have. $\endgroup$ Commented May 2, 2016 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$ Commented May 4, 2016 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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.