Decomposition in product of sparse matrices

In the following \(k\in \mathbb{N}\) is a fixed positive integer.

A matrix \(M\in\mathcal{M}_{n\times n}\) is \(k\)-decomposable into a product of sparse matrices if their exists \(A_1,\ldots,A_{t}\in \mathcal{M}_{n\times n}\) such that:

• \(\sum_{i,j} |a_{i,j}|\leq kn\)
• \(M=A_1\cdots A_k\).

1. Can we find a (decidable) caracterisation of matrices which are \(k\)-decomposable?
2. What happen when choosing a semiring among: Boolean, Integers, Tropical?

Compiled the: dim. 07 janv. 2024 23:19:29 CET