3
$\begingroup$

Suppose $A$ and $P$ are symmetric, positive definite matrices and that we factor $P^{-1}=EE^\top.$ Is it true that the condition number of $PA$ is upper-bounded by the condition number of $E^{-1}AE^{-\top}$?

The two matrices clearly have the same eigenvalues, but $PA$ may not be symmetric. So, I wasn't sure if this still implies that they have the same singular values.

[Apologies if this is a goofy question! Just a potential hole in a proof of preconditioning for conjugate gradients...]

REVISION: The two matrices do not have the same singular values, but numerically it appears $\mathrm{cond}\ PA\geq\mathrm{cond}\ E^{-1}AE^{-\top}.$ I'm totally stuck how to prove this!

Improve this question
$\endgroup$
4
  • $\begingroup$ I understand! In this case, I know that $PA$ and $E^{-1}A E^{-\top}$ have the same eigenvalues. Am I missing an obvious argument that applies the definition you mention to showing that they have the same singular values? $\endgroup$
    – Justin
    Commented May 28, 2015 at 17:39
  • $\begingroup$ This is what I'm trying to do :-) In other words, we're comparing the eigenvalues of $PAAP$ and $E^{-1}APAE^{-\top}$. These are not obviously the same to me -- but I'm operating on very little sleep at the moment! A student asked about this and I'm embarrassed I'm stumped :-) $\endgroup$
    – Justin
    Commented May 28, 2015 at 17:46
  • $\begingroup$ Oh, sorry to have given obvious pointers. I agree that that it does not follow that the SVs are the same. $\endgroup$
    – Yoav Kallus
    Commented May 28, 2015 at 17:48
  • $\begingroup$ Updated a bit. The two matrices don't have the same singular values, but the condition number statement appears to be true. Totally stuck! $\endgroup$
    – Justin
    Commented May 28, 2015 at 19:09

1 Answer 1

Reset to default
2
$\begingroup$

Yes, $\kappa(E^{-1}AE^{-T}) \le \kappa(PA)$. For any matrix $X$, $|\lambda| \le \Vert X \Vert$ holds for any eigenvalue and any induced norm (since $\Vert \lambda u \Vert$ = $\Vert X u \Vert \le \Vert X \Vert \Vert u \Vert$ for the eigenvector $u$). Similarly, if $X$ is invertible, then $|\lambda^{-1}| \le \Vert X^{-1} \Vert$ for any eigenvalue. Now take $X = PA$ and apply these inequalities with the largest and smallest eigenvalues. Multiplying, we see that $$ \kappa( E^{-1}AE^{-T} ) = |\lambda_{\text{max}}|/|\lambda_{\text{min}}| \le \Vert PA \Vert \Vert (PA)^{-1} \Vert = \kappa( PA ) . $$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Of course! Thank you so much -- this has been driving me nuts. $\endgroup$
    – Justin
    Commented Jun 2, 2015 at 16:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .