Can a real matrix have arbitrary complex eigenvalues? Given a set $S$ of complex numbers such that $z\in S \implies \bar{z}\in S$ can I find a real matrix $M$ (in a space of dimension $|S|$) whose eigenvalues are precisely those in $S$? More generally is there a way to know when a real matrix M does exist?
I'm struggling to come up with any counter examples. I thought about proving the stronger statement "Every complex matrix is similar to a real matrix" but I don't think thats easier to show. Something like jordan normal form could be useful but we don't really care about the jordan structure, just the eigenvalues. Another stronger (but less so than the last) that could work is "Every diagonalisable complex matrix is similar to a real matrix". There are also some nice ideas like knowing that the determinant and trace of a real matrix are real but the conjugate property probably makes this useless.
 A: For the case $S=\{a+ib,a-ib\}$ we have the matrix $\begin{pmatrix}a & b\\-b &a\end{pmatrix}$.
For larger sets $S$ just take a matrix with appropriate $2\times 2$ blocks down the diagonal.
For your subsidiary questions clearly $\begin{pmatrix}i\end{pmatrix}$ is not similar to a real matrix.
[Note: Some people even define complex numbers to be these $2\times 2$ matrices.]
A: If a matrix $A$ is real then $P = det(A- \lambda E) = 0$ is a set of zeros of polynomial with real coefficients.
If $z_0$ is a zero of $P$, then $\bar{z}$ is also a zero. Hence, e.g., for $S = \{1, 1+i \}$ the answer is negative.
Now suppose that $S$ consists of real numbers $c_1, c_2, \ldots, c_k$ and pairs of complex numbers: $z_1, \bar{z}_1, ..., z_m, \bar{z}_m$ where $c_j = a_j + i b_j$. Consider $P(u)= (u-c_1)*...*(u-c_k)((u-a_1)^2+b_1^2)*...*((u-a_m)^2+b_m^2)$. It's possible to make a block matrix A with $det(A-uE)= P$: indeed, consider $1*1$ matrices $ (c_i)$ and $2*2$ matrices
\begin{pmatrix}a_j & b_j\\-b_j &a_j\end{pmatrix} and make zero matrix A, which is $ N*N $ matrix (with $N=k+2m$) and then place our $1*1$ and $2*2$ matrices onto diagonal of A.
A: The product $P=\prod_{a\in S}(X-a)$ is by hypothesis equal to its complex conjugate, so it has real entries (and it has of course $S$ as spectrum). Like any monic polynomial $P$ is the minimal (and characteristic) polynomial of the companion matrix of $P$, which therefore has real entries and has $S$ as spectrum.
