16
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ If you find a quick algorithm, tell someone, especially me or Will Orrick. Even having full access to an oracle would resolve the Hadamard matrix conjecture, with M being the identity times n. Gerhard "Ask Me About System Design" Paseman, 2011.07.16 $\endgroup$
    – Gerhard Paseman
    Jul 16, 2011 at 23:14
  • $\begingroup$ Actually, I spoke in haste. The oracle would be handy though, if it provided a no instance for some n which were multiples of 4. Gerhard "Need Say No But Once" Paseman, 2011.07.16 $\endgroup$
    – Gerhard Paseman
    Jul 16, 2011 at 23:19
  • $\begingroup$ Certainly you can check by Hasse-Minkowski whether there is a solution to your problem with $A$ rational. $\endgroup$
    – Will Jagy
    Jul 16, 2011 at 23:31
  • $\begingroup$ My guess would be that anything in the genus of $M$ works if anything else in the genus of $M$ works, so the number of classes in the genus of $M$ may not matter. $\endgroup$
    – Will Jagy
    Jul 16, 2011 at 23:38
  • 1
    $\begingroup$ @Will: checking that the determinant is a square is relatively easy: you compute the determinant (polynomial time, polynomial number of bits by Hadamard's bound), then you compute the (real) square root to one binary place. Round, and square the result. If you have the determinant you started with, you are golden. $\endgroup$
    – Igor Rivin
    Jul 17, 2011 at 18:26

3 Answers 3

Reset to default
13
$\begingroup$

A minor observation: $\left( \begin{smallmatrix} N & 0 \\ 0 & N \end{smallmatrix} \right)$ is of the form $A A^T$ if and only $N$ is of the form $a^2+b^2$. Specifically, if $N=a^2+b^2$ then $\left( \begin{smallmatrix} N & 0 \\ 0 & N \end{smallmatrix} \right) = \left( \begin{smallmatrix} a & b \\ -b & a \end{smallmatrix} \right) \left( \begin{smallmatrix} a & -b \\ b & a \end{smallmatrix} \right)$. The converse is left as an exercise.

So this problem is at least as hard as determining whether or not an integer is a sum of two squares.

We discussed the complexity of determining whether an integer is a sum of two squares here. Nobody really knew the answer, but it seemed that it might be as hard as factoring.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The Question does not mention explicitly that $A$ is a square matrix. If one drops this constraint, there is an obvious solution $A$ of size $2\times2N$, no matter what $N$ is. $\endgroup$
    – Denis Serre
    Jul 18, 2011 at 12:33
  • $\begingroup$ True, I didn't think of that interpretation. I would guess that every positive semi-definite integer matrix is of the form $A^T A$ if $A$ doesn't have to be square, but I haven't thought about it very hard. $\endgroup$
    – David E Speyer
    Jul 18, 2011 at 15:39
  • $\begingroup$ For $2 \times 2$ matrices, my comment above is IMO Shortlist 1995 problem A2. mks.mff.cuni.cz/kalva/short/soln/sh95a2.html $\endgroup$
    – David E Speyer
    Jul 18, 2011 at 17:52
  • 1
    $\begingroup$ David, sometimes it does not help to allow rectangular $A,$ see mathoverflow.net/questions/40624/… The other thing is, having read Kap's program (well, I wrote the code) a bit more carefully, he takes the $n$ principal minors and factors each determinant. $\endgroup$
    – Will Jagy
    Jul 18, 2011 at 18:03
  • $\begingroup$ Thanks! That's definitely not something I would have guessed. $\endgroup$
    – David E Speyer
    Jul 18, 2011 at 18:27
3
$\begingroup$

Let me just describe what I actually do in solving $$ M = A N A^t,$$ where $M,N$ are symmetric positive definite and integral, and I want $A$ integral.

If the determinants are small enough, I check whether $ \det M / \det N$ is an integral square. If I am sure that is false, I quit. ( I often solve $B G B^t = k F,$ where the positive integer $k$ makes the determinant ratio an integral square).

If it is worth continuing, I take the largest entry $\bar{m} = \max M_{ii}$ in the diagonal entries of $M,$ and use that to get explicit bounds on the entries of $A.$ This is easy enough, the set of row vectors $X$ with $ X N X^t = \bar{m}$ is a smooth ellipsoid, Lagrange multipliers give bounds on each entry of $X.$ Then I run a multiple loop. Each time I get some $ X N X^t = M_{jj}$ I save that $X$ as a vector in list number $j.$ Note that there is little benefit to running this search for $X$ vectors for separate diagonal entries, it is better to just run it once for $\bar{m} = \max M_{ii}.$

Finally, I have a bunch of lists of vectors, where $L_j$ is a list of all vectors that can serve as row $j.$ I run through $L_1.$ For each one, I run through $L_2.$ If the inner product $ X_1 N X_2^t = M_{1,2},$ I then go through all possible $L_3.$ And so on. If all inner product terms work out I print out the matrix $A.$ For what I do, I usually want all possible $A,$ so I do not stop after one solution.

I suppose in general what I do would be called a backtracking algorithm. The thing that is worth emphasizing is that it is just not possible to vary an entire square matrix at once, and there is no reason to do so.

EDIT: I had forgotten this. The program I wrote for Kap, very much on his instructions, was for the "oracle" part of your question. The surprise is that I wrote it for arbitrary dimension! I then put in features to take an integer sextuple and reproduce the related 3 by 3 positive symmetric matrix. What it does is compute the principal minor determinants in order, screw around with those in a recipe that goes back to Minkowski, Hasse, and Witt. It is in Mathematica. Anyway, you are welcome to it.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What sizes of matrices do you usually do this for (and what sort of coefficient sizes)? Part of the reason I wonder is that certainly for dimension > 2 the naive estimate on the running time of this is quite bad (I am thinking of $N = I,$ though one would think the general case would not be too different): without backtracking it would be something like the product of the diagonal entries to half-dimension..., so if this actually works much faster in practice, there ought to be a theorem there... $\endgroup$
    – Igor Rivin
    Jul 17, 2011 at 20:35
  • $\begingroup$ I've been thinking, I have no idea what Kap's program would do with the E_8 root lattice, even unimodular, see mathoverflow.net/questions/40624/… $\endgroup$
    – Will Jagy
    Jul 18, 2011 at 1:22
  • $\begingroup$ @Will : does "oracle" mean that your program decides wether there is an integer solution ? Or only that it satisfies all the necessary local conditions (meaning some form in the same genus has a representation) ? Also, is the number of necessary minor calculations exponential in $n$, or less ? $\endgroup$
    – BS.
    Jul 18, 2011 at 16:16
  • $\begingroup$ I'm going to be checking a little, in very small dimension (3) it is, in fact, an oracle for the integers. We get potential problems in dimension 11 or more when the identity matrix is not alone in its genus. I have not generally been concerned in any way with the possible behavior of my programs asymptotically, just that they work in the cases I am doing. $\endgroup$
    – Will Jagy
    Jul 18, 2011 at 17:45
1
$\begingroup$

This is a comment not an answer (don't have enough points to comment). If you de-symmetrize and consider $M=PQ^T$. Then you get a problem obviously harder than factoring if you choose $\det P, \det Q$ to be large primes. There should be efficient probabilistic algorithm for generating large pseudo-primes in determinant form so this may be a practical one way function. Also by choosing the size of the matrix to be moderately large say 100 , one can keep the matrix entries small and this may be advantageous. There seems to be no analogue of little Fermat (and high dimensional RSA), but there may be some other ways to use this.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ You need to exclude solutions with $\det P=\pm 1$, and especially $P=I$, if you wish to prove that this is "harder than factoring". $\endgroup$
    – Federico Poloni
    Jul 17, 2011 at 17:01
  • 2
    $\begingroup$ I'm not sure what the comment about little Fermat refers to, but for integer matrices one has $\text{tr } A^{p^n} \equiv \text{tr } A^{p^{n-1}} \bmod p^n$. See, for example, qchu.wordpress.com/2009/08/23/… . $\endgroup$
    – Qiaochu Yuan
    Jul 17, 2011 at 19:14
  • $\begingroup$ @Federico Poloni, Yes should factor out trivial factorisation $A=G(G^{-1}A)$. Thanks. @Qianchu, Was thinking if we have integer $\phi(N)$ with $M^{\phi(N)}=I$ mod $N$, obviously not possible $\endgroup$
    – Chua KS
    Jul 18, 2011 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.