Finding Well-Conditioned Similarities to Block-Diagonalize Nonsymmetric Matrices Is NP-Hard

Given an upper triangular matrix A ∈ R^n×n and a tolerance τ, we show that the problem of finding a similarity transformation G such that G⁻¹AG is block diagonal with the condition number of G being at most τ is NP-hard. Let ƒ(n) be a polynomial in n. We also show that the problem of finding a similarity transformation G such that G⁻¹AG is block-diagonal with the condition number of G being at most ƒ(n) times larger than the smallest possible is NP-hard.