Checking positive definiteness or stability of symmetric interval matrices is NP-hard

Jiří Rohn

Commentationes Mathematicae Universitatis Carolinae (1994)

  • Volume: 35, Issue: 4, page 795-797
  • ISSN: 0010-2628

Abstract

top
It is proved that checking positive definiteness, stability or nonsingularity of all [symmetric] matrices contained in a symmetric interval matrix is NP-hard.

How to cite

top

Rohn, Jiří. "Checking positive definiteness or stability of symmetric interval matrices is NP-hard." Commentationes Mathematicae Universitatis Carolinae 35.4 (1994): 795-797. <http://eudml.org/doc/247574>.

@article{Rohn1994,
abstract = {It is proved that checking positive definiteness, stability or nonsingularity of all [symmetric] matrices contained in a symmetric interval matrix is NP-hard.},
author = {Rohn, Jiří},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {positive definiteness; stability; nonsingularity; NP-hardness; positive definiteness; stability; interval matrix; NP-hard},
language = {eng},
number = {4},
pages = {795-797},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Checking positive definiteness or stability of symmetric interval matrices is NP-hard},
url = {http://eudml.org/doc/247574},
volume = {35},
year = {1994},
}

TY - JOUR
AU - Rohn, Jiří
TI - Checking positive definiteness or stability of symmetric interval matrices is NP-hard
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1994
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 35
IS - 4
SP - 795
EP - 797
AB - It is proved that checking positive definiteness, stability or nonsingularity of all [symmetric] matrices contained in a symmetric interval matrix is NP-hard.
LA - eng
KW - positive definiteness; stability; nonsingularity; NP-hardness; positive definiteness; stability; interval matrix; NP-hard
UR - http://eudml.org/doc/247574
ER -

References

top
  1. Garey M.E., Johnson D.S., Computers and Intractability: A Guide to the Theory of NP- Completeness, Freeman, San Francisco, 1979. Zbl0411.68039MR0519066
  2. Nemirovskii A., Several NP-hard problems arising in robust stability analysis, Math. of Control, Signals, and Systems 6 (1993), 99-105. (1993) Zbl0792.93100MR1358063
  3. Poljak S. and Rohn J., Checking robust nonsingularity is NP-hard, Math. of Control, Signals, and Systems 6 (1993), 1-9. (1993) MR1358057
  4. Rohn J., Positive definiteness and stability of interval matrices, SIAM J. Matrix Anal. Appl. 15 (1994), 175-184. (1994) Zbl0796.65065MR1257627

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.