5

Let $f\in \mathbb{R}[x]$ be a polynomial of degree $d$. Let $x_1, \dots, x_n$ be real numbers, I want to show the matrix $A$ given by $A_{ij} = f(x_i + x_j)$ has rank $\le d+1$.

My attempt: I tried writing the polynomial as $f(t)=\sum_{k=0}^d c_k t^k$, then I can write $A = \sum_{k=0}^d c_k B^{(k)},$ where $B^{(k)}$ is a matrix with entries $B^{(k)}_{ij} = (x_i+x_j)^k$. But this does not seem to be helpful.

Thank you in advance.

RunningMeatball
  • 501
  • 1
    Do you know that a matrix has rank $\leq k$ if and only if all its $\left(k+1\right)\times\left(k+1\right)$-submatrices have determinant $0$ ? This reduces your problem to showing that $\det\left(f\left(y_i + z_j\right)\right){1\leq i\leq d+2,\ 1\leq j\leq d+2} = 0$ for any $y_1, y_2, \ldots, y{d+2}, z_1, z_2, \ldots, z_{d+2}$. This is, in turn, well-known (e.g., Exercise 6.17 (c) in arXiv:2008.09862v2). – darij grinberg Sep 05 '21 at 02:25

1 Answers1

0

For convenience, I index matrices starting from 0 and consider the question with $x_0, \dots, x_{n-1}$ instead.

Define matrices $B\in\mathbb{R}^{n\times (d+1)}, C\in\mathbb{R}^{(d+1)\times (d+1)}, D\in\mathbb{R}^{(d+1)\times n}$ by \begin{align*} B_{il}&= x_i^l\\ C_{lm}&= 1\{m\le d-l\}\ c_{m+l} \binom{m+l}{l} \\ D_{mj}&= x_j^m \end{align*} Then \begin{align*} (BCD)_{ij} &= \sum_{l,m=0}^d B_{il}C_{lm}D_{mj} \\ &= \sum_{l=0}^d \sum_{m=0}^{d-l}c_{m+l}\binom{m+l}{l} x_i^l x_j^m \\ &= \sum_{l=0}^d \sum_{k=l}^{d}c_{k}\binom{k}{l} x_i^l x_j^{k-l} \\ &= \sum_{k=0}^d \sum_{l=0}^{k}c_{k}\binom{k}{l} x_i^l x_j^{k-l} \\ &= \sum_{k=0}^d c_{k}(x_i+x_j)^k \\ &= f(x_i+x_j) = A_{ij}, \end{align*} so $A=BCD$. Now since $C$ is a $(d+1)$ by $(d+1)$ matrix, the range of $A$ is at most $(d+1)$-dimensional.

This answer is motivated by the reference given in the comments.

RunningMeatball
  • 501