# Decomposition of a Matrix by Sparse Matrices

Let $\mathbb{F}$ is a field. Consider an $n \times n$ matrix $\bf A$ over $\mathbb{F}$.

$\bf A$ is called sparse matrix over $\mathbb{F}$ iff the number of non-zero entities of $\bf A$ be at most $2n$.

My question:

Consider a non-zero $n \times n$ matrix $\bf M$ over $\mathbb{F}$. Is there a method or an algorithm such that $\bf M$ can be decomposed as follows: $${\bf M}=\prod_{i=1}^n\, {\bf A}_i=A_1\,A_2\, \cdots \,A_n\, .$$ where ${\bf A}_i$'s are sparse $n \times n$ matrices over $\mathbb{F}$. (I need binary finite field or $\mathbb{F}_{2^q}$)

For simplicity, we can assume that ${\bf A}_i$'s have the same sparsity pattern.

• @RodrigodeAzevedo The restriction $n$ sparse matrix is important for me. In your answer there is no guarantee for parameter $n$ but your answer is interesting. – user0410 Jul 13 '18 at 9:59
• @RodrigodeAzevedo Is it possible to ask you to make an example for an $4 \times 4$ matrix over a finite field such as $GF(2^4)$ as an answer in this post similar to example that you made in this post. I appreciate and thank you for your support – user0410 Jul 15 '18 at 20:55