[proofplan]
Write the desired approximant as a linear combination of the Chebyshev system and regard the equations as a square linear system in the $n+1$ unknowns consisting of the coefficients and the scalar error $E$. It suffices to prove that the associated homogeneous system has only the zero solution. If the homogeneous error parameter is zero, the Chebyshev property rules out a nonzero function with too many zeros; if it is nonzero, the alternating signs force one zero in each interval between consecutive exchange points, again contradicting the Chebyshev property. Nonsingularity of the linear system then gives existence and uniqueness.
[/proofplan]
[step:Convert the interpolation conditions into a square linear system]
For each coefficient vector $c=(c_1,\dots,c_n) \in \mathbb{R}^n$, define the function
\begin{align*}
p_c: [a,b] \to \mathbb{R}, \qquad p_c(t)=\sum_{j=1}^n c_j u_j(t).
\end{align*}
Then $p_c \in X$, and every element of $X$ is of this form because $X=\operatorname{span}\{u_1,\dots,u_n\}$.
The equations
\begin{align*}
f(x_i)-p_c(x_i)=\sigma(-1)^iE
\end{align*}
are equivalent to
\begin{align*}
\sum_{j=1}^n c_j u_j(x_i)+\sigma(-1)^iE=f(x_i)
\end{align*}
for every $i \in \{0,\dots,n\}$. This is a linear system with $n+1$ equations in the $n+1$ real unknowns $c_1,\dots,c_n,E$. Therefore it is enough to prove that the corresponding homogeneous system has only the zero solution.
[/step]
[step:Show that the homogeneous system has no nonzero solution]
Assume that $h \in X$ and $F \in \mathbb{R}$ solve the homogeneous system
\begin{align*}
h(x_i)+\sigma(-1)^iF=0
\end{align*}
for every $i \in \{0,\dots,n\}$. Equivalently,
\begin{align*}
h(x_i)=\sigma(-1)^{i+1}F
\end{align*}
for every $i \in \{0,\dots,n\}$.
If $F=0$, then $h(x_i)=0$ for all $i \in \{0,\dots,n\}$. Thus $h$ has at least $n+1$ distinct zeros. Since $u_1,\dots,u_n$ form a Chebyshev system, every nonzero element of $X$ has at most $n-1$ zeros on $[a,b]$. Hence $h=0$.
Now suppose $F \neq 0$. For each $i \in \{0,\dots,n-1\}$,
\begin{align*}
h(x_i)h(x_{i+1})=-F^2<0.
\end{align*}
Since $h \in X \subset C([a,b])$, the restriction of $h$ to $[x_i,x_{i+1}]$ is continuous. By the [Intermediate Value Theorem](/theorems/180) (citing a result not yet in the wiki: [Intermediate Value Theorem](/theorems/629)), there exists $z_i \in (x_i,x_{i+1})$ such that $h(z_i)=0$. The points $z_0,\dots,z_{n-1}$ are distinct because they lie in pairwise disjoint open intervals. Hence $h$ has at least $n$ distinct zeros. The Chebyshev property again forces $h=0$. Substituting $h=0$ into $h(x_0)=\sigma(-1)F$ gives $F=0$, contradicting $F \neq 0$. Therefore the case $F \neq 0$ cannot occur.
Thus the only solution of the homogeneous system is $(h,F)=(0,0)$.
[guided]
We prove nonsingularity by testing the homogeneous system. Let $h \in X$ and $F \in \mathbb{R}$ satisfy
\begin{align*}
h(x_i)+\sigma(-1)^iF=0
\end{align*}
for every $i \in \{0,\dots,n\}$. Solving this equation for the value of $h$ at the exchange points gives
\begin{align*}
h(x_i)=\sigma(-1)^{i+1}F.
\end{align*}
There are two cases. First suppose $F=0$. Then
\begin{align*}
h(x_i)=0
\end{align*}
for every $i \in \{0,\dots,n\}$. Since the exchange points are strictly ordered, these are $n+1$ distinct zeros. The defining property of a Chebyshev system of $n$ functions is that every nonzero function in $X$ has at most $n-1$ zeros on $[a,b]$. Therefore $h$ cannot be nonzero, so $h=0$.
Now suppose $F \neq 0$. The point of the alternating sign condition is that adjacent prescribed values of $h$ have opposite signs. Indeed, for every $i \in \{0,\dots,n-1\}$,
\begin{align*}
h(x_i)h(x_{i+1})=\sigma(-1)^{i+1}F \cdot \sigma(-1)^{i+2}F=-F^2<0.
\end{align*}
Thus $h(x_i)$ and $h(x_{i+1})$ are nonzero [real numbers](/page/Real%20Numbers) of opposite sign. Because $h \in X$ and $X \subset C([a,b])$, the function $h: [a,b]\to \mathbb{R}$ is continuous. Applying the Intermediate Value Theorem (citing a result not yet in the wiki: Intermediate Value Theorem) on the interval $[x_i,x_{i+1}]$, there exists a point $z_i \in (x_i,x_{i+1})$ such that
\begin{align*}
h(z_i)=0.
\end{align*}
This construction gives one zero in each open interval $(x_i,x_{i+1})$ for $i=0,\dots,n-1$. These intervals are pairwise disjoint, so the points $z_0,\dots,z_{n-1}$ are distinct. Hence $h$ has at least $n$ distinct zeros.
The Chebyshev property now rules out a nonzero $h \in X$, because a nonzero element of $X$ has at most $n-1$ zeros. Therefore $h=0$. Substituting this into the homogeneous equation at $x_0$ gives
\begin{align*}
0=h(x_0)=\sigma(-1)F.
\end{align*}
Since $\sigma \in \{-1,1\}$, this implies $F=0$, contradicting the assumption $F \neq 0$. Therefore the nonzero-error case cannot occur, and the homogeneous system has only the zero solution.
[/guided]
[/step]
[step:Conclude existence and uniqueness from nonsingularity]
The homogeneous system associated to the coefficient matrix has only the zero solution. Therefore the coefficient matrix is nonsingular as a [linear map](/page/Linear%20Map) $\mathbb{R}^{n+1}\to\mathbb{R}^{n+1}$. Hence, for the right-hand side vector
\begin{align*}
(f(x_0),\dots,f(x_n)) \in \mathbb{R}^{n+1},
\end{align*}
there is a unique solution $(c_1,\dots,c_n,E) \in \mathbb{R}^{n+1}$.
Define
\begin{align*}
p: [a,b]\to \mathbb{R}, \qquad p(t)=\sum_{j=1}^n c_j u_j(t).
\end{align*}
Then $p \in X$, and the solved linear system gives
\begin{align*}
f(x_i)-p(x_i)=\sigma(-1)^iE
\end{align*}
for every $i \in \{0,\dots,n\}$. The uniqueness of $(c_1,\dots,c_n,E)$ gives uniqueness of $(p,E)$, since the Chebyshev property in particular implies that $u_1,\dots,u_n$ are linearly independent. This proves the theorem.
[/step]
