Rank of smoothing matrix The solution to the minimizing problem: $$RSS(f, \lambda) = \sum_{i=1}^n (y_i - f(x_i))^2 + \lambda \int (f''(t))^2 dt$$ is written in matrix form as $f = N\theta = \sum_{j = 1}^n N_j(x_i) \theta_j$ where the $N_j(x)$ are a $n$-dimensional set of basis functions representing a natural cubic spline. Together with a choice of $\lambda$ we have a smoothing spline with the estimate $$\hat f = S_\lambda y$$ where $$S_\lambda = N(N^tN + \lambda \Sigma_N)^{-1}N^t$$ and $\Sigma_{N_{ij}} = (\int N''_i(t)N''_j(t) dt)_{ij}$ and $N_{ij} = N_j(x_i)$.

Why is $\mathrm{Rank}(S_\lambda) = n$, or equivalently $N$ invertible?
 A: A spline is a method of fitting a function to a set of points $(x_1,y_1),$ $(x_2,y_2),$ $\ldots, (x_n,y_n).$ The answer to the question is because natural cubic splines exist.
The full explanation appears in the last two sentences of this post.  The intervening material consists of standard definitions, constructions, and observations in linear algebra to establish notation and fix the concepts.  It is included because (a) the comment thread to the question indicates there is a risk of misinterpreting some of the terminology and (b) taking this abstract approach will demonstrate we need to know only that splines exist, but we don't need any details of their construction.  As such, the results are both easy to obtain and they apply to any kind of spline (in the extremely general sense defined below).
The vector space interpretation is also helpful for bringing to the fore two fundamental operations associated with splines: (i) using splines to approximate arbitrary functions and (ii) passing splines through finite sets of points.  I will address these in turn, but wish to emphasize there's little to demonstrate and nothing to calculate.
Linear algebra
To set the stage, we will be working with functions $f:X\to \mathcal R$ defined on the set $X$ of all possible values of the data $x_i.$ The codomain is a field $\mathcal R$ (usually the real or complex numbers). The set of these functions, $\mathbb R^X,$ is naturally a vector space under pointwise addition of functions and scalar multiplication.  That is, given any $x\in X,$ for all $f,g\in \mathcal R^X$ and $\alpha,\beta\in\mathcal R,$
$$(\alpha f+\beta g)(x) = \alpha f(x)+\beta g(x).$$
A spline is, first of all, a vector subspace $\mathbb G \subset \mathcal R^X:$ we intend to use the functions in $\mathbb G$ to approximate arbitrary functions in $\mathcal R^X.$
Any finite collection of distinct "knots" $\Xi=(\xi_1, \xi_2, \ldots, \xi_p)\in X^p$ determines a linear transformation $\iota_\Xi: \mathcal R^X \to \mathcal R^\Xi$ via restriction to the domain $\Xi,$
$$\iota_\Xi(f)(\xi_j) = f_{|\Xi(\xi_j)} = f(\xi_j)$$
for $j= 1, 2, \ldots, p.$  The codomain $\mathcal R^\Xi$ is canonically isomorphic to the standard $p$-dimensional vector space $\mathcal R^p:$ simply write the function $\iota_\Xi(f)$ as the vector $\mathbf y = (f(\xi_1),f(\xi_2),\ldots,f(\xi_p)).$  I will therefore treat these as the same vector space without further comment.
The image $\iota_\Xi(\mathbb G) \subset \mathcal R^\Xi$ is the set of values that spline functions can take on $\Xi.$  The assertion "splines exist" means that whenever $\Xi$ is a sequence of knots, $\iota_{\Xi}$ is a surjection: to every possible set of values $\mathbf y = (y_1,y_2,\ldots, y_p),$ there is a spline function $f\in\mathbb G$ attaining those values at the knots.
The foregoing characterizes a spline as a function space $\mathbb G$ with an existence property.  I am not aware of any such characterization in the literature, but believe it applies to every type of spline that has been invented.
Existence is usually proven by exhibiting a right inverse for arbitrary $\iota_\Xi.$ That is, given $\mathbf y,$ a function $g\in\mathbb G$ is constructed for which $\iota_\Xi(g) = \mathbf y.$  This chapter of ESL includes several such constructions for natural cubic splines defined on real numbers $X=\mathbb R,$ so I take the existence as not in question here.
Let $\iota_\Xi^*$ be such a right inverse: that is, $\iota_\Xi^*$ is a vector space isomorphism between $\mathcal R^p$ and a subspace of $\mathbb G$ where, for all $\mathbf y \in \mathcal R^p,$
$$\iota_\Xi(\iota_\Xi^*(\mathbf y)) = \mathbf y.$$
Because $\iota_\Xi$ is an isomorphism, any basis $\mathcal E$ of $\mathcal R^p$ (that is, a linearly independent spanning subset) corresponds to a basis $\iota_\Xi^*(\mathcal E)$ of the image.  The latter is what ESL means by a basis of spline functions.  As we have seen, these really are functions and it really is a basis of a special finite-dimensional subspace of functions.
The circumstances of the question
That's it for the linear algebra preliminaries.  Next, let's address the unstated assumptions of the question.  These are

*

*$N$ is the matrix determined by a spline with "knots at the data values."


*The $x_i$ are distinct.
These indicate the matrix $N$ in the question is a special one where $p=n$ (assumption (1)) and the data values $x_i$ are the knots $\xi_i$ (which must be distinct, assumption (2)).
Pick any basis $\mathcal E = (\mathbf e_1, \ldots, \mathbf e_n).$  Each $\mathbf e_j = (e_{ij}, j = 1, \ldots, n)$ is an $n$-vector.  The matrix $N$ in the question is constructed from the $n$ knots $\Xi \subset \mathcal R^X$ and the basis $\mathcal E \in \left(\mathcal R^n\right)^n$ by applying each of the corresponding basis spline functions to the data:
$$N = (n_{ij}) = \iota_\Xi^*(\mathbf e_j)(x_i) = \iota_\Xi^*(\mathbf e_j)(\xi_i) = (e_{ij}).\tag{*}$$
(In the notation of the question, the basis functions are $N_j = \iota_\Xi^*(\mathbf e_j)$ and $N = (n_{ij}) = N_j(x_i).$)
Solution
The identity $(*)$ shows $N$ is a square $n\times n$ matrix equal to the matrix of $\mathcal E.$ Because $\mathcal E$ is linearly independent, this matrix has rank $n$ and so does its transpose.  Equivalently, $N$ is invertible.
The question concerns the rank of a matrix of the form
$$S_\lambda = N^\prime A_\lambda^{-1} N.$$
The interior matrix in this product is invertible (its inverse is $A_\lambda$).  Because natural cubic splines exist, $N$ is invertible, whence $S_\lambda$ (which represents a composition of three invertible linear transformations) also is invertible and therefore must have the same rank $n$ as its components, QED.
A: This is a partial answer to be completed, I posted it just for clarification and drawing more attention.
I have consulted the ESL section.  Let me first clarify the notations.  The problem is 1D function estimation so the training data is $(x_i, y_i): i = 1, \ldots, n$ (as I pointed out in the comment, using $N$ to denote the number of observations is an unfortunate confusion, even in ESL the spline matrix is boldfaced.  So here I will still use $n$ to denote the number of observations).  The spline matrix $N$ is defined as
\begin{align}
N = \begin{bmatrix}
N_1(x_1) & N_2(x_1) & \cdots & N_n(x_1) \\
N_1(x_2) & N_2(x_2) & \cdots & N_n(x_2) \\
\vdots   & \vdots   & \ddots & \vdots   \\
N_1(x_n) & N_2(x_n) & \cdots & N_n(x_n)
\end{bmatrix}. \tag{1}
\end{align}
Evidently, if $x_i = x_j$ for some $i \neq j$, then clearly $N$ is not invertible (because then the $i$-th row and the $j$-th row are identical).  So in order $\operatorname{rank}(S_\lambda) = n$ (a claim made by ESL, p.153), $x_1, \ldots, x_n$ must be distinct (without loss of generality, assume $x_1 < x_2 < \cdots < x_n$).
According to the author:

$N_j(x)$ are an $n$-dimensional set of basis functions for representing this family of natural splines...

By calling $\{N_1(x), \ldots, N_n(x)\}$ "basis functions" (to be fair, doing so without first proving they really formed a basis of a vector space -- which was not clearly stated in advance, is loose), they are necessarily linearly independent in the vector space $V$ of spline functions (known as "spline space", more accurately, given knots $x_1 < x_2 < \cdots < x_n$ and only cubic splines are under consideration, I think $V$ is a real vector space spanned by
$\{1, x, x^2, x^3, (x - x_1)_+^3, \ldots, (x - x_n)_+^3\}$).  As you are interested in, this statement, of course requires a mathematical proof, which the text omitted.
Recall $N_j(x)$ is defined as (Equation (5.4) in ESL):
\begin{align}
N_1(x) = 1, N_2(x) = x, N_{k + 2}(x) = d_k(x) - d_{n - 1}(x), k = 1, \ldots, n - 2,
\tag{2}
\end{align}
where
\begin{align}
d_k(x) = \frac{(x - x_k)_+^3 - (x - x_n)_+^3}{x_n - x_k}. \tag{3}
\end{align}
Plug $(2)$ and $(3)$ into $(1)$, then $\det(N)$ (denoted by $D_n$) is
\begin{align}
& D_n = \begin{vmatrix}
1 & x_1 & 0                                   & 0 &\cdots & 0 \\      
1 & x_2 & (x_2 - x_1)^3/(x_n - x_1)           & 0 & \cdots & 0 \\
\vdots & \vdots & \vdots                      & \vdots & \ddots & \vdots \\
1 & x_{n - 1} & (x_{n - 1} - x_1)^3/(x_n - x_1) & (x_{n - 1} - x_2)^3/(x_n - x_2) & 
\cdots & (x_{n - 1} - x_{n - 2})^3/(x_n - x_{n - 2}) \\
1 & x_n & (x_n - x_1)^2 - (x_n - x_{n - 1})^2 & (x_n - x_2)^2 - (x_n - x_{n - 1})^2 & \cdots & (x_n - x_{n - 2})^2 - (x_n - x_{n - 1})^2
\end{vmatrix} \\
& ???? \neq 0.
\end{align}
When $n = 1, 2, 3$,
\begin{align}
& D_1 = 1 \neq 0, \\
& D_2 = x_2 - x_1 \neq 0, \\
& D_3 = 2(x_2 - x_1)^2(x_3 - x_2) \neq 0,
\end{align}
all confirming $N$ is invertible.  However, for $n \geq 4$, it is more difficult to make a conclusion.  I have calculated
\begin{align}
D_4 &= (x_4 - x_1)^{-1}(x_2 - x_1)(x_3 - x_2)^2(x_2 + x_3 - 2x_1)(2x_4 - x_2 - x_3) \\
&+ (x_4 - x_2)^{-1}(x_2 - x_1)(x_3 - x_2)^3[(x_1 - x_2)^2 + (x_3 - x_4)^2 - (x_4 - x_1)^2],
\end{align}
but it is not immediate to see if $D_4 \neq 0$.
