# When matrix generated by polynomial in a ring starts repeating

If we have a polynomial lets say $0 + x + 12x^2 + 11x^3$ in $\mathbb{Z}_{13} / x^4 + 1$ (quotient ring over finite field). Then if we multiply that polynomial by $x^i \text{ for } i \in [0, \dots, r]$. Then rows start repeating after some number of rows.

For example, given width equal to $4$, then 9th row is the same as first row. What is the value of $r$ with respect to dimension of that first polynomial (or width of matrix)?

[ 0  1 12 11] --> x^0 * (0 + x + 12x^2 + 11x^3)
[ 2  0  1 12] --> x^1 * (0 + x + 12x^2 + 11x^3) = 2 + 0x + 1x^2 + 12x^3 <-- [ 2  0  1 12]
[ 1  2  0  1] --> x^2 * ...
[12  1  2  0] --> x^3 * ...
[ 0 12  1  2] --> x^4 * ...
[11  0 12  1] --> x^5 * ...
[12 11  0 12] --> x^6 * ...
[ 1 12 11  0] --> x^7 * ...
[ 0  1 12 11] --> x^8 * ... = first row!

• Observation: you need both a bound on the coefficients (from the finite field) and a bound on the degree (from the ideal quotient). If either of these are lacking, the. There are examples such that the rows never repeat. In generality, this is a question about quotient rings over finite fields – Stella Biderman Feb 26 '17 at 3:49

## 2 Answers

The polynomials you mention live in $R = \Bbb Z_{13}[x]/(x^4+1)$ not in $\Bbb Z_{13}/(x^4+1)$. Now in the algebra $R$ of dimension $4$ the multiplication with $x$ can, as a linear operator, be represented by a matrix : $$M_x = \begin{pmatrix} 0 & 0 & 0 & -1 \\ 1 & 0& 0& 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 &0 \end{pmatrix}$$. This matrix expresses that the multiplcation with $x$ maps: $1 \mapsto x, x \mapsto x^2, x^2 \mapsto x^3, x^3 \mapsto x^4 = -1$. It is easily verified that $M$ has order $8$.

Note that, as we are in a finite field , we have cancellation, so $x^rf(x) = f(x)$ iff $x^r = 1$. So the point at which the sequence $x^{\mathbb{Z}}f(x)$ repeats is independent of $f$; it is the multiplicative order of $x$.

If $x \in F$, $F$ a finite field, we know $\mathcal{o}(x) \mid |F|-1$. But determining whether $x$ is a primitive root is already hard over $\mathbb{Z}/(n)$, so I doubt you can do better at pinning down $\mathcal{o}(x)$.

EDIT: OP has pointed out that the quotient ring given in the OP is not a finite field. But the above conclusions carry over with a few adjustments.

Let the quotient ring be $R[x]/(h(x))$. $R[x]$ is a UFD, so write $h(x)=x^ng(x)$ with $x, g(x)$ coprime. Then, by Bézout, $(x^n)+(g(x))=R[x]$, so, by Chinese Remainder Theorem, $R[x]/(h(x))\cong R[x]/(x^n)\times R[x]/(g(x))$. A cycle in the LHS will (of course) also lead to a cycle in the RHS too. $x^n$ is nilpotent in the first factor, so the action of "multiplication by x" cannot lead to a cycle there. Hence the canonical homorphism given by the CRT must take $f(x)$ to $(0, p(x))$ for some $p(x)\in R[x]/(g(x))$. In this ring, again by Bézout, x is a unit. So may cancel $x$.

We needn't have $\mathcal{o}(x) \mid |R[x]/(h(x))|-1$, but the spirit remains. Let $R[x]/(g(x))$ have $N$ units; then $\mathcal{o}(x) \mid N$.

• ${\bf Z}_{13}[x]/(x^4+1)$ is not a field. $x^4+1=(x^2+5)(x^2-5)$ is not irreducible. – Gerry Myerson Feb 26 '17 at 4:59