Let $m\geq 3$ be a positive odd number and let $M$ be the $m\times m$ matrix defined by
$$M=\begin{bmatrix}0&1&0&0&\cdots&0\\
0&0&1&0&\cdots &0\\
0&0&0&1&\cdots &0\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&0&0&\cdots &1\\
1&-2&2&-2&\cdots&2\end{bmatrix}.$$
It can be proven that $M^{2m}=I_m$, the identity matrix of size $m$. Now I would like to compute the $k$-th power of $M$ for $k=0,1,\ldots,2m-1$. My observation is as follows:
Let $N$ be the $(2m)\times m$ matrix defined by
$$N=\begin{bmatrix}
1&0&0&0&\cdots&0&0\\
0&1&0&0&\cdots&0&0\\
0&0&1&0&\cdots &0&0\\
0&0&0&1&\cdots &0&0\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&0&\cdots &1&0\\
0&0&0&0&\cdots &0&1\\
1&-2&2&-2&\cdots&-2&2\\
2&-3&2&-2&\cdots&-2&2\\
2&-2&1&-2&\cdots&-2&2\\
2&-2&2&-3&\cdots&-2&2\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
2&-2&2&-2&\cdots&-3&2\\
2&-2&2&-2&\cdots&-2&1\\
\end{bmatrix}.$$
We call the top row of $N$ the $0$-th row. Then for $k=0,1,\ldots,2m-1,2m$, $M^k$ is obtained from $N$ by taking the $k\!\pmod{2m}$-th row, $(k+1)\!\pmod{2m}$-th row, etc., up to the $(k+m-1)\!\pmod{2m}$-th row and form a matrix. For example,
$$M^2=\begin{bmatrix}
0&0&1&0&\cdots &0&0\\
0&0&0&1&\cdots &0&0\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&0&\cdots &1&0\\
0&0&0&0&\cdots &0&1\\
1&-2&2&-2&\cdots&-2&2\\
2&-3&2&-2&\cdots&-2&2
\end{bmatrix}.$$
while $$M^{2m-1}=\begin{bmatrix}2&-2&2&-2&\cdots&-2&1\\1&0&0&0&\cdots&0&0\\
0&1&0&0&\cdots&0&0\\
0&0&1&0&\cdots &0&0\\
0&0&0&1&\cdots &0&0\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&0&\cdots &1&0\\\end{bmatrix}$$
This seems to be an interesting way to compute the powers of the matrix $M$, but I am not sure how to verify this method, though some specific examples seem to suggest that this method is valid. Could anyone help with proving this method?
Best Answer
Nice observation.
The key idea is that the matrix product of the $r$-th row of $N$ and $M$ is the $(r+1)$-th row of $N$ (where the $2m$-th row is interpreted as the $0$-th row), which ensures the position of $M^{k+1}$ as a submatrix of $N$ will be one row below the position of $M^k$ as a submatrix of $N$.
The following is a detailed proof.
Fix $m$, an odd integer $\ge3$.
Let $P[r]$ denote the $r$-th row of a matrix $P$, $r=0, 1, \cdots$.
Note that $N[0], N[1], \cdots, N[m-1]$ are the standard unit row vectors with $m$ coordinates. Hence for all $m\times m$ matrix $P$ and $0\le r<m$ $$N[r]P=P[r].$$ Lemma: $N[r] M = N[(r+1)\%(2m)]$ for $0\le r<2m$.
Proof: Let $b=(2,-2,2,-2,\cdots,2)$.
$N[r]=b-N[r-m]$ for $m\le r< 2m.$
Verify that $bM=b$. $$N[r] M=\begin{cases} M[r]=N[r+1] &\text{if }0\le r < m -1\\ M[m-1]=N[m] &\text{if }r= m-1\\ (b-N[r-m])M=b-N[r-m+1]=N[r+1] &\text{if } m\le r<2m-1\\ (b-N[m-1])M=b-M[m-1]=N[0] &\text{if } r=2m-1 \end{cases}$$
Claim (OP's observation): For all $k\ge0$ and $0\le r\le m-1$, $$M^k[r]=N[(k+r)\% (2m)].$$ Proof: Do induction on $k$.