I'm reading a paper by Parks and McClellan and have a question on Chebyshev set.

Consider a set of $n$ functions $\{f_1(x),f_2(x),\cdots,f_n(x)\}$ on [a,b]. They are called the Chebyshev set on $[a,b]$ when all the linear combinations $$\sum_{i=1}^n a_i f_i(x)$$ have at most $n-1$ distinct roots on $[a,b]$ for any $a_1,\cdots,a_n$.

Theorem: Assume that $\{f_1(x),f_2(x),\cdots,f_n(x)\}$ is a Chebyshev set on [a,b]. Pick $n$ distinct points $x_1,x_2,\cdots,x_n$ from $[a,b]$ to define an $n\times n$ matrix $T$: \begin{equation*} T = \begin{bmatrix} f_1(x_1) & f_2(x_1)& \cdots & f_n(x_1) \\ f_1(x_2) & f_2(x_2)& \cdots & f_n(x_2) \\ \vdots & \vdots & \ddots & \vdots \\ f_1(x_n) & f_2(x_n)& \cdots & f_n(x_n) \\ \end{bmatrix} \end{equation*}

Then $T$ is invertible.

How can I prove it?


1 Answer 1


Let $a = (a_1,\dots,a_n)^T$, and note that $$ Ta = \pmatrix{ a_1f_1(x_1) + a_2f_2(x_1) + \cdots + a_n f_n(x_1)\\ a_1f_1(x_2) + a_2f_2(x_2) + \cdots + a_n f_n(x_2)\\ \vdots\\ a_1f_1(x_n) + a_2f_2(x_n) + \cdots + a_n f_n(x_n)} $$ If the $f_i$ form a Chebyshev set, then there is no non-zero choice of $a$ such that the above vector is zero. That is, $Ta = 0 \implies a = 0$. This means that $T$ is invertible, since it has a trivial kernel (nullspace).

  • $\begingroup$ Thank you for your quick answer. Can you please explain how the "at most $n−1$ distinct roots of the linear combination" kicks in the proof? $\endgroup$
    – user19906
    Commented Dec 18, 2015 at 13:40
  • $\begingroup$ Note that "$Ta = 0$" means exactly that "the function $\sum a_i f_i(x)$ has roots $\{x_1,\dots,x_n\}$", which of course means that this function has $n$ distinct roots. However, if the $a_i$ are not all equal to zero, this function can have at most $n-1$ distinct roots, which makes this outcome impossible. Thus, we can only have $Ta = 0$ if every $a_i$ is zero. Does that clear things up? $\endgroup$ Commented Dec 18, 2015 at 14:15
  • $\begingroup$ Now I read The Approximation of Functions: Linear theory by John R. Rice to find out that the other direction of the theorem is also true: A function set forms a Chebyshev set if and only if the matrix T is invertible. (p. 55 of Rice's book.) $\endgroup$
    – user19906
    Commented Dec 20, 2015 at 16:11
  • $\begingroup$ And yes. Your answer does help, Thanks. $\endgroup$
    – user19906
    Commented Dec 20, 2015 at 16:12
  • $\begingroup$ @user19906 note that the other condition requires that we consider every possible set of distinct $x_i$. $\endgroup$ Commented Dec 20, 2015 at 18:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .