# Basic Linear Algebra Question

I am trying to figure out why dim(colA) = dim(row A), where col A is the column space of A and row A is the row space of A.

-
Try to show that rank of $A$ and it transpose $A^t$ is the same. This may help. –  William Sep 17 '12 at 23:51
The canonical approach is by reducing a matrix to row echelon form. –  lhf Sep 18 '12 at 0:05

Denote $\rho^c$ the column rank and $\rho^r$ the row rank.

First of all, $\rho^c(A)=1 \iff A=u\cdot v^T$ for column vectors $u,v$ $\iff \rho^r(A)=1$.

Then prove that $\rho^c(A_1+\ldots+A_n) \le \rho^c(A_1)+\ldots+\rho^c(A_n)$. Finally, for an arbitrary $A$, $r:=\rho^c(A)$, using the $r$ independent columns, construct $r$ pieces of rank 1 matrices $A_i$ such that $A=A_1+\ldots+A_r$.

This shows that $\rho^c(A) = \min\{k \mid \exists A_1,..,A_k$ with rank 1$: A=A_1+\ldots+A_k \}$. And the same for $\rho^r$.

-
The inequality $\rho^c(A_1+\ldots+A_n) \le \rho^c(A_1)+\ldots+\rho^c(A_n)$ holds because the column space of $A_1+..A_n$ is contained in the sum of column spaces of $A_i$: $$(A_1+..+A_n)x \in \mathrm{col}A_1+\dots +\mathrm{col}A_n$$ –  Berci Sep 19 '12 at 11:11

Consider $rref(A)$. The column correspondence principle (CCP) states that any linear dependence of the columns of $A$ is also found in the columns of $rref(A)$. It follows that the pivot columns of $A$ form a basis for $Col(A)$.

Next, you can argue that the pivot rows of $rref(A)$ form a basis for the row space of $A$.

Or, alternatively, argue that the pivot columns of $A^T$ form a basis for $Col(A^T)$ and $Row(A)=Col(A^T)$.

If you haven't proven any of these statements yet then you really should try since these give you simple computations to find bases for row and column space.

-