Froebenius norm is unitarily invariant. I'm considering the norm defined on matrices by
$$\|A\|_F = \sqrt{\sum_{i,j}|a_{ij}|^2}$$
I want to show that it is unitarily invariant, so that for unitary $U$ we have that
$$\|UA\|_F = \|A\|_F = \|AU\|_F$$
however I have trouble doing it directly. Writing $\|UA\|_F$ directly I find by Cauchy-Schwarz that
$$\|UA\|_F = \sqrt{\sum_{i,j}\left|\sum_{k=1}^{n}u_{ik}a_{kj}\right|^2}= \sqrt{\sum_{i,j}|\langle U_i,\overline{A_j}\rangle|^2}\leq \sqrt{\sum_{i,j}\|A_j\|^2}$$
where $U_i$ denotes the $i$th row of $U$ and $A_j$ the $j$th column of $A$. However this estimate is to crude and will not equal $\|A\|_F$. I would like to prove this without refering to trace or singular values and would appreciate a hint, rather than a full solution, on how to tackle this problem.

EDIT: Completion of the proof based on the answer from $A.\Gamma$:
Since the rows of $U$ constitute an orthonormal basis for $\mathbb{C}^n$ we find by Parsevals theorem that
$$\|UA_j\|_2^2 = \sum_{i=1}^{n}\left|\sum_{k=1}^{n}u_{ik}a_{kj}\right|^2 = \sum_{i=1}^{n}|\langle U_i,\overline{A_j}\rangle|^2 = \|\overline{A_j}\|_2^2 = \|A_j\|_2^2$$
 A: Quick and dirty:
$$\|UA\|_F^2 = \operatorname{Tr}((UA)^*(UA)) = \operatorname{Tr}(A^*U^*UA) = \operatorname{Tr}(A^*A) = \|A\|_F^2$$
and then since $U^*$ is also unitary
$$\|AU\|_F^2 = \|(U^*A^*)^*\|_F^2 = \|U^*A^*\|_F^2 = \|A^*\|_F^2 = \|A\|_F^2$$

Alternative argument:
Note that $A^*A \ge 0$ so there exists an orthonormal basis $\{u_1, \ldots, u_n\}$ for $\mathbb{C}^n$ such that $A^*A u_i = \lambda_i u_i$ for some $\lambda \ge 0$.
We have
$$\sum_{i=1}^n \|Au_i\|_2^2 = \sum_{i=1}^n \langle Au_i, Au_i\rangle = \sum_{i=1}^n \langle A^*Au_i, u_i\rangle = \sum_{i=1}^n \lambda_i =\operatorname{Tr}(A^*A) = \|A\|_F^2$$
because the trace is the sum of eigenvalues.
The interesting part is that the sum $\sum_{i=1}^n \|Au_i\|_2^2$ is actually independent of the choice of the orthonormal basis $\{u_1, \ldots, u_n\}$. Indeed, if $\{v_1, \ldots, v_n\}$ is some other orthonormal basis for $\mathbb{C}^n$, we have
\begin{align}
\sum_{i=1}^n \|Au_i\|_2^2 &= \sum_{i=1}^n \langle A^*Au_i, u_i\rangle\\
&= \sum_{i=1}^n \left\langle \sum_{j=1}^n\langle u_i,v_j\rangle A^*A v_j , \sum_{k=1}^n\langle u_i,v_k\rangle v_k\right\rangle\\
&=  \sum_{j=1}^n \sum_{k=1}^n \left(\sum_{i=1}^n\langle u_i,v_j\rangle \langle v_k,u_i\rangle\right)\langle A^*A v_j,v_k\rangle\\
&= \sum_{j=1}^n \sum_{k=1}^n \langle v_j,v_k\rangle\langle A^*A v_j,v_k\rangle\\
&= \sum_{j=1}^n \langle A^*A v_j,v_j\rangle\\
&= \sum_{j=1}^n \|Av_j\|_2^2
\end{align}
Now, if $U$ is unitary, for any orthonormal basis $\{u_1, \ldots, u_n\}$ we have that $\{Uu_1, \ldots, Uu_n\}$ is also an orthonormal basis so:
$$\|AU\|_F^2 = \sum_{i=1}^n \|A(Ue_i)\|^2 = \|A\|_F^2$$
A: Since
$$
UA=[UA_1\ UA_2\ \ldots\ UA_n]
$$
you need to prove that
$$
\|UA\|_F^2=\sum_{j=1}^n\|UA_j\|_2^2\stackrel{?}{=}\sum_{j=1}^n\|A_j\|_2^2=\|A\|_F^2.
$$
It suffice to prove that $\|UA_j\|_2^2=\|A_j\|_2^2$.
P.S. For $AU$ use conjugation.
