Complexity of a linear algebra problem Let matrix $M \in \{0,1\}^{r \times s}$ ($s&gt;r$), let function $f:\Bbb Z^{} \rightarrow \pm1$ and let $\alpha \in \Bbb Z \cap (0,s)$ be given. 

Is it NP-complete to decide if $\exists u \in \{0,1\}^{1 \times r}$ with $v=uM$: $|f(v)| = {\sum_{i=1}^{s}f(v_{i})^{}} \geq \alpha$?
Yes, it is NP-complete, by reduction from 3SAT.  In particular, we will go through an intermediate problem, which I will define as follows:

Definition.  The 1-to-3 of $k$ problem is as follows: given $n$ sets $S_1,\dots,S_n$, decide whether there exists $y_1,\dots,y_m \in \{0,1\}$ such that $1 \le \sum_{j\in S_i} y_j \le 3$ holds for all $i$.

Theorem 1. The 1-to-3 of $k$ problem is at least as hard as 3SAT.

Proof: Suppose we have a formula $\varphi$ with $n$ clauses over $m$ variables, $x_1,\dots,x_m$.  Introduce $m'=2m$ variables, $y_1,\dots,y_m$.  The intent is that these will correspond to the $2m$ literals $x_1,\dots,x_m,\neg x_1,\dots,\neg x_m$ (e.g., $y_i=1$ if and only if $x_i=\text{True}$; $y_{m+i}=1$ if and only if $x_i=\text{False}$); we will introduce a few sets to enforce this intent.  There are $n'=n+m+\lceil m/3\rceil$ sets, as follows:


First, there are $n$ sets, one for each clause of $\varphi$.  If $\varphi$ has the clause $(y_a\lor y_b\lor y_c)$ (where $y_a,y_b,y_c$ are three literals), then we'll add a set $S=\{a,b,c\}$ to enforce that at least one of $y_a,y_b,y_c$ must be true.
The next $m$ sets enforce that $x_i \lor \neg x_i$ is true for all $i$.  In particular, for each $i$, we add a set to enforce that at least one of $x_i, \neg x_i$ must be true, e.g., the set $S=\{i,i+m\}$ (if $y_i$ corresponds to $x_i$ and $y_{i+m}$ corresponds to $\neg x_i$).
Finally, the last $\lceil m/3 \rceil$ sets enforce that $x_i$ and $\neg x_i$ are not allowed to both be true.  We'll do this by enforcing that one, two, or three of $x_1,\neg x_1,x_2,\neg x_2,x_3,\neg x_3$ are true (e.g., the set $S=\{1,2,3,m+1,m+2,m+3\}$), and that at least one, two, or three of $x_4,\neg x_4,x_5,\neg x_5,x_6,\neg x_6$ are true (e.g., the set $S=\{4,5,6,m+4,m+5,m+6\})$, and so on.   Notice that, thanks to the previous category of sets, surely at least three of these 6 literals will be true, so asking that "one, two, or three should be true" amounts to asking that exactly three of them must be true -- which has the desired effect.


Finally, it is easy to see that this 1-to-3 of $k$ problem has a solution if and only if $\varphi$ has a satisfying assignment.  That completes the proof.

Theorem 2. Your problem is at least as hard as the 1-to-3 of $k$ problem.

Proof. Suppose we have a 1-to-3 of $k$ problem with $s$ sets over variables $y_1,\dots,y_r$.    Define $f(0)=0$, $f(1)=1$, $f(2)=1$, $f(3)=1$, and $f(k)=0$ for all $k&gt;3$.  Define the matrix $M$ based upon the sets $S_1,\dots,S_s$.  In particular, if $S_i=\{a,b,c,\dots\}$, the $i$th column of $M$ has a 1 in the $a$th, $b$th, $c$th, $\ldots$ rows and is zero elsewhere ($M_{j,i}=1$ if and only if $j \in S_i$).  Finally, set $\alpha=s$.

Now $|f(v)|\ge \alpha$ holds if and only if $f(v_1)=f(v_2)=\dots=f(v_s)=1$.  Thus, this choice of $f$ and setting of $\alpha$ ensures that the only way to satisfy the equation $|f(v)|\ge \alpha$ is if each $v_i$ is 1, 2, or 3.  If we focus on $v_i$, corresponding to the set $S_i=\{a,b,c,\dots\}$, then $f(v_i)=1$ if and only if $1 \le y_a+y_b+y_c+\dots \le 3$.  Therefore, this instance of your problem has a solution if and only if the original 1-to-3 of $k$ instance does.