unitary reduction of $q$-normal matrices The unitary reduction of normal matrices is a well-known fact: if $A\in M_n(\mathbb C)$ commutes with its Hermitian adjoint $A^*$, then there exists a unitary $U\in\mathbb U_n$ and a diagonal matrix $D$ such that $A=U^*DU$. And conversely, such a $U^*DU$ is normal.
Besides, the theorem of Amitsur & Levitski tells us that the standard polynomial $\mathcal S_{2n}$ in non-commutative variables vanishes identically over $M_n(k)$, where
$$\mathcal S_p(A_1,\ldots,A_p):=\sum_\sigma \epsilon(\sigma)A_{\sigma(1)}\cdots A_{\sigma(p)},$$
where $\sigma$ runs over the symmetric group $\mathfrak S_p$.
Now, let me say that a matrix $A$ is $q$-normal if $\mathcal S_{2q}$ vanishes identically over the sub-algebra spanned by $A$ and $A^*$. For instance, a $1$-normal matrix is normal, whereas every $n\times n$ matrix is $2n$-normal.

Given a $q$-normal matrix $A$. Does there exist a unitary matrix $U$ and a block-diagonal matrix $D$ with diagonal blocks of sizes $\le q$, such that $A=U^*DU$ ?

 A: Yes.  First, decompose $A$ as an orthogonal sum of irreducible operators.  Call $B$ one of the irreducible summands, acting on a space $M$ of dimension $m$, and note that $B$ is $q$-normal.  Irreducibility implies that the algebra generated by $B$ and $B^*$ is precisely the algebra of linear operators on $M$.  Thus the algebra of $m\times m$ matrices satisfies ${\mathcal S}_q$, and this implies that $m\le q$.
A: The following is a development along Hari's answer.
As mentionned by Hari, we may assume that $B$ is an irreducible summand of size $m$. It inherits $q$-normality. Let $L$ be the sub-algebra of $M_m(\mathbb C)$ spanned by $B$ and $B^*$. 
The subspace $\ker B\cap\ker B^* $ is invariant under $B$ and $B^* $. From irreducibility, we must have $\ker B\cap\ker B^* =\{0\}$. Set $H:=BB^* + B^* B$, which is Hermitian positive definite. From Cayley-Hamilton, $I_m$ is a polynomial in $H$, thus belongs to $L$. Therefore $L$ is unit algebra.
We prove now that $L$ is a simple algebra: let $J\ne(0)$ be a two-sided ideal in $L$. Denote $K$ the intersection of all $\ker M\cap\ker M^* $  when  $M\ne0$ runs over $J$. Because of finite dimension, it is actually the intersection of finitely many, say for $M_1,\ldots,M_r$. Then $K=\ker \sum_j(M_jM_j^* +M_j^* M_j)$. Because $J$ is an ideal, $K$ is stable under $B$ and $B^*$. Because $B$ is irreducible, one has either $K=(0)$ or $K={\mathbb C}^m$. The latter is impossible, and the former tells us that $J$ contains an invertible element. Therefore $J=L$ and $L$ is simple.
By Wedderburn's theorem, $L$ is isomorphic to $M_r(K)$ for some $r\ge1$, where $K$ is a division ring with $\mathbb C$ in its center. Because $L$ is finitely generated, $K$ must be of finite dimension over $\mathbb C$. From Frobenius' theorem, $K=\mathbb C$. Finally, $L$ is isomorphic to $M_r(\mathbb C)$. 
At last, the morphism $M\mapsto M$ from $L$ into $M_m(\mathbb C)$ is a representation. By assumption, it is irreducible. From Corollary 11.6 and Lemma 11.5 of M. Takesaki's Theory of Operator Algebra, I, we obtain $r=m$. Therefore $L=M_m(\mathbb C)$.
By assumption, $\mathcal S_{2q}$ vanishes identically over $L$, thus over $M_m(\mathbb C)$. This implies easily $m\le q$.
