Binary ↔ Gray permutation matrix

Generating a Gray code representation of a binary number can be thought of as mapping one binary number onto another binary number. Therefore, $$n$$-bit Gray code is a permutation of $$2^n$$ elements.

What would be an efficient way to generate the corresponding permutation matrix (having sparsity 1)?

A brute-force solution would be to go through all the integers from $$0$$ to $$2^{n-1}$$, converting each of them from binary to Gray using smth like

def convert_gray(binary):
binary = int(binary, 2)
binary ^= (binary >> 1)
return bin(binary)[2:]


considering each outcome as a binary, and filling the corresponding matrix entry.

I am wondering if there exists a faster and a more compact solution?

• How are you storing your permutation matrix? If you are storing it as a dense matrix, that is, as a list of $4^n$ entries, then the algorithm you describe is already optimal, since generating the Gray sequence takes a lot less time than $4^n$. You can speed that part up by generating the Gray sequence as a sequence, but it won't make much difference in running time. Commented Jan 30, 2021 at 20:11
• In my application, I will store at as a numpy array, because I will later multiply it by another matrix... Commented Jan 30, 2021 at 20:20
• Numpy arrays are dense. It will take $4^n$ time just to touch all entries in your matrix. This is a lot more than generating a Gray sequence even in a naive way. Commented Jan 30, 2021 at 20:54