# Showing system has unique solution

I want to show that the system:$$\begin{cases}y_1=x_n+x_1+x_2+x_3\\y_2=x_1+x_2+x_3+x_4\\y_3=x_2+x_3+x_4+x_5\\ \vdots \\ y_{n-1}=x_{n-2}+x_{n-1}+x_n+x_1 \\ y_n=x_{n-1}+x_n+x_1+x_2 \end{cases}$$ has a unique solution for even $$n$$. For odd $$n$$ I was able to show that the determinant was non-zero which means that it has a unique solution, but for even $$n$$ it is equal to zero. How can I show this? Appreciate help

Edit: I note that it holds that $$y_1+y_5+y_9+\dots+y_{n-3}=y_2+y_6+y_{10}+\dots+y_{n-2}=y_5+y_7+y_{11}+\dots+y_{n-1}=y_4+y_8+y_{12}+\dots +y_n$$

If this can be used?

• If the determinant you’re getting is zero, why do you think there will be a unique solution? – cmk Jun 7 at 16:25
• Test small values before generalising - what happens for $n=4$? – Mark Bennet Jun 7 at 16:27
• Look up "circulant matrix" on the web. – user1551 Jun 7 at 16:46
• Your system will have a unique solution for a given $n$ if an only if the polynomials $x^n - 1$ and $1 + x + x^2 + x^{n-1}$ are relatively prime over $\Bbb C$ – Omnomnomnom Jun 7 at 20:41
• If $n$ is even, then $x_k=(-1)^k$ solves the homogeneous system, i.e. the system in which $y_k=0\forall k\in\{1,\ldots,n\}.$ So there can't be a unique solution. For each solution $(x_k)$, $(x_k+(-1)^k c)$ is also a solution. – Reinhard Meier Jun 8 at 13:01

Using the properties of circulant matrices, it can be shown that the solution space of the homogeneous system $$(y_k=0\;\forall k\in\{1,\ldots,n\})$$ is one-dimensional if $$n\equiv 2\pmod 4$$ and three-dimensional if $$n\equiv 0\pmod 4.$$
Note: You have to find the indices $$j,\;0\leq j which satify $$x^3 + x^2 + x + 1 =0 \;\;\text{with}\;\;x=e^{2\pi ij/n}$$ This is $$j=\frac{n}{2}$$ if $$n\equiv 2\pmod 4$$ and $$j\in\left\{\frac{1n}{4},\frac{2n}{4},\frac{3n}{4}\right\}$$ if $$n\equiv 0\pmod 4.$$
We can easily find vectors that span the solution space. If $$n\equiv 2\pmod 4$$, then $$w=(1, -1, 1, -1, \ldots , 1,-1)^T$$ does the job. If $$n\equiv 0\pmod 4$$, then we can use $$v_1 = (1,-1,0,0,1,-1,0,0,\ldots , 1,-1,0,0)^T \\ v_2 = (0,1,-1,0,0,1,-1,0,\ldots , 0,1,-1,0)^T \\ v_3 = (0,0,1,-1,0,0,1,-1,\ldots , 0,0,1,-1)^T$$ Those vectors can also be used to check if the system of linear equations is solvable. You must get $$\sum_k w_ky_k = 0$$ if $$n\equiv 2\pmod 4$$ and $$\sum_k (v_1)_ky_k=\sum_k (v_2)_ky_k=\sum_k (v_3)_ky_k=0$$ if $$n\equiv 0\pmod 4.$$ This last condition is exactly what you have already discovered yourself.
If $$n\equiv 2\pmod 4$$, then check $$\sum_k w_ky_k = 0.$$ If this is true, remove the last equation (it is redundant) and set $$x_n=0$$ (or any other value you like). Find the other $$x_k$$ by solving the remaining system of linear equations ($$n-1$$ equations and $$n-1$$ unknowns.) You get a particular solution $$x_0,$$ and the general solution is $$x=x_0+\lambda w,\;\lambda\in\mathbb{R}$$ If $$n\equiv 0\pmod 4$$, then check $$\sum_k (v_1)_ky_k=\sum_k (v_2)_ky_k=\sum_k (v_3)_ky_k=0.$$ If this is true, remove the last three equations (they are redundant) and set $$x_{n-2}=x_{n-1}=x_n=0$$ (or any other values you like). Find the other $$x_k$$ by solving the remaining system of linear equations ($$n-3$$ equations and $$n-3$$ unknowns.) You get a particular solution $$x_0,$$ and the general solution is $$x=x_0+\lambda_1 v_1+\lambda_2 v_2+\lambda_3 v_3,\;\lambda_1,\lambda_2,\lambda_3\in\mathbb{R}$$