Maximization inequality for Frobenius norm after adding orthogonal matrix

Question

Let $A$ be a matrix and $Q$ be an orthogonal matrix such that $AQ^T$ is symmetric, positive semidefinite. Show that $$||A+Q||_F\geq||A+P||_F$$ for any orthogonal matrix $P$. Here, $||\cdot||_F$ is the Frobenius norm.

Answer 1

Let $AQ^T=VDV^T$ be an orthogonal diagonalisation. Then $D$ is a nonnegative diagonal matrix and $U=V^TPQ^TV$ is orthogonal. Since Frobenius norm is unitarily invariant, we have \begin{aligned} \|A+Q\|_F^2-\|A+P\|_F^2 &=\|V^T(A+Q)Q^TV\|_F^2-\|V^T(A+P)Q^TV\|_F^2\\ &=\|D+I\|_F^2-\|D+U\|_F^2\\ &=2\operatorname{tr}(D)-\operatorname{tr}(DU)-\operatorname{tr}(U^TD)\\ &=2\operatorname{tr}(D(I-U)), \end{aligned} but this trace is nonnegative because $D(I-U)$ has a nonnegative diagonal.