Let $\mathcal{A}$ be the unital *-algebra generated by $N^2$ projections $u_{i,j}=u_{i,j}^2=u_{i,j}^*$, such that the rows/columns are partitions of unity $\sum_k u_{ik}=1_\mathcal{A}=\sum_k u_{kj}$, and $u_{ik}u_{i\ell}=u_{kj}u_{\ell j}=\delta_{k,\ell}$. That is $\mathcal{A}$ is the algebra of regular functions on the quantum permutation group $S_N^+$. It has, for $N>4$, various completions to a $\mathrm{C}^*$-algebra.
If you want, please just assume that $\mathcal{A}$ is generated by $N^2$ projections. I suspect that the relations beyond that don't make things harder or easier.
We will use the notation $|x|^2=x^*x$. Suppose that there exists a state $\phi:\mathcal{A}\rightarrow \mathbb{C}$, a positive functional such that $\phi(1_{\mathcal{A}})=1$, such that for all monomials $f\in\mathcal{A}$, that $\phi(|f|^2)>0$.
- If $g\in\mathcal{A}$ is another monomial, can we say anything useful about:
$$\phi(|f+g|^2)?$$
- Can we say that $\phi(|f+g|^2)\geq 0$ with equality only when $f=-g$?
- Is $f=-g$ possible for monomial $f,\,g\in\mathcal{A}$?
- Can we conclude that $\phi$ is faithful, that for all $a\in\mathcal{A}$, $\phi(|a|^2)=0\Rightarrow a=0$
@JP, you are going to laugh at this, but the counter examples are always the same!
As you mentioned that the relations are not so important, I will ignore them. In this case I presume that the number $N^2$ is not so crucial either, so I will look instead at just two projections.
In the algebra $C([0,1],M_2)$, consider the two projections $P$ and $Q$, defined by $$ P(t)= \pmatrix{1 & 0 \cr 0 & 0}, \quad \text{and} \quad Q(t):= \pmatrix{t & \sqrt{t-t^2}\cr \sqrt{t-t^2} & 1-t}, $$ for all $t\in [0,1]$.
By the universal property of $\mathcal A$, there is a *-homomorphism $$ \pi : \mathcal A \to C([0,1],M_2), $$ sending the two projections $p$ and $q$ generating $\mathcal A$, respectively to $P$ and $Q$.
Fixing any $t_0$ in $(0, 1)$, consider the state $\phi$ on $\mathcal A$ defined by $$ \phi(a) = \langle \pi (a)|_{t_0}e_1, e_1\rangle . $$ In other words, $\phi(a)$ is the top-left entry of the matrix $\pi (a)|_{t_0}$.
We claim that $\phi$ is strictly positive on any monomial, that is, on any product whose terms lie in the set $\{p, q\}$. The reason is that the matrices $$ \pmatrix{1 & 0 \cr 0 & 0}, \quad \text{and} \quad \pmatrix{{t_0} & \sqrt{{t_0}-{t_0}^2}\cr \sqrt{{t_0}-{t_0}^2} & 1-{t_0}}, $$ have the following two properties
all entries are nonnegative,
the top-left entry is strictly positive,
and it is easy to see that the set of matrices satisfying these properties is closed under multiplication.
Thus, if $f$ is a monomial, then $|f|^2$ is also a monomial, whence $\phi( |f|^2)>0$.
However, $\phi$ is not faithful. To see this, consider the element $$ a = pqp-t_0p. $$ We then have that $\pi (a)|_{t_0}=0$, so also $\phi(a^*a) = 0$.
On the other hand, one may verify by direct computation that $$ \pi (a)|_{t}\neq 0,\quad\forall t\in (0, 1)\setminus \{t_0\}, $$ so $a\neq 0$.