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 N34cb1b8998d4481ea8a4ab1ccd4334f3
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 Nc4327cdf2d1f4b3ba0773c54a59f4b6d
20 Ndf8d6649730549e2afa08492e3bc90e2
21 sg:journal.1135855
22 schema:name Checking robust nonsingularity is NP-hard
23 schema:pagination 1-9
24 schema:productId N6557de89ee394603b081210a1487ae9d
25 Nc9303bcf133d4668880ad4e75b7e3a1e
26 Nd4ba6b3f9d784f38bea36450c622160b
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 N36423cba5bce46cc91204734862e8edd
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 N120aef1f04d740d290d7d89baed24c2a rdf:first sg:person.013253342331.37
37 rdf:rest rdf:nil
38 N34cb1b8998d4481ea8a4ab1ccd4334f3 rdf:first sg:person.010341750121.94
39 rdf:rest N120aef1f04d740d290d7d89baed24c2a
40 N36423cba5bce46cc91204734862e8edd schema:name Springer Nature - SN SciGraph project
41 rdf:type schema:Organization
42 N6557de89ee394603b081210a1487ae9d schema:name readcube_id
43 schema:value d31442f63cc99497c475ed9096b44aa281a6132e233b7cdee966f259dd9bf27b
44 rdf:type schema:PropertyValue
45 Nc4327cdf2d1f4b3ba0773c54a59f4b6d schema:issueNumber 1
46 rdf:type schema:PublicationIssue
47 Nc9303bcf133d4668880ad4e75b7e3a1e schema:name dimensions_id
48 schema:value pub.1044313251
49 rdf:type schema:PropertyValue
50 Nd4ba6b3f9d784f38bea36450c622160b schema:name doi
51 schema:value 10.1007/bf01213466
52 rdf:type schema:PropertyValue
53 Ndf8d6649730549e2afa08492e3bc90e2 schema:volumeNumber 6
54 rdf:type schema:PublicationVolume
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)


...