Proving that the eigenvalues of a certain matrix product are positive

Question

Let $A$ be an $m \times n$ matrix, and define: \begin{align*} U &= {\rm diag} \{ \frac{1}{\beta_j} \}, \beta_j = \sum_{k=1}^m |a_{kj}|, j = 1 \dots n \\ V &= {\rm diag} \{ \frac{1}{\alpha_i} \}, \alpha_i = \sum_{k=1}^n |a_{ik}|, i = 1 \dots m. \end{align*}

i.e. $\beta_j$ is the 1-norm of the $j$th column of $A$, and $\alpha_i$ is the 1-norm of the $i$th row. Let $M = UA^TVA$, an $n \times n$ matrix. A direct calculation gives its $(i,j)$th element as \begin{align*} m_{ij} &= \frac{1}{\beta_i} \sum_{k=1}^m \frac{a_{ki} a_{kj}}{\alpha_k}. \end{align*}

If all the elements of $A$ are positive, it's fairly straightforward to show that all the rows of $M$ sum to 1, thus $\Vert M \Vert_\infty=1$, and since $\lambda=1$ is an eigenvalue, it follows that $\rho(M)=1$.

My question is: can one prove that all the eigenvalues of $M$ are positive as well (i.e. that they all lie between 0 and 1)? Empirically this seems to be the case, but I'm having a hard time proving why. $M$ is not SPD. It seems that it might be totally positive, but I'm not sure how to prove that. Any ideas?

(This matrix arises in the Simultaneous Algebraic Reconstruct Technique (SART), an iterative method for solving linear systems.)

Answer 1

That matrix is the product of two positive definite matrices, $M=UW$, with $W=A^TVA$. Hence it is similar to the symmetric matrix $U^{1/2}WU^{1/2}$, which is congruent to $W$ and thus positive definite. For a slightly more general result, see Horn, Johnson, Matrix analysis, 1st ed, Theorem 7.6.3.