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

  • $\begingroup$ I think $M$ can be singular: for example if $A$ is the $n \times n$ matrix with all entries $1,$ then $M$ has all entries $\frac{1}{n},$ and has rank $1$. $\endgroup$ Aug 28 '14 at 15:38

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.

  • $\begingroup$ Isn't the matrix $W$ just positive semi-definite in general? $\endgroup$ Aug 28 '14 at 13:33
  • $\begingroup$ Yes, it is, you are correct. The correct statement should be "$M$ has the same inertia as $W$" (provided $U$ is positive definite --- if $U$ is positive semidefinite as well, a continuity argument can be used). $\endgroup$ Aug 28 '14 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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