TAOCP 3.3.4 Exercise 9

Let f(\mathbf{x})=\mathbf{x}^{T}A\mathbf{x}, where $A$ is a positive definite symmetric matrix of order $t$.

taocpmathematicsalgorithmsvolume-2hm-hard

Section 3.3.4: The Spectral Test

Exercise 9. [HM32] (C. Hermite, 1846.) Let $f(x_1, \ldots, x_t)$ be a positive definite quadratic form, defined by the matrix $U$ as in (17), and let $\theta$ be the minimum value of $f$ at nonzero integer points. Prove that $\theta \le \left(\frac{4}{3}\right)^{(t-1)/2} |\det U|^{2/t}$. [Hints: If $W$ is any integer matrix of determinant 1, the matrix $WU$ defines a form equivalent to $f$; and if $S$ is any orthogonal matrix (that is, if $S^{-1} = S^T$), the matrix $US$ defines a form identically equal to $f$. Show that there is an equivalent form $g$ whose minimum $\theta$ occurs at

$(1, 0, \ldots, 0)$. Then prove the general result by induction on $t$, writing $g(x_1, \ldots, x_t) = \theta(x_1 + \beta_2 x_2 + \cdots + \beta_t x_t)^2 + h(x_2, \ldots, x_t)$ where $h$ is a positive definite quadratic form in $t - 1$ variables.]

Verified: yes
Solve time: 10m46s

Exercise 3.3.4.9 [HM32]

Let

$$ f(\mathbf{x})=\mathbf{x}^{T}A\mathbf{x}, $$

where $A$ is a positive definite symmetric matrix of order $t$. Let

$$ \theta=\min_{\mathbf{x}\in\mathbb Z^t\setminus{\mathbf0}} f(\mathbf{x}). $$

In Knuth's notation the form is defined by a matrix $U$ as in (17), so that

$$ A=UU^{T}, \qquad \det A=(\det U)^2. $$

We must prove

$$ \theta\le \left(\frac43\right)^{(t-1)/2} |\det U|^{2/t}. $$

Since $|\det U|^{2}=\det A$, this is equivalent to

$$ \theta\le \left(\frac43\right)^{(t-1)/2} (\det A)^{1/t}. $$

We proceed by induction on $t$.

Reduction to a form whose minimum occurs at $(1,0,\ldots,0)$

Let $\mathbf m\in\mathbb Z^t$ be a vector for which $f(\mathbf m)=\theta$.

Since $\mathbf m$ is primitive, there exists a unimodular integer matrix $W$ whose first column is $\mathbf m$. Define

$$ g(\mathbf x)=f(W\mathbf x). $$

Then $g$ is equivalent to $f$, has the same minimum $\theta$, and

$$ g(1,0,\ldots,0)=f(\mathbf m)=\theta . $$

Replacing $f$ by $g$, we may therefore assume that

$$ \theta=g(1,0,\ldots,0). $$

Let $B=(b_{ij})$ be the matrix of $g$. Since

$$ g(1,0,\ldots,0)=b_{11}, $$

we have $b_{11}=\theta$.

Completing the square in the variable $x_1$,

$$ g(x_1,\ldots,x_t) = \theta\Bigl(x_1+\beta_2x_2+\cdots+\beta_tx_t\Bigr)^2 + h(x_2,\ldots,x_t), $$

where $h$ is a positive definite quadratic form in $t-1$ variables.

Let $H$ be the matrix of $h$.

Because this decomposition is obtained by a unit upper-triangular change of variables, the determinant satisfies

$$ \det B=\theta,\det H. $$

Hence

$$ \det H=\frac{\det B}{\theta} =\frac{\det A}{\theta}. $$

A lower bound for the minimum of $h$

Let

$$ \mu=\min_{\mathbf y\in\mathbb Z^{t-1}\setminus{\mathbf0}} h(\mathbf y). $$

We claim that

$$ \mu\ge \frac34,\theta. $$

Let $\mathbf y=(y_2,\ldots,y_t)\neq0$ be an integer vector for which

$h(\mathbf y)=\mu$, and put

$$ \alpha=\beta_2y_2+\cdots+\beta_ty_t. $$

Choose an integer $m$ nearest to $-\alpha$. Then

$$ |m+\alpha|\le \frac12. $$

Since $(m,\mathbf y)\neq\mathbf0$, the minimality of $\theta$ gives

$$ \theta \le g(m,\mathbf y) = \theta(m+\alpha)^2+h(\mathbf y). $$

Using $|m+\alpha|\le \frac12$,

$$ \theta \le \frac{\theta}{4}+\mu. $$

Therefore

$$ \mu\ge \frac34,\theta. $$

Equivalently,

$$ \theta\le \frac43,\mu. $$

Application of the induction hypothesis

The form $h$ has dimension $t-1$. By the induction hypothesis,

$$ \mu \le \left(\frac43\right)^{(t-2)/2} (\det H)^{1/(t-1)}. $$

Combining this with $\theta\le \frac43,\mu$,

$$ \theta \le \left(\frac43\right)^{t/2} (\det H)^{1/(t-1)}. $$

Using $\det H=\det A/\theta$,

$$ \theta \le \left(\frac43\right)^{t/2} \left(\frac{\det A}{\theta}\right)^{1/(t-1)}. $$

Raise both sides to the power $t-1$:

$$ \theta^{,t-1} \le \left(\frac43\right)^{t(t-1)/2} \frac{\det A}{\theta}. $$

Hence

$$ \theta^{,t} \le \left(\frac43\right)^{t(t-1)/2} \det A. $$

Taking $t$-th roots,

$$ \theta \le \left(\frac43\right)^{(t-1)/2} (\det A)^{1/t}. $$

Finally, since $\det A=(\det U)^2$,

$$ (\det A)^{1/t} = |\det U|^{2/t}. $$

Therefore

$$ \boxed{\theta\le \left(\frac43\right)^{(t-1)/2} |\det U|^{2/t}}. $$

Basis of induction

For $t=1$,

$$ f(x)=ax^2,\qquad a>0, $$

so $\theta=a$, and

$$ \theta=a=|\det U|^{2} = \left(\frac43\right)^0|\det U|^{2/1}. $$

Thus the result holds with equality.

By induction, the theorem is true for all $t\ge1$. ∎