Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.11556 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908294711345152 |
|---|---|
| author | Johnston, Nathaniel Moein, Shirin Plosker, Sarah |
| author_facet | Johnston, Nathaniel Moein, Shirin Plosker, Sarah |
| contents | A matrix is said to have factor width at most $k$ if it can be written as a sum of positive semidefinite matrices that are non-zero only in a single $k \times k$ principal submatrix. We explore the ``factor-width-$k$ rank'' of a matrix, which is the minimum number of rank-$1$ matrices that can be used in such a factor-width-at-most-$k$ decomposition. We show that the factor width rank of a banded or arrowhead matrix equals its usual rank, but for other matrices they can differ. We also establish several bounds on the factor width rank of a matrix, including a tight connection between factor-width-$k$ rank and the $k$-clique covering number of a graph, and we discuss how the factor width and factor width rank change when taking Hadamard products and Hadamard powers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_11556 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Factor Width Rank of a Matrix Johnston, Nathaniel Moein, Shirin Plosker, Sarah Combinatorics 05C50, 15A18, 15B48 A matrix is said to have factor width at most $k$ if it can be written as a sum of positive semidefinite matrices that are non-zero only in a single $k \times k$ principal submatrix. We explore the ``factor-width-$k$ rank'' of a matrix, which is the minimum number of rank-$1$ matrices that can be used in such a factor-width-at-most-$k$ decomposition. We show that the factor width rank of a banded or arrowhead matrix equals its usual rank, but for other matrices they can differ. We also establish several bounds on the factor width rank of a matrix, including a tight connection between factor-width-$k$ rank and the $k$-clique covering number of a graph, and we discuss how the factor width and factor width rank change when taking Hadamard products and Hadamard powers. |
| title | The Factor Width Rank of a Matrix |
| topic | Combinatorics 05C50, 15A18, 15B48 |
| url | https://arxiv.org/abs/2405.11556 |