0
$\begingroup$

How to construct a full-rank $n \times m$ matrix over $\mathbb{F}_2$ with $m > n$, minimizing width and row sparsity?

Goal:

Construct a matrix $X \in \mathbb{F}_2^{n \times m}$, with $m > n$, such that:

  • $X$ has full row rank: $\text{rank}(X) = n$ to ensure that the linear system $M\cdot S=V$, where $M \in \mathbb{F}_2^{n \times m}$,$S \in \mathbb{F}_2^{m \times 1}$,$V \in \mathbb{F}_2^{n \times 1}$ , has a unique solution.
  • Minimize the number of columns (m) so that the ratio $n/m$ remains close to 1. This ensures that the solution vector $S \in \mathbb{F}_2^m $ does not become unnecessarily large, thereby reducing storage and communication overhead.
  • Maximize the number of nonzero entries per row, as denser rows can sometimes reduce the computational complexity of solving for $S$.

It is inspired by designing a efficient algorithm from $M\cdot S=V$, where $M \in \mathbb{F}_2^{n \times m}$,$S \in \mathbb{F}_2^{m \times 1}$,$V \in \mathbb{F}_2^{n \times 1}$ to solve $S \in \mathbb{F}_2^m $, $m > n$ and ensured lower computation and the higher ratio $n/m$?

Improve this question
$\endgroup$
13
  • $\begingroup$ Any matrix where each row has a single zero and the zeroes are in different columns does the trick for every $m>n$. $\endgroup$ Commented Apr 18 at 1:19
  • $\begingroup$ I understand that, based on your approach, it is indeed possible to construct a linearly full-rank $n \times m $matrix$M$. However, when we are faced with solving the system $ M S = V $, where $ M \in \mathbb{F}^{n \times m} $, $S\in \mathbb{F}^{m \times 1} $ and $ V \in \mathbb{F}^{n \times 1} $, the complexity of solving for $ S $remains at $ O(n^2 m) $, which is approximately $ O(n^3) $ for dense matrices. In my case, I aim to reduce the complexity of solving for $S$ as much as possible. This is why I prefer matrix designs where the number of zeros is higher, leading to increased sparsity. $\endgroup$ Commented Apr 18 at 2:48
  • $\begingroup$ Actually, I am looking for an algorithm to solve the system $ M S = V $, where $M \in \mathbb{F}_2^{n \times m} $, $ S \in \mathbb{F}_2^{m \times 1} $, and$ V \in \mathbb{F}_2^{n \times 1} $, such that the computational complexity of solving for $ S $ is reduced to$ O(n) $. Of course, this depends heavily on the structure of $ M $. $\endgroup$ Commented Apr 18 at 2:54
  • $\begingroup$ So far, the most effective construction I have found is to use a Random Band Matrix , where each row contains a small, constant number of nonzero entries, and the nonzero positions are randomly selected within a local band. This structure ensures that $ M $ is full-rank with high probability while remaining sparse, which enables linear-time solvers. $\endgroup$ Commented Apr 18 at 2:56
  • 1
    $\begingroup$ Do you want to maximize the number of nonzero matrices or minimize? $\endgroup$ Commented Apr 18 at 10:07

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.