# Analyzing a recurrence relation given by a Toeplitz matrix

Let $p$ be an odd prime, and $M_p$ be the $p\times p$ Toeplitz matrix over $\mathbb{F}_2$ given by $a_0=a_1=1$ and $a_{-p+1}=1$, e.g. for $p=5$ we have

$$M_5=\left[\begin{array}{ccccc} 1 & & & & 1\\ 1 & 1\\ & 1 & 1\\ & & 1 & 1\\ & & & 1 & 1 \end{array}\right]$$

Let $v_0=(1,0,\dots,0)\in\mathbb{F}_2^p$ and define the sequence $v_0,v_1,v_2,\dots$ by the recurrence relation $$v_{n+1}=M_p v_n$$

This sequence must be periodic because of the pigeonhole principle.

1. I want to find the period. i.e., find a way to compute from $p$, without computing the whole sequence, $a$ and $b$ such that $v_{a+kb}=v_a$ for every $k\ge 0$. A formula giving $a,b$ from $p$ will be the best, but even non trivial estimates are good.

2. I want, if possible, a closed-form description of $v_{n}$ computable from $n$ and $p$, again without computing the whole sequence.

-
Some information can be found at en.wikipedia.org/wiki/Circulant_matrix. For instance, the eigenvectors (over the algebraic closure of $\mathbb F_2$) are determined by the $p$-th roots of unity (they live in a finite extension of $\mathbb F_2$ whose degree is the multiplicative order of $2$ modulo $p$). – Marc van Leeuwen Jun 16 '12 at 9:46

Theorem: Let $M$ be an $n \times n$ matrix over a field $F$ and fix $1 \le i, j \le n$. Suppose that over $\bar{F}$ the characteristic polynomial of $M$ has roots $\lambda_1, ... \lambda_m$ with multiplicities $e_1, ... e_m$. Then we can write $$(M^n)_{ij} = \sum_{k=1}^m p_k(n) \lambda_k^n$$

where $p_i$ is a polynomial of degree at most one less than the largest size of a Jordan block of $M$ with eigenvalue $\lambda_i$. This follows from the theory of Jordan normal form.

In this case $M$ is a circulant matrix so one can write down its eigenvalues fairly explicitly using the discrete Fourier transform (equivalently, using the representation theory of a finite cyclic group): they are given by $$\lambda_k = \zeta_p^k (1 + \zeta_p^{-1})$$

where $\zeta_p$ is a primitive $p^{th}$ root of unity over $\mathbb{F}_2$. The polynomial $x^p - 1$ is separable over $\mathbb{F}_2$, so the $\lambda_k$ are distinct and the polynomials $p_k(n)$ are constant.

Now, $1 + \zeta_p^{-1}$ has conjugates $$1 + \zeta_p^{-1}, 1 + \zeta_p^{-2}, 1 + \zeta_p^{-2^2}, 1 + \zeta_p^{-2^3}, ...$$

by repeatedly applying the Frobenius map. This sequence starts repeating precisely at the smallest $r$ such that $2^r \equiv 1 \bmod p$, so in other words $1 + \zeta_p^{-1}$ lives in $\mathbb{F}_{2^r}$ where $r$ is the order of $2 \bmod p$ and hence has multiplicative order dividing $\boxed{2^r - 1}$. Since $p | 2^r - 1$ by assumption, each $\lambda_k$ has this period also.

You can determine a closed form in one of various ways. My preferred general method is to write down the matrix generating function $$(I - tM)^{-1} = \sum_{n \ge 0} M^n t^n$$

and isolate its entries using Cramer's rule. In this particular case it is fairly straightforward to write your initial vector as a linear combination of the eigenvectors of $M$. These eigenvectors are $$u_{ij} = \frac{1}{p} \zeta_p^{ij}$$

where $u_k$ has eigenvalue $\lambda_k$ (representation theory of cyclic groups!), and we have $$v_0 = \frac{1}{p} \sum_{k=0}^{p-1} u_k$$

hence $$v_n = \frac{1}{p} \sum_{k=0}^{p-1} \zeta_p^{nk} (1 + \zeta_p^{-1})^n u_k.$$

-

I was going to write something more detailed, but Qiaochu Yuan beat me to it. So let me just state the steps that determine the period you are after. First find the multiplicative order $r$ of $2$ modulo $p$, i.e., the smallest positive integer for which $2^r\equiv 1\pmod p$; this is a divisor of $p-1$, rather often equal to $p-1$ as you can see from the frequency of $2$ in this sequence. Now you need to work in $\mathbb F_{2^r}$, where the primitive $p$-th roots of unity over $\mathbb F_2$ live. You operator has an obvious eigenvalue $0$, apart from that the eigenvalues are the values $\alpha+1$ where $\alpha$ runs through those primitive $p$-roots of unity (Qiaochu give more naturally $1+\alpha^{-1}$, but if $\alpha$ is one of these primitive roots, $\alpha^{-1}$ is another). Decomposing your initial vector in the basis of eignenvectors, all of these eigenvalues occur, so the period you are looking for is the least common multiple of the multiplicative orders (in $\mathbb F_{2^r}$) of these elements $\alpha+1$.

If $r=p-1$ then all $\alpha$ are conjugate under the Galois group, and you need to compute only one multipliciative order; in this case you can realize $\mathbb F_{2^r}$ as $\mathbb F_2[X]/(1+X+X^2+\cdots+X^{p-1})$, you can take $\alpha$ to e the image of $X$, and you just need to compute the multiplicative order of $1+X$ in the quotient. For instance for $p=3,5$ you actually hit a generator of the multiplicative group, giving periods $2^{p-1}-1=3,15$ respectively, but for $p=11$ you find an element of order $341$, a proper divisor of $2^{10}-1=1023$. The main advantage of this computation over straightforward determination of the period is that you are in a multiplicative group rather than a monoid, so you know that you will come back to $1$, and that the exponent required divides the order $2^r-1$ of the multiplicative group.

The case where $r$ strictly divides $p-1$ is a bit more complicated. You need to decompose the polynomial $1+X+X^2+\cdots+X^{p-1}\in\mathbb F_2[X]$ into irredicible factors $F_i$ of degree $r$, each of which is the minimal polynomial of a class (under the Galois group) of primitive $p$-th roots of unity. For each factor you can realise $\mathbb F_{2^r}$ as $\mathbb F_2[X]/(F_i)$, and you can compute the multiplicative order of $1+X$ in the quotient for every $F_i$ (certainly a divisor of $2^r-1$), and take their LCM. In the end you will definitely get a divisor of $2^r-1$, so if you wnat to avoid some cumbersome calculations, you could just iterate your original operation over divisors of $2^r-1$ to see which one defines the period; just don't forget to start at the first image $(1,1,0,0,0,\dots)$ to be sure you've got rid of the component of the eigenvector for eigenvalue $0$. For instance, for $p=17$ it is not so easy to factor $1+X=X^2+\cdots+X^{16}$ over $\mathbb F_2$ into two factors of degree $8$, but $2^8-1=255$ factors as $3*5*17$, and it is easy to see your period neither divides $15$ nor $17$, so it must be $255$.

-