1
$\begingroup$

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.

I appreciate references to papers or books about this subject.

$\endgroup$
1
  • $\begingroup$ Do you agree with my edits? $\endgroup$ Commented Aug 5, 2023 at 6:33

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – user0410
    Commented Jul 12, 2018 at 20:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .