Rigidity matroids and linear algebraic matroids with applications to matrix completion and tensor codes
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918366860541952 |
|---|---|
| author | Brakensiek, Joshua Dhar, Manik Gao, Jiyang Gopi, Sivakanth Larson, Matt |
| author_facet | Brakensiek, Joshua Dhar, Manik Gao, Jiyang Gopi, Sivakanth Larson, Matt |
| contents | We establish a connection between problems studied in rigidity theory and matroids arising from linear algebraic constructions like tensor products and symmetric products. A special case of this correspondence identifies the problem of giving a description of the correctable erasure patterns in a maximally recoverable tensor code with the problem of describing bipartite rigid graphs or low-rank completable matrix patterns. Additionally, we relate dependencies among symmetric products of generic vectors to graph rigidity and symmetric matrix completion. With an eye toward applications to computer science, we study the dependency of these matroids on the characteristic by giving new combinatorial descriptions in several cases, including the first description of the correctable patterns in an (m, n, a=2, b=2) maximally recoverable tensor code. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_00778 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Rigidity matroids and linear algebraic matroids with applications to matrix completion and tensor codes Brakensiek, Joshua Dhar, Manik Gao, Jiyang Gopi, Sivakanth Larson, Matt Combinatorics Discrete Mathematics Information Theory 94B05, 52C25, 05B35 We establish a connection between problems studied in rigidity theory and matroids arising from linear algebraic constructions like tensor products and symmetric products. A special case of this correspondence identifies the problem of giving a description of the correctable erasure patterns in a maximally recoverable tensor code with the problem of describing bipartite rigid graphs or low-rank completable matrix patterns. Additionally, we relate dependencies among symmetric products of generic vectors to graph rigidity and symmetric matrix completion. With an eye toward applications to computer science, we study the dependency of these matroids on the characteristic by giving new combinatorial descriptions in several cases, including the first description of the correctable patterns in an (m, n, a=2, b=2) maximally recoverable tensor code. |
| title | Rigidity matroids and linear algebraic matroids with applications to matrix completion and tensor codes |
| topic | Combinatorics Discrete Mathematics Information Theory 94B05, 52C25, 05B35 |
| url | https://arxiv.org/abs/2405.00778 |