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.

I appreciate to address me paper or book about this subject.

Thanks for any suggestions.

  • $\begingroup$ Related: mathoverflow.net/q/258283/91764 $\endgroup$ – Rodrigo de Azevedo Jul 13 '18 at 8:04
  • $\begingroup$ @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. $\endgroup$ – user0410 Jul 13 '18 at 9:59
  • $\begingroup$ @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 $\endgroup$ – user0410 Jul 15 '18 at 20:55
  • $\begingroup$ Isn't it just Gaussian elimination over a finite field? Consult a table to find the multiplicative inverses. $\endgroup$ – Rodrigo de Azevedo Jul 15 '18 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.