Revision as of 15:01, 8 December 2010

Statement: I am going to show that if V is a subspace of Rⁿ. then dim(V)+dim(V^orth)=n

Notes: Because of the lack of the orthagonal symbol in the wikipedia formatting page, I will be type 'orth' in a superscript to symbolize that. 

Proof:

First, let us say we have the following:

V which is a subspace of Rⁿ, and {v₁,v₂,v₃,..,v_k} are a basis for V. (The entries in the braces are vectors)

To refresh, a basis means those entries span V, AND are also linearly independent. 

So, therefore, then dim(V)=k (k is the number of vectors in our basis, which obviously is a non-finite amount, so I use k to denote that fact.)

Now that we have those assumptions and definitions out of the way, let me construct a matrix for you.

We will call this matrix A (A seems to the most common letter in the linear algebra world...but i digress)

Matrix A is a (n x k) matrix. (For reference, n is the rows, and k is the columns)

$ \begin{bmatrix} v_{1} & v_{2} & v_{3} & v_{k} \\ v_{1} & v_{2} & v_{3} & v_{k} \\ v_{1} & v_{2} & v_{3} & v_{k} \\ .... & .... & .... & .... \\ .... & .... & .... & .... \\ .... & .... & .... & .... \\ v_{1} & v_{2} & v_{3} & v_{k} \\ \end{bmatrix} $

Observe that the vectors are not just ordinary vectors, but rather, they are a very specific type called a COLUMN vector... 

Pressing on, we can say the following:

V= span(v₁,v₂,v₃,..,v_k)= c(A) (Again, the entries in the braces are vectors)

c(A) is a way to notate the column space of A. Additionally, look at the important relation that the span is equal to the column space of A! Keep this in mind, as it will be important for the rest of this. 

The next statement is an axiom from the textbook, and should be implied (i.e. to proove the fundamentals of the statement is over my head).

N(A^T)= c(A^orth)

This states that the nullity of A transpose is equal to the column space of A's orthagonal compliment. 

Now, that above relationship between nullity and the orthagonal compliment is straight from the textbook, but I will now relate that to the above work which has been done. 

It is logical to say that 

N(A^T)= c(A^orth) is ALSO equal to V^orth. (i.e. if V=c(A), then it will apply if you orthagonalizeboth matrices as well).

So, that leaves us with a nice triple equality, 

N(A^T)= c(A^orth)=V^orth. Brilliant

So, therefore, it can be said that: 

dim(V^orth)=dim(N(A^T))  (In case any of you guys forgot, dim(N(A^T)) is the NULLITY of A^T. Ask Momin if your confused. This is another axiom that is integral for this proof).

Now, it is actually time to draw the A^T matrix, so let's just do it already. 

A^T is going to be a (k x n) matrix where k is rows and n is columns.

$ \begin{bmatrix} v_{1}^T & v_{1}^T & v_{1}^T & v_{1}^T \\ v_{2}^T & v_{2}^T & v_{2}^T & v_{2}^T \\ v_{3}^T & v_{3}^T & v_{3}^T & v_{3}^T \\ .... & .... & .... & .... \\ .... & .... & .... & .... \\ .... & .... & .... & .... \\ v_{k}^T & v_{k}^T & v_{k}^T & v_{k}^T \\ \end{bmatrix} $

Now, while A had column vectors, it is logical to expect to see ROW vectors for the transpose.

If you are slightly confused by this, consider this more concrete definition of nullspace, and such. Lets say we have a vector B (2nd most common letter in linear algebra world...)

'B = [b₁,b₂,b₃,...,b_n], now we are gonna put this into reduced row echelon form (rref).'

rref:

$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} $

So, the first 3 columns are the pivot columns. The rank of B is just simply the number of pivot columns in the rref matrix. So, the free columns (non-pivot columns) refer to the nullspace...

Now, thats been cleared out of the way, time for some gritty math.

The Grit:

Rank(A^T) + Nullity (A^T)= n

Rank (A) + Nullity (A^T)= n

dim (c(A)) + dim (N(A^T))= n

therefore,

dim(V) + dim(V^orth) = n

Q.E.D.

-sanjay