1
$\begingroup$

If
$x_1+x_2+x_3 = c_1$
$x_2+x_3+x_4 = c_2$
$x_3+x_4+x_5 = c_3$
.
.
$x_{99}+x_{100}+x_1 = c_{99}$
$x_{100}+x_1+x_2 = c_{100}$

$x_i$ denote variables and $c_i$ denote constants.
How to calculate $x_1,x_2,\dots,x_{100}?$

$\endgroup$
6
  • $\begingroup$ The variables here are reals? That can be positive and negative? $\endgroup$
    – alan2here
    Dec 14, 2018 at 15:50
  • 1
    $\begingroup$ yes they are real. $\endgroup$ Dec 14, 2018 at 15:52
  • $\begingroup$ If this were drawn visually, it'd seem like some puzzles in the back of newspapers. You can always do the thing with vectors/matrices to solve this sort of system of equations. But I'd expect there to be neater solution for a specific case like this. Also you could have it go 1 to N rather than 1 to 100. $\endgroup$
    – alan2here
    Dec 14, 2018 at 16:13
  • $\begingroup$ how can i find just any one element i will use it for finding other elements $\endgroup$ Dec 14, 2018 at 16:32
  • 1
    $\begingroup$ @alan2here For general $N$ there will be surprises. Should $N$ be divisible by three, the matrix of the system is singular. This can, sort of, be seen from the circulant view Damien suggested. $\endgroup$ Dec 14, 2018 at 20:32

2 Answers 2

2
$\begingroup$

Edit: this answer was largerly edited, but keeping the same methodology, dealing with this problem by pure polynomial manipulation

Let us call $D$ the cyclic delay operator, the matrix is equal to $A=I+D+D^2$ with $D^{100}=I$

All circulant matrices can be represented in this way. A key point here is that the subset (ring) of circulant matrices is commutative, which allows classical algebric manipulations, here formal polynomial manipulation.

We first note that

$$\sum_{i=0}^{99} D^i = (I+D+D^2) \sum_{i=0}^{32}D^{3i} + D^{99}$$ $$ D^{99} = D^{-1}$$ $$(I+D+D^2) \sum_{i=0}^{99} D^i = 3\, \sum_{i=0}^{99} D^i $$

It follows: $$(I+D+D^2)^{-1} = \frac{1}{3} \sum_{i=0}^{99} D^i - \sum_{i=0}^{32} D^{3i+1}$$

And finally: $$x_j = \frac{1}{3} \sum_{i=1}^{100} c_i - \sum_{i=0}^{32} c_{j+3i+1} $$

When the indices $j+3i+1$ must be understood in a 'cyclic' way.

Note 1: the matrix $A$ corresponds to a cyclic filtering operation. The inversion can be interpreted as equalization

Note 2: all circulant matrices have same eigenvectors, corresponding to the DFT matrix. This can be used for example to show that the corresponding ring is commutative. It could be used also to perform the matrix inversion ("equalization in the frequency domain"). This proves that when an inverse of a circulant matrix exists, this matrix is circulant

$\endgroup$
4
  • $\begingroup$ How could i use to solve this set of equations,would u please explain $\endgroup$ Dec 14, 2018 at 17:06
  • $\begingroup$ Yes (the upvote is mine), this will work. As long as you remember that the condition $D^{100}=1$ makes your time axis cyclic, meaning that you need to do a DFT. Division by eigenvalues works fine because the zeros of $A$ are the third roots of unity, and we are plugging in 100th roots of unity. $\gcd(3,100)=1\implies$ no problems. $\endgroup$ Dec 15, 2018 at 5:11
  • $\begingroup$ @JyrkiLahtonen Thank you.I need to complete this answer. I know about DFT use for circulant matrices. My first intention is to use a polynomial approach, using the fact that the relevant subset (ring) is commutative, allowing classical algebric manipulations. If it appears to be too fastidious, I will come back to DFT (frequency domain equalization !) $\endgroup$
    – Damien
    Dec 15, 2018 at 8:54
  • $\begingroup$ @NavneetHingankar Is it clear enough now ? $\endgroup$
    – Damien
    Dec 15, 2018 at 15:50
0
$\begingroup$

I inverted the matrix of coefficients for the $10 \times 10$ case in a spreadsheet. If we call the entries of the matrix $a_{ij}$ we get $$a_{ij}=\begin {cases} -\frac 23&j \gt i, j-i \equiv 1 \pmod 3 \\ -\frac 23 & i \gt j,i=j \equiv 0 \pmod 3 \\\frac 13 & \text {otherwise} \end {cases}$$ You can multiply the column matrix of the $c_i$ by this to get the $x_i$. I am sure the pattern will continue for all matrices of size $1 \bmod 3$. You can verify the inverse by multiplying it by your coefficient matrix. It will take some keeping track of indices, but it should work. An image of three times the inverse in the $10 \times 10$ case is below. enter image description here

This gives $$x_1=\frac 13 \sum_{i=1}^{100} c_i-\sum_{j=1}^{33}c_{3j-1}$$ and all the others are cyclic shifts of this.

$\endgroup$
4
  • $\begingroup$ what if nth term is not 100 $\endgroup$ Dec 14, 2018 at 17:05
  • $\begingroup$ This works for any $n$ that is $1 \bmod 3$. The same approach will work for other $n$ but you would have to see how the pattern comes out. The reason $\bmod 3$ matters is that you have $3$ terms in each line on the left. For $n=9$ the matrix is singular, so there is no general solution. $\endgroup$ Dec 14, 2018 at 17:07
  • $\begingroup$ how to calculate x2 using your equations $\endgroup$ Dec 14, 2018 at 17:11
  • $\begingroup$ As I said, it is just the cyclic shift of the equation for $x_1$ Increase all the indices by $1$ and wrap around when you get to $100$. $\endgroup$ Dec 14, 2018 at 17:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.