A certain power of a matrix is Identity

Question

I have a vector say $v=[1 1 1 1 1 0 0 0]$ with this i generate a circulant matrix if order $8\times 8$. Now i see that the circulant matrix generated by this matrix has a property that $$ M^4\equiv I~\text{mod}~2$$ Now my question is the power $4$ involved which yields the identity matrix does this have a special name? and what other properties does this matrix have in relation to the dimension and the number of $1$`s in the matrix and their positioning in the matrix. Can somebody refer to some text or explain any concept with these kind of matrices?

Answer 1

Let $X = \left[\matrix{0&1&0&0&0&0&0&0 \\ 0&0&1&0&0&0&0&0 \\ 0&0&0&1&0&0&0&0 \\ 0&0&0&0&1&0&0&0 \\ 0&0&0&0&0&1&0&0 \\ 0&0&0&0&0&0&1&0 \\ 0&0&0&0&0&0&0&1 \\ 1&0&0&0&0&0&0&0}\right]$.

Then clearly $X^8 = I$ and $M = 1+X+X^2+X^3+X^4$. Let $F$ be a field and $\mathcal C_8$ be the ring of circulant matrices over $F$ of dimension 8, then there is a ring isomorphism $$ \begin{aligned} \mathcal C_8 &\to F[x]/(x^8 - 1) \\ X \ &\mapsto \quad \qquad x. \end{aligned} $$

So it all boils down to determining the structure of $F[x]/(x^8-1)$, equivalently, how the polynomial $x^8-1$ is factored in $F[x]$.

Since you are asking things modulo $2$, which corresponds to the finite field case $F = \mathbb F_2$, one then sees that it is in particular interesting because it is extremal: $$ x^8-1 = (x+1)^8. $$

Projecting things back to the ring, one immediately sees that $$ \mathbb F_2[x]/(x^8-1) \cong \mathbb F_2[x]/((x+1)^8) \cong \mathbb F_2[\epsilon]/(\epsilon^8), $$ where the last isomorphism is made under the linear transformation $x \mapsto \epsilon + 1$.

Then one can read things off from the ring $\mathbb F_2[\epsilon]/(\epsilon^8)$:

• Half ($2^7$) of them are nilpotent, if you look along the way of the transform $\mathcal C_8 \to \mathbb F_2[x]/((x+1)^8) \to \mathbb F_2[\epsilon]/(\epsilon^8)$, you will see that the circulant matrix $N \in \mathcal C_8$ satisfy $N^r = 0$ for some $r$ no greater than $8$ if the row vectors of $N$ have even $1$'s.
• The other half of them are units, so you can look at the $2$-group $(\mathbb F_2[\epsilon]/(\epsilon^8))^\times$. Either by using undergraduate's dream to brute force it, or by the following chain of canonical surjective homomorphisms $$ (\mathbb F_2[\epsilon]/(\epsilon^8))^\times \twoheadrightarrow (\mathbb F_2[\epsilon]/(\epsilon^4))^\times \twoheadrightarrow (\mathbb F_2[\epsilon]/(\epsilon^2))^\times \twoheadrightarrow (\mathbb F_2[\epsilon]/(\epsilon))^\times \cong \{1\}, $$ One can actually see that $(\mathbb F_2[\epsilon]/(\epsilon^8))^\times \cong (\mathbb Z/8)\times (\mathbb Z/4)\times(\mathbb Z/2)\times (\mathbb Z/2)$.
• If you look more closely at the homomorphisms along the way, you can even tell how to read the minimal $r$ such that $N^r = I$ from $N \in \mathcal C_8$.
• Write $N = \sum_{i=0}^7 a_iX^i$. Then such $r$ exists if and only if $\sum a_i$ is odd (otherwise $N$ is nilpotent). In this case, we always have $r \leq 8$. And $r \leq 4$ if $N = \sum_{i=0}^3 a_iX^i$ (terms beyond $X^4$ vanishes). And $r \leq 2$ if $N = \sum_{i=0}^1 a_iX^i$.

Also let us briefly look at the case of dimension $n$ modulo a prime $p$. To understand the structure of $\mathbb F_p[x]/(x^n-1)$ it usually takes three steps:

1. Write $n = n'p^e$ with $p \not | \ n'$. Take $y = x^{p^e}$ and consider $\mathbb F_p[y]/(y^{n'}-1)$.
2. Use the identity $$ y^{n'}-1 = \prod_{d \ | \ n'}\Phi_d(y), $$ where $\Phi_d$ is the $d$-th cyclotomic polynomial.
3. To factorize $\Phi_d(y)$ in $\mathbb F_p$, I will just say that let $s$ be the minimal number such that $p^s \equiv 1 \pmod d$, then $\Phi_d(y)$ factorizes into $s$ irreducible polynomials of degree $\phi(d)/s$, where $\phi$ is the Euler's function.

Anyway this should give you the ring structure of $\mathbb F_p[x]/(x^n-1)$, which is a product of rings of the form $\mathbb F_q[\epsilon](\epsilon^{p^e})$, where $\mathbb F_q = \mathbb F_{p^t}$ is a finite field of characteristic $p$.

This is at least theoretically manageable, at least should be possible to write a computer program for this, though this general case might be messy already at this stage, and seeing directly the relations between the row vectors of your circulant matrix and the minimal order might be hard.