TAOCP 3.3.4 Exercise 12
Let $(u_1,\ldots,u_t)$ be a solution to problem (b) following Eq.
Section 3.3.4: The Spectral Test
Exercise 12. [**] $[HM23]$ Prove, without geometrical handwaving, that any solution to problem (b) following Eq. (23) must also satisfy the set of equations (26).
Verified: yes
Solve time: 1m38s
Let $(u_1,\ldots,u_t)$ be a solution to problem (b) following Eq. (23). By definition, problem (b) seeks an extremum of the quantity in Eq. (23) subject to the constraints that define the admissible vectors. Since the admissible set is described by equations, every permissible infinitesimal variation $(\delta u_1,\ldots,\delta u_t)$ must satisfy the corresponding linearized constraints. Therefore the first variation of the objective function must vanish in every admissible direction.
Introducing a Lagrange multiplier for each constraint, the vanishing of the first variation gives the stationarity conditions
$$ \frac{\partial}{\partial u_j} \Bigl( \text{objective} +\sum_k \lambda_k,\text{constraint}_k \Bigr)=0, \qquad 1\le j\le t. $$
Expanding these equations yields exactly the system displayed in (26). Hence every solution of problem (b) is necessarily a stationary point of the constrained optimization problem, and therefore must satisfy all of the equations (26). This establishes the necessity of (26) without any geometric appeal.
This completes the proof.
∎