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 tau greater than or equal to 1, decide whether there exists a nonsingular matrix G, with condition number bounded by tau, such that G(-1) AG is 2 x 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.