Let \(V\) be a vector space. Let \(P\) be the set of linearly independent subsets of \(V\). Note that \(P\) is a poset under inclusion. Suppose \(C \subseteq P\) is a chain in \(P\). Let \(S = \cup_{W \in C} W\). Suppose \(S\) is linearly dependent. Then there exists a finite linearly dependent subset \(v_1,\ldots, v_n \in S\). By construction, each \(v_i\) is an element of \(W_i\) for some \(W_i \in C\). Since \(C\) is a chain, one of \(W_1,\ldots, W_n\) is greater than or equal to all the others; say \(W_n\). Thus \(W_n\) contains \(v_1,\ldots,v_n\) and is linearly dependent. Since \(P\) (and thus \(C\)) only contains linearly independent sets, we have a contradiction. Thus \(S\) is linearly independent. By construction, \(W \subseteq S\) for all \(W \in C\). Thus the chain \(C\) has an upper bound. Since every chain in \(P\) has an upper bound, we conclude that \(P\) has a maximal element \(B\) by Zorn’s Lemma.

We claim \(B\) spans \(V\). Otherwise, there exists a \(v \in V\) such that \(v \notin \operatorname{span}(B)\). But then \(B \cup \{v\}\) is linearly independent, contradicting maximality. Thus \(B\) spans \(V\) and is a basis.

Part (a) was more challenging than I intended. The standard way to do this is to show that in fact \(A\) is an orthogonal set for an appropriate inner product as in assignment 2. However, the following is a bit more direct (and was more in the vein of what most people tried.)

Observe that for positive integers \(n,k\), we have \[ \left.\frac{d^{4k}}{dx^{4k}}\right|_{x=0} \cos(nx) = (n^4)^k. \] Given a linear dependence relation \[ a_0 + a_1\cos(x) + a_2\cos(2x) + \cdots + a_n\cos(nx) = 0 \] we evaluate the operator \(\left.\frac{d^{4k}}{dx^{4k}}\right|_{x=0}\) for \(k=0, \ldots, n\) to obtain \(n+1\) new equations. Put in matrix form, we obtain: \[ \begin{pmatrix} 1 & 1 & 1 & \ldots & 1\\ 0 & 1^4 & (1^4)^2 & \ldots & (1^4)^n\\ 0 & 2^4 & (2^4)^2 & \ldots & (2^4)^n\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & n^4 & (n^4)^2 & \ldots & (n^4)^n\\ \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_n \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix}. \] Ignoring the top row and leftmost column, this is a Vandermonde matrix as in Problem 3 below. Thus the matrix is invertible.

For part (b), we first establish that \(\cos(nx)=T_n(\cos(x))\) for a polynomial \(T_n(z) \in \mathbb{R}[z]\) of degree \(\le n\). (These are the Chebyschev polynomials of the first kind.) We proceed by induction on \(n\). For the basis step, we observe \(T_0=1\) and \(T_1=z\). The induction step immediately follows from the hint, which gives the recurrence relation \(T_n(z) = 2zT_{n-1}(z)-T_{n-2}(z)\).

Now define \[A_N = \{ \cos(nx) \mid n \in \mathbb{Z}, 0 \le n \le N \}\] and \[B_N = \{ \cos^n(x) \mid n \in \mathbb{Z}, 0 \le n \le N \}.\] The Chebyshev polynomial argument has established that \(\operatorname{span}_k A_N \subseteq \operatorname{span}_k B_N\).

Since \(A_N\) is linearly independent, \(\dim_k \left( \operatorname{span}_k A_N\right) = N+1\). Since \(B_N\) has \(N+1\) elements, \(\dim_k \left( \operatorname{span}_k B_N\right) \le N+1\). Thus \(\operatorname{span}_k A_N = \operatorname{span}_k B_N\). The result follows by taking the union as \(N \to \infty\).

1. follows immediately from the definitions.

For (b), suppose there is a linear dependence relation \[l=a_0f_0 + \cdots + a_nf_n=0.\] Evaluating at \(c_i\), we obtain \(l(c_i)=a_i=0\) for every \(i\). Thus the set is linearly independent. Since there are \(n+1\) elements in the set and \(k[x]_{\le n}\) has dimension \(n+1\), it must be a basis.

For (c), let \(p_0, \ldots, p_n\) be distinct points of \(k\) and let \(q_i=g(p_i)\) for each \(i=0, \ldots, n\). From part (a), we see that \(g(x)=q_0f_0(x)+\cdots + q_nf_n(x)\). From part (b), we know that this representation is unique since \(f_0,\ldots, f_n\) is a basis.

Finally, for part (d), the result follows from observing that \[ x^k = c_0^k f_0(x) + \cdots c_n^k f_n(x)\] for every non-negative integer \(k\). To see this, evaluate both sides at \(c_0,\ldots,c_n\), which uniquely determines the right hand side.

Note that the change of basis matrix should be interpreted as follows. Given \(g=\sum_{i=0}^n a_ix^i\) we want to find the expression \(g=\sum_{i=0} b_if_i\) for appropriate \(b_i\). This is accomplished by the matrix multiplication: \[ \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix} = \begin{pmatrix} 1 & c_0 & c_0^2 & \ldots & c_0^n\\ 1 & c_1 & c_1^2 & \ldots & c_1^n\\ 1 & c_2 & c_2^2 & \ldots & c_2^n\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & c_n & c_n^2 & \ldots & c_n^n\\ \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_n \end{pmatrix}.\]

Define a function \(\Psi : \operatorname{Hom}_k(k,V) \to V\) by \(\Psi(f)=f(1)\).

For \(f,g \in \operatorname{Hom}_k(k,V)\) and \(\lambda \in k\), we have \[\Psi(\lambda f + g) = (\lambda f + g)(1) = \lambda f(1) + g(1) = \lambda \Psi(f) + \Psi(g).\] Thus, \(\Psi\) is a \(k\)-linear map.

For all \(v \in V\), define \(f_v : k \to V\) by \(f_v(\lambda)=\lambda v\). Since \(f_v(\lambda a+b)=\lambda f_v(a) + f_v(b)\) for all \(a,b,\lambda \in k\), we conclude \(f_v \in \operatorname{Hom}_k(k,V)\). Since \(\Psi(f_v)=v\), we conclude \(\Psi\) is surjective.

Suppose \(f \in \ker(\Psi)\). Then \(f(1)=0\) and so \(f(\lambda)=\lambda f(1)=0\) for all \(\lambda \in k\). Thus \(f = 0\) and so \(\Psi\) is injective.

We begin with the first map, which will be called \(\Psi\). Suppose we are given a \(k\)-linear map \[f : W \to \prod_{i=0}^\infty V_i.\] For each \(i \in \mathbb{N}\), define \[\Psi(f)_i : W \to V_i\] via \[\Psi(f)_i(w)=f(w)_i\] for all \(w \in W\). We check that \[\Psi(f)_i(\lambda w_1 + w_2)=\lambda \Psi(f)_i(w_1) + \Psi(f)_i(w_2)\] so each \(\Psi(f)_i\) is in \(\operatorname{Hom}_k\left(W,V_i\right)\). Thus, \[\Psi(f):=(\Psi(f)_0,\Psi(f)_1, \ldots )\] is a well-defined function.

We see that \(\Psi\) is \(k\)-linear since \[\Psi(\lambda f_1 + f_2)_i=\lambda \Psi(f_1)_i + \Psi(f_2)_i\] for every \(i \in \mathbb{N}\), \(\lambda \in k\), and appropriate functions \(f_1,f_2\). The map \(\Psi\) is a bijection since we can explicitly exhibit its inverse: \[ \Psi^{-1}(g_0,g_2,\ldots )(w) = (g_0(w),g_1(w),\ldots ).\] We see immediately that \(\Psi \circ \Psi^{-1}\) and \(\Psi^{-1} \circ \Psi\) are identities.

Now we consider the second map, which we will call \(\Phi\). Suppose we are given a \(k\)-linear map \(f : \bigoplus_{i=0}^\infty V_i \to W\). For each \(i \in \mathbb{N}\), define \[f_i : V_i \to W\] via \(f_i(v)=f(\ldots,0,v_i,0,\ldots )\). We see that \(f_i\) is \(k\)-linear since \(f\) is \(k\)-linear. Thus \(\Phi(f)=(f_0,f_1,\ldots )\) gives a well defined function as desired.

We see that \(\Phi\) is \(k\)-linear since \[\Phi(\lambda f_1 + f_2)_i = \lambda \Phi(f_1)_i + \Phi(f_2)_i\] for every \(i \in \mathbb{N}\), \(\lambda \in k\), and appropriate \(f_1,f_2\). We have an explicit inverse again. First, we remark that \(g_i(0)=0\) for all \(k\)-linear \(g_i : V_i \to W\). Thus, for \((v_0,v_1,\ldots) \in \ \bigoplus_{i=0}^\infty V_i\), we see that \[ \left[\Phi^{-1}(g_0,g_1,\ldots)\right](v_0,v_1,\ldots) := \sum_{i=0}^\infty g_i(v_i)\] is well-defined since all but finitely many of the \(v_i\) are zero. We see immediately that \(\Phi \circ \Phi^{-1}\) and \(\Phi^{-1} \circ \Phi\) are identities.