Rank

Wow -- this is -very- in depth!
Key points:
- rank/nullity
- various definitions of rank
  (and row rank = column rank is essentially rank/nullity)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The rank $k$ of a linear transform $T\from V \to W$ is:
- the dimension of the image
- the codimension of the kernel [for finite dimensions!]
  [these are equal by rank-nullity]
- the minimum $k$ s.t. $T$ factors as $T\from V \to U \to W$,
  where $\dim U = k$ (equiv, $U=F^k$)
[Equivalent b/c $V \to \im T < W$ is such a minimal one.
 ("such a" means first dim >= second dim;
  minimal means first <= second, which is by universal property
  of image)]
- viewing $\Hom(V,W)=V^* \otimes W$, it's the minimum number of
  $v\otimes w$ needed to express $T$ as a sum.
  [follows from matrix expression below]
  [more abstractly, take a basis $w_i$ for the image and
   pull it back to $v_i$. Let $v^*_i$ be dual vectors
   (yeah, only defined up to elements of $\ker T$ but don't care).
   so $T=\sum v^*_i \otimes w_i$: it takes $v_i$ to $w_i$
   and kills other stuff.
   conversely, given $T=\sum v^*_i \otimes w_i$, the $w_i$
   span the image and thus are at least the rank]

For an $m \times n$ matrix $M$, it's:
- (column rank) max number of linearly independent columns
    [or min number of spanning columns]
- (row rank) max number of linearly independent rows
    [or min number of spanning rows]
- (factorization rank)
  the minimum $k$ s.t. $M$ factors as $M=AB$,
  where $A$ is $m \times k$ and $B$ is $k \times n$.
  That is: if $M$ has row rank $k$, then its row-space has dimension
  $k$. Choose a basis for this, and let that be $B$, and then
  the rows of $A$ are the coordinates of the columns of $M$ in the
  basis given by the rows of $B$.
  Analogously for columns.
- (minor rank)
  the maximum $k$ s.t. M has a non-vanishing k-minor
  i.e., a $k \times k$ submatrix whose determinant doesn't vanish.
  Note that this is symmetric: obviously
    minor rank M = minor rank $M^t$
  Clearly minor rank is at most row rank or column rank;
  the hard part is that they're equal. See below for why.
  
Why are these (transform and matrix) the same?
- column rank is obviously rank in terms of image
- row rank is obviously codim kernel
  (each independent row cuts kernel dimension by 1)
- the factorization rank is obviously the same in both cases

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Column space = image $T$
Row space = image $T^t$
  (abstractly $T^*$, but we've written a basis)
Transposition of matrices is easily interpreted;
what it means geometrically is subtle -- it's the adjoint in a
basis.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Theorems:
- rank/nullity
  dim image = codim kernel
  (equiv., given $T\from V \to W$,
   $\rank T + \nullity T := \dim \Im T + \dim \ker T = \dim V$)
  The easiest way to prove rank/nullity is to classify transforms:
  pick basis for image [extend to basis of $W$], pull back to $V$
  and extend to basis of $V$.
  In these bases, $T$ has the standard form.
  Alternatively (instead of lifting a basis), pick a basis for the
  kernel, extend to basis of $V$, then push forward to $W$.
  The kernel stuff dies, and the rest maps to a basis of image.

  More deeply, it says: given $T\from V \to W$, look at
  the ses:
  $$0 \to \ker T \to V \to \im T \to 0$$
  Now either:
  - pick a splitting $\phi\from \im T \to V$
    [exists b/c vector spaces are free, hence projective]
    and show $\phi \im T \oplus \ker T$ is a decomposition
  - pick a complimentary subspace $V'$ s.t.
    $V = \ker T \oplus V'$
    and show $V'$ maps iso to $\im T$
  [these parallel the above POVs]
  This is b/c:
  - $\im T = V/\ker T$
  - and $V/W \cong W'$ for any complimentary subspace $W'$
    (so $V = W \oplus W'$)
  
  most categorically, image = coker(ker)
  and given $U \from V \to W$:
  - codim ker = dim image
  - dim coker = codim image
  so dim image U = codim (image ker U) = codim U
  [but this is just a statement: the proof is as above]

- row rank = column rank
  Note that this is a priori a statement about -matrices-, not about
  -transforms-.
  
  The deep abstract reason this is true is b/c
  $\rank T = \rank T^*$.
  
  This is b/c
  $\ker T^* = \Ann \im T$,
    $\im T = \Ann \ker T^*$
  $\ker T = \Ann \im T^*$,
    $\im T^* = \Ann \ker T$
  b/c $T^*(w^*) = 0$ iff $<T^*w^*,v> := T^*(w^*)v=0$ for all $v$
    and $<T^*w^*,v> = <w^*,Tv>$ (by char of adjoint)
    so iff $w^*$ vanishes on image of $T$, i.e.,
    iff $w^*\in \Ann \im T$
  so:
  dim ker T* = codim im T
    dim im T = codim ker T*, etc.
  so rank T = dim im T = codim ker T* = dim im T* = rank T*
  by rank-nullity.

  
  In terms of matrices, it follows from the symmetry of the
  factorization rank definition.
  
  Why is this true intuitively?
  As above, it's really by rank-nullity:
  column rank = dim image
  row rank = codim kernel
  rank-nullity -- they're the same!

  Concretely:
  [The key case is showing that $k$ columns are linearly independent
   iff $k$ rows are, in an $m \times k$ matrix (full rank).]
  
  Given $k$ columns, for them to be linearly independent you need at
  least $k$ -different- coordinates.
  That is, if there's no linear dependence between the columns, then
  ker = 0 -- but need k linearly independent rows/equations to do
  this: codim ker = row rank. Now apply rank-nullity.
  
  Why is this complicated?
  Suppose rank M = k, and the top k rows and left k columns of M are
  linearly independent.
  Then there's -two- natural factorizations:
 column:
  M = CB, where C is the first k columns
  and B is: $[I_k|stuff]$

 row:
  M = AR, where R is the first k rows
  and A is:
  $[I_k]
   [stuff]$
  If N is the top-left kxk submatrix
  (so
  $M=[NX]
     [YZ]$), then
  $CB = CN^{-1}NB = AR$
  In terms of factorization of the transform,
  we're picking two different bases for the $\bR^k$ in the middle:
  the column POV says "columns are a basis of image, so pick some and
  pull 'em back to $\bR^k$";
  the row POV says "rows are a basis for the image of the adjoint",
  so pick these, pull 'em back to $(\bR^k)^*$, and take the dual basis
  of $\bR^k$.
  The change of basis matrix is $N$.
  (this could be clarified further)

- minor rank = row/column rank
  if you show that the minor rank equals one of row/column rank, then
  by symmetry you show row rank = column rank -- but this statement is
  a bit stronger.
  That is, a non-vanishing k-minor gives k indep rows and k indep
  columns, but the k-minor defined by k indep rows and k indep columns
  -need not- be non-vanishing:
  1 0
  0 1
  the first column is non-zero, and the second row is non-zero, but
  the minor they define is 0.

  This is actually what we showed above: if k columns are linearly
  independent, then k -of their rows- are linearly independent,
  [as opposed to k rows in some bigger ambient matrix]
  so -this minor- is non-vanishing.
