Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

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$.

V.

share|improve this answer
1  
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
    
@JReichardt you are right. A positive cone around the eigendirection is preserved but not necessarily a cone with the good shape! In dim 3, let v1, v2 and v3 be the eigenvectors with v1 dominating. Then the cone generated by v1-v2, v1+v2, v1-v3 and v1+v3 is preserved. If v2 and v3 are small these 4 vectors are positive. Hence, the question resumes to find 3 vectors instead of 4. In dim 2 my condition seems to work. Do you think that the positivity of the dominant eigenvector and the trace is sufficient in dim 3? Many thanks for your correction and my apologies for my wrong answer! –  V. Delecroix Aug 27 '13 at 1:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.