3
$\begingroup$

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
    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)$?2011-07-19
  • 0
    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.2011-07-19
  • 0
    @Peter: I assume it means a matrix whose entries are in the ring $\mathbb{Z}/n\mathbb{Z}$.2011-07-19
  • 3
    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$.2011-07-19
  • 0
    Arturo - Of course, I know that works. I am wondering though 1. How to diagonalize efficiently when it can be done (something like Berlekamp's algorithm?), and 2. what to do when the matrix is a square but not diagonalizable, or if the diagonal entries aren't squares. In particular, if I choose a matrix M, and tell you its square, how often can you tell me M?2011-07-19
  • 1
    @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.2011-07-20

0 Answers 0