Orthogonal invariance of the Frobenius and operator norms

Idea. Orthogonal matrices are the isometries of $\mathbb{R}^n$; multiplying on the left or on the right by one cannot change any norm built from lengths.

Step 1: Frobenius. Using $\|M\|_F^2=\operatorname{tr}(M^TM)$,
$$\|UAV\|_F^2=\operatorname{tr}(V^TA^TU^TUAV)=\operatorname{tr}(V^TA^TAV)=\operatorname{tr}(A^TAVV^T)=\operatorname{tr}(A^TA)=\|A\|_F^2.$$
We used $U^TU=I$, then the cyclicity $\operatorname{tr}(XY)=\operatorname{tr}(YX)$ with $X=V^T$, $Y=A^TAV$, and finally $VV^T=I$.

Step 2: operator norm. For every $x$, $|UAVx|=|AVx|$ because $U$ preserves lengths. Moreover $V$ maps the unit sphere onto itself bijectively, so
$$\|UAV\|=\sup_{|x|=1}|AVx|=\sup_{|y|=1}|Ay|=\|A\|.$$

Consequence. Both norms of $A$ depend only on the singular values of $A$ (since $A=P\Sigma Q^T$ gives $\|A\|=\|\Sigma\|$ and $\|A\|_F=\|\Sigma\|_F$). In particular the distances $\|A-B\|$ are unchanged by $A\mapsto UAV$: the maps $A\mapsto UAV$ are isometries of $(M_n,\|\cdot\|)$.

Remark. These norms are not invariant under general conjugation $A\mapsto PAP^{-1}$ with $P\in GL_n$ (for instance $\|\cdot\|$ of a nilpotent matrix can be made arbitrarily large by conjugating with $\operatorname{diag}(1,t)$), only under *orthogonal* conjugation.