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 of $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$).

$\begingroup$ According to Mathematica, your example has eigenvalues 1 and 1 for any $q.$ $\endgroup$ – Igor Rivin Jan 5 '11 at 15:34

2$\begingroup$ More people should vote Denis's answer up. It responds to Eslam's updates, and adds a lot of insight. $\endgroup$ – David E Speyer Jan 5 '11 at 17:16
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.)

$\begingroup$ @David. You beat for seconds. My example was the transpose of yours. I delete it. $\endgroup$ – Denis Serre Jan 5 '11 at 15:49

$\begingroup$ thanks for your reply. Seemingly I forgot to add very important piece of information which is that $A e^{i q} + B e^{i q}$ is hermitian (and thus $A$ and $B$ are hermitian conjugates of each other). Also in the case I am considering $n$ is always even (although I am not sure if this is relevant) $\endgroup$ – Eslam Jan 5 '11 at 15:58

$\begingroup$ Let me edit your question and add this assumption. $\endgroup$ – Denis Serre Jan 5 '11 at 16:17

1$\begingroup$ @David. You might be interested by my recent paper (collaboration with Thierry Gallay) The numerical measure of a complex matrix, arXiv:1009.1522v1 . $\endgroup$ – Denis Serre Jan 6 '11 at 7:52
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.

2$\begingroup$ To connect our ideas together, the point here is that there are plenty of polynomials $F(x,y)$ such that $F$ is hyperbolic, and $F \equiv 1 \mod x^2+y^2$, but $F$ is not a function of $x^2+y^2$. For example, your matrix gives $13(x^2+y^2)+2x (x^2+y^2)$ $\endgroup$ – David E Speyer Jan 5 '11 at 16:42

$\begingroup$ Thanks for the reply. Seemingly all the details of my particular problem has to do with the fact that my eigenvalues come out independent on q for all even dimensions I tried so far. For example one more thing I deduced is that in my problem (whether or not the matrices are nilpotent) the eigenvalues can be written as $\epsilon_k(q) = \sum_{l=0}^{\infty} a_{kl} cos(\frac{n}{2}lq)$ where n is the matrix dimension (which is always even) $\endgroup$ – Eslam Jan 5 '11 at 16:51

$\begingroup$ Continuing to use Denis's very nice coordinates, we have $X=\cos \theta$ and $Y = \sin \theta$. Your added condition is that $F(\cos \theta, \sin \theta)$ has all Fourier coefficients even or, in other words, that it is an even function of $\theta$. That means there must be no odd powers of $y$. Denis's polynomial has that property. $\endgroup$ – David E Speyer Jan 5 '11 at 17:07

$\begingroup$ Oh and, of course, you can easily embed Denis's example into a $4 \times 4$ example by padding with $0$'s. $\endgroup$ – David E Speyer Jan 5 '11 at 17:09

$\begingroup$ the condition I added is not only that it is even but that only component which are multiples of $\frac{n}{2}$ are nonvanishing. $\endgroup$ – Eslam Jan 5 '11 at 17:31
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).