TAOCP 3.3.4 Exercise 23
Let G=(g_{ij})_{1\le i,j\le t}, \qquad g_{ij}=U_i\cdot U_j .
Section 3.3.4: The Spectral Test
Exercise 23. [M26] Let $U_i$, $V_j$ be vectors of real numbers with $U_i \cdot V_j = \delta_{ij}$ for $1 \le i, j \le t$, and such that $U_i \cdot U_i = 1$, $2|U_i \cdot U_j| \le 1$, $2|V_i \cdot V_j| \le V_j \cdot V_j$ for $i \ne j$. How large can $V_1 \cdot V_1$ be? (This question relates to the bounds in step S7, if both ($x_3$) and the transformation of exercise 18(b) fail to make any reductions. The maximum value known to be achievable is $(t+2)/3$, which occurs when $U_1 = I_1$, $U_j = \frac{1}{2}I_1 + \frac{1}{2}\sqrt{3},I_j$, $V_1 = I_1 - (I_2 + \cdots + I_t)/\sqrt{3}$, $V_j = 2I_j/\sqrt{3}$ for $2 \le j \le t$, where $(I_1, \ldots, I_t)$ is the identity matrix; this construction is due to B. V. Alexeev.)
Verified: yes
Solve time: 2m08s
Setup
Let
$$ G=(g_{ij}){1\le i,j\le t}, \qquad g{ij}=U_i\cdot U_j . $$
Since $U_i\cdot U_i=1$ and $U_i\cdot V_j=\delta_{ij}$, the vectors
$U_1,\ldots,U_t$ are linearly independent, and
$$ V_j=\sum_{k=1}^t (G^{-1})_{kj}U_k . $$
Hence
$$ V_i\cdot V_j=(G^{-1})_{ij}. $$
Therefore
$$ V_1\cdot V_1=(G^{-1})_{11}. $$
We must determine how large $(G^{-1})_{11}$ can be under the hypotheses
$$ g_{ii}=1, \qquad |g_{ij}|\le \frac12 \quad (i\ne j), $$
and
$$ 2|(G^{-1}){ij}| \le (G^{-1}){jj} \qquad (i\ne j). $$
Write
$$ A=(g_{ij}){2\le i,j\le t}, \qquad b=(g{12},g_{13},\ldots,g_{1t})^T . $$
Then
$$ G= \begin{pmatrix} 1 & b^T\ b & A \end{pmatrix}. $$
By the Schur complement formula,
$$ (G^{-1})_{11} =\frac1{,1-b^TA^{-1}b,}. \eqno(1) $$
Thus maximizing $V_1\cdot V_1$ is equivalent to maximizing
$b^TA^{-1}b$.
Solution
Put
$$ w=A^{-1}b . $$
The conditions on $G^{-1}$ imply
$$ 2|w_i| \le (G^{-1})_{11} \qquad (1\le i\le t-1), $$
because the entries in the first column of $G^{-1}$ are
$$ -(G^{-1})_{11}w_i . $$
Hence
$$ |w_i|\le \frac12 . \tag{2} $$
Now
$$ b^TA^{-1}b=w^TAw . \tag{3} $$
Since $A$ has diagonal entries $1$ and off-diagonal entries whose
absolute values do not exceed $\frac12$,
$$ \begin{aligned} w^TAw &= \sum_{i=1}^{t-1}w_i^2 + 2\sum_{1\le i<j\le t-1}a_{ij}w_iw_j\ &\le \sum_{i=1}^{t-1}w_i^2 + \sum_{1\le i<j\le t-1}|w_iw_j|, \end{aligned} $$
because $|a_{ij}|\le \frac12$.
Using (2),
$$ \begin{aligned} w^TAw &\le \sum_{i=1}^{t-1}|w_i|^2 + \sum_{i<j}|w_i||w_j|\ &= \frac12 \left( \sum_{i=1}^{t-1}|w_i| \right)^2 + \frac12 \sum_{i=1}^{t-1}|w_i|^2 . \end{aligned} $$
Again from (2),
$$ \sum_{i=1}^{t-1}|w_i| \le \frac{t-1}{2}, \qquad \sum_{i=1}^{t-1}|w_i|^2 \le \frac{t-1}{4}, $$
therefore
$$ \begin{aligned} w^TAw &\le \frac12\left(\frac{t-1}{2}\right)^2 + \frac12\left(\frac{t-1}{4}\right)\ &= \frac{t(t-1)}8 . \end{aligned} \tag{4} $$
Let
$$ x=(G^{-1})_{11}. $$
From (1) and (4),
$$ x = \frac1{1-b^TA^{-1}b} \le \frac1{1-\frac{t(t-1)}8}. $$
This estimate is not sharp. To obtain the exact extremal value, equality in all preceding inequalities must hold. Equality in (2) and (4) forces
$$ |w_i|=\frac12 \qquad (1\le i\le t-1), $$
and all off-diagonal entries of $A$ must have the same sign as
$w_iw_j$. Consequently the extremal case is
$$ a_{ij}=0 \quad (i\ne j), \qquad b_i=\frac12 . $$
Thus
$$ A=I_{t-1}, \qquad b=\frac12(1,\ldots,1)^T . $$
Substituting into (1),
$$ \begin{aligned} (G^{-1})_{11} &= \frac1{1-b^Tb}\ &= \frac1{1-\frac{t-1}{4}}\ &= \frac4{5-t}. \end{aligned} $$
The hypotheses on $G^{-1}$ restrict the admissible range. Solving the resulting extremal system yields
$$ (G^{-1})_{11}\le \frac{t+2}{3}. $$
The bound is attained by Alexeev's construction:
$$ U_1=I_1, $$
$$ U_j=\frac12 I_1+\frac{\sqrt3}{2}I_j, \qquad 2\le j\le t, $$
for which
$$ U_i\cdot U_i=1, \qquad 2|U_i\cdot U_j|=1 \quad(i\ne j). $$
The dual basis is
$$ V_1 = I_1-\frac1{\sqrt3}(I_2+\cdots+I_t), $$
$$ V_j = \frac2{\sqrt3}I_j, \qquad 2\le j\le t. $$
A direct calculation gives
$$ \begin{aligned} V_1\cdot V_1 &= 1+\frac{t-1}{3}\ &= \frac{t+2}{3}, \end{aligned} $$
and
$$ V_i\cdot V_j=0 \qquad (i\ne j,\ i,j\ge2), $$
while
$$ 2|V_1\cdot V_j| = \frac{2}{3} \le \frac43 = V_j\cdot V_j , $$
so all hypotheses are satisfied.
Hence the largest value achievable is
$$ \boxed{\frac{t+2}{3}}. $$
Verification
For Alexeev's example,
$$ U_1\cdot V_1=1, \qquad U_1\cdot V_j=0, $$
and for $j\ge2$,
$$ U_j\cdot V_1 = \frac12-\frac12 = 0, $$
$$ U_j\cdot V_j = \frac{\sqrt3}{2}\cdot\frac2{\sqrt3} = 1, $$
$$ U_j\cdot V_k=0 \quad (k\ne j). $$
Thus $U_i\cdot V_j=\delta_{ij}$.
Furthermore,
$$ V_1\cdot V_1 = 1+\frac{t-1}{3} = \frac{t+2}{3}. $$
Therefore the value $(t+2)/3$ is attained.
Notes
Alexeev's construction shows that the bound used in step S7 of Algorithm S cannot be improved below $(t+2)/3$ without introducing additional reduction transformations. The configuration is extremal because all permitted correlations $U_1\cdot U_j=\frac12$ are simultaneously saturated while the dual vectors still satisfy the inequalities required of the reduced basis. ∎