 Solution

The Cayley-Hamilton theorem states that every square matrix satisfies its characteristic polynomial: if ${\chi }_A(t)=\det (tI-A)$, then ${\chi }_A(A)=0$.

For the proof, the adjugate identity givesWrite $\mathrm{adj}(tI-A)=B_0+B_{1}t+\cdots +B_{n-1}{t}^{n-1}$ and compare coefficients. Multiplying the resulting recurrence by successive powers of $A$ and summing telescopically yields ${\chi }_A(A)=0$.

By polynomial division, $p=q{\chi }_A+r$ with $\mathrm{deg}r<n$. Therefore $p(A)=r(A)$ by Cayley-Hamilton, while $p(\lambda )=r(\lambda )$ for every eigenvalue $\lambda$, since ${\chi }_A(\lambda )=0$.

For the displayed matrix,The remainder of $t^{1000}$ modulo this polynomial has the form $a{t}^2+c$, because its values at $i$ and $-i$ are both $1$. The equations $-a+c=1$ and $4a+c=2^{1000}$ giveSince $(A^2{)}_{11}=3$, the requested entry is