Is it easy (computationally) to take square roots of matrices over Z/nZ, if you know the factorization of n?

If the matrix is diagonalizable, then does diagonalizing and taking the square roots work? What if the matrix isn't diagonalizable, or if the diagonal has entries which aren't squares? What does this imply about square roots of the matrix?

Sorry for not phrasing this question well originally. I am interested in finding ANY square root. But finding a random square root is even better. Also, you can imagine the input to be the square of a random matrix.

  • 1
    $\begingroup$ A square root of a matrix need not be unique. e.g. $\left( \begin{array}{cc} 0 & 1 \\ 0 & 0 \\ \end{array} \right)$ and $ \left( \begin{array}{cc} 0 & 0 \\ 0 & 0 \\ \end{array} \right)$ both satisfy $A^2 = 0$. So how would you define the square root of the $0$ matrix? Would it be $ \left( \begin{array}{cc} 0 & 1 \\ 0 & 0 \\ \end{array} \right)$ or $ \left( \begin{array}{cc} 0 & 0 \\ 0 & 0 \\ \end{array} \right)$? $\endgroup$ – algebra_fan Jul 19 '11 at 19:34
  • $\begingroup$ By the way, the $0$ matrix in my previous example is diagonalizable (it's already diagonal), so as the previous example shows, taking square roots of the diagonal entries does not produce all square roots of a matrix. $\endgroup$ – algebra_fan Jul 19 '11 at 19:37
  • $\begingroup$ @Peter: I assume it means a matrix whose entries are in the ring $\mathbb{Z}/n\mathbb{Z}$. $\endgroup$ – Qiaochu Yuan Jul 19 '11 at 19:42
  • 3
    $\begingroup$ If the matrix is diagonalizable and the entries are squares, say $P^{-1}AP = \mathrm{diag}(\lambda_1,\ldots,\lambda_n)$, and picking $\rho_i$ with $\rho_i^2=\lambda_i$, then $B=P\mathrm{diag}(\rho_1,\ldots,\rho_n)P^{-1}$ is a square root of $A$. But the condition is not necessary: the matrix $2I_2$ is diagonal over $\mathbb{Z}/3\mathbb{Z}$, the diagonal entries are not squares, but $\left(\begin{array}{cc}0&2\\1&0\end{array}\right)^2 = 2I_2$. $\endgroup$ – Arturo Magidin Jul 19 '11 at 20:33
  • 1
    $\begingroup$ @Jeff: I would expect diagonalization algorithms that work over finite fields would be a good way to go, though you may run into trouble when working over $\mathbb{Z}/n\mathbb{Z}$; as to what to do in the other cases, I don't know off-hand. $\endgroup$ – Arturo Magidin Jul 20 '11 at 5:30

Your Answer

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

Browse other questions tagged or ask your own question.