What's the most sparse block-diagonalization you can do with unitary equivalence? My question is, in general, what is the simplest form (most sparse and/or smallest diagonal blocks) an $n\times n$ matrix $A$ can be put in if we are allowed only unitary equivalence 
$$A = U B U^{-1}$$
where $B$ is "simple" and $U$ is unitary? We know that if $U$ is allowed to be any invertible matrix then $B$ can have Jordan normal form. We also know that if $U$ is unitary then $B$ can be made upper triangular. Can we do any better?
 A: The reference given by Omno is an excellent one.
In complex case, we can also reason as follows. We are dealing with REAL algebraic sets, with real dimensions $dim(M_n(\mathbb{C})=2n^2,dim(U_n)=n^2$. Let $A\in M_n(\mathbb{C})$ be a GENERIC matrix (for example, randomly choose it).
We consider the trajectory under the action $U\in U_n\mapsto UAU^*$; this trajectory contains a triangular matrix; that is one has at most $n^2+n$ real parameters in such a representation.  Assume that we can do better, that is, we can obtain representations with at most $n^2+n-k$ real parameters. Note that here one has a finite number of entries. Then we can write the equality
$2n^2=(n^2+n-k)+n^2-dim(C(A))$ where $C(A)$ is the algebraic set $\{U\in U_n;AU=UA\}$. Clearly, when $A$ is generic, $C(A)=\{e^{i\theta}I_n;\theta\in\mathbb{R}\}$ has real dimension $1$. Thus the maximum value for $k$ is $n-1$. 
$\textbf{Conclusion.}$ Roughly speaking, this means that we can choose in our triangular representation at most $n-1$ locations where the entries are real (for example). In fact, we can really do that as follows
Let our triangular representation be $T=[t_{i,j}]$ with $t_{k,k}=\lambda_k,t_{k-1,k}=\rho_ke^{i\theta_k}$ (polar form).
Then $Te_k=\lambda_ke_k+\rho_ke^{i\theta_k}e_{k-1}+\cdots$. We change $e_k$ with $f_k=e^{-i\theta_k}e_k$. 
Then $Tf_k=\lambda_kf_k+\rho e_{k-1}+\cdots$. By iterating this method, the false diagonal $(i,i+1)$ -with $n-1$ elements- becomes real($\geq 0$).
