# Finding an Integer, Unimodular Matrix that connects two given matrices

I have two symmetric, integer matrices, $K$ and $K_2$ which have the same determinant and the same signature (number of positive - number of negative eigenvalues). I want to find an integer valued matrix, $X$, such that $$X^T K X= K_2$$ and determinant of $X = \pm 1$.

For example,

K = {{0, 2, 1, 1}, {2, 0, 0, 0}, {1, 0, 1, 0}, {1, 0, 0, -1}};
K2 = {{0, 2, 0, 0}, {2, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, -1}};


Is there a way to approach this besides using FindInstance (which doesn't seem to work in finite time for even a $4\times4$ matrix)? The system is under constrained since the matrices are symmetric, but I'm just looking for a way to find even one such $X$ for a given pair, $K$ and $K_2$, which could be as large as $8\times8$.

Using Smith Normal Form you can get two integer matrices with determinant 1 that would satisfy the equation

$$X1.K.X2 = K_2$$

May be this is a good start you can use...

resK = SmithDecomposition[K];
MatrixForm /@ resK

resK2 = SmithDecomposition[K2];
MatrixForm /@ resK2

resK[] == resK2[]
(* True *)

K2 ==
Inverse[resK2[]].resK[].K.resK[].Inverse[resK2[]]
(* True *)

X1 = Inverse[resK2[]].resK[];

X2 = resK[].Inverse[resK2[]];

X1.K.X2 == K2
(* True *)

Det /@ {X1, X2}
(* {1, 1} *)

MatrixForm /@ {X1, X2} • Yes, both the Smith and Hermite decompositions do involve unimodular factors, but I don't see a straightforward way to derive a congruence transformation from them, which is what the OP apparently seeks. – J. M.'s technical difficulties May 25 '16 at 14:48
• @J.M. Well the OP asks for two matrices satisfying four conditions, and apparently two matrices satisfying three of them for the matrices provided can be found not using FindInstance. This might be good enough or a good start... – Anton Antonov May 25 '16 at 15:20
• Hmm, the OP already has $k$ and $k_2$, and is only looking for one matrix that does the required congruence. I'm just saying it does not seem to look straightforward to do with those two decompositions. – J. M.'s technical difficulties May 25 '16 at 15:26
• @J.M. "[...] only looking for one matrix that does the required congruence" -- I see one of the conditions for $X1.K.X2=K2$ to be $X1=X2^T$. – Anton Antonov May 25 '16 at 15:47
• I agree; the problem seems to be in how to arrange the successive unimodular transformations for that condition to hold. – J. M.'s technical difficulties May 25 '16 at 15:50