STRONG NP-COMPLETENESS OF A MATRIX SIMILARITY PROBLEM

Consider the following problem: given an upper triangular matrix A, wi th rational entries and distinct diagonal elements, and a tolerance ta u greater than or equal to 1, decide whether there exists a nonsingula r matrix G, with condition number bounded by tau, such that G(-1) AG i s 2 x 2 block diagonal. This problem, which we shall refer to as DICHO TOMY, is an important one in the theory of invariant subspaces. It has recently been proved that DICHOTOMY is NP-complete. In this note we m ake some progress proving that DICHOTOMY is actually NP-complete in th e strong sense. This outlines the ''purely combinatorial'' nature of t he difficulty, which might well arise even in case of well scaled matr ices with entries of small magnitude.