Using Elimination Theory to Construct Rigid Matrices
Original manuscript September 23, 2012
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2013
|
| Online Access: | http://hdl.handle.net/1721.1/80833 |
| _version_ | 1826190026075013120 |
|---|---|
| author | Kumar, Abhinav Lokam, Satyanarayana V. Patankar, Vijay M. Sarma, M. N. Jayalal |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Kumar, Abhinav Lokam, Satyanarayana V. Patankar, Vijay M. Sarma, M. N. Jayalal |
| author_sort | Kumar, Abhinav |
| collection | MIT |
| description | Original manuscript September 23, 2012 |
| first_indexed | 2024-09-23T08:33:53Z |
| format | Article |
| id | mit-1721.1/80833 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:33:53Z |
| publishDate | 2013 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/808332022-09-23T12:56:04Z Using Elimination Theory to Construct Rigid Matrices Kumar, Abhinav Lokam, Satyanarayana V. Patankar, Vijay M. Sarma, M. N. Jayalal Massachusetts Institute of Technology. Department of Mathematics Kumar, Abhinav Original manuscript September 23, 2012 The rigidity of a matrix A for target rank r is the minimum number of entries of A that must be changed to ensure that the rank of the altered matrix is at most r. Since its introduction by Valiant (1977), rigidity and similar rank-robustness functions of matrices have found numerous applications in circuit complexity, communication complexity, and learning complexity. Almost all n × n matrices over an infinite field have a rigidity of (n − r)[superscript 2]. It is a long-standing open question to construct infinite families of explicit matrices even with superlinear rigidity when r = Ω(n). In this paper, we construct an infinite family of complex matrices with the largest possible, i.e., (n − r)[superscript 2], rigidity. The entries of an n × n matrix in this family are distinct primitive roots of unity of orders roughly exp(n[superscript 2] log n). To the best of our knowledge, this is the first family of concrete (but not entirely explicit) matrices having maximal rigidity and a succinct algebraic description. Our construction is based on elimination theory of polynomial ideals. In particular, we use results on the existence of polynomials in elimination ideals with effective degree upper bounds (effective Nullstellensatz). Using elementary algebraic geometry, we prove that the dimension of the affine variety of matrices of rigidity at most k is exactly n[superscript 2] – (n – r)[superscript 2] + k. Finally, we use elimination theory to examine whether the rigidity function is semicontinuous. National Science Foundation (U.S.) (CAREER Grant DMS-0952486) 2013-09-20T15:47:35Z 2013-09-20T15:47:35Z 2013-04 Article http://purl.org/eprint/type/JournalArticle 1016-3328 1420-8954 http://hdl.handle.net/1721.1/80833 Kumar, Abhinav, Satyanarayana V. Lokam, Vijay M. Patankar, and M. N. Jayalal Sarma. “Using Elimination Theory to Construct Rigid Matrices.” computational complexity (April 9, 2013). en_US http://dx.doi.org/10.1007/s00037-013-0061-0 computational complexity Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag arXiv |
| spellingShingle | Kumar, Abhinav Lokam, Satyanarayana V. Patankar, Vijay M. Sarma, M. N. Jayalal Using Elimination Theory to Construct Rigid Matrices |
| title | Using Elimination Theory to Construct Rigid Matrices |
| title_full | Using Elimination Theory to Construct Rigid Matrices |
| title_fullStr | Using Elimination Theory to Construct Rigid Matrices |
| title_full_unstemmed | Using Elimination Theory to Construct Rigid Matrices |
| title_short | Using Elimination Theory to Construct Rigid Matrices |
| title_sort | using elimination theory to construct rigid matrices |
| url | http://hdl.handle.net/1721.1/80833 |
| work_keys_str_mv | AT kumarabhinav usingeliminationtheorytoconstructrigidmatrices AT lokamsatyanarayanav usingeliminationtheorytoconstructrigidmatrices AT patankarvijaym usingeliminationtheorytoconstructrigidmatrices AT sarmamnjayalal usingeliminationtheorytoconstructrigidmatrices |