.. _SVDrank:

Rank from the SVD
=================

.. index:: rank

There are multiple ways to compute the rank of a matrix. An example of
using Gaussian elimination to find the rank of a matrix is shown in
:ref:`rank`. The MATLAB ``rank`` function uses the SVD. According to
the MATLAB documentation, the SVD algorithm requires more computation
than some alternatives, but it is the most reliable.

.. index::  rank from the singular values theorem

.. _th-rankSVD:

.. rubric::  rank from the singular values theorem

.. prf:theorem::  Rank from the singular values
   :label: th-rankSVD

   The number of singular values greater than a small tolerance is the
   rank of the matrix. As previously noted, the singular values are
   ordered. The first :math:`r = \text{rank}(\mathbf{A})` singular
   values are positive values, and singular values :math:`r+1` to
   :math:`p = \min\{m, n\}` are zero or near zero.

.. prf:proof::

   Any linearly dependent rows and columns of :math:`\bf{A}` are also
   linearly dependent in :math:`\mathbf{A}^T \mathbf{A}`. The
   eigenvalues are the shift to the diagonal of a matrix needed to make
   it singular. So a singular matrix will have at least one zero-valued
   eigenvalue (:ref:`find-eigvals`). Likewise, if :math:`\bf{A}` is
   singular, :math:`\mathbf{A}^T \mathbf{A}` is singular and will have
   :math:`n-r` zero-valued eigenvalues.
   Recall that the singular values come from the eigenvalues of
   :math:`\mathbf{A}^T \mathbf{A}`.

   We can see why a rank-deficient matrix must have singular values near
   zero by reforming :math:`\bf{A}` from its factors using outer
   products (:ref:`outerProd`). Dependent rows and columns of
   :math:`\bf{A}` do not add new information to the matrix, so the
   matrix is complete with the sum of :math:`r` rank-1 outer products.
   Only the columns of :math:`\bf{U}` and rows of :math:`\mathbf{V}^T`
   that are multiplied by nonzero singular values contribute to the
   final values of the matrix.

   .. math::

      \mathbf{A} = \sum_{i=1}^{r} \sigma_i\,\bm{u}_i\,\bm{v}_i^T + 
      \sum_{i = r+1}^p (\sigma_i = 0)\,\bm{u}_i\,\bm{v}_i^T

   :math:`\qed`

We start with a full rank :math:`3{\times}3` matrix in the following
example and reduce the rank by one. The final singular value is near
zero, so the rank is 2.

::

   >> A(3,:) = A(1,:) - A(2,:);
   >> rank(A)
   ans =
        2 
   >> svd(A)
   ans =
      11.1167
       6.3576
       0.0000

   >> fprintf("%g\n", ans(3))
   1.32734e-15