Any complex number can be the eigenvalue of some non-negative matrix Let $z\in\Bbb C$. Show that there exists a non-negative matrix $A$ (with entries $\geq 0$) such that $z$ is an eigenvalue of $A$.
If $z$ is real, it is easy.
Since, $a\geq 0$ is an eigenvalue of 
$$\begin{pmatrix}
a&0\\
0&a
\end{pmatrix};$$
while $a<0$ is an eigenvalue of 
$$\begin{pmatrix}
0&-a\\
-a&0
\end{pmatrix}.$$
For complex $z$, we should need the rows of $A$ is greater than $3$...Con we construct it? Or could we prove the statement above by using some facts of non-negative matrices...
 A: Following Hagen's example, we have the following $3 \times 3$ solution:
Suppose that we have $z = a + b \omega$ where 
$\omega = -\frac 12 + i\frac{\sqrt 3}{2} = e^{2\pi i/3}$. Setting 
$$
J = \pmatrix{&1\\&&1\\1},\quad
K = \pmatrix{&1&1\\1&&1\\1&1}, \quad
x = \pmatrix{1\\ \omega \\ \omega^2}
$$
We note that $Jx = \omega x$ while $Kx = -x$.  Thus, we may state that for $a,b \in \Bbb R$,
$$
aI + bJ
$$
(where $I$ is the identity matrix) has the eigenvalue $a + b \omega$ (and $a + b \overline \omega$) whereas
$$
aK + bJ
$$
has the eigenvalue $-a + b\omega$ (and $-a + b \overline \omega$).
This family of matrices is sufficient.
It can be shown that any eigenvalue of a non-negative $2 \times 2$ matrix has positive real-part.

My original solution:
For $z$ with positive real part, it suffices to find any non-negative matrix with a complex eigenvalue.
In particular, we note that
$$
J = \pmatrix{&&&1\\1\\&1\\&&1}
$$
Has characteristic equation $\lambda^4 = 1$, so that $\pm i$ is an eigenvalue.  It follows that the matrix
$$
aI + bj
$$
(where $I$ is the identity matrix) has eigenvalue $a \pm bi$.
We could do something similar with the matrix $J =\pmatrix{&&1\\1\\&1}$ since we may write all complex numbers in the form $a + b \omega$, where $\omega^3 = 1$.
In fact, from here, we're done if we use the appropriate $2n \times 2n$ matrix: note that for any matrix $A$, the eigenvalues of the block-matrix
$$
\pmatrix{0&A\\A&0}
$$
Are $\pm \lambda$ for all eigenvalues $\lambda$ of $A$.
A: As Byron Schmuland has pointed out in another thread, every point $a+ib$ inside the closed equilateral triangle with corners $1,\omega,\omega^2$ (where $\omega$ is a cube root of unity) can be realised as the eigenvalue of a doubly stochastic matrix of the form
$$
P=\begin{bmatrix}1-s-t&s&t\\ t&1-s-t&s\\ s&t&1-s-t \end{bmatrix},
$$
where $s=\frac{1-a}3+\frac{b}{\sqrt{3}}$ and $t=\frac{1-a}3-\frac{b}{\sqrt{3}}$.
The constraint that $a+ib$ lies inside the triangle formed by $1,\omega,\omega^2$ would make $s,t\ge0$ and $s+t\le1$. (Note that $P$ is also a circulant matrix, so that its whole spectrum can be expressed explicitly in terms of the coefficients on the first row.)
Consequently, every complex number $z$ is the eigenvalue of some nonnegative multiple of a doubly stochastic matrix.
A: It suffices to consider nonnegative imaginary part.
We verify directly that
$$ 
\begin{pmatrix}a&b&0&0\\0&a&b&0\\0&0&a&b\\b&0&0&a\end{pmatrix}\begin{pmatrix}1\\i\\-1\\-i\end{pmatrix}=(a+bi)
\begin{pmatrix}1\\i\\-1\\-i\end{pmatrix} 
$$
and
$$ 
\begin{pmatrix}0&b&a&0\\0&0&b&a\\a&0&0&b\\b&a&0&0\end{pmatrix}\begin{pmatrix}1\\i\\-1\\-i\end{pmatrix}=(-a+bi)
\begin{pmatrix}1\\i\\-1\\-i\end{pmatrix} 
$$
A: And now for something much more complicated:
Suppose $\lambda \in \mathbb{C}$.
The OP has dealt with purely real eigenvalues, so we may assume that 
$\operatorname{im} \lambda \neq 0$. A real matrix has eigenvalues in conjugate pairs, so we need only deal with
$\operatorname{im} \lambda >0$. If the matrix $A$ has an eigenvalue $\lambda$, then the matrix $rA$ has an eigenvalue $r \lambda$, so we may assume that $|\lambda| = 1$, and so $\lambda = e^{i \theta}$ for some $\theta \in (0, \pi)$.
Let $P_n$ be the 'shift right' permutation matrix, that is, $P_ne_k = e_{k+1}$ for $k=1,...,n-1$ and $P_n e_n = e_1$. Since $P_n^k \neq I$ for $k=1,...,n-1$ and $P_n^n = I$, we see that the eigenvalues are the $n$th
roots of unity. Hence the eigenvalues of the permutation matrices $\{P_n\}$ are dense in the unit circle.
Note that $i$ is an eigenvalue of $P_4$, hence if $ \theta \in (0, { \pi \over 2}]$, we see that $e^{i \theta}$ is an eigenvalue of $(\cos \theta) I + (\sin \theta )P_4$.
We need to deal with the remaining case where $ \theta \in ({ \pi \over 2}, \pi)$.
In particular, we can find some $P_n$ with an eigenvalue $e^{i \omega}$, where ${ \pi \over 2} < \theta < \omega < \pi$. Then
$e^{i \theta}$ is an eigenvalue of $(\cos \theta - {\sin \theta \over \sin \omega} \cos \omega) I + {\sin \theta \over \sin \omega}P_n$ (since $\cos \theta \sin \omega - \sin \theta  \cos \omega = \sin (\omega-\theta)$, then $\cos \theta - {\sin \theta \over \sin \omega} \cos \omega \ge 0$).
