  We prove that for any fixed unitary matrix $U$, any abelian self-adjoint
algebra of matrices that is invariant under conjugation by $U$ can be embedded
into a maximal abelian self-adjoint algebra that is still invariant under
conjugation by $U$. We use this result to analyse the structure of matrices $A$
for which $A^*A$ commutes with $AA^*$, and to characterize matrices that are
unitarily equivalent to weighted permutations.
