# Algorithm for finding minimal-support solutions of underdetermined systems over finite fields

Given a finite field $F,$ a matrix $A \in F^{n,m}, \ m>n,$ and a vector $b \in F^n,$ describe the vector(s) $x \in F^m$ that solve $Ax=b$ and such that $\|x\|_0$ is minimal among all solutions. Here, $\|x\|_0$ is just the count of nonzero elements of $x.$

I am working on this problem as part of my dissertation, so I am not looking for a solution to this problem; any and all helpful suggestions will be cited in my paper.

Since I am primarily a teacher completing a graduate program under extreme time constraints (due to a long absence), this has been my first real foray into what it means to do research. I am a bit green with this!

My goal is to provide a non-"brute force" algorithm; that is, an algorithm that does more than simply collecting all answers to $Ax=b$ over the finite field $F$ and traversing the list for the answers for which $\|x\|_0$ is minimal.

Tao, Donoho and others have shown that the $\|x\|_1$ norm is effective as an approximation for the case over the real field, but since I am focused on finite fields, the use of such a norm to derive a similar asymptotically improved approximation algorithm is hopeless.

My dissertation committee is already aware that the problem is $NP-$hard (though, curiously, no actual proof of this result appeared in the literature until late 2014). My goal, then, is to either reduce the number of steps needed for some matrices with respect to "brute force" search of all solutions, or else to come up with a novel less-complex approximation method that recovers some minimal support solutions for finite fields.

In respect to the task set before me above, my working solution is to seek a process that manipulates the system to set apart solution sets according to the maximal number of zeros they can have as components. If successful, I would then traverse the set with the highest such maximal number and recover all minimal support solutions. The worst-case scenario is to receive a system $Ax=b$ whose solutions all have the same weight $\|x\|_0,$ which would of course mean that such an algorithm is no better than the "brute force method" of searching all solutions, but this would improve minimal-weight solution generation for some underdetermined systems over finite fields.

The attempt so far has been to try the following:

(1) Reduce the system $Ax=b$ over the finite field $F$ by finding the RREF, and check for inconsistency (no solution).

(2) Isolate the pivots in the RREF from step 1. Set these equal to the modified $b$ (called $v$) minus the space $A$ generated by the "free" variables: in other words, we now have the subproblem $P = v+A'x'.$

(3) Solve the modified subproblem $P=v+A'x'$ from Step 2 in some way.

I am stuck at step (3). My attempts to surpass this consist of further reducing the RREF in Step 1 by taking multiples of the first row to "zero out" the remaining rows of the last column, leaving the modified problem in (3) in the much more pleasant form $P=A'x'$ (with one row less than Step 2 would appear in general, of course). The result would be to represent some pivot variables in the RREF in terms of the free variables, and then simply substitute as many zeros as possible in the free (and pivot) variables and backsolve to check for consistency.

This was my initial proposal at my preliminary oral exam for my dissertation, and my committee seemed to believe at that time that this method would accomplish my goal.

I am struggling to untangle it four months later, and am beginning to wonder if I (and my committee) may have missed something here. With two months left to go before the Graduate College at my school imposes time limits on me, I am in a bit of a panic, but remain confident that some sort of fruitful analysis can come from this.

I appreciate any and all insights. Thank you!

• This seems a good question for this site, but please edit out the wall of text and leave only the first paragraph and your solution attempts. As you said, MO is not for psychological advice. :) In any case, it seems that you are struggling with the impostor syndrome; don't worry, it's natural and more or less everyone feels the same at some point in their life/career. – Federico Poloni Sep 24 '16 at 6:17
• Thanks for the suggestion - I have refocused the post more on the current status of my attempt to solve the problem. – Thomas Rasberry Sep 25 '16 at 0:06

## 1 Answer

If you let $b=0$ then the minimal $\| x \|_0$ satisfying the equation $Ax=0$ would be the minimum weight of the code $C$ over $F$ with length $m$ defined by the matrix $A$ as its parity check matrix. This is a hard problem, even with albebraically designed/structured matrices and in general NP-hard (I think).

Now, moving on to nonzero $b$ you are talking about the minimum weight of a coset (translate) of the same code, and its' weight distribution. This is an even harder problem. The $b\neq 0$ obtained via $Ar=b$ where $r$ is a received vector and $c$ is a transmitted codeword (thus satisfying $Ac=0$ is called the syndrome of the error pattern $e$ where $Ar=A(c+e)=Ac+Ae=Ae=b$) and is used for decoding by denoting the error to be the most likely vector (of minimum length) with that syndrome.

• I have explored the $Ax=0$ line in another question here when I was beginning my writing for my dissertation last year. It is $NP-$hard, and has been conjectured as such since the seventies, but it was curiously never proven in the literature until less than two years ago! I have attempted to reduce the $Ax=b$ problem to an $Ax=0$ problem by appending $-b$ as the last column to $A$ and modifying $x$ to have a $1$ as the bottom-row entry. This of course has the issue of leaving $x$ not entirely variate but it could still be helpful. – Thomas Rasberry Sep 25 '16 at 0:25