This is a version of 
[this question of Klim Efremenko.](https://mathoverflow.net/questions/59807)


Let $r>2$ be a natural number, say $r=3$ or $r=10$. Let $G$ be a finite group and $\rho$
be an irreducible complex representation of $G$. We consider the following minimum $m=m(r,G,\rho)$:
$$
m(r,G,\rho)= {\rm min\ rank} \sum\_{i=1}^r c\_i \rho(g\_i),
$$
where the $r$ elements $g\_1, ... , g\_r$ are arbitrary $r$ elements of $G$, and $c\_1, ..., c\_r$ are arbitrary complex numbers, not all of which are 0.


We want $m(r,G,\rho)$ to be small compared to ${\rm dim}\,\rho$. What can be said
about $m(r,G,\rho)$ when the order $|G|$ tends to infinity? Say, for $r=10$, can one find $(G,\rho)$ such that
$$ \frac{{\rm dim}\,\rho}{ m(10,G,\rho)} > \log^{200} |G|\ ? $$


For example, for $G=S\_n$ and $G={\rm GL}(n,\mathbb{F}\_q)$, the irreducible representations are classified. What can be said on $m(r,G,\rho)$ in these cases?



A small rank linear combination of a small number of elements of a group
This answer shows that one cannot find $(G,\rho)$ as required if $G$ is supposed to be group of Lie type defined over a large field.


Let $G$ be a group of Lie type defined over a field with $q$ elements. Let $\rho$ be an irreducible representation of $G$ which is not $1$-dimensional. Gluck (D. Gluck. Sharper character value estimates for groups of Lie type, J. Algebra 174 (1995), 229-266.) proved that there exists a constant (independent of $G$ and $\rho$) so that


$$|{\rm tr}(\rho(g))| \leq C \cdot \dim(\rho) \cdot q^{-1/2},$$
whenever $g$ is non-trival.


Let's assume that $\rho$ is unitary and denote by $\|.\|$ the spectral norm.
Now, let $f \in {\mathbb C}[G]$, $f= \sum\_{i=1}^r c\_i g\_i$ with $g\_i \neq g\_j$ for $i \neq j$. We get


$${\rm tr}(\rho(f)^\*\rho(f)) \leq {\rm rank}(\rho(f)) \cdot \|\rho(f)\|^2,$$
and
\begin{eqnarray\*}
{\rm tr}(\rho(f)^\*\rho(f)) &=& \sum\_{i,j=1}^r c\_i \bar{c\_j} \cdot {\rm tr}(\rho(g\_ig\_j^{-1}))\\
&\geq & \dim(\rho) \cdot \sum\_{i=1}^r |c\_i|^2 - C \cdot \dim(\rho) \cdot q^{-1/2} \cdot \sum\_{i \neq j} |c\_i \bar{c\_j}| \\
&\geq & \dim(\rho) \cdot \left(1/r - C \cdot q^{-1/2} \right) \cdot \left(\sum\_{i=1}^r |c\_i| \right)^2 \\
&\geq & \dim(\rho) \cdot \left(1/r - C \cdot q^{-1/2} \right) \cdot \|\rho(f)\|^2,
\end{eqnarray\*}
where I used Gluck's result and the basic estimate $$\sum\_{i=1}^r |c\_i| \leq r^{1/2} \cdot \left(\sum\_{i=1}^r |c\_i|^2 \right)^{1/2}.$$


Combining the two bounds for ${\rm tr}(\rho(f)^\*\rho(f))$ we get
$$\dim(\rho) \cdot \left(1/r - C \cdot q^{-1/2} \right) \cdot \|\rho(f)\|^2 \leq {\rm rank}(\rho(f)) \cdot \|\rho(f)\|^2.$$
and hence
$$\frac{\dim(\rho)}{{\rm rank}(\rho(f))} \leq \frac1{1/r - C \cdot q^{-1/2}} \leq r + 2 C \cdot r^2 \cdot q^{-1/2},$$
for $q$ large. 


There are similar character estimates for the symmetric group, comparing an arbitrary character with the character that counts fixed points of the permutation. These estimates probably show that the symmetric groups cannot work either (at least not in a way that is essentially better than for the standard representation).


