I'm trying to prove the following relation for a matrix $A\in \mathbb{Z}^{m\times m} $, $m\geq 2$. It is assumed that the characteristic polynomial of $A$ is primitive modulo $2$:

If $C$ is defined to be the remainder of $A^{2^m-1}\pmod{4}$ , i.e. $$A^{2^m-1}\equiv I+2C \pmod{4}$$ Then prove $$\textrm{det}(C)\equiv \textrm{det}(C+I)\equiv 1 \pmod{2}$$

My try: $$2C\equiv A^{2^m-1}-I\pmod{4}\Rightarrow C\equiv \frac{1}{2}(A^{2^m-1}-I)\pmod{2}$$

$$ \textrm{det}(C)\equiv \textrm{det}(\frac{1}{2}(A^{2^m-1}-I)) \pmod{2}$$

Then for $C+I$ $$C+I\equiv \frac{1}{2}(A^{2^m-1}-I)+I \equiv \frac{1}{2}(A^{2^m-1}+I)\pmod{2}$$

Therefore to prove the statement we must have: $$ \textrm{det}(\frac{1}{2}(A^{2^m-1}-I))\equiv \textrm{det}(\frac{1}{2}(A^{2^m-1}+I)) \equiv 1 \pmod{2} $$

Or $$\frac{1}{2^m}\textrm{det}(A^{2^m-1}-I)\equiv \frac{1}{2^m}\textrm{det}(A^{2^m-1}+I) \equiv 1 \pmod{2}$$ $$\Rightarrow\textrm{det}(A^{2^m-1}-I)\equiv \textrm{det}(A^{2^m-1}+I) \equiv 2^{m} \pmod{2^{m+1}}$$ If we call $P_{A^{2^m-1}}(\lambda)$ the characteristic polynomial of $A^{2^m-1}$ then I know that $\textrm{det}(A^{2^m-1}-\lambda I)\equiv P_{A^{2^m-1}}(\lambda)$, and therefore $$\textrm{det}(A^{2^m-1}-I)= P_{A^{2^m-1}}(1)\,,\textrm{det}(A^{2^m-1}+I)= P_{A^{2^m-1}}(-1)$$

EDIT: I've found out here that if eigenvalues of $A$ are $y_i$ then eigenvalues of $A^n$ will be $y_i^n$, however $y_i$ might be complex. Therefore: $$P_{A}(\lambda)=\prod_{i=0}^m(\lambda-y_i)\Rightarrow P_{A^{2^m-1}}(\lambda)=\prod_{i=0}^m(\lambda-y_i^{2^m-1})$$ Then I tried to compute each coefficient of $P_{A^{2^m-1}}$ in terms of coefficients of $P_{A}$, which leads to some kind of generalization of Newton identities I asked it here, however it seems it is not possible to compute all of them (Question has received no general answer yet).

I couldn't continue it further.


I've tested a few matrices (of degrees 2,3,4,5) with computer and the statement was true for them.

Primitive here means that the characteristic polynomial of $A$, $q(t)=\textrm{det}(A-tI)=t^m+a_1t^{m-1}+\ldots+a_m$, be primitive (irreducible) modulo 2. $$A=\left(\begin{array}{cccc} a_1 & \ldots & a_{m-1}& a_m\\ 1 & \ldots & 0 & 0\\ \vdots & \ddots & \vdots &\vdots\\ 0 & \ldots &1 & 0 \end{array}\right)$$

Important Edit:

An additional assumption is required for $P_A(x)$ modulo 4. Which is:

If $P_A(x)\equiv f(x^2)+xg(x^2)\pmod 2$ then the above claim is not true only if: $P_A(x)\equiv f(x)^2+xg(x)^2\pmod 4$


The claim is not true for $m=2$: Take $$ A=\pmatrix{1& 3\\1& 0}, \quad p_A = x^2-x-3 $$ $$ A^3 =\pmatrix{7 & 12 \\ 4 & 3} \equiv \pmatrix{3&0\\0&3} \equiv I + 2I \pmod 4 $$ hence $2C \equiv 2I \pmod 4$, $C\equiv I \pmod 2$, and $C+I\equiv 0\pmod2$, in contradiction to the claim $det(C+I)\equiv 1\pmod 2$.

Here is another counterexample for $m=3$: $$ A =\pmatrix{0&0&1\\ 1&0&3\\0&1&2}, \quad A^7 \equiv I \pmod 4, $$ hence $C=0$. The characteristic polynomial is $p_A=x^3+x+1$ modulo $2$, which is irreducible.

In the constructions above, I exploited the following. Denote by $p_{A,2}$ and $p_{A,4}$ the characteristic polynomials of $A$ modulo $2$ and $4$. The difference between them, $p_{A,4} - p_{A,2}$ was chosen to have degree $m-1$. This difference has even coefficients.

Then using the factorization of $A^{2^m-1}-I=(A-I)(A^{2^m-2}+\dots + I)$, using $p_{A,4}(A)=0$ to reduce the degree of the polynomial, one gets an expression for $C$, which depends on $A$ and $(p_{A,4}-p_{A,2})/2$. Chosing the latter to get $\det(C)=0$ was then the last step.

In the case $m=2$, the claim is true if and only if $p_{A,4}$ has at least one coefficient from $\{2,3\}$. Here, $p_{A,2}=x^2+x+1$ anyway. It holds $$ A^3-1 = (A-I)(A^2+A+I). $$ If $p_{A,4} = x^2+x+1$, then $A^3-I\equiv 0 \pmod 4$, and $C=0$. If not, then $p_{A,4} = x^2+x+1 + 2q$, where $q\in \{1,x,1+x\}$. Then $$ A^3-1 \equiv (A-I)(2M) \pmod 4, $$ where $M\in \{I,A,I+A\}$. Hence $$ C\equiv (A-I)M \equiv (A+I)M\pmod 2, $$ and $\det(C)\equiv 1\pmod 2$, since $$ \det(A) \equiv p_{A,2}(0) = 1, \ \det(I+A)\equiv p_{A,2}(1) = 1 \pmod 2. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.