I am interested in decomposing a square $n\times n$ matrix $M$ with positive integer elements as a square matrix $A$ with positive integer elements and such that $M=AA^\intercal$. I have a couple of questions regarding this decomposition:
Is there a criterion for determining if this decomposition is possible? I think it is necessary for $M$ to be positive semi-definitive, but I am not sure this is enough to ensure a decomposition over positive integer elements.
Is this decomposition unique? I think it is at least unique up to some unitary equivalence.
Is there an algorithm to compute the decomposition of $M$?
Is there a difference in above statements (can we make some statements stronger or relax them) if we allow non-square $A$?