Suppose $A = A^T$ and suppose the entries of $A$ are in $\mathbb{Z}^+$. I want to find all matrices
$M$ with natural entries so that:
$$M^2 = A$$
How can one do this? I know techniques that will get a square-root of an arbitrary matrix, but I want the full set. I want to be able to do this efficiently for large matrices ~$100 \times 100$.
Of course, the set must be finite because we are working over positive integers and the matrix $A$ gives upper bounds.
Best Answer
Find an invertible matrix $B$ and diagonal matrix $D$ such that $D=B^{-1}AB$. Then take all square roots $D_1,...,D_m$ (all of them diagonal, there are $m\le 2^n$ of these where $n$ is the size of $A$ because every non-negative number has at most 2 square roots) of $D$ and all matrices $BD_iB^{-1}$. Look which ones of these matrices are over natural numbers.