세 번 이동하면 돌아오는 행렬의 거듭제곱

C=\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}

자연수 n에 대하여 Cⁿ=E가 되는 조건을 구한다. 모든 성분이 0 또는 1이므로 거듭제곱해도 C 그대로라는 예측을 검토한다.

C^2=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix},\qquad C^3=E.

C와 C²는 E가 아니다. 성분마다 0과 1을 제곱하는 계산이 아니라 행렬 전체를 반복해 곱하기 때문이다. C³=E이므로 세 번 곱할 때마다 같은 계산으로 돌아온다.

n=3q+r, r=0,1,2로 나누면 Cⁿ은 각각 E,C,C²다. 따라서 Cⁿ=E일 필요충분조건은 n이 3의 배수인 것이다. 이때 E는 3행 3열의 단위행렬이다.

i행 j열은 i에서 j로 가는 표시로 읽는다. 이 이동 표로 해석하면 1→2→3→1이 반복된다. 한 번 이동한 표와 두 번 이동한 표는 다르지만 세 번 이동하면 출발점으로 돌아온다. 수업에서는 세 가지 결과를 먼저 실제 곱셈으로 확인한 뒤 일반적인 n의 조건을 적게 한다. 처음 두 결과에서 계속 달라진다고 추측하거나, 세 번째 결과만 보고 이후 항상 E라고 쓰는 답 모두 반복 횟수를 빠뜨린 것이다.

출처·착안: srcav, 「Grid Method Matrix Multiplication」. 문항과 풀이는 새로 작성했다.