# 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. May 25, 2016 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... May 25, 2016 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. May 25, 2016 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$. May 25, 2016 at 15:47
• I agree; the problem seems to be in how to arrange the successive unimodular transformations for that condition to hold. May 25, 2016 at 15:50