From a (not positive definite) Gram matrix to a (Kac-Moody) Cartan matrix Suppose I am given a symmetric matrix $G_{ij}$ with $G_{ii} = 2$. Can I always find an invertible integer matrix $S$ such that $(S^T G S)_{ii}=2$ and $(S^T G S)_{ij} \leq 0$ for $i \neq j$? Is there a practical algorithm to do so?
If you'd like a particular challenge, I'd like to know the answer for
$$G = \begin{pmatrix}
2 & -4 & 3 \\
-4 & 2 & -2 \\
3 & -2 & 2 \\
\end{pmatrix}.$$
 A: There is an algorithm, based on a 1907 article of Hurwitz I mention sometimes, based in turn on the tree of Markov numbers. 
We begin with a ternary quadratic form $\langle 1,1,1,r,s,t \rangle.$ The (Lehman) discriminant of this is 
$$ 4 + rst - r^2 - s^2 - t^2.  $$ We would like to know whether we can find replacement values of $r,s,t$ so that all are nonpositive. Note first that this means the maximum discriminant we can allow is $4;$ anything bigger and we are out of luck as far as getting nonpositive off-diagonal coefficients.
Next note that we can always negate two $(rst)$ coefficients at a time. We can also permute $rst$ as we like. 
What we actually do is an operation on the $(r,s,t)$ triples. Suppose that $r$ has opposite sign to $st,$ so that $|st-r| < |r|.$ If $r$ is the largest entry (in absolute value) for which this is true, we replace $r$ by $st-r$ and keep the same discriminant. Give me a few minutes to fiddle with matrices and find out what $3$ by $3$ matrix, of the type that David calls $S,$ that corresponds to this Hurwitz flip. Hurwitz gave no name to the operation; the high schoolers on MSE call it Vieta jumping.  Well; in order to have $rst$ negative, or nonpositive, we must have their absolute values fairly small. 
Later: the jump specified above goes with the matrix product
$$ 
\left(
\begin{array}{rrr}
      1  &    0 &     0 \\ 
     0  &    1   &   0 \\ 
     s    &  0  &    -1
\end{array}
\right) 
\left(
\begin{array}{rrr}
      2  &    t &     s \\ 
     t  &    2   &   r \\ 
     s    &  r  &    2
\end{array}
\right)
\left(
\begin{array}{rrr}
      1  &    0 &     s \\ 
     0  &    1   &   0 \\ 
     0    &  0  &    -1
\end{array}
\right) =
\left(
\begin{array}{rrr}
      2  &    t &     s \\ 
     t  &    2   &   st-r \\ 
     s    &  st-r  &    2
\end{array}
\right)
$$
Here is another, which could be found from the first with some permutations on both sides.
$$ 
\left(
\begin{array}{rrr}
      -1  &    0 &     s \\ 
     0  &    1   &   0 \\ 
     0    &  0  &    1
\end{array}
\right) 
\left(
\begin{array}{rrr}
      2  &    t &     s \\ 
     t  &    2   &   r \\ 
     s    &  r  &    2
\end{array}
\right)
\left(
\begin{array}{rrr}
      -1  &    0 &     0 \\ 
     0  &    1   &   0 \\ 
     s    &  0  &    1
\end{array}
\right) =
\left(
\begin{array}{rrr}
      2  &   rs- t &     s \\ 
     rs-t  &    2   &   r \\ 
     s    &  r  &    2
\end{array}
\right)
$$
Third:
$$ 
\left(
\begin{array}{rrr}
      1  &    0 &     0 \\ 
     0  &    1   &   0 \\ 
     0    &  r  &    -1
\end{array}
\right) 
\left(
\begin{array}{rrr}
      2  &    t &     s \\ 
     t  &    2   &   r \\ 
     s    &  r  &    2
\end{array}
\right)
\left(
\begin{array}{rrr}
      1  &    0 &     0 \\ 
     0  &    1   &   r \\ 
     0    &  0  &    -1
\end{array}
\right) =
\left(
\begin{array}{rrr}
      2  &    t &     rt-s \\ 
     t  &    2   &   r \\ 
     rt-s    &  r  &    2
\end{array}
\right)
$$
A: It is also possible to solve this with (integrally) invertible $S,$ as
$$ S =
\left(
\begin{array}{rrr}
      1  &    0 &     0 \\ 
     0  &    3   &   -2 \\ 
     -3    &  2  &    -1
\end{array}
\right)
$$
    parisize = 4000000, primelimit = 500509
    ? s =[      1  ,    0  ,    0;       0   ,   3  ,    -2 ;     -3   ,   2  ,    -1]
    %1 = 
    [1 0 0]

    [0 3 -2]

    [-3 2 -1]

    ? g = [ 2,-4,3; -4,2,-2; 3,-2,2 ]
    %2 = 
    [2 -4 3]

    [-4 2 -2]

    [3 -2 2]

    ? ss = mattranspose(s)
    %3 = 
    [1 0 -3]

    [0 3 2]

    [0 -2 -1]

    ? ss * g * s
    %4 = 
    [2 0 -1]

    [0 2 -2]

    [-1 -2 2]

? matdet(g)
%5 = -2
? matdet( ss * g * s)
%6 = -2

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
A: Well, having all sorts of trouble with 4 by 4. Apparently there is no trouble sending the $G$ below to $W^t G W$ of the same determinant and diagonal entries, but with nonpositive off-diagonal entries. However, i have had absolutely no luck performing this by  the steps that were so successful in the 3 by 3 case. Sigh.
parisize = 4000000, primelimit = 500509
? w = [   2,    1,   -1,   -1;   -2,    0,    1,   -1;    1,    0,    0,    1;   -2,    0,    0,   -1]
%1 = 
[2 1 -1 -1]

[-2 0 1 -1]

[1 0 0 1]

[-2 0 0 -1]

? matdet(w)
%2 = 1
? a = 1;b=2;c=3;d=4;e=5;f=6;
? g = [2,a,b,c; a,2,d,e; b,d,2,f; c,e,f,2]
%4 = 
[2 1 2 3]

[1 2 4 5]

[2 4 2 6]

[3 5 6 2]

? mattranspose(w) * g * w
%5 = 
[2 -2 -6 -2]

[-2 2 -1 -4]

[-6 -1 2 0]

[-2 -4 0 2]

? matdet(g)
%6 = 144

A: Wondering how well this would work out in $4$ by $4,$ given that David says the individual steps in the "algorithm" preserve something important:
$$ G =
\left(
\begin{array}{cccc} 
2 & a & b & c \\
a & 2 & d & e \\
b &   d & 2 & f \\ 
c & e & f& 2
\end{array}
\right)
$$
$$ \det G = a^2  f^2 + b^2  e^2 + c^2  d^2 - 2  (a  b  e  f + a  c  d  f + b  c  d  e) + 4  (a  b  d + a  c  e + b  c  f + d  e  f) -4  ( a^2 + b^2 + c^2 + d^2 + e^2 + f^2   ) + 16 $$
where the degree four terms can be regarded as the indefinite ternary form $\langle 1,1,1,-2,-2,-2 \rangle$ in $x=af, y=be,z=cd.$
$$ S =
\left(
\begin{array}{cccc} 
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 &   0 & 1 & f \\ 
0 & 0 & 0& -1
\end{array}
\right)
$$
$$ S^t G S =
\left(
\begin{array}{cccc} 
2 & a & b & fb-c \\
a & 2 & d & fd-e \\
b &   d & 2 & f \\ 
fb-c & fd-e & f& 2
\end{array}
\right)
$$
So, this basic operation (an involution) flips two positions at once..
$$ T =
\left(
\begin{array}{cccc} 
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 &   0 & -1 & 0 \\ 
0 & 0 & f& 1
\end{array}
\right)
$$
$$ T^t G T =
\left(
\begin{array}{cccc} 
2 & a & fc-b & c \\
a & 2 & fe-d & e \\
fc-b &   fe-d & 2 & f \\ 
c & e & f& 2
\end{array}
\right)
$$
hmmmm.......
Just checking, 
$$ N_1 =
\left(
\begin{array}{cccc} 
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 &   0 & 1 & 0 \\ 
0 & 0 & 0& -1
\end{array}
\right)
$$
$$ N_1 G N_1 =
\left(
\begin{array}{cccc} 
2 & a & b & -c \\
a & 2 & d & -e \\
b &   d & 2 & -f \\ 
-c & -e & -f& 2
\end{array}
\right)
$$
$$ N_2 =
\left(
\begin{array}{cccc} 
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 &   0 & -1 & 0 \\ 
0 & 0 & 0& -1
\end{array}
\right)
$$
$$ N_2 G N_2 =
\left(
\begin{array}{cccc} 
2 & a & -b & -c \\
a & 2 & -d & -e \\
-b &   -d & 2 & f \\ 
-c & -e & f& 2
\end{array}
\right)
$$
Right, that is enough to know on these because $-I$ changes nothing.
Really ought to see what a permutation, a single transposition, does
$$ T_2 =
\left(
\begin{array}{cccc} 
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 &   0 & 0 & 1 \\ 
0 & 0 & 1 & 0
\end{array}
\right)
$$
$$ T_2 G T_2 =
\left(
\begin{array}{cccc} 
2 & a & c & b \\
a & 2 & e & d \\
c &   e & 2 & f \\ 
b & d & f& 2
\end{array}
\right)
$$
Swaps two pairs
