# Exact solution of a particular system of non-linear equations (re-formulated to matrix equation)

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.

• @PietroMajer: The indexation is alright. $x_0=1$, as mentioned in the second line. – firestorm Feb 11 '17 at 20:19
• (sorry I missed it at the first reading) – 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.

• 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? – firestorm Feb 11 '17 at 21:06
• 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. – Max Alekseyev Feb 11 '17 at 21:20
• Why had this been deleted? (Just cast the final vote to undelete). – Stefan Kohl Sep 7 '18 at 9:40
• @StefanKohl: OP was deleted, and so was my answer. Thanks for the undelete vote. – Max Alekseyev Sep 7 '18 at 13:16
• Related question: mathoverflow.net/q/262054 – Max Alekseyev Sep 7 '18 at 14:26