2
$\begingroup$

Consider the equation: $$ C \equiv HMH^{-1} \pmod{p}, $$ where $C,M, H$ are, say, $2\times 2$ matrices, and $p$ is an odd prime. The elements of the matrices $C, M$ are integers. The elements of the matrix $H$ are the unknowns (call them $h_{11}, h_{12}, h_{21}, h_{22}$). I am trying to solve this system for the unknowns $h_{11}, h_{12}, h_{21}, h_{22}$.

Here is my approach:

$$ C \equiv HMH^{-1} \pmod{p} $$ implies that $$CH = HM.$$ This will result in four linear equations in $h_{11}, h_{12}, h_{21}, h_{22}$. That is, we have

$$W \> h \equiv 0 \pmod{p},$$ where ${h} = transpose(h_{11}, h_{12}, h_{21}, h_{22}). $ Now for the system to have non-trvial solution the matrix $W$ must be singular in $Z_p$ (i.e. $\det(W) \equiv 0 \pmod{p}$). This also would imply that the system $$W \> { h} \equiv 0 \pmod{p},$$ has at least one free variable, and hence, this system has at least $p-1$ non-trivial solutions.

Is the argument above correct? Any help with this will be highly appreciated. Thanks in advance!

$\endgroup$
2
1
$\begingroup$

@user244486,

  1. There is no general formula.

  2. Clearly, the associated theory is too complicated for you.

  3. Seek the solutions $H\in M_2(F)$ over $F=\mathbb{Z}/3\mathbb{Z}$ when $C=\begin{pmatrix}1&2\\1&1\end{pmatrix},\ M=\begin{pmatrix}a&1\\1&2\end{pmatrix}$. In particular, how to choose $a$ so that there are solutions ?

EDIT. Answer to user244486. It remains to find explicitly all the solutions in $H$ (there are $4$; why ?). Note that there are no eigenvalues of $C,M$ in $F$; indeed they are in an algebraic extension of $F$. Yet $C,M$ are similar over $F$ (this is a theorem !).

$\endgroup$
2
  • $\begingroup$ In this particular example, choose $a$ such that characteristic polynomial of $C$ and $M$ are identical. Setting $a=0$ results in trace($M$) = Trace($C$) = 2, $\det(M)=\det(C) = -1$. $\endgroup$
    – user244486
    Jun 2 '15 at 1:18
  • $\begingroup$ Do you mind sharing the associated theory? $\endgroup$
    – user244486
    Jun 2 '15 at 1:22
0
$\begingroup$

As far I see you are trying to decide if the matrix $C$ and $M$ are similar. See for example http://en.wikipedia.org/wiki/Matrix_similarity. A necessary condition for the existence of $H$ is going to be that the so called carateristic polinomial of $C$ and $M$ are the same, i.e. $\det(C) = \det(M)$ and ${\rm trace}(C) = {\rm trace}(M)$. But this conditions are not sufficient. Take for example $C = \left( \begin{array}{cc} 0 & 1 \\ 0 & 0 \\ \end{array} \right)$ and $M = \left( \begin{array}{cc} 0 & 0 \\ 0 & 0 \\ \end{array} \right)$.

Turning to your question. I think the condition $\det(W) = 0$ you got is equivalent to $\det(C) = \det(M)$ (but I did not check it). If this is so then of course the system $W.h = 0$ has a non trivial solution but could happen that the nonzero matrix $H$ you got is not invertible hence does not give you a solution of your original question i.e. if $C = H M H^{-1}$.

Summing up what you have to realize is that you are doing linear algebra in a vector space over a finite field. Then you can apply the standard techniques to solve the problem : given $C$ and $M$ does there exists $H$ such that $C = H M H^{-1}$ ? If you want I can give you the necessary and sufficient conditions for the existence of such $H$.

$\endgroup$
2
  • $\begingroup$ My guess is that the necessary and sufficient condition is that both of the matrices $M$ and $C$ have the same Jordan normal form? This is just a guess? $\endgroup$
    – user244486
    Jun 2 '15 at 1:06
  • $\begingroup$ The OP question was about $2 \times 2$ matrices so in this case the necessary and sufficient condition is : either the characteristic polynomial has two different roots or in case that the characteristic polynomial has a double root then both matrices are already diagonal or both matrices are non diagonal. Of course saying $M$ and $C$ had the same Jordan normal form is also a correct assertion but it preassume that you know the Jordan normal form. In such a case perhaps it is better to use the so called Rational Normal Form. $\endgroup$
    – Holonomia
    Jun 2 '15 at 9:54

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.