Creating a random normal matrix

I would like to create a random matrix with the constraint that the matrix must be normal, i.e. the matrix and its Hermitian conjugate must commute. I would create a random matrix "without constraints" as

    RandomReal[NormalDistribution[0,s],{n,n}]+ 

    I*RandomReal[NormalDistribution[0,s],{n,n}]

But I have no idea how I can implement the constraint, that the matrix must be normal.

Answer

Why not start with an eigendecomposition?

n = (* desired dimension *);
(* random unitary matrix *)
q = Orthogonalize[RandomVariate[NormalDistribution[], {n, n}] +
                  I RandomVariate[NormalDistribution[], {n, n}]]
(* random normal matrix *)

mat = q.DiagonalMatrix[RandomVariate[NormalDistribution[], n] +
                       I RandomVariate[NormalDistribution[], n]].ConjugateTranspose[q]

You can check the normality of mat with mat.ConjugateTranspose[mat] - ConjugateTranspose[mat].mat // Chop; it should return an array of 0s.

I'm not entirely sure of what distribution a matrix generated in this manner follows, though.