4
$\begingroup$

I am interested in solving the following system of $n$ equations:

$$x_j^2 = \sum_{i=1}^n B_{ij} x_i $$

for all $j\in\{1,\dots,n\}$, where $n$ is a positive integer and all the $0\leq B_{ij}\leq 1$ are known constants. The system has a trivial solution at $x=0$. Taking the square root of the equation, we can use the contraction mapping theorem Theorem 3 in this note to find that there is a unique real non-trivial positive solution. I'm hoping that this solution can be expressed in a simple way but I haven't been able to do so.

$\endgroup$
2
  • $\begingroup$ Well to start you can set $\tilde B_{ij} := A_j^{1/\alpha} B_{ij}$, hence ignore $A$ $\endgroup$ Commented May 12, 2016 at 12:40
  • $\begingroup$ @SteveHuntsman: That's right, thanks. I have simplified the question. $\endgroup$ Commented May 12, 2016 at 13:02

1 Answer 1

8
$\begingroup$

Sorry, there cannot be a simple solution. For example, taking $n=3$ and $B_{ij} = (i+j-1)/6$, we compute numerically (by iterating the contraction mapping as you suggest) $$ (x_1,x_2,x_3) = (1.26922421\ldots, 1.54095434\ldots, 1.77148256\ldots) $$ and then (using algdep in gp) that these satisfy irreducible sextic equations, respectively $$ 3888 x^6 - 2592 x^5 - 3888 x^4 + 936 x^3 + 210 x^2 + 90 x + 7 = 0, $$ $$ 3888 x^6 - 7776 x^5 + 1080 x^4 + 2592 x^3 - 129 x^2 + 162 x - 10 = 0, $$ $$ 3888 x^6 - 12960 x^5 + 12960 x^4 - 4176 x^3 + 678 x^2 - 342 x + 1 = 0 $$ with maximal Galois group $S_6$, and thus not solvable in radicals because the group $S_6$ is not solvable.

Added later: some further notes . . .

1) The calculation reported above is not quite a complete proof: to finish it, we can choose one of the variables, say $x_1$, which we guessed is a zero of the polynomial $P$, then write the others as polynomials in that variable (whose coefficients we can surmise in gp using lindep), and verify that the equations $x_j^2 = \sum_j B_{ij} x_i$ all hold modulo $P$. Here we find $$ x_2 = \frac1{9013} (81648 X^5 - 19764 X^4 - 101628 X^3 - 4182 X^2 + 7570 X + 1170), $$ $$ x_3 = \frac1{9013} (-54432 X^5 + 13176 X^4 + 67752 X^3 + 20814 X^2 - 8051 X - 780). $$

2) The formulas for our example become somewhat simpler when written as polynomials satisfied by $6x_i$ (to counteract the denominators of $6$ in $B_{ij} = (i+j-1)/6$); for instance $6x_1$ is a root of $x^6 - 4 x^5 - 36 x^4 + 52 x^3 + 70 x^2 + 180 x + 84 = 0$.

3) Usually one expects that an $n$-variable system of quadratic equations should yield solutions satisfying equations of degree $2^n-1$ (subtracting $1$ for the trivial solution at the origin), so $7$ for $n=3$; we got $6$ because our $B_{ij}$ form a degeenrate matrix, making the origin a solution of multiplicity $2$.

4) The contraction mapping argument is not actually correct: extracting square roots yields an expansion mapping for small $x_i$. The existence of a positive solution can nevertheless be proved using the fixed-point theorem on the $(n-1)$-simplex $\Delta = \{ x_i \geq 0, \sum_i x_i = 1 \}$: the composite of the linear transformation $B$, the coordinatewise square root, and the scaling $(x_i) \mapsto (x_i) / \sum_i x_i$ gives a continuous map $\Delta \to \Delta$; any fixed point has all coordinates $x_i$ positive, and can be scaled to a solution $c(x_i)$ of the original system. Uniqueness might still hold (it does for $n=1$ (trivially) and $n=2$, and I've not been able to find a counterexample for $n=3$ either), but would have to be proved some other way.

$\endgroup$
1
  • $\begingroup$ Thank you, this is very helpful. Regarding 4), I think Theorem 3 in this note can be used to show uniqueness. It relies, in particular, on Tarski's fixed point theorem and the concavity of the square root function. $\endgroup$ Commented Sep 10, 2016 at 21:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .