# A vector that is orthogonal to the null space must be in the row space

Simple question.

We know from the fundamental theorem of linear algebra that the nullspace of a matrix is the orthogonal complement of its row space.

I can write this as:

Let $M$ be a matrix. The following two conditions are equivalent: (i) $u$ is orthogonal to the null space of $M$. (ii) $u$ is in the row space of $M$.

That (ii) implies (i) is trivial, pretty much by definition.

Question: But why is it also true (or even obvious) that (i) implies (ii)?

• Possible duplicate of this question, but at least related to it. – Cameron Buie Oct 29 '13 at 16:49
• The trouble I have with the answer there is that it seems to show only that a vector in the row space and a vector in the null space are necessarily orthogonal. What I'm unable to see is why a vector that is orthogonal to every vector in the null space, is necessarily in the row space. Or, in other words, why is there no vector that is not in the row space, but is orthogonal to every vector in the null space. – user46234 Oct 29 '13 at 16:54
• Here is an answer I found: Suppose $u$ is orthogonal to the null space of $M$ but is not in the row space of $M$. Then we could add the row vector $u$ to $M$ to form a new matrix $N$. Note that the null space of $N$ is the same as that of $M$. But dim $N$ = dim $M$ + 1. This violates the rank nullity theorem. QED. I guess what I was looking for was this: Is there some obvious way to prove that (i) implies (ii) without resort to other results (like the rank nullity theorem)? – user46234 Oct 29 '13 at 17:27
• I'm not aware of such a way. The answer I posted ends up using rank-nullity as a background result, for example. Ultimately, I don't think there is a way around it, largely because several of the results I mention fail in infinite-dimensional vector spaces. – Cameron Buie Oct 29 '13 at 17:42
• @KennyLJ, I also have this question. If a vector is orthogonal to null space of a matrix then it necessarily lies in row space. I also found this explanation which you have mentioned in your comment. However, can you please help me understand why nullspace of N is the same as that of M. Why I ask is that I think it should change when we are adding a new row (which we assume to be not in row space) to M. – Koro May 10 '20 at 14:21

First, I'll prove/outline/mention a few preliminary results.

Lemma 1: If $V$ is a finite-dimensional real-vector space and $W$ is a subspace of $V,$ then for all $v\in V,$ there exist unique $w\in W,w'\in W^\perp$ such that $v=w+w'$.

Proof: It is readily seen that existence implies uniqueness, since if $w_1,w_2\in W$ and $w_1',w_2'\in W^\perp$ such that $w_1+w_1'=w_2+w_2',$ then $w_1-w_2=w_2'-w_1',$ but $w_1-w_2\in W$ and $w_2'-w_1'\in W^\perp,$ so since $W\cap W^\perp$ is the zero subspace (the zero vector is the only self-orthogonal vector), then $w_1-w_2=w_2'-w_1'=0,$ so $w_1=w_2$ and $w_1'=w_2'$. To prove existence, we can use the Gram-Schmidt process, starting with a basis for $W,$ to make an orthonormal basis for $W,$ which we then extend to an orthonormal basis for $V$ (possible in finite dimensions), and the added vectors will be an orthonormal basis for $W^\perp.$ $\Box$

Lemma 2: If $V$ is a real-vector space and $W$ is a subspace of $V,$ then $(W^\perp)^\perp\supseteq W$. [Readily seen by definition.] $\Box$

Lemma 3: If $V$ is a finite-dimensional real-vector space and $W$ is a subspace of $V,$ then $(W^\perp)^\perp=W.$

Proof: Take any $v\in(W^\perp)^\perp,$ and write $v=w+w'$ as in Lemma 1. Since $v\in(W^\perp)^\perp$ and $w'\in W^\perp,$ then $$0=v\cdot w'=(w+w')\cdot w'=w\cdot w'+w'\cdot w',$$ and so $0=w'\cdot w'$ since $w\in W$ and $w'\in W^\perp.$ Only the zero vector is self-orthogonal, so $w'=0,$ so $v=w\in W$, giving us the reverse inclusion of Lemma 2. $\Box$

Lemma 4: Given a finite dimensional vector space $V$ and subspaces $W$ and $X$ of $V$, we have that $W^\perp=X^\perp$ if and only if $W=X$.

Proof: One implication is trivial. For the other, suppose $W^\perp=X^\perp.$ Take $x\in X$. By Lemma 1, there exist unique $w,w'$ such that $x=w+w',$ $w\in W$, and $w'\in W^\perp=X^\perp.$ Then $$0=x\cdot w'=(w+w')\cdot w'=w\cdot w'+w'\cdot w'=w'\cdot w',$$ so $w'=0,$ whence $x=w\in W$, and so $X\subseteq W$. By symmetrical arguments, we likewise have $W\subseteq X$, so $W=X$. $\Box$

Now, because of Lemmas 3 and 4, to show that (i) implies (ii) is equivalent to showing that every vector in the null space of $M$ is orthogonal to every element of the row space of $M$. Indeed, Say that $M$ is an $m\times n$ matrix, and writing $M=[r_1^T\:\cdots\:r_m^T]^T$ where the $r_j$ are the rows of $M,$ we note that for any $n$-dimensional vector $x$ we have $$Mx=\left[\begin{array}{c}r_1\\\vdots\\r_m\end{array}\right]x=\left[\begin{array}{c}r_1x\\\vdots\\r_mx\end{array}\right]=\left[\begin{array}{c}r_1^T\cdot x\\\vdots\\r_m^T\cdot x\end{array}\right].$$ In particular, if $x$ is in the null space of $M$, then $r_j^T\cdot x=0$ for $1\le j\le m,$ meaning that $x$ is orthogonal to each row of $M$, so since the row space of $M$ is spanned by these rows then $x$ is in the orthogonal complement to the row space of $M,$ as desired.

Dimension (the finite kind) is the key. First prove that for any subspace $W$ of a finite dimensional vector space $V$ one has $\dim W+\dim W^\perp=\dim V$. This is like the rank-nullity theorem, which can actually be invoked as follows. If $w_1,\ldots,w_d$ are a basis of $W$, then $f:v\mapsto(\langle v\mid w_i\rangle)_{i=1,\ldots,d}$ is a linear map $V\to\Bbb R^d$ that is surjective (the dual basis of the $w_i$ in$~W$ maps to the standard basis of $\Bbb R^d$) and $\ker(f)=W^\perp$ by definition. As $\dim W=d=\dim\operatorname{im}(f)$, rank-nullity gives our dimension equation.

Now obviously $W\subseteq(W^\perp)^\perp$ (this is like your (ii)$\Rightarrow$(i) part). But also by the above applied twice one has $\dim W+\dim W^\perp=\dim V=\dim W^\perp+\dim(W^\perp)^\perp$, so $\dim W=\dim(W^\perp)^\perp$, and it follows from the inculsion that $W=(W^\perp)^\perp$.

The orthogonal complement of the ortgonal complement of a subspace $W$ is $W$ itself. This applies in particular if $W$ is your row space.

First show that: if u $\in$ Row(M), then $u\in Ker(M)^\perp$ which you already know how to do. For the other direction, consider any $v \in Ker(M)^\perp$. Then $vx=0$ for any $x \in Ker(M)$. Now write $v=v_1+v_2$, where $v_1 \in Row(M)$, $v_2 \in Row(M)^\perp$ by using the Lemma(i) pointed out by Cameron. Now $(v_1+v_2)x=0$ which implies $v_1x+v_2x=0$ which inturn implies $v_2x=0$ (notice $v_1x= 0$, row and ker ). So $v_2 \in Ker(M)^\perp$. Since $v_2\in Row(M)^\perp$, it is also in Ker(M). Thus $v_2 \in Ker(M)^\perp \cap Ker(M)$. Thus $v_2$ is the zero vector. Thus $v \in Row(M)$. (OK sorry about the formatting earlier, now fixed).

• Welcome to MSE! This is incredibly hard to read without proper formatting. – user296602 Feb 14 '16 at 18:50