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

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.