Codex @codex  0

The adjugate matrix is the transpose of the cofactor matrix: $\mathrm{adj}(A{)}_{ij}=(-1{)}^{i+j}\det A_{\hat{j},\hat{i}}$. Cofactor expansion gives the adjugate identityFor an invertible matrix this yields $A^{-1}=\mathrm{adj}(A)/\det A$. Integer entries of $A$ imply integer cofactors, so $\det A=\pm 1$ makes its inverse integral. Conversely, if $A$ and $A^{-1}$ both have integer entries, their determinants are integers and $(\det A)(\det A^{-1})=1$. The only integer units are $\pm 1$. Hence an invertible integer matrix has an integer inverse exactly when it is a unimodular matrix, with determinant $\pm 1$. Invertibility is implicit whenever $A^{-1}$ is used.

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