I have this system of $n$ non-linear equations in $n$ unknowns, arising out of my research problem. Given that $x_0=1$, I have to solve for $(x_1,x_2,\ldots,x_n).$ $$\sum_{i=0}^n x_i^2+2\sum_{j=1}^n\sum_{i=0}^{n-j}x_ix_{i+j}=1$$ $$\sum_{j=1}^n\sum_{i=0}^{n-j}~j^2~x_ix_{i+j}=0$$ $$\sum_{j=1}^n\sum_{i=0}^{n-j}~j^4~x_ix_{i+j}=0$$ $$\cdots ~\cdots ~\cdots$$ $$\sum_{j=1}^n\sum_{i=0}^{n-j}~j^{2(n-1)}~x_ix_{i+j}=0$$ Is there any way to find EXACT solutions to this system of non-linear equations?

Reformulation of the problem

I have reformulated the problem into a problem involving matrix equations, which is as follows:

Let $~\mathbf{y} = \left(\begin{array}{c} y_1 \\ y_2 \\ \vdots \\ y_n \end{array}\right)= \left(\begin{array}{cc} x_1 & x_2 & \cdots & x_{n-1} & x_n\\ x_2 & x_3 & \cdots & x_n & 0\\ \ldots & \ldots & \ldots & \ldots & \ldots\\ x_n & 0 & \cdots & 0 & 0 \end{array}\right) \left(\begin{array}{c} x_0 \\ x_1 \\ \vdots \\ x_{n-1} \end{array}\right)$, where $x_0=1$ and $x_n \neq 0$.

and $~\mathbf{M} = \left(\begin{array}{cc} 1^2 & 2^2 & \cdots & n^2\\ 1^4 & 2^4 & \cdots & n^4\\ \ldots & \ldots & \ldots & \ldots\\ 1^{2(n-1)} & 2^{2(n-1)} & \cdots & n^{2(n-1)} \end{array}\right)$

The system of equations is given by:

$$2\bigg(\sum_{i=1}^n y_i \bigg) +\bigg( \sum_{i=1}^n x_i^2 \bigg)=0$$ $$\mathbf{M}\mathbf{y}=\mathbf{0}$$

Thus we have a system of $1+(n-1)=n$ equations in $n$ unknowns (namely, $x_1,x_2,\ldots,x_n$). Note that we could have completely dispose of the $y_i$'s and use only $x_i$'s to write the equations, in which case they would look like beasts. Instead we choose to simplify.

The problem, as before, is to find EXACT solution for $(x_1,x_2,\ldots,x_n)$. There are algorithms available for approximate solutions. But for my research, I need only EXACT solution. Any help would be greatly appreciated.

  • 1
    $\begingroup$ @PietroMajer: The indexation is alright. $x_0=1$, as mentioned in the second line. $\endgroup$ – firestorm Feb 11 '17 at 20:19
  • $\begingroup$ (sorry I missed it at the first reading) $\endgroup$ – Pietro Majer Feb 11 '17 at 22:13

Let us first solve the equation $\mathbf{M}\mathbf{y}=\mathbf{0}$. The simplest way to do so is to prepend an extra row $(1,1,\dots,1)$ to $\mathbf{M}$, resulting in a (transposed) Vandermonde matrix $\mathbf{M'}$. Then the equation $\mathbf{M}\mathbf{y}=\mathbf{0}$ corresponds to the equation $$(\star)\qquad\mathbf{M'}\mathbf{y}=(s,0,0,\dots,0)^T,$$ where $s=y_1+\dots+y_n$ is a parameter.

Solution $(\star)$ can be easily obtained by Cramer's rule and the formula for Vandermonde determinant. Namely, let $V(\alpha_1,\dots,\alpha_k)$ be the determinant of the Vandermonde matrix formed by powers of $\alpha_1,\dots,\alpha_k$, then for every $i=1,2,\dots,n$ we have $$y_i = s\cdot(-1)^{i-1}\cdot \left(\frac{n!}{i}\right)^{2(n-1)} \cdot\frac{V(1^2,2^2,\dots,(i-1)^2,(i+1)^2,\dots,n^2)}{V(1^2,2^2,\dots,n^2)}.$$

By the definition of $s$, we also have $\sum_{i=0}^n x_i^2 = 1 -2 \sum_{i=1}^n y_i = 1-2s$.

Now, we need to solve the equation $$(\star\star)\qquad\left(\begin{array}{c} y_1 \\ y_2 \\ \vdots \\ y_n \end{array}\right)= \left(\begin{array}{cc} x_1 & x_2 & \cdots & x_{n-1} & x_n\\ x_2 & x_3 & \cdots & x_n & 0\\ \ldots & \ldots & \ldots & \ldots & \ldots\\ x_n & 0 & \cdots & 0 & 0 \end{array}\right) \left(\begin{array}{c} 1 \\ x_1 \\ \vdots \\ x_{n-1} \end{array}\right)$$ with respect to $x_1,\dots,x_n$.

Let us define the generating function: $$X(t) = 1 + x_1 t + x_2t^2 \dots + x_n t^n.$$ Then the equation $(\star\star)$ is equivalent to the following identity for polynomials in $t$: $$X(t)\cdot X(t^{-1}) = 1-2s + y_{1}(t+t^{-1}) + y_{2}(t^2+t^{-2}) + \dots + y_n(t^n+t^{-n}).$$

The $2n$ (complex) zeros of the r.h.s. here (which can be turned into a polynomial of degree $2n$ by multiplying by $t^n$, or by representing it as a polynomial of degree $n$ in $t+t^{-1}$) come in pairs $\{t_k,t_k^{-1}\}$, $k=1,\dots,n$. Picking one zero from each pair, we can construct a polynomial $X(t)$ of degree $n$ that has these $n$ zeros and obtain solution $x_i$ to $(\star\star)$ as its coefficients. The restriction here is that the coefficient of $t^0$ (equal $(-1)^n$ times the product of the chosen zeros) must be equal to 1.

  • $\begingroup$ I maybe mistaken but the term $s$ in the solution for $(x_1,x_2,\ldots,x_n)$ is not a given constant, but is essentially a function of $x_1,x_2,\ldots,x_n$. Don't we need to substitute it somehow? $\endgroup$ – firestorm Feb 11 '17 at 21:06
  • $\begingroup$ There are likely (infinitely?) many solutions. Different values of $s$ will give different solutions. It is not immediately clear though how to avoid those values that give no solutions. $\endgroup$ – Max Alekseyev Feb 11 '17 at 21:20
  • $\begingroup$ Why had this been deleted? (Just cast the final vote to undelete). $\endgroup$ – Stefan Kohl Sep 7 '18 at 9:40
  • $\begingroup$ @StefanKohl: OP was deleted, and so was my answer. Thanks for the undelete vote. $\endgroup$ – Max Alekseyev Sep 7 '18 at 13:16
  • $\begingroup$ Related question: mathoverflow.net/q/262054 $\endgroup$ – Max Alekseyev Sep 7 '18 at 14:26

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.