2
$\begingroup$

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.

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

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$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – sven svenson Jun 26 '20 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.