# Constraints $X^TBX = 1$, what's the maximum $X^TAX$?

(a) Find the maximum value of $$X^TAX$$ subject to the constraints $$X^TX = 1$$. (A is a $$n * n$$ symmetric matrix)

It is easy to solve (a) by using spectral decomposition.

(b) Let A, B be $$n * n$$ symmetric matrices. By using (a), Find the maximum value of $$X^TAX$$ and $$X$$ subject to the constraint is $$X^TBX = 1$$

How to find?

• Why should there be a maximum? Sep 29 '18 at 14:02
• @0 Hong Do you still assume that $X^TX=1$ in part (b)? Sep 29 '18 at 14:09
• Do you know if $B$ is also positive definite? Sep 29 '18 at 15:16
• @AnyAD I don't know.. but is (b) possible to solve if assume $X^TX = 1$ in part(b)? Sep 30 '18 at 2:34

Assume $$B$$ is invertible. Set $$x=B^{-1/2}y$$, then $$\left\langle x,Bx\right\rangle =1\Longleftrightarrow\left\langle y,y\right\rangle =1$$. Thus, \begin{align*} \left\langle x,Ax\right\rangle & =\left\langle y,B^{-1/2}AB^{-1/2}y\right\rangle , \end{align*} and \begin{align*} \max_{\left\langle x,Bx\right\rangle =1}\left\{ \left\langle x,Ax\right\rangle \right\} \end{align*} is the largest eigenvalue of $$B^{-1/2}AB^{-1/2}$$.
Hint: can you maximise $$x^2+ay^2$$ subject to $$x^2+by^2=1$$? Yes, iff $$a,\,b\ge 0$$. Working in a basis that diagonalises $$B$$, how in general do the signs of its eigenvalues matter?
It is equivalent to $$\max f(x)=x^tAx$$ with constraint $$g(x)=x^tBx-1=0$$. By Lagrange multiplier, to find critical point we solve following equation for $$(\lambda,x)$$ $$\nabla f=\lambda \nabla g,\ \ \ \ \ \ g(x)=0$$ Here $$\nabla f=2Ax$$ and $$\nabla g=2Bx$$. (Try to understand why we get such calculations). Then above equation becomes $$Ax=\lambda Bx$$
(1) if $$B$$ is invertible (notice that symmetric doesn't imply invertible), then $$B^{-1}Ax=\lambda x$$, that means solution $$x^*$$ is eigenvector w.r.t. eigenvalue $$\lambda$$. Thus $$f=(x^*)^tAx^*=\lambda (x^*)^tBx^*=\lambda\leq \max \lambda_i$$ Thus the maximum of $$f$$ is just the maximum eigenvalue of matrix $$B^{-1}A$$.
(2) If $$B$$ is not invertible, we can't move $$B$$ to the left. But we still have $$(A-\lambda B)x=0$$. To solve this system, note that we want a nonzero solution $$x$$. So by basic linear algebra, we must have $$det(A-\lambda B)=0$$ Therefore we can solve $$\lambda^*$$, then $$f=x^tAx=\lambda^* x^tBx=\lambda^*$$ In conclusion, comparing above results and choose the maximum one.