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?
 A: 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$.
