3
$\begingroup$

Does the condition number change when a matrix is reordered by e.g. Cuthill Mckee or some other method?

$\endgroup$

1 Answer 1

8
$\begingroup$

No. A reordering of a matrix $\boldsymbol{A}$ is equivalent to conjugation by a permutation matrix $\boldsymbol{P}$. In other words, the reordered matrix can be written as $\boldsymbol{A}_r = \boldsymbol{P}\boldsymbol{A}\boldsymbol{P}^*$ and $\boldsymbol{A}_r^{-1} = \boldsymbol{P}\boldsymbol{A}^{-1}\boldsymbol{P}^*$.

Since the spectral norm is unitarily invariant and permutation matrices are unitary, the $\ell^2$ condition number $$\kappa(\boldsymbol{A}_r) = \|\boldsymbol{A}_r\|_2\|\boldsymbol{A}_r^{-1}\|_2 = \|\boldsymbol{P}\boldsymbol{A}\boldsymbol{P}^*\|_2\|\boldsymbol{P}\boldsymbol{A}^{-1}\boldsymbol{P}^*\|_2 = \|\boldsymbol{A}\|_2\|\boldsymbol{A}^{-1}\|_2 = \kappa(\boldsymbol{A}).$$

$\endgroup$
1
  • 5
    $\begingroup$ Not only does the condition number not change under permutation, but the eigenvalues themselves also do not change. $\endgroup$ Aug 4, 2019 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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