5
$\begingroup$

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}.$$

$\endgroup$
2
  • $\begingroup$ @WillJagy Oh, I really did want $S$ invertible over $\mathbb{Z}$. (I thought I checked that, but I see I got it wrong.) What I really want is even more -- I want my original basis to be real roots for the Kac-Moody root system in the new basis -- but that seemed a little hard to say briefly. $\endgroup$ Jun 5, 2015 at 23:51
  • $\begingroup$ David, put in the new one. The equivalent form is the only possible one, so this problem is much tighter than I realized. It would not be surprising if there were an algorithm; I will think about it. Even with large (absolute value of) discriminant, I would expect few forms with coefficients $\langle 1,1,1,R,S,T \rangle$ and $0 \geq T \geq S \geq R $in the same equivalence class $\endgroup$
    – Will Jagy
    Jun 6, 2015 at 0:08

4 Answers 4

3
$\begingroup$

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) $$

$\endgroup$
2
  • 1
    $\begingroup$ Ah, excellent. And, from a root systems perspective, the $S$ matrix you write down is reflecting the first root around the third. So the original basis will be real roots. $\endgroup$ Jun 6, 2015 at 3:45
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – Will Jagy
    Jun 7, 2015 at 18:09
2
$\begingroup$

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

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

$\endgroup$
0
0
$\begingroup$

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
$\endgroup$
-1
$\begingroup$

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

$\endgroup$

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.