On Prime Matrix Product Factorizations
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908741488607232 |
|---|---|
| author | Akbari, Saieed Elahimanes, Mohamad Parsa Miraftab, Bobby |
| author_facet | Akbari, Saieed Elahimanes, Mohamad Parsa Miraftab, Bobby |
| contents | A graph $G$ factors into graphs $H$ and $K$ via a matrix product if $A = BC$, where $A$, $B$, and $C$ are the adjacency matrices of $G$, $H$, and $K$, respectively. The graph $G$ is prime if, in every such factorization, one of the factors is a perfect matching that is, it corresponds to a permutation matrix. We characterize all prime graphs, then using this result we classify all factorable forests, answering a question of Akbari et al. [\emph{Linear Algebra and its Applications} (2025)]. We prove that every torus is factorable, and we characterize all possible factorizations of grids, addressing two questions posed by Maghsoudi et al. [\emph{Journal of Algebraic Combinatorics} (2025)]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_24864 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Prime Matrix Product Factorizations Akbari, Saieed Elahimanes, Mohamad Parsa Miraftab, Bobby Combinatorics Discrete Mathematics 05C15, 05C50 A graph $G$ factors into graphs $H$ and $K$ via a matrix product if $A = BC$, where $A$, $B$, and $C$ are the adjacency matrices of $G$, $H$, and $K$, respectively. The graph $G$ is prime if, in every such factorization, one of the factors is a perfect matching that is, it corresponds to a permutation matrix. We characterize all prime graphs, then using this result we classify all factorable forests, answering a question of Akbari et al. [\emph{Linear Algebra and its Applications} (2025)]. We prove that every torus is factorable, and we characterize all possible factorizations of grids, addressing two questions posed by Maghsoudi et al. [\emph{Journal of Algebraic Combinatorics} (2025)]. |
| title | On Prime Matrix Product Factorizations |
| topic | Combinatorics Discrete Mathematics 05C15, 05C50 |
| url | https://arxiv.org/abs/2512.24864 |