Does the condition number change when a matrix is reordered by e.g. Cuthill Mckee or some other method?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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}).$$
-
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