# A question about an $n$-dimensional subspace of $\mathbb{F}^{S}$.

I am self-studying Hoffman and Kunze's book Linear Algebra. This is Exercise 3 from page 111.

Let $S$ be a set, $\mathbb{F}$ a field, and $V(S,\mathbb{F})$ the space of all functions from $S$ into $\mathbb{F}:$ $$(f+g)(x)=f(x)+g(x)\hspace{0.5cm}(\alpha f)(x)=\alpha f(x).$$ Let $W$ be any $n$-dimensional subspace of $V(S,\mathbb F)$. Show that there exist points $x_{1},\ldots,x_{n}\in S$ and functions $f_{1},\ldots, f_{n}\in W$ such that $f_{i}(x_{j})=\delta_{ij}$.

Since $W$ is an $n$-dimensional subspace of $V(S,\mathbb{F})$ we can say find a basis $\mathcal{B}=\{f_{1},\ldots, f_{n}\}$. But I got stuck here. I don't know what to do from now on. I mean, what should I do in order to find those points $x_{1},\ldots,x_{n}\in S$ such that $f_{i}(x_{j})=\delta_{ij}$.

PS:This is the section about the double dual.

-
You left out a rather important part of the question :-) –  joriki Mar 18 '12 at 14:20
@spohreis: What is $W$? –  Rudy the Reindeer Mar 18 '12 at 14:20
@MattN. $W$ is any $n$-dimensional subespace of $V(S,\mathbb{F})$. –  spohreis Mar 18 '12 at 14:30
@joriki: Thank you for correcting my mistake, but I will blame Sunday morning. :) –  spohreis Mar 18 '12 at 14:31

You can prove this by induction on $n$. Here's a sketch:

Base Case: ($n = 0$ is totally trivial). $n =1$: a one-dimensional subspace of $\mathbb{F}^S$ is the set of scalar multiples of a single not identically zero function $f: S \rightarrow \mathbb{F}$. So there exists some $x \in S$ such that $f(x) \neq 0$, and then by rescaling there exists some $x \in S$ and $\alpha \in \mathbb{F}$ such that $\alpha f(x) = 1$.

Inductive Step: Suppose that the result holds for any $n$-dimensional subspace $W = \langle f_1,\ldots,f_n \rangle$, and now suppose that we add to $W$ one linearly independent function $g$. By induction there is a subset $S_n = \{x_1,\ldots,x_n\}$ of $S$ such that that elements of $W$, when restricted to functions on $S_n$, give all possible functions on $S_n$. Therefore there is some linear combination of the $f_i$'s which induces the same function on $S_n$ as $g$ does, i.e., there are scalars $\alpha_1,\ldots,\alpha_n$ such that $(g - \sum_{i=1}^n \alpha_i f_i)(x_j) = 0$ for all $1 \leq j \leq n$. But since $g$ is linearly independent from $W$, $(g - \sum_{i=1}^n \alpha_i f_i)$ is not the zero function. Can you complete the argument from here?

By the way, I agree that double duality is also relevant. But I think the above approach is more "hands on" -- after proving it this way, one can think about what it means in terms of double dual spaces.

-
@Peter L. Clark. Sorry I am slow! Then there is $x_{n+1}\in S$ and $x_{n+1}\notin S_{n}$ such that $(g-\sum_{i=1}^{n}\alpha_{i}f_{i}(x_{i}))=\alpha\neq 0$. Then we put $f_{i+1}=\dfrac{1}{\alpha}(g-\sum_{i=1}^{n}\alpha_{i}f_{i})$. Then $S_{n+1}=\{x_{1},\ldots,x_{n},x_{n+1}\}.$ Am I right? –  spohreis Mar 18 '12 at 17:47
@spohreis: yes, essentially. I guess what you wrote as $f_{i+1}$ should be $f_{n+1}$. Then you should go back and modify $f_1,\ldots,f_n$ to make sure that they are all zero at $x_{n+1}$... –  Pete L. Clark Mar 18 '12 at 17:52
Then there is $x_{n+1}\in S$ and $x_{n+1}\notin S_{n}$ such that $(g-\sum_{i=1}^{n}\alpha_{i}f_{i})(x_{n+1})=\alpha\neq 0$. Then we put $f_{n+1}=\dfrac{1}{\alpha}(g-\sum_{i=1}^{n}f_{i})$. –  spohreis Mar 18 '12 at 18:03

For your basis $\mathcal B$, for each $x$ consider the $n$-dimensional vector with components $f_i(x)$. There is a linearly independent set of $n$ of these vectors. If $S$ is finite, this follows directly because the matrix formed by all these vectors has rank $n$ because $\mathcal B$ is a basis. It also holds for infinite $S$, however, for if not, some $n-1$ of these vectors would have to span all of them; the matrix formed by those $n-1$ vectors would have rank at most $n-1$, so it would be possible to express one of the functions as a linear combination of the others at the corresponding $n-1$ points, but then since the vectors corresponding to the remaining points are spanned by the $n-1$ vectors, the one function would in fact be identical to the linear combination of the others at all points, contrary to the fact that $\mathcal B$ is a basis.

So we have $n$ points $x_1,\dotsc,x_n$ such that the corresponding $n$ vectors $f_i(x_j)$ are linearly independent. But then their entries $A_{ij}=f_i(x_j)$ form an invertible matrix, and since

$$\delta_{ij}=\sum_kA^{-1}_{ik}A_{kj}=\sum_kA^{-1}_{ik}f_k(x_j)=\left(\sum_kA^{-1}_{ik}f_k\right)(x_j)$$

the points $x_1,\dotso,x_n\in S$ and the functions $\sum_kA^{-1}_{ij}f_k\in W$ have the desired property.

-