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.

Strong NP-completeness of a Matrix Similarity Problem / V., Brimkov; B., Codenotti; Leoncini, Mauro; G., Resta. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 165:(1996), pp. 483-490.

Strong NP-completeness of a Matrix Similarity Problem

LEONCINI, Mauro;
1996

Abstract

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.
165
483
490
Strong NP-completeness of a Matrix Similarity Problem / V., Brimkov; B., Codenotti; Leoncini, Mauro; G., Resta. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 165:(1996), pp. 483-490.
V., Brimkov; B., Codenotti; Leoncini, Mauro; G., Resta
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/454046
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact