Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2308.12399 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910696102428672 |
|---|---|
| author | Bukovšek, Damjana Kokol Šmigoc, Helena |
| author_facet | Bukovšek, Damjana Kokol Šmigoc, Helena |
| contents | A factorization of an $n \times n$ nonnegative symmetric matrix $A$ of the form $BCB^T$, where $C$ is a $k \times k$ symmetric matrix, and both $B$ and $C$ are required to be nonnegative, is called the Symmetric Nonnegative Matrix Trifactorization (SN-Trifactorization). The SNT-rank of $A$ is the minimal $k$ for which such factorization exists. The SNT-rank of a simple graph $G$ that allows loops is defined to be the minimal possible SNT-rank of all symmetric nonnegative matrices whose zero-nonzero pattern is prescribed by a given graph.
We define set-join covers of graphs, and show that finding the SNT-rank of $G$ is equivalent to finding the minimal order of a set-join cover of $G$. Using this insight we develop basic properties of the SNT-rank for graphs and compute it for trees and cycles without loops. We show the equivalence between the SNT-rank for complete graphs and the Katona problem, and discuss uniqueness of patterns of matrices in the factorization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_12399 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Symmetric Nonnegative Trifactorization of Pattern Matrices Bukovšek, Damjana Kokol Šmigoc, Helena Combinatorics A factorization of an $n \times n$ nonnegative symmetric matrix $A$ of the form $BCB^T$, where $C$ is a $k \times k$ symmetric matrix, and both $B$ and $C$ are required to be nonnegative, is called the Symmetric Nonnegative Matrix Trifactorization (SN-Trifactorization). The SNT-rank of $A$ is the minimal $k$ for which such factorization exists. The SNT-rank of a simple graph $G$ that allows loops is defined to be the minimal possible SNT-rank of all symmetric nonnegative matrices whose zero-nonzero pattern is prescribed by a given graph. We define set-join covers of graphs, and show that finding the SNT-rank of $G$ is equivalent to finding the minimal order of a set-join cover of $G$. Using this insight we develop basic properties of the SNT-rank for graphs and compute it for trees and cycles without loops. We show the equivalence between the SNT-rank for complete graphs and the Katona problem, and discuss uniqueness of patterns of matrices in the factorization. |
| title | Symmetric Nonnegative Trifactorization of Pattern Matrices |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2308.12399 |