1
$\begingroup$

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?

$\endgroup$
4
  • 4
    $\begingroup$ Is this a puzzle question, or one to which you don't know the answer? $\endgroup$ Sep 19, 2017 at 7:21
  • 1
    $\begingroup$ How is it related to golf? $\endgroup$ Sep 19, 2017 at 13:39
  • $\begingroup$ @IlyaBogdanov It is similar in spirit to code golf. $\endgroup$ Sep 19, 2017 at 14:36
  • $\begingroup$ It is very easy to determine the space of all solutions and find its dimension. $\endgroup$ Sep 25, 2017 at 3:48

1 Answer 1

8
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ @FedericoPoloni: Thanks! Corrected. $\endgroup$ Sep 20, 2017 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.