# Column space of a matrix?

Recently I started learning about matrices and know for example that the pivot columns of a matrix form a basis for the column space of this matrix. I just can't seem to find out when two matrices have the same column space. I also heard something about column reducing a matrix to see if two matrices have the same column space, although I have no idea how reducing with columns works. Is column reducing a matrix the same as row reducing the transpose of this same matrix?

Maybe it is easier to tell when two matrices don't have the same column space? Can I for example use the fact that if two matrices don't have the same dimension for the column space, that the column spaces cannot be equal?

-
You: Is column reducing a matrix the same as row reducing the transpose of this same matrix? Yes, exactly. – Jeppe Stig Nielsen Mar 31 '13 at 17:11
@JeppeStigNielsen Would column reducing two matrices be a way to know if these two matrices have the same column space? Can you give me some more info on this? – n00b1990 Mar 31 '13 at 19:56
It is indeed true that if the column spaces do not have the same dimension they cannot be equal. However, the opposite is not true, so two column spaces that have the same dimension will not necessarily be equal. – Bitwise Mar 31 '13 at 20:38

Lemma 1: Given an $m\times n$ matrix $A,$ the null space of $A^T$ is the orthogonal complement of the column space of $A.$

Proof: Write $A=[c_1\:\cdots\:c_n]$ where the $c_j$ are the columns of $A,$ and note that for any $m$-dimensional vector $x$ we have $$A^Tx=\left[\begin{array}{c}c_1^T\\\vdots\\c_n^T\end{array}\right]x=\left[\begin{array}{c}c_1^Tx\\\vdots\\c_n^Tx\end{array}\right]=\left[\begin{array}{c}c_1\cdot x\\\vdots\\c_n\cdot x\end{array}\right].$$ Since the column space of $A$ is spanned by $c_1,...,c_n$, then $x$ is in the orthogonal complement to the column space of $A$ if and only if $x$ is orthogonal to each $c_j$ if and only if each $c_j\cdot x=0$ if and only if $A^Tx$ is the $n$-dimensional zero vector if and only if $x$ is in the null-space of $A^T.$ $\Box$

Lemma 2: Let $V,W$ be subspaces of some finite-dimensional space $X$. $V$ and $W$ have the same orthogonal complement if and only if $V=W$.

Proof: If $V=W$, then their orthogonal complements are trivially the same.

Suppose $V,W$ have the same orthogonal complement. Take $v\in V$. Since $X$ is the direct sum of $W$ and its orthogonal complement, and since $x\in V\subseteq X$, then there exist unique $w,w'$ such that $v=w+w',$ $w\in W$, and $w'$ in the orthogonal complement of $W$. Since $V,W$ have the same orthogonal complement, then $w'$ is orthogonal to $v,$ and so $$0=v\cdot w'=(w+w')\cdot w'=w\cdot w'+w'\cdot w'.\tag{\star}$$ Since $w'$ is in the orthogonal complement of $W$ and $w\in W$, then $w\cdot w'=0$, so it follows by $(\star)$ that $$w'\cdot w'=0.$$ Now, no non-zero vector is self-orthogonal, so $w'$ must be the zero vector, whence $v=w\in W$, and so $V\subseteq W$. By symmetrical arguments, we likewise have $W\subseteq V$, so $V=W$. $\Box$

Proposition: Given matrices $A,B$ of the same dimensions, $A$ and $B$ have the same column space if and only if $A^T$ and $B^T$ have the same reduced row echelon form.

Proof: Let $rref(M)$ indicate the reduced row echelon form of a matrix $M$. Recall that we can obtain $rref(M)$ by Gauss-Jordan elimination, which involves multiplication on the left by some finite collection of elementary matrices--that is, for any $M$, there exist elementary matrices $E_1,\cdots,E_n$ of appropriate dimension such that $rref(M)=E_n\cdots E_1M.$ This collection of elementary matrices is not unique, but that isn't important. Note, though, that elementary matrices are invertible, so it follows that the null spaces of $rref(M)$ and $M$ are the same.

Thus, $A^T$ and $B^T$ have the same reduced row echelon form if and only if they have the same null space. By Lemma 1, $A^T$ and $B^T$ have the same null space if and only if the column spaces of $A$ and $B$ have the same orthogonal complement. By Lemma 2, the column spaces of $A$ and $B$ have the same orthogonal complement if and only if the column spaces of $A$ and $B$ are the same. $\Box$

Upshot: The Proposition lets us get around needing to know what the column spaces of two matrices are, and simply determine whether they have the same column space by converting their transposes to reduced row echelon form.

-
I finally understand how to check for the same column space so thank you very much! I do want to ask: If the row reduced echolon forms of the transposes of the matrices are the same then they have the same column space. Should I take augmented matrices into account? What should I do with augmented matrices? Should I take the transpose of a matrix with the last column not included? – n00b1990 Apr 1 '13 at 15:15
Augmented matrices are useful tools for many things. For example, we can use them to find a basis for a matrix's null space, or we can use them to determine what a square matrix's inverse (if it exists) is or to solve a linear equation (when possible). However, augmented matrices are only tools--useful notation that make things easier for us. We will never be interested in their column space, since they are not intended to represent linear operators (as normal matrices are). – Cameron Buie Apr 1 '13 at 15:24
Now I finally understand. And what if I want to find a basis for the column space of a matrix. Can I just row reduce the matrix and take the pivot columns as the basis? Personally I don't think this is the right way to do it because you can only say what the dimension of the matrix is? I appreciate the help. – n00b1990 Apr 2 '13 at 16:47
If you row-reduce the matrix to echelon form, you can indeed take the pivot columns from the original matrix to be a basis for its column space. That will incidentally tell you what the rank of the matrix is, but it tells you more than that. A basis for the column space lets you to completely describe the image of the linear transformation represented by the matrix. Given $n>1$ and $0<k<n$, we know that $\Bbb R^n$ has infinitely many different subspaces of dimension $k$, so being able to completely describe an image is a great deal more information than just stating its dimension. – Cameron Buie Apr 2 '13 at 16:58