I have a matrix that is given by $A e^{i q} + A^* e^{i q}$ with $A$ a nilpotent $n\times n$ matrix. The eigenvalues I get turn out always to be independent on q but I cannot prove it. I want to know how can I prove this (or if this alone is not sufficient for the eigenvalues to be independent on q)

The OP has added a lot of conditions to his original statement, so my answer is significantly revised. The OP's statement is still not true. This answer uses ideas from Denis's answer so, if you like this, vote us both up. Let $A=(B/2)i(C/2)$, with $B$ and $C$ hermitian. Set $z=x+iy$. We will be interested in the polynomial $$F(x,y) := \det(\mathrm{Id}+zA+\overline{z}A^*) = \det(\mathrm{Id} + x B + y C).$$ By a result of Helton and Vinnikov, given a degree $n$ polynomial $F(x,y)$, there are Hermitian matrices $B$ and $C$ such that $F=\det(\mathrm{Id} + x B + y C)$ if and only if $F(0,0)=1$ and every line through the origin meets $F=0$ at $n$ (real) points. (Vinnikov's paper analyzes the case that $F=\det(xB+yC+D)$, with $D$ positive definite. But, if $D$ is positive definite then we can write $D=SS^*$ and then $\det(S^{1} B (S^*)^{1} x + S^{1} C (S^*)^{1} C+\mathrm{Id})$ is a scalar multiple of $\det(xB+yC+D)$. So it is easy to relate Vinnikov's formulation to ours.) I will give polynomials $F$ and thus implicitly give matrices $A$. Making this correspondence explicit is a difficult computational task, so I won't do it. Of course, I need to check that (Condition 1) Every line through $(0,0)$ meets it at $n$ (real) points, and $F(0,0)=1$. Now, the OP has imposed the following conditions: (Condition 2) The matrix $A$ is nilpotent. This is equivalent to $\det(\mathrm{Id}+zA) = 1$. So we want $F \equiv 1 \mod (xiy)$. Since $F$ is a polynomial with real coefficients, I might as well rewrite this as $F \equiv 1 \mod x^2+y^2$. (Condition 3) $\det (e^{i \theta} A + e^{i \theta} A^*)$ is of the form $a + b \cos (n/2) \theta + c \cos n \theta$. Switching to our $x$, $y$ coordinates, when $z=e^{i \theta}$ we have $x=\cos \theta$ and $y = \sin \theta$. So this condition says that $F(\cos \theta, \sin \theta) = a + b \cos (n/2) \theta + c \cos n \theta$. In my example, we will have $F(\cos \theta, \sin \theta) =1$. The OP asks whether this implies that the eigenvalues of $e^{i \theta} A + e^{i \theta} A^*$ are independent of $\theta$. These eigenvalues are real numbers, since they are eigenvalues of a Hermitian matrix. We see that $s$ is an eigenvalue if and only if $\det (\mathrm{Id}  s^{1}(e^{i \theta} A + e^{i \theta} A^*))=0$ or, in other words, if $F(s^{1} \cos \theta, s^{1} \sin \theta)=0$. So these eigenvalues are the reciprocals of the points where a line through the origin meets $F=0$. In short, the question is whether conditions 1, 2 and 3 force $F=0$ to be a union of concentric circles. And the answer is no. Consider the polynomial $$110(x^2+y^2)(x^2+y^21)(x^2+2y^23)$$ As you can see in the plot below, this is $3$ ovals nested around the origin, so every line through $(0,0)$ meets it $6$ times. The other conditions are obvious. (Note that, although the inner ovals look like circles, they are not; this polynomial is irreducible. In any case, the outer polynomial is clearly not a circle.) 


Even with the assumption that $e^{iq}A+e^{iq}B$ is Hermitian, that is $B=A^* $, the claim is not true. The characteristic polynomial $P(X,z)$ of $zA+\bar zA^*$, written in terms of the real and imaginary parts $z=Y+iZ$ is a Hyperbolic polynomial. Actually, every hyperbolic polynomial can be written that way, according to a conjecture of P. Lax, proved by Helton and Vinnikov. For instance, $$X^2Y^2Z^2=\det\begin{pmatrix} XY & Z \\\\ Z & X+Y \end{pmatrix}$$ corresponds to the matrix $$A=\begin{pmatrix} 1 & i \\\\ i & 1 \end{pmatrix}.$$ This matrix turns out to be nilpotent, as you require. Perhaps this is the case that you investigated, because here the eigenvalues of $zA+\bar zA^* $ are $\pmz$, thus constant $\equiv\pm1$ when $z=e^{iq}$. However, the following is a counterexample: $$A=\begin{pmatrix} 0 & 1 & 1 \\\\ 0 & 0 & 1 \\\\ 0 & 0 & 0 \end{pmatrix}.$$ When $z$ runs over the unit circle, the eigenvalues of $zA+\bar zA^* $ form a cardioid, plus its bitangent. Edit. The parity of $n$ does not matter. As said by David, there are plenty of hyperbolic polynomials. Take $n=4$ and $P_0(X,z)=(X^2z^2)(X^22z^2)$. It is strictly hyperbolic (distinct roots for every nonzero $z$). Then every polynomial $P(X,Y,Z)$ close enough to $P_0$ is hyperbolic. According to LaxHeltonVinnikov, $P$ is the characteristic polynomial of some $zA+\bar zA^* $. Actually, you can start from the nilpotent matrix $A_0$ attached to $P_0$ and perturb it keeping it nilpotent.. Still you get plenty of $P$, most of them nonconstant over the unit circle. 


Let $$A=\pmatrix{0&0&0\cr 1&0&0\cr 1&1&0}.$$ The eigenvalues of $A+A^T$ (q=0) are 2,1,1. The eigenvalues of $AA^T$ (q=$\pi$) are 2,1,1. 


I finally found out the property that resulted in the fact that eigenvalues in my case are independent of $q$. In my case, I found that $Tr((A e^{i q} + A^* e^{i q})^m)$ is independent on $q$ for any $m$. In which case, it is not difficult to prove that the eigenvalues should be independent on $q$ having $\sum_i \lambda_i^m \frac{\partial \lambda_i }{\partial q}= 0 $ for all $m$ we can form a linear combination of these equations such that $\sum_i P(\lambda_i) \frac{\partial \lambda_i }{\partial q}= 0 $ where P is some polynomial that we can choose such that $P(\lambda_i) = \frac{\partial \lambda_i }{\partial q}$ given any $q$ and this way we can see that $\frac{\partial \lambda_i }{\partial q}$ vanishes. However, I am still interested to see how such a constraint can be implemented in David's solution (what does it correspond to regarding F). 

