Conjecture that relates matrix systems with some polynomials of integer coefficients as solution sets

Question

Assume $x$ is a variable belongs to $\mathbb R \setminus \{ 0,-1,+1 \}$ and consider for all $i, j \in \mathbb N$,

$$a(i,j) = \frac{(x^{i+1} + 1)^{j-1} + (x-1)}{x}$$

then for all $n \in \mathbb N$ the solution set of the matrix system $[a(i,j) \mid 1 \leq i \leq n, 1 \leq j \leq (1+n)]$ exists and is unique with respect to $n$ and $x$ and all elements in it are polynomials of integer coefficients. I put this conjecture and it was tried well; and all results were in agreement with the conjecture.

---

Example

For $n=7$, the solution set will be

x^34 + x^33 + x^32 + x^31 + 2*x^30 + 2*x^29 + 3*x^28 + 3*x^27 + 4*x^26 + 4*x^25 + 5*x^24 + 5*x^23 + 6*x^22 + 6*x^21 + 7*x^20 + 6*x^19 + 7*x^18 + 7*x^17 + 6*x^16 + 7*x^15 + 6*x^14 + 6*x^13 + 5*x^12 + 5*x^11 + 4*x^10 + 4*x^9 + 3*x^8 + 3*x^7 + 2*x^6 + 2*x^5 + x^4 + x^3 + x^2 + 1

-x^33 - x^32 - x^31 - 3*x^30 - 3*x^29 - 5*x^28 - 5*x^27 - 9*x^26 - 9*x^25 - 12*x^24 - 13*x^23 - 16*x^22 - 18*x^21 - 21*x^20 - 20*x^19 - 24*x^18 - 25*x^17 - 22*x^16 - 28*x^15 - 24*x^14 - 26*x^13 - 22*x^12 - 23*x^11 - 19*x^10 - 19*x^9 - 16*x^8 - 16*x^7 - 11*x^6 - 11*x^5 - 6*x^4 - 6*x^3 - 6*x^2 - 7

x^30 + x^29 + 2*x^28 + 2*x^27 + 6*x^26 + 6*x^25 + 9*x^24 + 11*x^23 + 14*x^22 + 19*x^21 + 22*x^20 + 24*x^19 + 30*x^18 + 33*x^17 + 30*x^16 + 43*x^15 + 37*x^14 + 44*x^13 + 38*x^12 + 42*x^11 + 36*x^10 + 36*x^9 + 35*x^8 + 35*x^7 + 25*x^6 + 25*x^5 + 15*x^4 + 15*x^3 + 15*x^2 + 21

- x^26 - x^25 - 2*x^24 - 3*x^23 - 4*x^22 - 8*x^21 - 9*x^20 - 12*x^19 - 16*x^18 - 19*x^17 - 18*x^16 - 31*x^15 - 27*x^14 - 36*x^13 - 32*x^12 - 38*x^11 - 34*x^10 - 34*x^9 - 40*x^8 - 40*x^7 - 30*x^6 - 30*x^5 - 20*x^4 - 20*x^3 - 20*x^2 - 35
                                                                                                  
x^21 + x^20 + 2*x^19 + 3*x^18 + 4*x^17 + 4*x^16 + 10*x^15 + 9*x^14 + 14*x^13 + 13*x^12 + 17*x^11 + 16*x^10 + 16*x^9 + 25*x^8 + 25*x^7 + 20*x^6 + 20*x^5 + 15*x^4 + 15*x^3 + 15*x^2 + 35
                                                                                                                                                                              
- x^15 - x^14 - 2*x^13 - 2*x^12 - 3*x^11 - 3*x^10 - 3*x^9 - 8*x^8 - 8*x^7 - 7*x^6 - 7*x^5 - 6*x^4 - 6*x^3 - 6*x^2 - 21
                                                                                                                                                                                                                                         
x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 7

Thank you.

Answer 1

Let me denote $u_i = x^{i+1} + 1$. As I learned from the previous question, under the "matrix system" OP understands the following matrix equation (up to a factor $\frac{1}{x}$): $$My = b,$$ where $$M:=\begin{bmatrix} u_1^0 + x - 1 & u_1^1 + x - 1 & \cdots & u_1^{n-1} + x - 1 \\ \vdots & \vdots & \ddots & \vdots \\ u_n^0 + x - 1 & u_n^1 + x - 1 & \cdots & u_n^{n-1} + x - 1 \end{bmatrix} \quad\text{and}\quad b := \begin{bmatrix} u_1^n + x - 1 \\ \vdots \\ u_n^n + x - 1 \end{bmatrix}. $$

---

First, it is easy to see that it always has a unique solution: $$y = M^{-1} b = AA^{-1}M^{-1} b = A (MA)^{-1} b,$$ where $$A := \begin{bmatrix} \frac{1}{x} & - \frac{x-1}{x} & - \frac{x-1}{x} & \cdots & - \frac{x-1}{x} \\ 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \end{bmatrix}$$ so that $$MA = V = V(u_1,\dots,u_n)$$ is a Vandermonde matrix.

---

Second, let us find the value of $V^{-1}b$.

The Vandermonde matrix inverse $V^{-1}$ has elements $$(V^{-1})_{i,j} = [z^{i-1}]\ \frac{F(z)}{F'(u_j)(z-u_j)},$$ where $$F(z) := (z-u_1)\cdots (z-u_n)$$ and $[z^k]$ is the operator taking the coefficient of $z^k$. Hence, $V^{-1} b$ is composed of the coefficients of $$G(z):=\sum_{j=1}^n \frac{F(z)}{F'(u_j)(z-u_j)} (u_j^n+x-1)=z^n - F(z) + x-1,$$ where the latter equality holds since the right-hand and left-hand sides as polynomials in $z$ both have degree $\leq n-1$ and at $z=u_j$ evaluate to $u_j^n+x-1$ (i.e., they have equal values at $n$ distinct points).

Hence, $$(V^{-1}b)_k = [z^{k-1}]\ G(z) = \begin{cases} (-1)^{n-1} u_1\cdots u_n + x-1, & k=1;\\ (-1)^{n-k} e_{n+1-k}(u_1,\dots,u_n), & k>1; \end{cases}$$ where $e_k()$ are elementary symmetric polynomials.

---

Finally, from $y=A(V^{-1}b)$ we get $$y_1 = (-1)^{n+1} u_1\cdots u_n + x-1 - \frac{x-1}{x}G(1)$$ and $$y_k = (-1)^{n+k} e_{n+1-k}(u_1,\dots,u_n),\quad k>1.$$ Recalling the definition of $u_i$, we conclude that the free term of $G(1) = x -(1-u_1)\cdots(1-u_n)$ as polynomial in $x$ is zero, and thus $\frac{x-1}{x}G(1)$ is a polynomial in $x$ with integer coefficients. Then so are all $y_1,\dots,y_n$.