# Evaluating a hopeless algorithm for recovering sparse solutions to $Ax=b$ over a finite field

Given a matrix $A \in F^{n \times m},$ $m>n,$ with rank $n$ and in row-reduced echelon form and a nonzero vector $b \in F^n$: (1) Perform elementary row operations to obtain $b_1 \not = 0$ and $b_k=0$ for all $k=2, \ldots, n.$ (2) Select $A'$ to be the matrix of columns with zero first-row entries from $A$, and select $b'$ to be a column of $A$ with nonzero first-row entry (making a row swap if needed). Remove the first rows of $A'$ and $b'.$ If one row remains, stop. Otherwise, set $A=A'$ and $b=b'$, perform row reduction and repeat (1). After the stop, substitute as few zero values in the remaining $x_k$ as possible in order to solve the previously deleted equation, and continue to solve previously deleted equations in this way until a solution is obtained.

I found this algorithm buried in my preliminary oral notes in hopes that it would provide all minimal-support solutions with at least some fewer steps than the exhaustive approach (that is, simply multiplying $A$ by vectors of increasing weight until $b$ is obtained). My thought may have been that there would be a certain class of matrices for which this algorithm was certain to be superior to the exhaustive approach, but I can't remember.

I am about to dispense of this algorithm for good, but it haunts me that I mentioned it during my preliminary oral and received no immediate negative feedback for it, either from my committee or from my major professor. Was letting this algorithm go uncriticized during my preliminary a collective error on mine and my committee's part, as I suspect, or have I simply been unable to reconnect with a valid line of thinking here?