rank

let \(A\) be an \(m\times n\) matrix. Say that it represents a linear map from the space of \(m\) dimensional vectors to \(n\) dimensional vectors
if \(rank(A)=m\), then the linear map is surjective or "onto". If \(A\) represents a system of equations, then we will definitely be able to find a solution. There are at least as many variables as equations.
- what if \(n > m\)? Think of a wide matrix. There are a couple of redundant columns. So everything in \(\mathbb{R}^n\) will be covered more than once. In other words, we won't be able to find a unique solution for the system of equations. The system is "under-determined"
if \(rank(A)=n\), then the linear map is injective or "one-to-one". If there is a solution to the system of equations, then it will be unique.
- if \(m>n\): Think of a narrow matrix. The solution to the system of equations lies in \(\mathbb{R}^m\), but our column space only covers a \(\mathbb{R}^n\) dimensional space. So there may not be a solution, if one doesn't lie in that space. There are more equations than unknowns. The system is "over-determined"

Let \(A\) be an \(m \times n\) matrix
First, we show that the null space of \(A\) is the same as the null space of \(A^TA\)
- Note that \(Ax = 0 \Rightarrow A^TAx = 0\)
- Note that \(A^TAx = 0 \Rightarrow x^TA^TAx = 0\)
Next, we show that \(rank(A)=m\) iff \(A^TA\) is invertible
- if \(rank(A)=m\) then \(A\) is full column-rank. That is, \(A\) is a one-to-one, i.e., injective, mapping from \(m\) -length vectors to \(n\) -length vector. Then, say that \(A^TA\) is not invertible. Then, there is some \(x\neq 0\) such that \(A^TAx = 0\). But then \(x\) is in the null-space of \(A\). But, \(A\) is a one-to-one linear map. So the only thing that it maps to the zero \(n\) -vector should be the zero \(m\) -vector.
- Assume \(A^TA\) is invertible. Say that A is not full column-rank. Then there is \(x\neq 0\) such that \(Ax=0\). Then \(A^TAx=0\), so \(A^TA\) is not invertible.

1. see also