Consider the following system $$ y_i=\sum_{|j-i|\leq k} x_{j} $$ for some $k< \lfloor (n-1)/2\rfloor$, and with indexes in the $\mathbb{Z}/n\mathbb{Z}$ ring. Essentially, $y_i$ is the sum of $x_i$ and its $2k$ "nearest neighbors". How can I transform this system to write it in terms of $x_j$?
Note that, alternatively, we may write $$ y_i=\sum_{j=-k}^kx_{i+j} $$ For example, with $n=5$ and $k=1$, the system becomes $$ y_i=\sum_{|j-i|\leq 1} x_{j}\Leftrightarrow\begin{cases} y_1=x_1+x_5+x_2\\ y_2=x_2+x_1+x_3\\ y_3=x_3+x_2+x_4\\ y_4=x_4+x_3+x_5\\ y_5=x_5+x_4+x_1 \end{cases} $$ which can be sketched by the periodic ring
How can I rewrite $\{x_j\}$ in terms of $\{y_i\}$?
Comment: Motivated by @aschepler's answer, we can actually just see this problem as $$ \mathbf{y}=T_{n,k}\mathbf{x} $$ where $$ T_{n,k}=B_{2k+1}+(J_{n}-B_{2(n-k-1)+1}) $$ where $B_k$ is the symmetric banded matrix with a maximum of $k$ ones in each row of its diagonal band and $J_n$ is the $n\times n$ matrix of ones. We are looking for $T_{n,k}^{-1}$. Schematically,
and so, for $n=5$ and $k=1$,
However, it is not always possible to compute $T_{n,k}^{-1}$. For $n=6$ and $k=1$, $T_{6,1}$ is singular:
It could be interesting to stipulate the conditions on $n$ and $k$ such that $T_{n,k}$ is non-singular. Also, can we hope for an expression for $T_{n,k}^{-1}$ in terms of banded matrices?
Let $T: \mathbb{R}^n \to \mathbb{R}^n$ be the linear transformation from vector $x$ to vector $y$.
If $2k+1$ and $n$ are relatively prime, $T$ is non-singular. But if $d>1$ is a divisor of both $n$ and $2k+1$, then for every $r \in \{0, 1, \ldots, d-1\}$,
$$ x_i = \begin{cases} 1 & i \equiv r \pmod{d} \\ 0 & i \not \equiv r \pmod{d} \end{cases} $$
is a vector with $y = Tx$ giving the same vector $y = \frac{2k+1}{d} \mathbf{1}_n$, so $T$ is not injective.
Assuming then that $2k+1$ and $n$ are relatively prime, there is a unique number $\ell \in \{1,\ldots,n-1\}$ so that $(2k+1) \ell \equiv 1 \pmod{n}$. Let $m$ be the positive integer $m=\frac{(2k+1)\ell-1}{n}$.
The $y_i$ are related to $x_i$ by a circular discrete convolution with a rectangular filter:
$$ r_i = \begin{cases} 1 & [i] \in \{[-k], [-k+1], \ldots, [k-1], [k]\} \\ 0 & \textrm{otherwise} \end{cases} $$
$$ y = r \ast x $$
where $[c]$ denotes the equivalence class $c + n\mathbb{Z} \in \mathbb{Z}/n\mathbb{Z}$.
Intuitively, we can imagine shifting the vector $r$ in $\mathbb{Z}$ by $2k+1$ positions at a time to get a sequence with $1$ repeated $t(2k+1)$ times. This is another convolution, by a vector with $t$ elements of value $1$, each pair separated by $2k$ elements with value $0$. If we do the same in $\mathbb{Z}/n\mathbb{Z}$, the sequence wraps around and overlaps itself. But if $t=\ell$, the first $1$ in the sequence and the last $1$ coincide, and the sum in that position is exactly one more than all the others.
Working this idea out, let $s$ be the sequence
$$ s_i = \begin{cases} 1 & [i] \in \{[k], [3k+1], [5k+2], \ldots, [k+(\ell-1)(2k+1)]\} \\ 0 & \mathrm{otherwise} \end{cases} $$
Convoluting $s \ast r$ gives, for $0 \leq a < n$,
$$ \begin{align*} (s \ast r)_a &= \big|\big\{(i,j) \in \mathbb{Z} \times \mathbb{Z} : -k \leq i \leq k, 0 \leq j < \ell, i+k+j(2k+1) \equiv a \pmod{n} \big\}\big| \\ (s \ast r)_a &= \big|\big\{q \in \mathbb{Z} : 0 \leq q < \ell(2k+1), q \equiv a \pmod{n} \big\}\big| \\ (s \ast r)_a &= \left\lceil \frac{\ell(2k+1)-a}{n} \right\rceil = \begin{cases} m+1 & a=0 \\ m & a \neq 0 \end{cases} \end{align*} $$
Then
$$ s \ast r \ast x = x + m (\mathbf{1}_n \ast x) = x + m \sum_{i=0}^{n-1} x_i $$
The sum of $x$ and the sum of $y$ are related by
$$ \mathbf{1}_n \ast y = \sum_{j=0}^{n-1} y_j = \sum_{j=0}^{n-1} \sum_{i=-k}^k x_{i+j} = \sum_{i=-k}^k \sum_{j=0}^{n-1} x_{i+j} = (2k+1) \sum_{j=0}^{n-1} x_j = (2k+1)(\mathbf{1}_n \ast x) $$
So finally,
$$ s \ast y = s \ast r \ast x = x + \frac{m}{2k+1} \mathbf{1}_n \ast y $$
$$ x = \left(s - \frac{m}{2k+1} \mathbf{1}_n \right) \ast y $$
For the example $n=5, k=1$, we have $2k+1=3$, $\ell=2$, $m=1$, $r = (1,1,0,0,1)$, $s = (0,1,0,0,1)$, and
$$ s - \frac{m}{2k+1} \mathbf{1}_n = (0,1,0,0,1) - \frac{1}{3} \mathbf{1}_n = \frac{1}{3} (-1, 2, -1, -1, 2) $$
That is, if $\sigma_y = \sum_{i=0}^{n-1} y_i$,
$$ \begin{align*} x_1 &= y_5 + y_2 - \frac{\sigma_y}{3} \\ x_2 &= y_1 + y_3 - \frac{\sigma_y}{3} \\ x_3 &= y_2 + y_4 - \frac{\sigma_y}{3} \\ x_4 &= y_3 + y_5 - \frac{\sigma_y}{3} \\ x_5 &= y_4 + y_1 - \frac{\sigma_y}{3} \end{align*} $$
or the matrix form of $T^{-1}$ is
$$ x = \frac{1}{3} \left(\begin{array}{ccccc} -1 & 2 & -1 & -1 & 2 \\ 2 & -1 & 2 & -1 & -1 \\ -1 & 2 & -1 & 2 & -1 \\ -1 & -1 & 2 & -1 & 2 \\ 2 & -1 & -1 & 2 & -1 \end{array}\right) y $$