Boolean Rank via Monomial Ideals
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_ | 1866912583423885312 |
|---|---|
| author | Geraci, Juliann Kunin, Alexander B. Seceleanu, Alexandra |
| author_facet | Geraci, Juliann Kunin, Alexander B. Seceleanu, Alexandra |
| contents | Boolean matrix factorization (BMF) has many applications in data mining, bioinformatics, and network analysis. The goal of BMF is to decompose a given binary matrix as the Boolean product of two smaller binary matrices, revealing underlying structure in the data. When interpreting a binary matrix as the adjacency matrix of a bipartite graph, BMF is equivalent to the NP-hard biclique cover problem.
By approaching this problem through the lens of commutative algebra, we utilize algebraic structures and techniques--particularly the Castelnuovo-Mumford regularity of combinatorially defined ideals--to establish new lower bounds for Boolean matrix rank. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_09570 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Boolean Rank via Monomial Ideals Geraci, Juliann Kunin, Alexander B. Seceleanu, Alexandra Commutative Algebra Combinatorics 13P25 Boolean matrix factorization (BMF) has many applications in data mining, bioinformatics, and network analysis. The goal of BMF is to decompose a given binary matrix as the Boolean product of two smaller binary matrices, revealing underlying structure in the data. When interpreting a binary matrix as the adjacency matrix of a bipartite graph, BMF is equivalent to the NP-hard biclique cover problem. By approaching this problem through the lens of commutative algebra, we utilize algebraic structures and techniques--particularly the Castelnuovo-Mumford regularity of combinatorially defined ideals--to establish new lower bounds for Boolean matrix rank. |
| title | Boolean Rank via Monomial Ideals |
| topic | Commutative Algebra Combinatorics 13P25 |
| url | https://arxiv.org/abs/2509.09570 |