Strong NP-completeness of a Matrix Similarity Problem

Consider the following problem: given an upper triangular matrix A, with rational entries and distinct diagonal elements, and a tolerance τ greater than or equal to 1, decide whether there exists a nonsingular matrix G, with condition number bounded by τ, such that G^(−1)AG is 2 × 2 block diagonal. This problem, which we shall refer to as DICHOTOMY, is an important one in the theory of invariant subspaces. It has recently been proved that DICHOTOMY is NP-complete. In this note we make some progress proving that DICHOTOMY is actually NP-complete in the strong sense. This outlines the “purely combinatorial” nature of the difficulty, which might well arise even in case of well scaled matrices with entries of small magnitude.