MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Suppose I have a symmetric positive definite matrix $M$ with integer entries. I want to decide whether $M = A A^t,$ with $A$ likewise integral. I assume that decision problem is NP-complete, as is the question of finding the $A$ even if an oracle tells you such an $A$ exists. Can someone provide a reference (I would very much like to be wrong about the hardness of the problem...)

EDIT A remark: this question is equivalent to finding a collection of integral vectors (the columns of $A$) with prescribed distances (by the parallelogram law, the inner products give us the distances). If we require $A$ to be a $0-1$ matrix, I am pretty sure that this can encode knapsack, so is NP-complete. It seems that as per Will Jagy and Gerhard Paseman, this question (via Hasse-Minkowski) might only be as hard as factoring (which is generally conjectured to be less than NP-complete), but I haven't yet completely understood what is entailed in the Hasse-Minkowski approach...

Further EDIT

In fact, the Hasse local-to-global principle works fine for small dimensions, since the class number of identity equals one in that case, and one can enumerate solutions by the Smith-Minkowski-Siegel mass formula. This apparently works only in dimension at most eight. This gives the oracle (the wiki article cited seems to imply that the right hand side can be computed in polynomial time, though I am none-too-certain of this), so this gives the required oracle in small dimensions, though not obviously an algorithm for finding solutions. In dimensions greater than eight we seem to be sunk.

3 edited tags
Suppose I have a symmetric positive definite matrix $M$ with integer entries. I want to decide whether $M = A A^t,$ with $A$ likewise integral. I assume that decision problem is NP-complete, as is the question of finding the $A$ even if an oracle tells you such an $A$ exists. Can someone provide a reference (I would very much like to be wrong about the hardness of the problem...)
EDIT A remark: this question is equivalent to finding a collection of integral vectors (the columns of $A$) with prescribed distances (by the parallelogram law, the inner products give us the distances). If we require $A$ to be a $0-1$ matrix, I am pretty sure that this can encode knapsack, so is NP-complete. It seems that as per Will Jagy and Gerhard Paseman, this question (via Hasse-Minkowski) might only be as hard as factoring (which is generally conjectured to be less than NP-complete), but I haven't yet completely understood what is entailed in the Hasse-Minkowski approach...