Maximising $Tr(PAPB)$ for orthogonal projection matrix $P$ and symmetric $A,B$.

Question

I want to find a vector $u$ that maximises $Tr(PAPB)$ where $P$ is an orthogonal projection over $u$, for symmetric $A,B$. Does this problem have a closed form solution?

Thanks

Answer 1

Suppose $\|u\|=1$, you can write $P=uu^T$, then \begin{align*} \text{Tr}(PAPB) &= \text{Tr}(uu^TAuu^TB)\\ &= \text{Tr}(u^TAuu^TBu)\\ &= u^TAuu^TBu \end{align*} since it is a scalar. So this is the expression that you want to maximize.

I do not know a closed form expression for that, however so bounds can be given, a trivial one is that since $u$ has unit norm, we have $u^T A u\in[\lambda_1(A),\lambda_n(A)]$ and $u^T B u\in[\lambda_1(B),\lambda_n(B)]$, where $\lambda_k(X)$ is the $k$'th smalest eigenvalue of $X$. If we take $u$ to be the eigenvector associated to the $k$'th eigenvalue of $A$, we obtain that $u^T A u=\lambda_k(A)$ and so $$u^T A u u^T B u = \lambda_k(A)u^T B u\geq \min(\lambda_k(A)\lambda_n(B),\lambda_k(A)\lambda_1(B))$$This means that \begin{align*} \max_u u^TAuu^TBu &\geq \max_k \min(\lambda_k(A)\lambda_n(B),\lambda_k(A)\lambda_1(B))\\ &=\max(\min(\lambda_1(A)\lambda_n(B),\lambda_1(A)\lambda_1(B)),\min(\lambda_n(A)\lambda_n(B),\lambda_n(A)\lambda_1(B))) \end{align*} You can also inverse the role of $A$ and $B$ to get that \begin{align*} \max_u u^TAuu^TBu &\geq \max(\min(\lambda_1(B)\lambda_n(A),\lambda_1(B)\lambda_1(A)),\min(\lambda_n(B)\lambda_n(A),\lambda_n(B)\lambda_1(A))) \end{align*}

We can find $A$ and $B$ such that this is tight, but the value can also go up to $\max(\lambda_1(A)\lambda_1(B), \lambda_n(A)\lambda_n(B))$ when the same eigenvector achieves the largest (lowest if they are negative) eigenvalues. So in general any value between those two is achievable by some matrices $A$ and $B$.

---

If $A$ and $B$ are both PSD, then all eigen values are positive and \begin{align*} &\max(\min(\lambda_1(A)\lambda_n(B),\lambda_1(A)\lambda_1(B)),\min(\lambda_n(A)\lambda_n(B),\lambda_n(A)\lambda_1(B)))\\ =&\max(\lambda_1(A)\lambda_n(B),\lambda_1(A)\lambda_1(B))\\ =&\lambda_1(A)\lambda_n(B) \end{align*} and similarly we are bounded by $\lambda_n(A)\lambda_1(B)$.