Ivan Neretin la respuesta de puntos, todos los polinomios deben ser estrictamente lineal. Es decir, cada polinomio puede ser escrito matricially $p_j = {\bf}_j' {\bf x}$, donde ${\bf}_j$ y ${\bf x}$ son $k \1$ matrices (polinomio de coeficientes y variables respectivamente).
Entonces $$p_j^2 = ({\bf}_j' {\bf x})^2 = {\bf x}' A_j {\bf x}$$
donde $A_j = {\bf}_j{\bf}_j'$ es un $k\times k$ (rango uno, positiva definida) de la matriz.
A continuación, [ * ], debido a que $\sum_{i=1}^k x_i^2= {\bf x}' {\bf x}$ queremos
$$ \sum_{j=1}^n {\bf x}' A_j {\bf x}= {\bf x}' {\bf x} = {\bf x}' {\bf x} $$
donde $A = \sum_{j=1}^n A_j $ (simétrica, definida positiva). Esto implica $A=I_k$.
Pero tenemos que suma al menos $k$ matrices de rango uno, para obtener un rango de $k$ matriz. Por lo tanto $n\ge k$
[*] Como se ha dicho en los comentarios, una alternativa equivalente camino aquí es:
Debemos tener ${\bf x}' {\bf x}=\sum_{i=1}^k x_i^2>0$ para ${\bf x}\ne {\bf 0}$. Esto implica ${\bf x} \ne {\bf 0}$ (${\bf x}\ne {\bf 0}$), por lo tanto $$ debe tener rango completo ($k$). Luego, al final del párrafo anterior se aplica.