<p>This problem is NP-hard in general.</p>

<p>This is equivalent to finding the sparsest vector $y\in \mathbb F^n$ such that 
$$Ay = -Ax$$</p>

<p><a href="http://statweb.stanford.edu/~donoho/Reports/2005/NonNegative-R5.pdf">As finding a sparsest solution vector</a> for an underdetermined system of linear equations is NP-hard, so is your problem.</p>

CC BY-SA 3.0
2014-11-24T17:13:28.903Z
2014-11-24T17:13:28.903Z
R B
<p>Let $\mathbb F$ be a field (ex. a finite field, or the reals), $A$ a $m\times n$ matrix over $\mathbb F$, and $x\in \mathbb F^n$ a vector. I'm interested in finding the smallest number of coordinates I need to change in $x$ to order to have $Ax=\mathbb 0$. </p>

<p>What would be an algorithm to find this, or alternatively, an intractability result (ex. NP-completeness)?</p>

<p>Note: I am thinking of this in the context of matrix rigidity.</p>

<linear-algebra>
Finding the minimum number of coordinates to change to get a vector inside a subspace
Holden Lee
# Finding the minimum number of coordinates to change to get a vector inside a subspace

(Asked by: username_0 on 2014-11-24)

Let $\mathbb F$ be a field (ex. a finite field, or the reals), $A$ a $m\times n$ matrix over $\mathbb F$, and $x\in \mathbb F^n$ a vector. I'm interested in finding the smallest number of coordinates I need to change in $x$ to order to have $Ax=\mathbb 0$.

What would be an algorithm to find this, or alternatively, an intractability result (ex. NP-completeness)?

Note: I am thinking of this in the context of matrix rigidity.

**Tags:** linear-algebra

---

## 1 answers

### Answer by username_1 on 2014-11-24. Score: 6 | Accepted answer

This problem is NP-hard in general.

This is equivalent to finding the sparsest vector $y\in \mathbb F^n$ such that
$$Ay = -Ax$$

[As finding a sparsest solution vector](http://statweb.stanford.edu/~donoho/Reports/2005/NonNegative-R5.pdf) for an underdetermined system of linear equations is NP-hard, so is your problem.


---

