# Vector orthogonal to null space is in row space (but over general field)

I am new here, so I hope this question hasn't been asked before. And I hope that it is not out of place to ask this kind of question.

My question is basically the following. Suppose we are given a collection of linear maps $\phi_{1}, \ldots, \phi_{m}$ from $k^n$ to $k$, where $k$ is a field. Suppose moreover that $\phi:k^n\rightarrow{k}$ satisfies $\phi(v)=0$ for all $v$ in the intersection of the kernels of the $\phi_{i}$'s. I am supposed to show that $\phi$ then has to be in $Span\{\phi_{1}, \ldots, \phi_{m}\}$. Translated to matrix language, if the $\phi_{i}$'s are the rows of a matrix with entries in $k$, the result I'm trying to prove says that if a vector is "orthogonal" to the nullspace of the matrix, then it is in the row space. If $k=\mathbb{R}$ this is known since then multiplying a row vector with a column vector is the same as using the standard inner product $\mathbb{R}^n$. But in this more general situation I assume I have to prove things differently.

In the case $m=1$ I have been able to prove it, as follows:

Let $V=ker(\phi_{1})$. If $V=k^n$ then $\phi_{1}=0$ so the result is trivial, since then $\phi=0$ also. So we can assume we can find an element $v_{1}\notin{V}$ satisfying $\phi_{1}(v_{1})\neq{0}$. Choose $a_{1}\in{k}$ such that $\phi(v_{1})=a_{1}\phi_{1}(v_{1})$. Now assume $\phi$ is not generated by $\phi_{1}$, so that we can find $w\notin{V}$ with $\phi(w)\neq{a_{1}\phi_{1}(w)}$. Choose $\gamma_{1}\in{k}, \gamma_{1}\neq{0}$ with $\gamma_{1}\phi_{1}(w)=\phi_{1}(v_{1})$.Let $x=\gamma_{1}w-v_{1}$. Then $\phi_{1}(x)=0$ so $x\in{V}$. But $\phi(x)=\gamma_{1}\phi(w)-\phi(v_{1})=\gamma_{1}\phi(w)-a_{1}\phi_{1}(v_{1})=\gamma_{1}(\phi(w)-a_{1}\phi_{1}(w))\neq{0}$, a contradiction.

Now I have been really struggling to generalize this, even in the case $m=2$. I started out with the following:

Choose $v_{1}, \ldots, v_{m}$ such that $\phi_{i}(v_{i})\neq{0}$, $i=1,\ldots, m$. To see that this is ok note that if for some $i$ we had $\phi_{i}(v)=0$ for all $v$, then $\phi_{i}=0$ and so we could throw it out and assume we had $m-1$ functions. Now IF we also could choose the $v_{i}$ such that $\phi_j(v_{i})=0$ for $j\neq{i}$ then a similar argument to the one given above can be used. However, it is certainly not always the case that we can do this. F.ex. if $m=2$ then we could have $ker(\phi_{1})\subset{ker(\phi_{2})}$ etc. But maybe the proof could be divided into cases, depending on which $\phi_{j}(v_{i})=0$ or not. For $m=2$ I have been able to do it provided not both $\phi_{1}(v_{2})$ and $\phi_{2}(v_{1})$ are different from zero. Even if I could show it in the last case too, I am a bit at loss how to generalize it to a general $m$. The main obstacle is constructing an element $x\in{k^n}$ which vanish at all the $\phi_{i}$,while at the same time satisfying $\phi(x)\neq{0}$.

Is this the right way to go, or is there some much simpler way of proof which I am missing? (I assume the result is true; at least I've been told so).

Any useful help would be greatly appreciated!

UPDATE: I think I have succeeded in proving it using Marc's method:

We claim that we may take the $\phi_{i}$ to be linearly independent. For if,say, $\phi_{j}$ could be written as a linear combination of the others then $V=\bigcap_{i=1}^{m} ker(\phi_{i})=\bigcap_{i=1, i\neq{j}}^{m} ker(\phi_{i})$ and so we could throw out $\phi_{j}$ and reduce to the $m-1$ case (by induction).

Assuming linear independence, we can choose elements $v_{1}, \ldots, v_{m}\in{k}$ satisfying $\phi_{i}(v_{i})\neq{0}$ and $\phi_{j}(v_{i})=0$ for $j<i$, $i=1, \ldots, m$. First note that for all $i$ we can choose $v_{i}$ with $\phi_{i}(v_{i})\neq{0}$, for if not then $\phi_{i}$ would be the zero map and that would contradict the linear independence of the $\phi_{i}$. Fix an index $j$. Suppose we could not choose the element $v_{j}$ as described above. Then $\phi_{j}(v)\neq{0}$ would always imply that $\phi_{i}(v)\neq{0}$ for at least one $i<j$. This is equivalent to the following inclusion: $\bigcap_{i=1, i\neq{j}}^{m} ker(\phi_{i})\subset{ker(\phi_{j})}$. Hence $\phi_{j}$ is a linear functional which vanish on the intersection of the kernels of all the previous $\phi_{i}$, and hence it is generated by them, a contradiction.

We claim that $E=V\cup{Span\{v_{1}, \ldots, v_{m}\}}$. Suppose $v\notin{V}$. Then $\phi_{i}(v)\neq{0}$ for at least one $i$. We assume $i$ is the least such index, that is we assume $\phi_{k}(v)=0$ for $k<i$. Choose an element $a\in{k}$ satisfying $\phi_{i}(v)=a\phi_{i}(v_{i})$. Then by construction $v-av_{i}$ is in the kernel of $\phi_{i}$. But if $k<i$ then we also have $\phi_{k}(v-av_{i})=\phi_{k}(v)-a\phi_{k}(v_{i})=0-0=0$. Hence $v-av_{i}\in{\bigcap_{j=1}^{i} ker(\phi_{j})}$. If it is also in the kernel of the remaining $\phi_{j}$'s then we are done. If not, let $l$ be the least index such that $\phi_{l}(v-av_{i})\neq{0}$. Applying the same procedure once more, we can choose $b\in{k}$ with $\phi_{l}(v-av_{i})=\phi_{l}(v_{l})$. Then the element $v-av_{i}-bv_{l}$ will be in the intersection of the kernels $ker(\phi_{j})$, $j=1,\ldots, l$. We continue like this, and sooner or later the process must terminate, since $m$ is finite.

For the final part of the proof, we will construct a linear combination of the $\phi_{i}$'s which takes the same values as $\phi$ on all $v_{i}$. We will then have to conclude that this linear combination is equal to $\phi$. First choose $a_{m}\in{k}$ such that $a_{m}\phi_{m}(v_{m})=\phi(v_{m})$. Next choose $a_{m-1}$ such that $a_{m-1}\phi_{m-1}(v_{m-1})=\phi(v_{m-1})-a_{m}\phi_{m}(v_{m-1})$. In general, choose $a_{k}$ such that: \begin{align*} a_{k}\phi_{k}(v_{k})=\phi(v_{k})-a_{k+1}\phi_{k+1}(v_{k})-a_{k+2}\phi_{k+2}(v_{k})-\ldots-a_{m}\phi_{m}(v_{k}) \end{align*} It can then be checked that this choice of $a_{i}$'s will do the job!

END PROOF

Does this look ok? Anyway, thanks for all the useful hints and comments. Maybe I will try and look at the more general situation too( hinted at by Blah)later.

-
 I can't envision a way in which this question is out of place. And you've explained your thoughts, which is great. – Dylan Moreland Mar 17 '12 at 14:58

Here are some thoughts that may help you advance with this problem. First note that the converse to what you want to prove is obvious: if $\phi$ is a linear combination of $\phi_1,\ldots,\phi_m$, then it will certainly vanish on the intersection $V=\bigcap_i\ker(\phi_i)$ of their kernels. Now while this is not immediately helpful for $\phi$, you can also use it for the $\phi_i$: if and one of the $\phi_i$ is linearly dependent on the others, then it will vanish on the intersection of their kernels, and therefore its presence will not affect that intersection. It also won't affect the span of the others, so if such a $\phi_i$ exists, one can throw it out and the problem remains the same. For this reason we may assume without loss of generality that $\phi_1,\ldots,\phi_m$ are linearly independent. Note that this automatically takes care of the situation that $\phi_i=0$, which you disposed of explicitly in your attempt, but other cases of linear dependence are more subtle but equally disruptive to concentrating on the essential things, so it is good to have done away with all of them.

Now if one imagines a proof by induction on $m$, then assuming $\phi_1,\ldots,\phi_m$ are linearly independent and considering them one by one, the induction hypothesis implies (by contraposition) that each $\phi_i$ does not vanish on the intersection of the kernels of $\phi_1,\ldots,\phi_{i-1}$. This means you can find a vector $v_i$ such that $\phi_j(v_i)=0$ for all $j<i$, but $\phi_i(v_i)\neq0$. Now if you choose such $v_i$ for $i=1,\ldots,m$, it is not hard to show (by induction) that $V$ together with $\mathrm{Span}(v_1,\ldots,v_m)$ span all of your space $E=k^n$; in fact $E$ will be the direct sum of those subspaces. If you can find a linear combination of $\phi_1,\ldots,\phi_m$ that takes the same values on each of the $v_i$ as $\phi$ does, then that combination will have to be equal to $\phi$, since both vanish on $V$. Now all that is left is to prove the existence of such a linear combination, by induction on $m$. You'll have to decide first whether you want to find the coefficient of $\phi_m$ before or after applying the induction hypothesis.

By the way, this proof will not use in any way that $E=k^n$, nor indeed that $E$ is finite dimensional (though it does of course use that $m$ is finite).

-

Hint: You have not used the fact that $\phi$ is zero on $V=\bigcap ker(\phi_i)$ - consider your $m=1$-approach with this modification. How many $v$ do you really need?

-

You might do it more generally: a subspace $$W \subseteq V^*$$ defines a subspace (the nullspace $v\in W^*$ iff $w(v)=0$ for all $w \in W$) $$W^* \subseteq V$$ Your claim is that for a linear form $\lambda \in V^*$ the following statement is true $$\lambda |_{W^*}=0 \Leftrightarrow \lambda \in W$$ The $\Leftarrow$ is easy, and for $\Rightarrow$ consider the map $$V \rightarrow V/W^* \text{ and its dual } (V/W^*)^* \rightarrow V^*$$ The second map is injective, $W$ is in the image, the dimension formula shows that all that remains to prove is $$\text{dim}(V/W^*) = \text{dim}(W)$$ And for that take $w_1,\dots,w_k$ a basis for $W^*$, extend it to a basis $w_1,\dots,w_n$ for $V$ and think about the last $n-k$ elements of the dual basis $w^1,\dots,w^k,w^{k+1},\dots,w^n$

-