# Decomposition of a matrix by sparse matrices

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

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 = {\bf A}_1 \, {\bf A}_2 \, \cdots \, {\bf A}_n$$

where $${\bf A}_i$$'s are sparse $$n \times n$$ matrices over $$\mathbb{F}$$? I need binary finite field $$\mathbb{F}_{2^q}$$. For simplicity, we can assume that the matrices $${\bf A}_i$$ have the same sparsity pattern.

Over any field, you can do the job with $2n-2$ "sparse" (according to your definition) matrices. Behind lies the decomposition LU.
Take $A_1,\cdots A_{n-1}$ lower triangular with $2$ bands and diagonal vector $[1,\cdots,1]$. Take $A_n,\cdots A_{2n-2}$ upper triangular with $2$ bands.
• I know what you mean, but the restriction $n$ sparse matrix is important for me. The complete answer with this approach is given in answer of this post. Thnaks Commented Jul 12, 2018 at 20:36