# Matrix golf puzzle: enumerate a series by matrix multiplication

It is super easy to find matrices $X_0$, $F$ and $H$ such that $H F^n X_0$ is equal to $n$-nth element of the sequence $0,1,0,1,0,1,0,1,0,1,0,1,...$

$$X_0 = \left(\begin{array}{c}1\\1\\\end{array}\right)$$ $$F = \left(\begin{array}{c}-1 & 1\\0 & 1\\\end{array}\right)$$ $$H = \left(\begin{array}{c}1 & 0\end{array}\right)$$

Maybe it is a slightly harder challenge to find matrices $X_0$, $F$ and $H$ such that $H F^n X_0$ is equal to the $n$-nth element of the Fibonacci sequence $1,1,2,3,5,8,13,21,34,...$

$$X_0 = \left(\begin{array}{c}0\\1\\\end{array}\right)$$ $$F = \left(\begin{array}{c}0 & 1\\1 & 1\\\end{array}\right)$$ $$H = \left(\begin{array}{c}1 & 0\end{array}\right)$$

No big deal, isn't it?

Then try to find matrices $X_0$, $F$ and $H$ such that $H F^n X_0$ is equal to the $n$-nth element of the sequence $\left(\begin{array}{c}0\\0\\0\\\end{array}\right), \left(\begin{array}{c}0\\0\\1\\\end{array}\right), \left(\begin{array}{c}0\\1\\0\\\end{array}\right), \left(\begin{array}{c}0\\1\\1\\\end{array}\right), \left(\begin{array}{c}1\\0\\0\\\end{array}\right), \left(\begin{array}{c}1\\0\\1\\\end{array}\right), \left(\begin{array}{c}1\\1\\0\\\end{array}\right), \left(\begin{array}{c}1\\1\\1\\\end{array}\right), ...$

This is the sequence of all 3-digit binary numbers; please assume that this series repeats itself forever.

And what if I want to express this way the sequence of all $k$-digit binary numbers? How big does the matrix $F$ need to be? There is a very straightforward solution where F has dimensions $2^k \times 2^k$. Is there a better solution?

• Is this a puzzle question, or one to which you don't know the answer? – Federico Poloni Sep 19 '17 at 7:21
• How is it related to golf? – Ilya Bogdanov Sep 19 '17 at 13:39
• @IlyaBogdanov It is similar in spirit to code golf. – Federico Poloni Sep 19 '17 at 14:36
• It is very easy to determine the space of all solutions and find its dimension. – მამუკა ჯიბლაძე Sep 25 '17 at 3:48

For any row $R$, column $C$, and matrix $F$ (of compatible sizes), the numbers $a_n=RF^nC$ satisfy a recurrence relation with characteristic polynomial coinciding with the characteristic polynomial of $F$ (due to the Cayley--Hamilton theorem). So, to minimize the size of your $F$, we need to find the minimal order of (homogeneous linear) recurrence relation which all components of the sequence of vectors satisfy.
It is easy to make this for each component separately. The sequence $$\underbrace{0,0,\dots,0}_{2^t},\underbrace{1,1,\dots,1}_{2^t},\underbrace{0,0,\dots,0}_{2^t},\dots$$ cannot satisfy a relation of order $2^t$, because $2^t$ zeroes are followed by a non-zero. On the other hand, it satisfies the relation $a_{2^t+n+1}+a_{n+1}=a_{2^t+n}+a_n$, so the minimal characteristic polynomial for it is $P_t(\lambda)=\lambda^{2^t+1}-\lambda^{2^t}+\lambda-1=(\lambda-1)(\lambda^{2^t}+1)$.
Since we need a recurrence relation working for all $k$ coordinates simultaneously, we need to take the l.c.m. of all minimal polynomials which is $$(\lambda-1)\prod_{t=0}^{k-1}(\lambda^{2^t}+1)=\lambda^{2^k}-1.$$ Thus $2^k$ is indeed the minimal size of a required matrix $F$.