Im interested in solving the system of equations $C_{i,j} = C_{i,j-1} + C_{i,j+1} + C_{i-1,j} + C_{i+1,j}$ for $0 \leq i < N$ and $0 \leq j < N$, where $C_{i,j} \in \mathbb{C}$. One could think of this a regular grid where each entry of a cell corresponds to the sum of the neighboring cells. Additionally i want to have periodic boundary conditions in both indices, i.e. $C_{i+N, j} = C_{i, j}$ and $C_{i, j+N} = C_{i, j}$, hence we can think of the grid mentioned before as a torus. Problem: find all possibile non-trivial solutions of this system of equations. My first attempt was to substract $- 4C_{i,j}$ on both sides such that we can think of the problem as $- 3 C_{i,j} = C_{i,j-1} - 2 C_{i,j} + C_{i,j+1} + C_{i-1,j} - 2C_{i,j} + C_{i+1,j}$ which is essentially a discrete version of theHelmholtz equation on a unit grid, i.e. $\frac{\partial^{2} C_{i,j}}{\partial i^2} + \frac{\partial^{2} C_{i,j}}{\partial j^2} + 3 C_{i,j}$. Due to lack of knowledge i did not find any other good ansatz. Has this problem already been solved?

Thanks in advance!


One could use the fact that the associated coefficient matrix is block-circulant.

Let $\otimes$ denote the Kronecker product. Let $\mathbf e_0, \mathbf e_1,\dots,\mathbf e_{N-1}$ denote the standard basis of $\Bbb R^{N}$. Let $P$ denote the size-$N$ permutation matrix $$ P = \pmatrix{0&\cdots & 0 & 1\\1&0&\cdots&0\\\vdots & \ddots & \ddots & \vdots\\ 0 & \cdots & 1 & 0}. $$ Let $\mathbf c$ denote the column-vector $$ \mathbf c = (C_{0,0},C_{0,1},\dots,C_{0,N},C_{1,0},C_{1,1},\dots) = \sum_{i,j = 0}^{N -1} C_{ij}\, \mathbf e_i \otimes \mathbf e_j. $$ Your system of equations can be written in the form $M \mathbf c = 0$, where $$ M = I_{N} \otimes (P + P^T) + (P + P^T) \otimes I_{N} - I_{N^2}. $$ We see that this matrix can be diagonalized. In particular, we have $$ (F \otimes F) M (F \otimes F)^* = I_{N} \otimes D + D \otimes I_{N} - I_{N^2}, $$ where $D$ is the diagonal matrix $$ D = \operatorname{diag}(2\cos(0 \cdot \theta),2\cos(1 \cdot \theta), \dots, 2 \cos((N-1) \cdot \theta)), \quad \theta = \frac{2 \pi }{N}. $$

An alternative, simpler approach. Use the Ansatz $$ C_{p,q} = \omega_1^p \omega_2^q $$ where $\omega_1,\omega_2$ are complex numbers. We have $$ C_{p,q} = C_{p,q-1} + C_{p,q+1} + C_{p-1,q} + C_{p+1,q} \implies\\ \omega_1^p\omega_2^q = \omega_1^p\omega_2^{q+1} + \omega_1^p\omega_2^{q-1} + \omega_1^{p+1}\omega_2^q + \omega_1^{p-1}\omega_2^q \implies\\ \omega_1^p \omega_2^q = (\omega_1 + \omega_1^{-1} + \omega_2 + \omega_2^{-1})\omega_1^p \omega_2^q \implies\\ \omega_1 + \omega_1^{-1} + \omega_2 + \omega_2^{-1} = 1. $$ Now, due to the periodic boundary condition, we must have $\omega_1^{N} = \omega_2^{N} = 1$, so that we have $$ \omega_j = \exp(i k_j\theta), \quad \theta = \frac{2 \pi}{N}, \quad 0 \leq k_j \leq N-1, \quad j = 1,2. $$ For this value of $\theta$, there is a non-trivial solution to the system for every solution to the equation $$ \omega_1 + \omega_1^{-1} + \omega_2 + \omega_2^{-1} = 1 \implies\\ 2[\cos(k_1 \theta) + \cos(k_2 \theta)] = 1. $$ As can be shown using the matrix representation of the system from the first part, the system will have a solution if and only if this system has a solution for some integer values $k_1,k_2$.

An alternative formulation: let $\alpha = \theta/2$. With the sum to product formula, we can rewrite this as $$ \cos([k_1 + k_2]\alpha)\cos([k_1 - k_2]\alpha) = \frac 14. $$


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.