# 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?

Mastodon