# Gray code in Matrix

Suppose I have a matrix $$m \times n$$ with entry 0 or 1. Of course there is a possible $$2^{m\times n}$$ matrix. I want to sort all the matrices so that every two consecutive matrices are only 1 bit different, and the different ones must be neighboring. I can make the first 2 matrices arbitrarily, but the next matrix will depend on the previous matrix. For example 2 initial matrix is

$$\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$$ and $$\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$$

The changed bit is $$a_{22}$$ from 0 to 1. The third possible matrix is

$$\begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}$$ or $$\begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}$$

Because neighbors $$a_{22}$$ are $$a_{12}$$ and $$a_{21}$$. Can not change $$a_{11}$$ because it is not neighboring $$a_{22}$$

I can use dynamic programming, but complexity problems will arise if $$m, n$$ is large enough. Is there maybe a better algorithm? Or special case?

This is one of examples output for $$m = n = 2$$

$$\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$$

$$\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}$$

$$\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$$

$$\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$

$$\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}$$

$$\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$$

• Can you please argue that it is always possible for general $m, n$ to have "consecutive change positions" differ by one column only or one row, only (even "allowing wraparound": for a 3×3 matrix, $a_{21}$ and $a_{23}$ would be neighbours, too). – greybeard Mar 3 at 10:10
• @greybeard tbh i can't guarantee it. Yes you're right $a_{21}$ and $a_{23}$ are neighbors of $a_{22}$ in 3×3 matrix – L Lawliet Mar 3 at 10:37
• a₂₁ and a₂₃ are neighbors of a₂₂ I tried to get at $a_{21}$ and $a_{23}$ being neighbours to each other (so every element has four neighbours, including "corner elements" like $a_{11}$. – greybeard Mar 3 at 10:59
• @greybeard corner element has two neighbors. Edge element has three neighbors. a_12 and a_21 are the only neighbors of a_11 – L Lawliet Mar 3 at 13:12
• Have you checked Wikipedia? It mentions many different Gray codes with various properties. – Yuval Filmus Mar 3 at 15:16