Finding integer roots of an integer quadratic form

Question

Let $ Q\in \mathbb{Z}[x_1, \dots, x_n ] $ be an integer quadratic form. That is, $ Q $ is a homogeneous degree $ 2 $ polynomial with integer coefficients. Is there a good way to determine if $ Q $ has any integer roots (other than all $ 0 $)?

I don't know if this helps but in the example I'm thinking about there are about $ 20 $ variables and the coefficients are very small, $ < 10 $.

For context I have a set $ \mathcal{E} $ of 15 orthogonal matrices with integer entries and I'm trying to find integer zeroes of the quadratic form $ Q $: $$ Q(x_{ij}):= \sum_{E \in \mathcal{E}}(\text{Tr}(EX))^2−\sum_{E \in \mathcal{E}}\text{Tr}(EXE^{−1}X) $$ where the variables I am solving for are the entries of the symmetric matrix $ X $, and $\text{Tr}$ is the trace.

I would even be satisfied if I could determine if $ Q $ has real roots. But integer roots are preferable.

Answer 1

$ \newcommand\trans{^{\mathrm T}} \newcommand\span{\mathrm{span}} $You're looking for "isotropic elements of $Q$ in the module $\mathbb Z^n$". This is the same as finding roots over the vector space $\mathbb Q^n$ because if you have such a root $x$ then $ax \in \mathbb Z^n$ for some $a \in \mathbb Z$.

I will start with the real case because it is easier, and then explain what changes with $\mathbb Q$.

---

For existence of real roots you just have to check that $Q$ is not positive- or negative-definite.

To find real roots, you can diagonalize: form the symmetric matrix $M$ such that $x\trans Mx = Q(x)$ with $x = (x_1,\dotsc,x_n)\trans$ and diagonalize $M = V\trans DV$. If $e_i = (0,\dotsc,1,\dotsc,0)\trans$ with $1$ in the $i^\text{th}$ position (so that $\{e_i\}_{i=1}^n$ forms the standard basis of $\mathbb R^n$) then $f_i = V^Te_i$ is an orthogonal basis for $Q$. By construction $Q(f_i) = D_{ii}$. The signature $(p, q, r)$ of $Q$ is the number of $f_i$ such that $Q(f_i) > 0$, $Q(f_i) < 0$, and $Q(f_i) = 0$, respectively.

We could also start with a basis of $\mathbb R^n$ and apply Gram-Schmidt, but there are edge cases to consider when $Q$ is not definite.

Let $a_1,\dotsc,a_p$ be those $f_i$ with $Q(f_i) > 0$, let $b_1,\dotsc,b_q$ those with $Q(f_i) < 0$, and $c_1,\dotsc,c_r$ those with $Q(f_i) = 0$. Also normalize $a_1,\dotsc,a_p$ so that $Q(a_i) = 1$ and normalize $b_1,\dotsc,b_q$ so that $Q(b_i) = -1$.

If $r \ne 0$ then all linear combinations of $c_1,\dotsc,c_r$ give a root of $Q$. These are called radical vectors. However, I can easily imagine you constructed $Q$ such that $r = 0$ and there are no radical vectors. From here on we assume $r = 0$.

From here, every vector $v$ is of the form $$ v = \alpha_1a_1 + \dotsb + \alpha_qa_p + \beta_1b_1 + \dotsb + \beta_qb_q $$ and $v$ is isotopic iff $$ \sum_{i=1}^p\alpha_i^2 - \sum_{j=1}^q\beta_j^2 = 0. $$ But we can say some more.

The quantity $w = \min\{p, q\}$ is precisely the Witt index of $Q$. This is the dimension of a maximal totally isotropic subspace, i.e. a subspace of maximal dimension where all vectors are isotropic and so roots of $Q$. If $w = 0$ then $q = 0$ or $p = 0$ and $Q$ is positive- or negative-definite and has no roots.

If $w \ne 0$, then we can construct two such maximal totally isotropic subspace $W, W'$ by pairing up basis vectors. Define $\nu_i = a_i + b_i$ and $\eta_i = a_i - b_i$ for (say) $i = 1,\dotsc,w$. Then $Q(\nu_i) = Q(\eta_i) = 0$ and we can take $$ W = \span\{\nu_1,\dotsc,\nu_w\},\quad W' = \span\{\eta_1,\dotsc,\eta_w\}. $$ These subspaces are complementary in the sense that we can construct $W'$ knowing just $W$ and vice versa. The space $H = W \oplus W'$ is called a hyperbolic subspace. Finding more isotropic vectors in $H$ is easy; every vector $v \in H$ may be written $$ v = \alpha_1\nu_1 + \dotsb + \alpha_w\nu_w + \beta_1\eta_1 + \dotsb + \beta_w\eta_w $$ where $\alpha_i, \beta_i \in \mathbb R$. If every pair $(\alpha_i,\beta_i)$ has $\alpha_i = 0$ or $\beta_i = 0$ then $v$ is isotropic; more generally $v$ is isotropic iff $\sum_i\alpha_i\beta_i = 0$.

If $p \ne q$ then we still have some $a_{w+1},\dotsc,a_p$ or $b_{w+1},\dotsc,b_q$ remaining. Let $m = \max\{p,q\}$ and call these $\xi_1,\dotsc,\xi_{m-w}$. These span a subspace $A = \span\{\xi_1,\dotsc,\xi_{m-w}\}$ which is anisotropic, meaning there are no isotropic vectors. Any of $\xi_1,\dotsc,\xi_{m-q}$ can replace $a$ or $b$ (whichever is appropriate) in the construction of $W, W'$ to get other maximal totally isotropic subspaces.

Returning briefly to $r$ not necessarily $0$ and defining $R = \span\{c_1,\dotsc,c_r\}$, the decomposition $$ \mathbb R^n = A\oplus H\oplus R $$ is called a Witt decomposition of $\mathbb R^n$, and the dimensions of each piece are invariants of $Q$.

To be clear, not all isotropic vectors lie in $W$ or $W'$, this is just a convenient way of constructing many of them.

---

When we consider $\mathbb Q^n$ instead of $\mathbb R^n$, much of this is the same. There are two potential difficulties I see:

1. Diagonalizing $M$ rationally. In this case it is probably best to apply Gram-Schmidt or another orthogonalization algorithm, but I don't have much knowledge of this.
2. The vectors $f_i$ cannot be normalized unless $Q(f_i)$ is a perfect square in $\mathbb Q$. My construction of totally isotropic subspaces requires that $Q(a_i) = -Q(b_i)$, and there's no way to achieve this unless there is $\delta \in \mathbb Q$ such that $\delta^2Q(a_i) = -Q(b_i)$ whence we can replace $a_i$ with $\delta a_i$.

Answer 2

Your problem is the same problem has finding rational because, if $x$ is a zero, so is $ax$ for all $a\in\mathbb{Q}^\times$.

If you want to have any non trivial zero, you must have a real zero.

You may compute the rank and the signature of your quadratic $Q$ (viewed as a rational quadratic form), and then decide.

More precisely:

Viewing $Q$ has a rational quadratic form, you can use Gauss reduction to write $Q=\sum_{i=1}^r \alpha_i L_i^2$, where $L_1,\ldots,L_r$ are linearly independent $\mathbb{Q}$-linear forms, and $\alpha_i\in\mathbb{Q}^\times$.

If $r<n$, then $\bigcap_i\ker(L_i)$ is non trivial, and contain a non zero rational vector, hence (multiplying by a suitable integer) an nonzero integer vector, and we are done.

So assume now that $r=n$.

At this point, $Q$ has a non trivial real zero if and only if $Q$ is indefinite, that is the $\alpha_i$'s do not all have the same sign (Keyword: signature of quadratic form).

Now you are in luck: if $n\geq 5$ and $Q$ is indefinite, then a difficult theorem of Hasse Minkowski says that $Q$ has a non trivial zero. However, it does not produce you a way to compute it.

Answer 3

I made up a problem ... I typed in a bunch of nubers as a six by six matrix. Then I had gp-pari add it to its transpose, making a symmetric matrix with even numbers on the diagonal. Then I had my first program diagonalize over the integers.

Maybe I will have the patience to get something with the other program, stick with integers and try for fewer off-diagonal elements

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ P^T H P = D $$

$$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ - \frac{ 9 }{ 2 } & 1 & 0 & 0 & 0 & 0 \\ \frac{ 37 }{ 53 } & - \frac{ 73 }{ 53 } & 1 & 0 & 0 & 0 \\ - \frac{ 36 }{ 59 } & \frac{ 20 }{ 59 } & - \frac{ 42 }{ 59 } & 1 & 0 & 0 \\ \frac{ 315 }{ 79 } & - \frac{ 1394 }{ 237 } & \frac{ 407 }{ 79 } & - \frac{ 1399 }{ 474 } & 1 & 0 \\ - \frac{ 2161927 }{ 175346 } & \frac{ 3046161 }{ 175346 } & - \frac{ 2849569 }{ 175346 } & \frac{ 912841 }{ 87673 } & - \frac{ 341933 }{ 87673 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 2 & 9 & 11 & 6 & 6 & 8 \\ 9 & 14 & 13 & 10 & 9 & 10 \\ 11 & 13 & 8 & 8 & 15 & 15 \\ 6 & 10 & 8 & 14 & 35 & 21 \\ 6 & 9 & 15 & 35 & 240 & 733 \\ 8 & 10 & 15 & 21 & 733 & 42 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & - \frac{ 9 }{ 2 } & \frac{ 37 }{ 53 } & - \frac{ 36 }{ 59 } & \frac{ 315 }{ 79 } & - \frac{ 2161927 }{ 175346 } \\ 0 & 1 & - \frac{ 73 }{ 53 } & \frac{ 20 }{ 59 } & - \frac{ 1394 }{ 237 } & \frac{ 3046161 }{ 175346 } \\ 0 & 0 & 1 & - \frac{ 42 }{ 59 } & \frac{ 407 }{ 79 } & - \frac{ 2849569 }{ 175346 } \\ 0 & 0 & 0 & 1 & - \frac{ 1399 }{ 474 } & \frac{ 912841 }{ 87673 } \\ 0 & 0 & 0 & 0 & 1 & - \frac{ 341933 }{ 87673 } \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 53 }{ 2 } & 0 & 0 & 0 & 0 \\ 0 & 0 & - \frac{ 118 }{ 53 } & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 474 }{ 59 } & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{ 87673 }{ 474 } & 0 \\ 0 & 0 & 0 & 0 & 0 & - \frac{ 485147265 }{ 175346 } \\ \end{array} \right) $$ $$ $$

$$ Q^T D Q = H $$

$$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ \frac{ 9 }{ 2 } & 1 & 0 & 0 & 0 & 0 \\ \frac{ 11 }{ 2 } & \frac{ 73 }{ 53 } & 1 & 0 & 0 & 0 \\ 3 & \frac{ 34 }{ 53 } & \frac{ 42 }{ 59 } & 1 & 0 & 0 \\ 3 & \frac{ 36 }{ 53 } & - \frac{ 180 }{ 59 } & \frac{ 1399 }{ 474 } & 1 & 0 \\ 4 & \frac{ 52 }{ 53 } & - \frac{ 361 }{ 118 } & \frac{ 521 }{ 474 } & \frac{ 341933 }{ 87673 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 53 }{ 2 } & 0 & 0 & 0 & 0 \\ 0 & 0 & - \frac{ 118 }{ 53 } & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 474 }{ 59 } & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{ 87673 }{ 474 } & 0 \\ 0 & 0 & 0 & 0 & 0 & - \frac{ 485147265 }{ 175346 } \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & \frac{ 9 }{ 2 } & \frac{ 11 }{ 2 } & 3 & 3 & 4 \\ 0 & 1 & \frac{ 73 }{ 53 } & \frac{ 34 }{ 53 } & \frac{ 36 }{ 53 } & \frac{ 52 }{ 53 } \\ 0 & 0 & 1 & \frac{ 42 }{ 59 } & - \frac{ 180 }{ 59 } & - \frac{ 361 }{ 118 } \\ 0 & 0 & 0 & 1 & \frac{ 1399 }{ 474 } & \frac{ 521 }{ 474 } \\ 0 & 0 & 0 & 0 & 1 & \frac{ 341933 }{ 87673 } \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} 2 & 9 & 11 & 6 & 6 & 8 \\ 9 & 14 & 13 & 10 & 9 & 10 \\ 11 & 13 & 8 & 8 & 15 & 15 \\ 6 & 10 & 8 & 14 & 35 & 21 \\ 6 & 9 & 15 & 35 & 240 & 733 \\ 8 & 10 & 15 & 21 & 733 & 42 \\ \end{array} \right) $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

Got to admit, with the fractions in $D,$ if I multiplied through by a common denominator it might take me a while to find a null vector, that is $v^TDv = 0$

This is better. One step at a time, reached a nice ternary section

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ P^T H P = D $$

$$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ - 3 & 0 & 0 & 1 & 0 & 0 \\ - 1 & 0 & 0 & - 1 & 0 & 1 \\ - 7 & - 1 & 0 & 5 & 0 & - 1 \\ 43 & 0 & 0 & 62 & 1 & - 58 \\ - 12 & 0 & - 1 & 7 & 0 & - 1 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 2 & 9 & 11 & 6 & 6 & 8 \\ 9 & 14 & 13 & 10 & 9 & 10 \\ 11 & 13 & 8 & 8 & 15 & 15 \\ 6 & 10 & 8 & 14 & 35 & 21 \\ 6 & 9 & 15 & 35 & 240 & 733 \\ 8 & 10 & 15 & 21 & 733 & 42 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & - 3 & - 1 & - 7 & 43 & - 12 \\ 0 & 0 & 0 & - 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & - 1 \\ 0 & 1 & - 1 & 5 & 62 & 7 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & - 1 & - 58 & - 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} 2 & 0 & 0 & - 1 & 0 & - 1 \\ 0 & - 4 & 1 & 0 & - 57 & 0 \\ 0 & 1 & 12 & 1 & 0 & - 2 \\ - 1 & 0 & 1 & 32 & - 664 & 59 \\ 0 & - 57 & 0 & - 664 & - 40074 & - 456 \\ - 1 & 0 & - 2 & 59 & - 456 & 96 \\ \end{array} \right) $$ $$ $$

$$ Q^T D Q = H $$

$$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 4 & - 1 & - 1 & 0 & 0 \\ 5 & 6 & - 1 & 0 & 0 & - 1 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 3 & - 4 & 58 & 0 & 1 & 0 \\ 4 & 1 & 1 & 0 & 0 & 0 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 2 & 0 & 0 & - 1 & 0 & - 1 \\ 0 & - 4 & 1 & 0 & - 57 & 0 \\ 0 & 1 & 12 & 1 & 0 & - 2 \\ - 1 & 0 & 1 & 32 & - 664 & 59 \\ 0 & - 57 & 0 & - 664 & - 40074 & - 456 \\ - 1 & 0 & - 2 & 59 & - 456 & 96 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & 4 & 5 & 3 & 3 & 4 \\ 0 & 4 & 6 & 1 & - 4 & 1 \\ 0 & - 1 & - 1 & 0 & 58 & 1 \\ 0 & - 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & - 1 & 0 & 0 & 0 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} 2 & 9 & 11 & 6 & 6 & 8 \\ 9 & 14 & 13 & 10 & 9 & 10 \\ 11 & 13 & 8 & 8 & 15 & 15 \\ 6 & 10 & 8 & 14 & 35 & 21 \\ 6 & 9 & 15 & 35 & 240 & 733 \\ 8 & 10 & 15 & 21 & 733 & 42 \\ \end{array} \right) $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

This time the matrix I am still calling $D$ has a pleasant upper left corner, three by three, namely

$$ C = \left( \begin{array}{rrr} 2 & 0 & 0 \\ 0 & - 4 & 1 \\ 0 & 1 & 12 \\ \end{array} \right) $$

Using familiar variables and half the Hessian I have $c(x,y,z) = x^2 -2 y^2 + 6 z^2 + yz $ This is isotropic (indeed the $y,z$ binary is), there are infinitely many triples that give zero, with $ x = 7u^2 + 7uv \; , \; \; \; y = 5u^2 + 4 uv + 2 v^2 \; , \; \; z = - u^2 + 2 uv + v^2.$ For example, taking $u=0$ and $v = 1$ gives us null vector $(0,3,-2)$ We extend this to column vector $w_1= (0,3,-2,0,0,0)^T$ Using this integer $P$ we form $w = P w_1 = (-7,0,0,5,0,-2)^T$ This should be a null vector for the original matrix $H.$ IT WORKS.

Answer 4

Here $H$ is the upper left 9 by 9 corner of your 36 by 36 matrix. I did just invertible integer operations and got only as far as displaying a zero on the diagonal of $P^THP $ And the same vector will work for the full 36 by 36 when padded with zeroes,

$$( 0,0,0,0,0,1,0,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$$ when written as a a row

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ P^T H P = D $$

$$\left( \begin{array}{rrrrrrrrr} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ \left( \begin{array}{rrrrrrrrr} 120 & 0 & 0 & 0 & 0 & 0 & - 8 & - 16 & 8 \\ 0 & - 144 & - 72 & - 72 & - 72 & - 72 & 0 & 0 & 0 \\ 0 & - 72 & - 96 & - 48 & - 48 & - 24 & 0 & 0 & 0 \\ 0 & - 72 & - 48 & - 96 & - 24 & - 48 & 0 & 0 & 0 \\ 0 & - 72 & - 48 & - 24 & - 96 & - 48 & 0 & 0 & 0 \\ 0 & - 72 & - 24 & - 48 & - 48 & - 96 & 0 & 0 & 0 \\ - 8 & 0 & 0 & 0 & 0 & 0 & 140 & - 20 & 6 \\ - 16 & 0 & 0 & 0 & 0 & 0 & - 20 & - 20 & 8 \\ 8 & 0 & 0 & 0 & 0 & 0 & 6 & 8 & 28 \\ \end{array} \right) $$ $$ \left( \begin{array}{rrrrrrrrr} 0 & 0 & 0 & 0 & 0 & - 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ = \left( \begin{array}{rrrrrrrrr} 0 & - 72 & - 24 & - 48 & - 48 & 16 & - 28 & - 24 & 72 \\ - 72 & - 144 & - 72 & - 72 & - 72 & 0 & 0 & 0 & 0 \\ - 24 & - 72 & - 96 & - 48 & - 48 & 0 & 0 & 0 & 0 \\ - 48 & - 72 & - 48 & - 96 & - 24 & 0 & 0 & 0 & 0 \\ - 48 & - 72 & - 48 & - 24 & - 96 & 0 & 0 & 0 & 0 \\ 16 & 0 & 0 & 0 & 0 & 120 & 8 & 16 & - 8 \\ - 28 & 0 & 0 & 0 & 0 & 8 & 140 & - 20 & 6 \\ - 24 & 0 & 0 & 0 & 0 & 16 & - 20 & - 20 & 8 \\ 72 & 0 & 0 & 0 & 0 & - 8 & 6 & 8 & 28 \\ \end{array} \right) $$ $$ $$

$$ Q^T D Q = H $$

$$\left( \begin{array}{rrrrrrrrr} 0 & 0 & 0 & 0 & 0 & - 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & - 2 & - 2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ \left( \begin{array}{rrrrrrrrr} 0 & - 72 & - 24 & - 48 & - 48 & 16 & - 28 & - 24 & 72 \\ - 72 & - 144 & - 72 & - 72 & - 72 & 0 & 0 & 0 & 0 \\ - 24 & - 72 & - 96 & - 48 & - 48 & 0 & 0 & 0 & 0 \\ - 48 & - 72 & - 48 & - 96 & - 24 & 0 & 0 & 0 & 0 \\ - 48 & - 72 & - 48 & - 24 & - 96 & 0 & 0 & 0 & 0 \\ 16 & 0 & 0 & 0 & 0 & 120 & 8 & 16 & - 8 \\ - 28 & 0 & 0 & 0 & 0 & 8 & 140 & - 20 & 6 \\ - 24 & 0 & 0 & 0 & 0 & 16 & - 20 & - 20 & 8 \\ 72 & 0 & 0 & 0 & 0 & - 8 & 6 & 8 & 28 \\ \end{array} \right) $$ $$ \left( \begin{array}{rrrrrrrrr} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & - 2 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & - 2 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ = \left( \begin{array}{rrrrrrrrr} 120 & 0 & 0 & 0 & 0 & 0 & - 8 & - 16 & 8 \\ 0 & - 144 & - 72 & - 72 & - 72 & - 72 & 0 & 0 & 0 \\ 0 & - 72 & - 96 & - 48 & - 48 & - 24 & 0 & 0 & 0 \\ 0 & - 72 & - 48 & - 96 & - 24 & - 48 & 0 & 0 & 0 \\ 0 & - 72 & - 48 & - 24 & - 96 & - 48 & 0 & 0 & 0 \\ 0 & - 72 & - 24 & - 48 & - 48 & - 96 & 0 & 0 & 0 \\ - 8 & 0 & 0 & 0 & 0 & 0 & 140 & - 20 & 6 \\ - 16 & 0 & 0 & 0 & 0 & 0 & - 20 & - 20 & 8 \\ 8 & 0 & 0 & 0 & 0 & 0 & 6 & 8 & 28 \\ \end{array} \right) $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

Answer 5

showing more null vectors. Note how the outcome $D$ has four by four with all $0$ on the diagonal. The lower 5 by 5 is visibly indefinite, so it is guaranteed that at least one more diagonal zero can be arranged, using just variables $x_5, x_6, x_7, x_8, x_9$ and hence keeping the upper left four the same; Tartakowsky. Hmmmm, checking. Tartakowsky's original theorem may have been slightly different. Anyway, the magic number is 5.

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ P^T H P = D $$

$$\left( \begin{array}{rrrrrrrrr} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 2 & 2 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 2 & 2 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 2 & 2 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrrrrr} 120 & 0 & 0 & 0 & 0 & 0 & - 8 & - 16 & 8 \\ 0 & - 144 & - 72 & - 72 & - 72 & - 72 & 0 & 0 & 0 \\ 0 & - 72 & - 96 & - 48 & - 48 & - 24 & 0 & 0 & 0 \\ 0 & - 72 & - 48 & - 96 & - 24 & - 48 & 0 & 0 & 0 \\ 0 & - 72 & - 48 & - 24 & - 96 & - 48 & 0 & 0 & 0 \\ 0 & - 72 & - 24 & - 48 & - 48 & - 96 & 0 & 0 & 0 \\ - 8 & 0 & 0 & 0 & 0 & 0 & 140 & - 20 & 6 \\ - 16 & 0 & 0 & 0 & 0 & 0 & - 20 & - 20 & 8 \\ 8 & 0 & 0 & 0 & 0 & 0 & 6 & 8 & 28 \\ \end{array} \right) \left( \begin{array}{rrrrrrrrr} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 2 & 2 & 2 & 2 & 0 & 0 & 0 & 1 & 0 \\ 2 & 2 & 2 & 2 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrrrrr} 0 & 48 & 48 & 72 & - 16 & - 72 & - 28 & - 24 & 72 \\ 48 & 0 & 72 & 48 & - 16 & - 72 & - 28 & - 24 & 72 \\ 48 & 72 & 0 & 48 & - 16 & - 72 & - 28 & - 24 & 72 \\ 72 & 48 & 48 & 0 & - 16 & - 72 & - 28 & - 24 & 72 \\ - 16 & - 16 & - 16 & - 16 & 120 & 0 & - 8 & - 16 & 8 \\ - 72 & - 72 & - 72 & - 72 & 0 & - 144 & 0 & 0 & 0 \\ - 28 & - 28 & - 28 & - 28 & - 8 & 0 & 140 & - 20 & 6 \\ - 24 & - 24 & - 24 & - 24 & - 16 & 0 & - 20 & - 20 & 8 \\ 72 & 72 & 72 & 72 & 8 & 0 & 6 & 8 & 28 \\ \end{array} \right) $$ $$ $$

$$ Q^T D Q = H $$

$$\left( \begin{array}{rrrrrrrrr} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & - 2 & - 2 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & - 2 & - 2 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & - 2 & - 2 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & - 2 & - 2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrrrrr} 0 & 48 & 48 & 72 & - 16 & - 72 & - 28 & - 24 & 72 \\ 48 & 0 & 72 & 48 & - 16 & - 72 & - 28 & - 24 & 72 \\ 48 & 72 & 0 & 48 & - 16 & - 72 & - 28 & - 24 & 72 \\ 72 & 48 & 48 & 0 & - 16 & - 72 & - 28 & - 24 & 72 \\ - 16 & - 16 & - 16 & - 16 & 120 & 0 & - 8 & - 16 & 8 \\ - 72 & - 72 & - 72 & - 72 & 0 & - 144 & 0 & 0 & 0 \\ - 28 & - 28 & - 28 & - 28 & - 8 & 0 & 140 & - 20 & 6 \\ - 24 & - 24 & - 24 & - 24 & - 16 & 0 & - 20 & - 20 & 8 \\ 72 & 72 & 72 & 72 & 8 & 0 & 6 & 8 & 28 \\ \end{array} \right) \left( \begin{array}{rrrrrrrrr} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & - 2 & - 2 & - 2 & - 2 & 0 & 1 & 0 \\ 0 & 0 & - 2 & - 2 & - 2 & - 2 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrrrrr} 120 & 0 & 0 & 0 & 0 & 0 & - 8 & - 16 & 8 \\ 0 & - 144 & - 72 & - 72 & - 72 & - 72 & 0 & 0 & 0 \\ 0 & - 72 & - 96 & - 48 & - 48 & - 24 & 0 & 0 & 0 \\ 0 & - 72 & - 48 & - 96 & - 24 & - 48 & 0 & 0 & 0 \\ 0 & - 72 & - 48 & - 24 & - 96 & - 48 & 0 & 0 & 0 \\ 0 & - 72 & - 24 & - 48 & - 48 & - 96 & 0 & 0 & 0 \\ - 8 & 0 & 0 & 0 & 0 & 0 & 140 & - 20 & 6 \\ - 16 & 0 & 0 & 0 & 0 & 0 & - 20 & - 20 & 8 \\ 8 & 0 & 0 & 0 & 0 & 0 & 6 & 8 & 28 \\ \end{array} \right) $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

I wrote a little program, here are the integer null vectors with absolute values bounded by $1$

1   -1   -1    0    0    1   -1   -1   -1
1   -1    0   -1    1    0   -1   -1   -1
1   -1    0    1   -1    0   -1   -1   -1
1   -1    1    0    0   -1   -1   -1   -1
1    0   -1   -1    0    0   -1   -1   -1
1    0   -1   -1    1    1   -1   -1   -1
1    0   -1    0   -1    0   -1   -1   -1
1    0   -1    1   -1    1   -1   -1   -1
1    0    0   -1    0   -1   -1   -1   -1
1    0    0    0   -1   -1   -1   -1   -1
1    0    0    0    1    1   -1   -1   -1
1    0    0    1    0    1   -1   -1   -1
1    0    1   -1    1   -1   -1   -1   -1
1    0    1    0    1    0   -1   -1   -1
1    0    1    1   -1   -1   -1   -1   -1
1    0    1    1    0    0   -1   -1   -1
1    1   -1    0    0    1   -1   -1   -1
1    1    0   -1    1    0   -1   -1   -1
1    1    0    1   -1    0   -1   -1   -1
1    1    1    0    0   -1   -1   -1   -1