# Eigenvector problem with ellipsoids (maximizing quadratic form)

Let $$B$$ be a symmetric, positive definite matrix and consider the problem

$$\begin{array}{ll} \text{maximize} & x^\top B x\\ \text{subject to} & \|x\| = 1\\ & b^\top x = 0\end{array}$$

for some unit vector $$b$$, not necessarily an eigenvector of $$B$$. If $$b$$ is an eigenvector, this is easy: just pick the largest eigenvalue among all eigenvectors orthogonal to $$b$$. But what if $$b$$ is not an eigenvector?

My intuition is as follows. Let $$z_i$$ be the eigenvectors of $$B$$ (with corresponding eigenvalues $$\lambda_i$$. Each eigenvector can be projected onto the orthogonal complement of $$b$$ by taking the vector rejection

$$\hat{b}_i = z_i - \left(b^\top z_i\right)b$$

I believe that the maximizer should be one of the $$\hat{b}_i$$ vectors, but I don't know how to prove it or how to further characterize the right $$i$$. I guess that it should depend on both $$\lambda_i$$ and $$(b^\top z_i)^2$$, but don't know how to proceed further. Would appreciate any suggestions.

• Have you tried using Lagrange multipliers? – Rodrigo de Azevedo Jun 26 '20 at 13:00
• Some characterizations of this maximum (which is, in a sense, the maximal eigenvalue of a "submatrix") can be obtained from this paper. – Ben Grossmann Jun 26 '20 at 13:08
• if $b=0$ and the $||\cdot||_\infty$-norm is used, this problem is known to be NP-complete – LinAlg Sep 9 '20 at 23:56

## 1 Answer

One approach to the problem is as follows: extend $$b$$ into an orthonormal basis, so that $$b,v_2,\dots,v_{n}$$. Note that for any unit vector $$y \in \Bbb R^{n-1}$$, the matrix $$Qy$$ is a vector in $$b^\perp$$. Conversely, every unit vector $$x \in b^\perp$$ can be expressed as $$Qy$$ for some vector $$y \in \Bbb R^{n-1}$$.

So, we can reframe your question as $$\max_{\|y\| = 1}(Qy)^TB(Qy) = \max_{\|y\| = 1}y^T (Q^TBQ)y.$$ In other words, the maximum that we want is the largest eigenvalue of $$Q^TBQ$$.

The Courant-Fischer theorem tells us that this maximum will necessarily fall between (or be equal to one of) the two largest eigenvalues of $$B$$.

It does not necessarily hold that the maximum is equal to the projection of the eigenvector. As an example, consider $$B = \pmatrix{3&0&0\\ 0&2&0\\ 0&0&1}, \quad b = (1,1,1)/\sqrt{3} \implies\\ Q = \pmatrix{1/\sqrt{2}&1/\sqrt{6}\\-1/\sqrt{2}&1/\sqrt{6}\\0&-2/\sqrt{6}}, \quad Q^TBQ = \pmatrix{5/2 & 1/\sqrt{12}\\ 1/\sqrt{12} & 2/3}.$$ The maximizer here is $$y = v/\|v\|$$, with $$v = (\frac 16 (11 \sqrt{3} + \sqrt{399}), 1)$$. You can verify that $$x = Qy$$ is not the projection of $$(1,0,0)$$ onto $$b^\perp$$.

• Thanks! I am wondering if it might be possible to use a similar technique to derive a lower bound on x^\top B x when the condition is b^\top x = a for some small a \neq 0. Since any such x must take the form ab + \hat{x} with \hat{x} orthogonal to b, I conjecture that the lower bound should be (a^2)*\lambda_1 + (1 - a^2)*\lambda_2. The second term is by analogy with what you showed, and I think there should be some "inverse" relationship between how close \hat{x} is to the second eigenvector vs. how close b is. Just wondering if you might have some thoughts. – sven svenson Jun 26 '20 at 16:09