4

Consider a $m \times n$ matrix $M$ such that each cell in $M$ is equal to the sum of its adjacent cells (sharing either an edge or a corner with this cell). What are the values in this matrix.

I am trying to find a non-zero matrix satisfying this condition. Does there exist such a matrix, or if not, is there a proof for it?

I know that when the matrix values are equal to average of surrounding cells, then all values in the matrix are equal. Is there a similar conclusion we can reach to in this case?

Siddharth Joshi
  • 1,488
  • By a cell do you mean a matrix entry/element? – JMJ Jan 30 '20 at 18:48
  • 1
    How do you define 'adjacent' cells? Is it in a cross pattern, or do diagonally adjacent cells also count? – Fimpellizzeri Jan 30 '20 at 18:50
  • @Mortified Through Math : yes – Siddharth Joshi Jan 30 '20 at 18:50
  • @ Fimpellizieri : Sorry. Will edit the question. – Siddharth Joshi Jan 30 '20 at 18:51
  • It's easy to see by hand that only the $0$ matrix satisfies the requirements in the $2\times 2$ case. I have a feeling this also occurs whenever $m,n\geqslant 2$. – Fimpellizzeri Jan 30 '20 at 18:59
  • The matrix $[1,1,0,-1,-1]$ works and is nontrivial. – Fimpellizzeri Jan 30 '20 at 19:07
  • @Fimpellizeri : Can't understand. Can you post an answer? – Siddharth Joshi Jan 30 '20 at 19:10
  • 1
    If we can find $a$ and $b$ such that $\cos \tfrac{a \pi}{m+1} + \cos \tfrac{b \pi}{n+1} = \tfrac{1}{2}$, then $A_{ij} = \sin \tfrac{ai\pi}{m+1} \sin \tfrac{bj\pi}{n+1}$ works because $\sin \tfrac{a(i-1)\pi}{m+1} + \sin \tfrac{a(i+1)\pi}{m+1} = 2 \cos \tfrac{a \pi}{m+1} \sin \tfrac{a i \pi}{m+1}$. Jaroslaw Matlak's solution is this for $\tfrac{a}{m+1} = \tfrac{1}{2}$ and $\tfrac{b}{n+1} = \tfrac{1}{3}$, so $\cos \tfrac{\pi}{2} + \cos \tfrac{\pi}{3} = \tfrac{1}{2}$. I haven't found any other rational angles that work. – David E Speyer Feb 03 '20 at 15:49
  • The solution $\cos 0 - \cos \tfrac{2 \pi}{3} = \tfrac{1}{2}$ unfortunately gives the $0$-matrix, since $\sin 0 = 0$. – David E Speyer Feb 03 '20 at 15:55
  • @DavidESpeyer: Just a small clarification. In my case, each cell is equal to sum of its adjacent cells, with which this cell shares either an edge or a corner. You're probably finding a solution for the case when each cell is equal to sum of cells that share only an edge with this cell. – Siddharth Joshi Feb 03 '20 at 16:16
  • @SiddharthJoshi Thanks, you are right. – David E Speyer Feb 03 '20 at 16:19
  • 1
    So we want $(2 \cos \alpha+1)(2 \cos \beta + 1) = 2$, rather than $2 \cos \alpha + 2 \cos \beta = 1$, and it is a coincidence that $(\cos \alpha, \cos \beta) = (\tfrac{1}{2}, 0)$ solves both. – David E Speyer Feb 03 '20 at 16:24
  • That's a neat solution. It would be interesting to prove that any solution is of this form, although I have no ideas to prove this without maybe eigenvalues or something. – Siddharth Joshi Feb 03 '20 at 16:26

2 Answers2

5

For sure such matrix could be found for $m \in 2\mathbb{N}+1, n \in 3\mathbb{N}+2$:

$$\left[\begin{matrix} a&a&0&-a&-a&0&a&a&0&\cdots & 0 & a &a & 0 &-a &-a\\ 0&0&0&0&0&0&0&0&0&\cdots&0&0&0&0&0&0\\ -a&-a&0&a&a&0&-a&-a&0&\cdots & 0 & -a &-a & 0 &a &a\\ 0&0&0&0&0&0&0&0&0&\cdots&0&0&0&0&0&0\\ \cdots&&&&&&&&&\cdots\\ 0&0&0&0&0&0&0&0&0&\cdots&0&0&0&0&0&0\\ a&a&0&-a&-a&0&a&a&0&\cdots & 0 & a &a & 0 &-a &-a\\ \end{matrix}\right]$$ Of course depending on the value of $n$ and $m$ last row and two last columns might be different (last row might start with $-a, -a$ and last columns might start with $a,a$), but general idea is the same.

Jaroslaw Matlak
  • 4,895
  • How did you get the idea? – Siddharth Joshi Jan 30 '20 at 19:12
  • 2
    That's brilliant. If you try small examples with $m=1$ or $n=1$, you will see that $[1,1,0,-1,-1]$ gives a non-trivial answer. Up to a factor of $a$, Jaroslaw uses a very clever layout to build up on the small example. – Fimpellizzeri Jan 30 '20 at 19:14
  • So you started finding a solution for $n\times 1$ and then extended it? Nice. – Siddharth Joshi Jan 30 '20 at 19:17
  • 1
    As @Fimpellizieri noticed, it's easy to notice the pattern in matrices $1\times n$ - non-zero blocks are separated by zero cells. I've used the same idea to expand it to the second dimension - i separate non-zero rows with zero rows. The same thinking can be used to extend the solution to three dimensions (non-zero matrices separated by zero-matrices) and so on. – Jaroslaw Matlak Jan 30 '20 at 19:27
2

The point of this answer is to show that the only solutions are Jaroslaw Matlak's solution (when $m \equiv 1 \bmod 2$ and $n \equiv 2 \bmod 3$), the transpose of his solution, and linear combinations of the above (when $m \equiv n \equiv 5 \bmod 6$).

Let's first avoid boundary effects by studying the problem on an $M \times N$ torus, so indices wrap around. Let $\phi$ be the linear map from $M \times N$ matrices which replaces each entry of the matrix with the sum of its $8$ neighbors. We want to understand the $1$-eigenspace of $\phi$.

In fact, it is easy to diagonalize $\phi$ completely. For any $0 \leq a < M$ and $0 \leq b < N$, the matrix $$A_{jk} = \exp\left( (2 \pi i) \left( \tfrac{aj}{M} + \tfrac{bk}{N} \right) \right)$$ is an eigenvector of $\phi$ with eigenvalue $(2 \cos \tfrac{a \pi}{M} + 1)(2 \cos \tfrac{b \pi}{N} + 1)-1$. That's $MN$ eigenvectors in an $MN$ dimensional vector space, and it is easy to show they are linearly independent. So we have found all the eigenvectors.

We want $$(2 \cos \tfrac{a \pi}{M} + 1)(2 \cos \tfrac{b \pi}{N} + 1)=2 \quad (\ast).$$ I will now show that the only solutions to $(\ast)$ in integers are $(\cos \tfrac{a \pi}{M}, \cos \tfrac{b \pi}{N}) = (1/2,0)$ and $=(0, 1/2)$.

Lemma Let $M > 6$. Then there is some $a$ with $M/4 < a < 3M/4$ and $\mathrm{GCD}(a,M)=1$.

Proof: We break into cases according to $M \bmod 4$. If $M$ is odd, $\tfrac{M-1}{2}$ does the trick. If $M \equiv 2 \bmod 4$, then $\tfrac{M-4}{2}$ works; if $M \equiv 0 \bmod 4$, then $\tfrac{M-2}{2}$ does. $\square$.

Now, suppose we have a solution to $(\ast)$ in lowest terms with $M>6$. The Galois group of $\mathbb{Q}(\cos \pi/M, \cos \pi/N)$ acts transitively on the values $\cos \tfrac{a \pi}{M}$ with $\mathrm{GCD}(a,M)=1$, so we can apply a Galois automorphism to make $a$ be as in the lemma, with $M/4 < a < 3M/4$.

But then $-1 < 2 \cos \tfrac{\pi a}{M} +1 < 0$, which means that $2 \cos \tfrac{\pi b}{N} +1 < -2$, an impossibility. We have a contradiction and deduce that $M \leq 6$; then we just check cases.

Finally, we need go from the torus case back to the rectangle. Given an $m \times n$ solution to the rectangular problem, we can build a $(2m+2) \times (2n+2)$ solution to the torus problem as shown in the example below for $(m,n) = (2,3)$.

$$\begin{bmatrix} u&v&w\\x&y&z \\ \end{bmatrix} \leadsto \begin{bmatrix} 0&0&0&0&0&0&0&0 \\ 0&u&v&w&0&-w&-v&-u \\ 0&x&y&z&0&-z&-y&-x \\ 0&0&0&0&0&0&0&0 \\ 0&-x&-y&-z&0&z&y&x \\ 0&-u&-v&-w&0&w&v&u \\ \end{bmatrix}.$$

So our previous solutions with $(\tfrac{a}{M}, \tfrac{b}{N}) = (\tfrac{1}{4}, \tfrac{1}{6})$ turn into $(\tfrac{a}{2m+2}, \tfrac{b}{2n+2}) = (\tfrac{1}{4}, \tfrac{1}{6})$ etcetera and, after a bit of cleaning up, we see that Jaroslaw Matlak has found them all.

David E Speyer
  • 61,724
  • That's a marvelous breakdown of the problem. Since I don't have as much knowledge as you do, I have a few doubts. Please answer if you have time. 1) Is there a simple way to prove that the Eigenvalues of $\phi$ are of this form as you said (I can say that they might satisfy, but why are these the only solutions) and 2) Do you have any reference from where I can read up more about Galois group and transitive action, which you have mentioned in your second proof. I am really curious to know (Since I don't have advanced mathematics education I have no idea about this) – Siddharth Joshi Feb 04 '20 at 16:03