Algorithm to determine if integer matrix is similar to symmetric integer matrix with nonnegative entries Let $A\in M_n(\mathbb{C})$ be a matrix with integer entries (treated as a matrix over the complex numbers).
Is there an efficient way to check if $A$ is similar to a symmetric matrix with nonnegative integer entries?
Partial answers will be appreciated as well (for example, discard the condition of positivity, or give interesting necessary conditions).
Ofcourse, such $A$ must be diagonalizable, and my $A$ is indeed diagonalizable.
 A: This is a partial answer. Let's look only for matrices that are similar to matrices with positive entries (not necessariy symmetric). Some simple sufficent conditions can be obtained. 
For example, let $A$ be a matrix of order $n$ with integer entries. Let us assume that the eigenvalues of $A$ are $\lambda_1,\ldots,\lambda_n$. Notice that the trace of $A$ can not be  negative. Thus, $\lambda_1+\ldots+\lambda_n\geq 0$.
A sufficient condition for this $A$ to be similar to a matrix with non negative integer entries is $$\lambda_1>0>\lambda_2>\ldots>\lambda_n\text{ and }\lambda_1+\ldots+\lambda_n\geq 0 .$$ 
Proof:
The minimal polynomial $m_A(x)$ of $A$ is the caractheristic polinomial since $A$ has distinct eigenvalues. So, $m_A(x)=(x-\lambda_1)\ldots(x-\lambda_n)=x^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0$. 
Let's prove by induction on the degree of the polynomial that $a_{i}\leq 0$ for $0\leq i\leq n-1$. Notice that $a_i$ is an integer, since the entries of $A$ are integers. For $n=1$, $m_A(x)=(x-\lambda_1)$. 
Suppose the result is true for $n=k$.
Consider $(x-\lambda_1)\ldots(x-\lambda_k)=x^{k}+b_{k-1}x^{k-1}+\ldots+b_1x+b_0$.
By induction hypothesis $b_i\leq 0$ for $0\leq i\leq k-1$. 
Now $(x-\lambda_1)\ldots(x-\lambda_k)(x-\lambda_{k+1})=(x^{k}+b_{k-1}x^{k-1}+\ldots+b_1x+b_0)(x-\lambda_{k+1})$ 
$=x^{k+1}+(b_{k-1}-\lambda_{k+1})x^k+(b_{k-2}-\lambda_{k+1}b_{k-1})x^{k-1}+\ldots+(b_0-\lambda_{k+1}b_1)x+(-\lambda_{k+1}b_0)$.
Notice that $b_{k-1}-\lambda_{k+1}=-\lambda_1\ldots-\lambda_{k+1}\leq 0$
Notice that $b_{k-s-1}-\lambda_{k+1}b_{k-s}\leq 0$, because $\lambda_{k+1}<0$ and $b_{s}\leq 0$. 
Thus,all coefficients are smaller or equal to $0$.
Finally, by the rational canonical form this matrix $A$ is similar to the companion matrix of the polynomial $m_A(x)$, which has non negative integer entries.  $\square$
