9.3. Rank from the SVD

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 Vector Spaces. 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.

rank from the singular values theorem

Theorem 9.2 (Rank from the singular values)

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 \(r = \text{rank}(\mathbf{A})\) singular values are positive values, and singular values \(r+1\) to \(p = \min\{m, n\}\) are zero or near zero.

Proof. Any linearly dependent rows and columns of \(\bf{A}\) are also linearly dependent in \(\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 (Finding Eigenvalues). Likewise, if \(\bf{A}\) is singular, \(\mathbf{A}^T \mathbf{A}\) is singular and will have \(n-r\) zero-valued eigenvalues. Recall that the singular values come from the eigenvalues of \(\mathbf{A}^T \mathbf{A}\).

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

\[\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\]

\(\qed\)

We start with a full rank \(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