0
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ If the determinant you’re getting is zero, why do you think there will be a unique solution? $\endgroup$
    – cmk
    Jun 7, 2019 at 16:25
  • 1
    $\begingroup$ Test small values before generalising - what happens for $n=4$? $\endgroup$ Jun 7, 2019 at 16:27
  • $\begingroup$ Look up "circulant matrix" on the web. $\endgroup$
    – user1551
    Jun 7, 2019 at 16:46
  • $\begingroup$ 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$ $\endgroup$ Jun 7, 2019 at 20:41
  • $\begingroup$ 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. $\endgroup$ Jun 8, 2019 at 13:01

1 Answer 1

1
$\begingroup$

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<n$ 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.

In short:

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} $$

$\endgroup$

You must log in to answer this question.

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