# When is a matrix similar to a non-negative matrix?

Consider a real square matrix $A$ of size $n\times n$. Under which conditions on $A$ does there exist a row-stochastic matrix $U$ (non-negative, rowsums = 1), such that $A'=U^{-1}AU$ is a non-negative matrix? In other words, does there exist a row-stochastic matrix $U$ such that the linear system $AU = UA'$ will have a solution with non-negative $A'$? Geometrically, we are asking: When are the columns of the product $AU$ inside the cone generated by the columns of $U$.

If $U$ exists, how can you determine it? If there is no analytic solution, I'd also be happy with a numerical procedure that converges to $U$.

Consider the following examples for $n=2$:

a) the trivial case: Let $A$ be already non-negative, then $U$ can be the identity and we are done. If all entries of $A$ are strictly positive we have an infinite number of possible matrices $U$. The cone spanned by the columns of $U$ only needs to contain the columns of $A$.

b) only one solution: consider $A=\left( \begin{array}{cc} -1/2 & 1\\\ 1/4 & 1/2\end{array}\right)$ which can be transformed with $U=\left( \begin{array}{cc} 1 & 0\\\ 1/2 & 1/2\end{array}\right)$ into $U^{-1}AU = A'=\left( \begin{array}{cc} 0 & 1/2\\\ 1 & 0\end{array}\right)$

c) no solution: consider $A=\left( \begin{array}{cc} -1/2 & 1\\\ 1/4 & 1/8\end{array}\right)$ for which one cannot find an appropriate $U$.

Thanks for any suggestions!

-

If the column of $AU$ belongs (strictly) inside the space generated by the columns of $U$ then you have a dominant eigenvector inside $U$ (ie an eigenvector whose eigenvalue is real positive and of maximum modulus). It is Perron-Frobenius theorem.
EDIT: Now given a matrix $A$, a necessary condition is to check that it admits a real positive dominant eigenvalue whose eigenvector is positive. Another necessary condition is that the trace of $A$ is positive (see the comment of @JReichardt below).
In your second example the positive eigenvector whose eigenvalue is positive ($0.40\ldots$) is not dominating as the other eigenvalue is $-0.77\ldots$.
One necessary condition is certainly that the trace of $\mathbf{A}$ be non-negative, as the trace is conserved under similarity transform. This is not the case in example c), hence no solution. In example b), the trace is zero which might hint at the fact that there is only one solution. I think one could construct a matrix with positive dominant eigenvalue and all non-negative dominant eigenvector and still have a negative trace when $n>2$ and thus no solution. What V. Delecroix seems suggesting there is a converse of the PF-Theorem, which I don't think exists. Please prove me wrong! –  J Reichardt Aug 15 '13 at 12:13