3
$\begingroup$

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

$\endgroup$
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$
  • 5
    $\begingroup$ Not only does the condition number not change under permutation, but the eigenvalues themselves also do not change. $\endgroup$ – Wolfgang Bangerth Aug 4 at 20:34

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.