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:

  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