Let $p_1, p_2,...,p_n$ be real polynomials of $k$ variables $x_1,...,x_k$ and assume that $$p_1^2 + \dots +p_n^2=x_1^2 + \dots + x_k^2$$

Prove that $n \geq k$.

Out of so many questions that I have attempted, this is the first question that I have absolutely no idea how to start (I am ashamed of myself). Can anyone give some hint?

  • 1
    $\begingroup$ Just a note - for the equality case, the polynomials don't have to be $p_i=x_i$. They can for example be made up of pairs like $\frac{1}{4}(x_1+x_2)$, and $\frac{1}{4}(x_1-x_2)$ (at least for $k$ even). $\endgroup$ – Peter Woolfitt Dec 15 '15 at 7:12
  • 1
    $\begingroup$ From which contest is this from ? $\endgroup$ – Ewan Delanoy Dec 15 '15 at 8:11
  • 3
    $\begingroup$ Don't be ashamed of yourself! Every single person encounters problems they don't know how to start on. We just keep learning: last year's impossible problems are this year's warm-ups. $\endgroup$ – Greg Martin Dec 18 '15 at 0:34

Let's see. To begin with, all polynomials must be linear (otherwise the square of the highest-degree term of the highest-degree polynomial has degree more than 2 and no chances to cancel out with anything).

The rest is simple: for a linear polynomial, $p(\vec x)=0$ is a hyperplane which has a normal vector. With $n<k$, $n$ vectors do not form a complete basis in a $k$-dimensional space, so there is a non-zero vector perpendicular to all of them (that is, belonging to all hyperplanes where $p_i(\vec x)=0$). So for this vector $p_1(\vec x)=\dots=p_n(\vec x)=0$, hence $p_1^2 + \dots +p_n^2=0$, but $x_1^2 + \dots + x_k^2>0$.

With $n=k$ the solutions (besides the obvious $p_i=x_i$) are plenty; just take any orthonormal basis. For example, $({2\over3}x-{1\over3}y+{2\over3}z,\; {2\over3}x+{2\over3}y-{1\over3}z,\; -{1\over3}x+{2\over3}y+{2\over3}z)$ would do in 3D.

  • $\begingroup$ How do you prove the first assertion that a linear polynomial is a hyperplane with a normal vector? $\endgroup$ – Sandeep Silwal Dec 17 '15 at 21:58
  • $\begingroup$ Why, that's pretty well known: Wiki. $\endgroup$ – Ivan Neretin Dec 17 '15 at 22:34

As Ivan Neretin's answer points out, all polynomials must be strictly linear. That is, each polynomial could be written matricially as $p_j = {\bf a}_j' {\bf x}$, where ${\bf a}_j$ and ${\bf x}$ are $k \times 1$ matrices (polynomial coefficients and variables respectively).

Then $$p_j^2 = ({\bf a}_j' {\bf x})^2 = {\bf x}' A_j {\bf x}$$ where $A_j = {\bf a}_j{\bf a}_j'$ is a $k\times k$ (rank-one, positive definite) matrix.

Then [*], because $\sum_{i=1}^k x_i^2= {\bf x}' {\bf x}$ we want

$$ \sum_{j=1}^n {\bf x}' A_j {\bf x}= {\bf x}' A {\bf x} = {\bf x}' {\bf x} $$ where $A = \sum_{j=1}^n A_j $ (symmetric, positive definite). This implies $A=I_k$.

But we need to sum at least $k$ matrices of rank one to obtain a rank $k$ matrix. Hence $n\ge k$

[*] As said in the comments, an equivalent alternative way here is:

We must have ${\bf x}' A {\bf x}=\sum_{i=1}^k x_i^2>0$ for any ${\bf x}\ne {\bf 0}$. This implies $A {\bf x} \ne {\bf 0}$ (for ${\bf x}\ne {\bf 0}$), hence $A$ must have full rank ($k$). Then, the final paragraph above applies.

  • $\begingroup$ The fact that ${\bf x}' A {\bf x} = {\bf x}'{\bf x}$ for all $\bf x$ does not necessarily imply that $A=I_k$. But it does imply that $A$ must have full rank, which is what you need. $\endgroup$ – Joey Zou Dec 18 '15 at 1:01
  • $\begingroup$ @JoeyZou: Why does it imply that $A$ has full rank? We choosing $e_k$ for $x$, we can get that the diagonal entries of $A$ must all be $1's$. Does it follow from this? $\endgroup$ – Sandeep Silwal Dec 18 '15 at 1:47
  • 1
    $\begingroup$ @SandeepSilwal if $A$ did not have full rank, then there exists ${\bf x}\ne 0$ such that $A{\bf x} = 0$, so ${\bf x}' A {\bf x} = 0$. But ${\bf x}'{\bf x}\ne 0$ if ${\bf x}\ne 0$. $\endgroup$ – Joey Zou Dec 18 '15 at 1:56
  • $\begingroup$ @JoeyZou : $A$ is symmetric. And ${\bf x}' A {\bf x} = {\bf x}'{\bf x} \implies {\bf x}' B {\bf x} = 0$ with $B=A-I$ symmetric. This implies $B$ is zero. $\endgroup$ – leonbloy Dec 18 '15 at 2:07
  • $\begingroup$ Ah right, $A$ is symmetric because the $A_j$'s are symmetric by construction. $\endgroup$ – Joey Zou Dec 18 '15 at 2:12

Having written everything out, I now realize that this merely a paraphrasing of leonbloy's answer, using explicit indexed sums and filling out the details, but figure I might as well post it at this point.

As has already been pointed out, each polynomial must be strictly linear. That is, for each $q$, we may write $$p_q(\mathbf{x})=\sum_{i=1}^k \alpha_q^ix_i,$$ so that $\alpha_q^i$ is the scalar of $x_i$ in the $q^{\text{th}}$ polynomial. But then $$\sum_{q=1}^n(p_q(\textbf{x}))^2=\left(\sum_{i=1}^k \left[\sum_{q=1}^n (\alpha_q^i)^2\right](x_i)^2\right)+\left(\sum_{i=1}^k \sum_{j=1}^k \left[\sum_{q=1}^n 2\alpha_q^i\alpha_q^j\right]x_ix_j\right).$$

Thus, if these polynomials $p_1,p_2,\ldots,p_n$ satisfy the property that $\sum_{q=1}^n(p_q(\textbf{x}))^2=\sum_{i=1}^k (x_i)^2$, then necessarily $$\sum_{q=1}^n (\alpha_q^i)^2=1$$ for all $i$, while $$\sum_{q=1}^n 2\alpha_q^i\alpha_q^j=0$$ for all $i\neq j$. Thinking of these $\alpha_i^q$ as indexed vectors in $n-$dimensional euclidean space, we see that this boils down to the statement: "you can't have $q$ orthogonal unit vectors in $\mathbb{R}^n$ unless $n\geq q$", which follows from the basis theorem of linear algebra. I hope that this makes sense. Please let me know if anything here is unclear at all. Great question!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.