Problem Clarifications
There's a few things worth mentioning about the problem you asked.
First of all, we need to make sure that the expression you are maximizing is well defined, so the denominator must be non-zero. Simply adding the constraint that $\sum_{j=1}^Mx_j \ge 1$ is enough.
Second, I'd rather not get into the problem of talking about whether an optimization problem is NP-hard, so I'm going to explicitly state a decision version of the problem and then the rest of this answer will talk about that.
For the decision problem, the following are the inputs (note: variables follow the naming scheme from the question except $G$ which I introduce here and stands for "goal"):
- Two positive integers $N$ and $M$
- A collection of values $R_{ij}\in\{0,1\}$ specified for every pair of $i$ and $j$ with $1 \le i \le N$ and $1 \le j \le M$
- A positive integer $T$
- A value $G$
And the output is yes if and only if there exists an assignment of values to the variables $x_j$ for $1 \le j \le M$ such that
- for all $1 \le j \le M$, $x_j \in \{0,1\}$ and
- $1 \le \sum_{j=1}^Mx_j \le T$ and
- $\prod_{i=1}^N\left(\frac{\left(\sum_{j=1}^Mx_jR_{ij}\right)^2}{\sum_{j=1}^Mx_j}\right) > G$
This problem is NP-hard
Reduction
We prove this by reduction from dominating set. The dominating set problem asks for a given graph and number $k$ whether some choice of $k$ vertices has the property that every vertex in the graph is either chosen or next to a chosen vertex.
Suppose we are given an instance of dominating set consisting of a graph $G = (V, E)$ and a number $k$.
For convenience, label the vertices of $G$ as $v_1, v_2, ..., v_{|V|}$.
Then we construct an instance of the problem in question as follows:
- $N = M = |V|$
- $R_{ij} = 1$ if and only if $(v_i, v_j) \in E$ or $i=j$
- $T = k$
- $G = 0$
Polynomial Time
Very little needs to be done in the reduction to construct the instance, so this reduction is clearly polynomial time.
Answer preserving
Every instance generated by this reduction has $G = 0$. Therefore the condition that $\prod_{i=1}^N\left(\frac{\left(\sum_{j=1}^Mx_jR_{ij}\right)^2}{\sum_{j=1}^Mx_j}\right) > G$ is equivalent to the condition that for every $i$ with $1 \le i \le N$, $\sum_{j=1}^Mx_jR_{ij} \ne 0$. That in turn is equivalent to the condition that for all $i =1, ..., N$, there exists some $j \in \{1, ..., M\}$ such that $x_j = R_{ij} = 1$.
In other words, once we work in the fact that $N = M = |V|$ and $T = k$, we see that the instance is a yes instance if and only if there exists an assignment of zeros and ones to the variables $x_j$ such that
- at least one and at most $k$ values of $j$ have $x_j = 1$ and
- for all $i =1, ..., |V|$, there exists some $j \in \{1, ..., |V|\}$ such that $x_j = R_{ij} = 1$
That in turn is equivalent to choosing between $1$ and $k$ indices (the ones for which $x_j = 1$) such that for all $i =1, ..., |V|$, some one of the chosen indices $j$ has $R_{ij} = 1$.
But $R_{ij} = 1$ if and only if $i = j$ or $(v_i, v_j) \in E$. Thus solving the instance is equivalent to choosing between $1$ and $k$ indices from $1$ to $|V|$ such that for every $i$, either $i$ is chosen or $v_i$ is adjacent in $G$ to some $v_j$ with j chosen.
Restating this one last time, the answer to the instance generated by the reduction is the same as the answer to the following question: is it possible to choose between $1$ and $k$ vertices in $G$ such that each vertex is either chosen or adjacent to a chosen vertex. This is the original dominating set instance.
We have shown that the reduction is answer preserving, so this concludes the proof that the decision problem in question is NP-hard.
