# Dimension of the subspace of splines on $[a,b]$

Consider a grid $\Delta : a := x_0<x_1<\ldots <x_n =: b$ on $[a,b]$. Denote the space of piecewise polynomials of at most degree $m$ on $[a,b]$ by $\mathcal P_\Delta^m = \mathcal P^m$. We know it is a vector subspace in the vector space of all bounded functions on $[a,b]$. Furthermore, it's also known that $\dim\mathcal P^m = n(m+1)$, since for each subinterval we construct a polynomial of at most degree $m$, therefore we need to select a total of at most $n(m+1)$ coefficients.

Impose restrictions on the mentioned space. Consider all $S:[a,b]\to\mathbb R$ with $$\forall j, 1\leq j\leq n\quad S\in \mathcal P^m[x_{j-1},x_j] \\S\in C^{(m-k)}[a,b],$$ i.e all splines on $[a,b]$ : $\mathcal S_\Delta ^{m,k}$. One can simply check that it's a subspace in $\mathcal P^m$, therefore finite dimensional, but how do we compute its dimension? It's clear our choice of coefficients is going to be limited by conditions. For instance if $[a,b]$ is divided into two subintervals $[a,z]\cup [z,b]$ and we consider $\mathcal S_\Delta ^{2,1}$, then we have some two polynomials $f:[a,z]\to\mathbb R$ and $g:[z,b]\to\mathbb R$ $$f(x) = a_0 + a_1x + a_2x^2\quad\mbox{and}\quad g(x) = b_0 +b_1x + b_2x^2$$ with the necessary conditions $f(z) = g(z)$ and $f'(z) = g'(z)$.

Question: Are such conditions sufficient when we consider the dimension? E.g if we consider $\mathcal S_\Delta^{2,1}$ on $[a,b] = [a,z]\cup [z,b]$, would the dimension be $2(2+1) - (2-1)(2-1+1) = 4?$

In the general case, we have $n-1$ interior knots and $m-k+1$ (necessary) conditions for each interior knot i.e $$S_j^{(d)}(x_j) = S_{j+1}^{(d)}(x_j)\qquad j=1,\ldots ,n-1\quad d = 0,\ldots, m-k$$

• In the example you've given, using the equation $f(z)=g(z)$ lets you solve for $a_{0}$, say, in terms of $a_{1},a_{2},b_{0},b_{1},b_{2},$ and $z$. Thus, this equation reduces the number of free parameters from $6$ to $5$. The one worry is that some of these equations are linearly independent, so that satisfying some subcollection of them implies that the rest are also satisfied, so you would need to prove that this does not happen. Sep 13, 2017 at 18:19

We might express these conditions in terms of matrices in the following way. Suppose we have two polynomials of degree $m$ which must agree at the knot $x$,

\begin{align*} f(x)&=a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{m}x^{m},\\ g(x)&=b_{0}+b_{1}x+b_{2}x^{2}+\cdots+b_{m}x^{m}. \end{align*}

We might write these as $f(x)=\vec{x}^{T}\vec{f}=[1,x,x^{2},\ldots,x^{m}][a_{0},a_{1},a_{2},\ldots,a_{m}]^{T}$, and similarly for $g$. Then if we let $p=[\vec{f}^{T},\vec{g}^{T}]^{T},$ the condition $f(x)=g(x)$ may be written as $[\vec{x},-\vec{x}]p=0.$

For $m$ derivatives to be equal at this knot, we may write the matrix

$$A=[A_{x},-A_{x}]= \begin{bmatrix} 1&x&x^{2}&\cdots&x^{m}&-1&-x&-x^{2}&\cdots&-x^{m}\\ 0&1&2x&\cdots&mx^{m-1}&0&-1&-2x&\cdots&-mx^{m-1}\\ 0&0&2&\cdots&m(m-1)x^{m-2}&0&0&-2&\cdots&-m(m-1)x^{m-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&m!&0&0&0&\cdots&-m! \end{bmatrix},$$ which clearly has linearly independent rows, since the leading nonzero entries are in different columns. Then for all but one derivatives to be equal at this knot, we need $Ap=0$. If we only want $k$ derivatives to be equal, we take the first $k+1$ rows of this matrix, which are also linearly independent, and for this submatrix $A'$, we again require $A'p=0.$

Now to have these equalities holding at all of the knots, we make a vector like $p$ but with the coefficients of all of the polynomials in order, and the matrix of equations we need to hold looks like $$\begin{bmatrix} A_{x_{1}}&-A_{x_{1}}&0&0&\cdots&0\\ 0&A_{x_{2}}&-A_{x_{2}}&0&\cdots&0\\ 0&0&A_{x_{3}}&-A_{x_{3}}&\cdots&0\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&0&0&\cdots&-A_{n-1} \end{bmatrix}.$$

Since the main diagonal has all positive entries (though the matrix is not square!), the rows of this matrix, of which there are $(n-1)(m+1)$, are linearly independent. Thus, we have $n(m+1)-(n-1)(m+1)=m+1$ degrees of freedom in this case, the nullity of the matrix above. If we do not want all $m$ derivatives to be equal at each knot, we remove the rows corresponding to the extra conditions from this matrix. We might also add conditions to the polynomials on the intervals $[x_{0},x_{1}]$ and $[x_{n-1},x_{n}]$, at the points $x_{0}$ and $x_{n}$, in order to make the spline unique, when we are trying to approximate a function on this interval.

Let $\dim X = n$. We know that if $\varphi _1,\ldots \varphi _n\in\mathcal L(X,\mathbb R)$ constitute a basis, then $$\bigcap_{j=1}^n\mbox{Ker}\varphi _j = \{0\}.$$ By Rank-Nullity theorem, if $\varphi _1,\ldots,\varphi _k$, $k\leq n$ are linearly indep, then $$\dim\bigcap_{j=1}^k\mbox{Ker}\varphi_j = n-k$$ Denote $g(a\pm0) := \lim_{x\to a\pm} g(x)$. We define $\varphi _{ij} : \mathcal P^m\to\mathbb R$ with $$f\mapsto f^{(j)}(x_i+0) - f^{(j)}(x_i-0),\quad i=1,\ldots ,n-1,\quad j=0,\ldots ,m-k.$$ Of course, the $\varphi _{ij}$ are all linear and clearly the space $\mathcal S^{m,k}$ annihilates all the $\varphi_{ij}$ due to continuity at knots. It suffices to show $\varphi _{ij}$ are linearly independent. Suppose, for a linear combination $$\sum_{i=1}^{n-1}\sum_{j=0}^{m-k}\alpha _{ij}\left [f^{(j)}(x_i+0)- f^{(j)}(x_i-0)\right ] = 0\qquad (f\in\mathcal P^m)$$ Then taking $f(x) = (x-x_{n-1})^{m-k}_+$, where $$(x-c)^r_+ := \begin{cases}(x-c)^r, &x\geq c\\0, &x<c\end{cases},$$ necessarely $\alpha_{n-1, m-k} = 0$. To see, why this is so it suffices to note that $$f^{(m-k)}(x_{n-1}+0)>0 \quad\mbox{and}\quad f^{(m-k)}(x_{n-1}-0)=0.$$Proceed, by considering $f(x) = (x-x_{n-1})^{m-k-1}_+$. Repeat process with every knot and every power and indeed all the coefficients must be zero.

By Rank-Nullity, the dimension of the spline space $\mathcal S^{m,k}$ is equal to $$(m+1)n - (m-k+1)(n-1)$$