If a real matrix has a complex eigenvalue on the unit circle, when is it a root of unity? Let $A$ be a real matrix with integer entries, and suppose $z$ is a complex eigenvalue of $A$ with $|z|=1$. As shown in this answer, $z$ need not be a root of unity (i.e. there need not exist an $m$ with $z^m = 1$). Under which conditions on $A$ can this be guaranteed? What if all of $A$'s entries are either $1$ or $0$?

all 1 and 0 is not good enough. This first characteristic polynomial is the one given by Jose Carlos Santos in your earlier question If an eigenvalue of an integer matrix lies on the unit circle, must it be a root of unity?
$$
\left(
\begin{array}{cccc}
1&1&1&0 \\
1&1&0&1 \\
0&1&0&0 \\
0&0&1&0 \\
\end{array}
\right)
$$
$$ x^4 - 2 x^3 - 2x + 1 = \left(x^2 - (1 + \sqrt 3)x+1 \right) \left(x^2 - (1 - \sqrt 3)x+1 \right)$$
Characteristic polynomial can be solved by dividing by $x^2,$ then writing as a quadratic function of $x + \frac{1}{x}$
Here is another one, the characteristic polynomial is once again palindromic. The roots can be found by the same trick.  
$$
\left(
\begin{array}{cccc}
1&1&1&1 \\
1&1&1&0 \\
0&1&0&1 \\
1&1&0&0 \\
\end{array}
\right)
$$
$$ x^4 - 2 x^3 - 2 x^2 - 2x + 1 = \left(x^2 - (1 + \sqrt 5)x+1 \right) \left(x^2 - (1 - \sqrt 5)x+1 \right) $$
parisize = 4000000, primelimit = 500000
? m =    [1,1,1,0;1,1,0,1;0,1,0,0;0,0,1,0]
%1 = 
[1 1 1 0]

[1 1 0 1]

[0 1 0 0]

[0 0 1 0]

? charpoly(m)
%2 = x^4 - 2*x^3 - 2*x + 1
? 
? 

