Description
How ill-conditioned must a matrix S be if it (block) diagonalizes a given matrix T, i.e. if S(-1)TS is block diagonal? The answer depends on how the diagonal blocks partition T's spectrum; the condition number of S is bounded below by a function of the norms of the projection matrices determined by the partitioning. In the case of two diagonal blocks we compute an S which attains this lower bound, and we describe almost best conditioned S's for dividing T into more blocks. We apply this result to bound the error in an algorithm to compute analytic functions of matrices, for instance exp(T). Our techniques also produce bounds for submatrices that appear in the square-root-free Choleskt and in the Gram-Schmidt orthogonalization algorithms.