Checking robust nonsingularity is NP-hard View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1993-03

AUTHORS

Svatopluk Poljak, Jiří Rohn

ABSTRACT

We consider the following problem: givenk+1 square matrices with rational entries,A0,A1,...,Ak, decide ifA0+r1A1+···+rkAk is nonsingular for all possible choices of real numbersr1, ...,rk in the interval [0, 1]. We show that this question, which is closely related to the robust stability problem, is NP-hard. The proof relies on the new concept ofradius of nonsingularity of a square matrix and on the relationship between computing this radius and a graph-theoretic problem. More... »

PAGES

1-9

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01213466

DOI

http://dx.doi.org/10.1007/bf01213466

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1044313251


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Charles University", 
          "id": "https://www.grid.ac/institutes/grid.4491.8", 
          "name": [
            "Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostransk\u00e9 n\u00e1m. 25, 118 00, Praha 1, Czechoslovakia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Poljak", 
        "givenName": "Svatopluk", 
        "id": "sg:person.010341750121.94", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010341750121.94"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Charles University", 
          "id": "https://www.grid.ac/institutes/grid.4491.8", 
          "name": [
            "Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostransk\u00e9 n\u00e1m. 25, 118 00, Praha 1, Czechoslovakia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rohn", 
        "givenName": "Ji\u0159\u00ed", 
        "id": "sg:person.013253342331.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013253342331.37"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0166-218x(86)90065-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007919180"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(86)90065-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007919180"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-82739-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035782209", 
          "https://doi.org/10.1007/978-3-642-82739-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-82739-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035782209", 
          "https://doi.org/10.1007/978-3-642-82739-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0024-3795(89)90004-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036753136"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(86)90192-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052392540"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(86)90192-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052392540"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322248.322260", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053243506"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1049/ip-d.1982.0053", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1056847779"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0401037", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062844526"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/cdc.1989.70071", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086182591"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4064/cm-23-1-165-171", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091799178"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1993-03", 
    "datePublishedReg": "1993-03-01", 
    "description": "We consider the following problem: givenk+1 square matrices with rational entries,A0,A1,...,Ak, decide ifA0+r1A1+\u00b7\u00b7\u00b7+rkAk is nonsingular for all possible choices of real numbersr1, ...,rk in the interval [0, 1]. We show that this question, which is closely related to the robust stability problem, is NP-hard. The proof relies on the new concept ofradius of nonsingularity of a square matrix and on the relationship between computing this radius and a graph-theoretic problem.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01213466", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1135855", 
        "issn": [
          "0932-4194", 
          "1435-568X"
        ], 
        "name": "Mathematics of Control, Signals, and Systems", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "6"
      }
    ], 
    "name": "Checking robust nonsingularity is NP-hard", 
    "pagination": "1-9", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d31442f63cc99497c475ed9096b44aa281a6132e233b7cdee966f259dd9bf27b"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01213466"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044313251"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01213466", 
      "https://app.dimensions.ai/details/publication/pub.1044313251"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:34", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000370_0000000370/records_46772_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF01213466"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf01213466'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf01213466'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01213466'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01213466'


 

This table displays all metadata directly associated to this object as RDF triples.

96 TRIPLES      21 PREDICATES      36 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01213466 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N26599123f22b4caa8ac9df4ae33efc68
4 schema:citation sg:pub.10.1007/978-3-642-82739-6
5 https://doi.org/10.1016/0012-365x(86)90192-5
6 https://doi.org/10.1016/0024-3795(89)90004-9
7 https://doi.org/10.1016/0166-218x(86)90065-x
8 https://doi.org/10.1049/ip-d.1982.0053
9 https://doi.org/10.1109/cdc.1989.70071
10 https://doi.org/10.1137/0401037
11 https://doi.org/10.1145/322248.322260
12 https://doi.org/10.4064/cm-23-1-165-171
13 schema:datePublished 1993-03
14 schema:datePublishedReg 1993-03-01
15 schema:description We consider the following problem: givenk+1 square matrices with rational entries,A0,A1,...,Ak, decide ifA0+r1A1+···+rkAk is nonsingular for all possible choices of real numbersr1, ...,rk in the interval [0, 1]. We show that this question, which is closely related to the robust stability problem, is NP-hard. The proof relies on the new concept ofradius of nonsingularity of a square matrix and on the relationship between computing this radius and a graph-theoretic problem.
16 schema:genre research_article
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf N8391d354602b425fa2b5b22ee404e201
20 Nf4c71aebd68040878a0bca68d5ab864d
21 sg:journal.1135855
22 schema:name Checking robust nonsingularity is NP-hard
23 schema:pagination 1-9
24 schema:productId N1a8eec0aa33341c2903ee691b85eb48f
25 N2bba8835fff544cfa1b27a2b5d8943a7
26 N7d51bf23ec364cf7adeab0b95309e99b
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044313251
28 https://doi.org/10.1007/bf01213466
29 schema:sdDatePublished 2019-04-11T13:34
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N9a3d053f88014a5b810ca6fe4b39babe
32 schema:url http://link.springer.com/10.1007/BF01213466
33 sgo:license sg:explorer/license/
34 sgo:sdDataset articles
35 rdf:type schema:ScholarlyArticle
36 N1a8eec0aa33341c2903ee691b85eb48f schema:name doi
37 schema:value 10.1007/bf01213466
38 rdf:type schema:PropertyValue
39 N26599123f22b4caa8ac9df4ae33efc68 rdf:first sg:person.010341750121.94
40 rdf:rest Nc8666d0eef184b8ca9dbce911aeb94a9
41 N2bba8835fff544cfa1b27a2b5d8943a7 schema:name dimensions_id
42 schema:value pub.1044313251
43 rdf:type schema:PropertyValue
44 N7d51bf23ec364cf7adeab0b95309e99b schema:name readcube_id
45 schema:value d31442f63cc99497c475ed9096b44aa281a6132e233b7cdee966f259dd9bf27b
46 rdf:type schema:PropertyValue
47 N8391d354602b425fa2b5b22ee404e201 schema:volumeNumber 6
48 rdf:type schema:PublicationVolume
49 N9a3d053f88014a5b810ca6fe4b39babe schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 Nc8666d0eef184b8ca9dbce911aeb94a9 rdf:first sg:person.013253342331.37
52 rdf:rest rdf:nil
53 Nf4c71aebd68040878a0bca68d5ab864d schema:issueNumber 1
54 rdf:type schema:PublicationIssue
55 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
56 schema:name Information and Computing Sciences
57 rdf:type schema:DefinedTerm
58 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
59 schema:name Computation Theory and Mathematics
60 rdf:type schema:DefinedTerm
61 sg:journal.1135855 schema:issn 0932-4194
62 1435-568X
63 schema:name Mathematics of Control, Signals, and Systems
64 rdf:type schema:Periodical
65 sg:person.010341750121.94 schema:affiliation https://www.grid.ac/institutes/grid.4491.8
66 schema:familyName Poljak
67 schema:givenName Svatopluk
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010341750121.94
69 rdf:type schema:Person
70 sg:person.013253342331.37 schema:affiliation https://www.grid.ac/institutes/grid.4491.8
71 schema:familyName Rohn
72 schema:givenName Jiří
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013253342331.37
74 rdf:type schema:Person
75 sg:pub.10.1007/978-3-642-82739-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035782209
76 https://doi.org/10.1007/978-3-642-82739-6
77 rdf:type schema:CreativeWork
78 https://doi.org/10.1016/0012-365x(86)90192-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052392540
79 rdf:type schema:CreativeWork
80 https://doi.org/10.1016/0024-3795(89)90004-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036753136
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1016/0166-218x(86)90065-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1007919180
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1049/ip-d.1982.0053 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056847779
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1109/cdc.1989.70071 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086182591
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1137/0401037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844526
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1145/322248.322260 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053243506
91 rdf:type schema:CreativeWork
92 https://doi.org/10.4064/cm-23-1-165-171 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091799178
93 rdf:type schema:CreativeWork
94 https://www.grid.ac/institutes/grid.4491.8 schema:alternateName Charles University
95 schema:name Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czechoslovakia
96 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...