.. _fund-subspaces:

Fundamental Matrix Subspaces
============================

There are four fundamental subspaces of an :math:`m{\times}n` matrix.
The subspaces are found from rank-determined regions of the SVD factors.
The regions are identified in figure :numref:`fig-svdsubspaces` as the
Column Space (:math:`\mathbf{\tilde{U}}`), Left Null Space
(:math:`\mathbf{U}_{null}`), Row Space (:math:`\mathbf{\tilde{V}}^T`),
and Null Space (:math:`\mathbf{V}_{null}^T`).

.. _fig-svdsubspaces:

.. figure:: nullSVD.png
   :figclass: center-caption
   :align: center
   :width: 60%
   :alt: The columns of U and rows of V transpose from the SVD constitute the four fundamental matrix subspaces of the matrix. The subspace that a row or column is part of is determined by whether it is multiplied by a nonzero or zero singular value.

   The columns of :math:`\bf{U}` and rows of :math:`\mathbf{V}^T` from the SVD
   constitute the four fundamental matrix subspaces of the matrix. The subspace
   that a row or column is part of is determined by whether it is multiplied by
   a nonzero or zero singular value.

If we consider the SVD of a singular system as :math:`\mathbf{A\, V} =
\mathbf{U\,\Sigma}`, then we can divide the :math:`\bf{V}`,
:math:`\bf{\Sigma}`, and :math:`\bf{U}` matrices into blocks related to
the nonzero and zero-valued singular values.

.. math::
   :label: eq-svdsubspaces

   \begin{aligned}
           &\mathbf{A}\,\begin{bmatrix}
                           \tilde{\mathbf{V}}  & \mathbf{V}_{null}
                        \end{bmatrix} = 
   \begin{bmatrix}
      \tilde{\mathbf{U}}  & \mathbf{U}_{null}
   \end{bmatrix}\, 
   \begin{bmatrix}
      \mathbf{\Sigma}  \\ 
      \mathbf{0} 
   \end{bmatrix} \\
           &\mathbf{A}\,\tilde{\mathbf{V}} = 
   \tilde{\mathbf{U}}\,\mathbf{\Sigma}, \quad \text{and} \quad
   \mathbf{A}\,\mathbf{V}_{null} = 
   \mathbf{U}_{null}\,\mathbf{0} = \mathbf{0}
   \end{aligned}

.. _colspace:

Column Space
------------

The *column space* (:math:`\mathbf{\tilde{U}}`) of a matrix
:math:`\bf{A}`, which we denote as :math:`\text{Col}( \bf{A} )`, is the
vector space spanned by the independent columns of :math:`\bf{A}`. It is
the first :math:`r` columns of :math:`\bf{U}`, and includes all columns
of :math:`\bf{U}` if :math:`\bf{A}` is square and full rank. The column
space from :math:`\bf{U}` forms a set of basis vectors for the columns
of :math:`\bf{A}`. However, :ref:`OrthBasis` lists other algorithms
for finding orthogonal basis vectors.

.. topic:: Rank and Column Space Dimension

   The *rank* of the matrix is the same as the dimension of the column
   space, which is the number of basis vectors in the column space.

When there is an exact solution to the equation
:math:`\mathbf{A}\,\bm{x} =
\bm{b}`, we say that :math:`\bm{b}` is “*in the column space of*
:math:`\bf{A}`” because it is a linear combination of the independent
columns of :math:`\bf{A}`. The vector :math:`\bm{x}` tells us the
coefficients for the linear combination of the columns needed to get to
:math:`\bm{b}`.

Here is a singular matrix example showing that the independent columns
of :math:`\bf{A}` are in the vector space of the basis vectors. The
first two columns of :math:`\bf{U}` and :math:`\bf{A}` are in the same
column space because the rank of the :math:`3{\times}4` augmented matrix
is still two.

::

    In [1]: import numpy as np

    In [2]: from scipy.linalg import svd

    # A is random 3-by-3
    In [3]: A = 5*np.random.rand(3, 3)

    In [4]: A[:,[2]] = A[:,[0]] - A[:,[1]]

    In [5]: np.linalg.matrix_rank(A)
    Out[5]: np.int64(2)

    In [6]: U,_,_ = svd(A)

    In [7]: np.linalg.matrix_rank(np.hstack((U[:,:2], A[:,:2])))
    Out[7]: np.int64(2)

.. index:: rank
.. index:: column space

.. _nullSpace:

Null Space
----------

.. index:: null

Columns :math:`r+1` to :math:`n` of :math:`\mathbf{V}` form the *null
space* (right null space) (:math:`\mathbf{V}_{null}^T` in figure
:numref:`fig-svdsubspaces`) of a matrix :math:`\bf{A}`, which we
denote as :math:`\text{Null}( \bf{A} )`. It is the vector space spanned
by all column vectors :math:`\bm{x}` that satisfy the matrix equation
:math:`\mathbf{A}\,\bm{x} = \bm{0}`, which is called the null solution.
As mentioned in :ref:`row-col-view`, the only square systems with a
null solution are singular. Singular square matrices and
under-determined matrices have a null space. The number of vectors in
the null space is the number of dependent columns
(``size(A, 2) - rank(A)``). If :math:`\bf{A}` is a square full-rank
matrix, then the null space is an empty set.

Finding the null space from elimination is covered in
:ref:`findEigvector`. But MATLAB’s ``null`` function returns the null
space from the SVD.

.. index:: null space from the SVD

.. _th-nullSVD: 

.. rubric:: Null space from the SVD

.. prf:theorem::  Null space from the SVD
   :label: th-nullSVD

   Let :math:`\mathbf{A} \in \mathbb{R}^{n{\times}n}` be singular with
   :math:`r = \text{rank}(\mathbf{A}) < n`. Each of the last :math:`n-r`
   columns of :math:`\bf{V}` are null solutions of :math:`\bf{A}`,
   :math:`\mathbf{A}\,\bm{v}_i = \bm{0}`.

.. prf:proof::

   Let the SVD of a singular system be
   :math:`\mathbf{A\, V} = \mathbf{U\,\Sigma}`. As equation
   :eq:`eq-svdsubspaces` shows, we can split the :math:`\bf{V}`,
   :math:`\bf{\Sigma}`, and :math:`\bf{U}` matrices into blocks related
   to nonzero and zero-valued singular values.

   The last :math:`n - r` columns of :math:`\bf{V}` is the null solution
   because :math:`\mathbf{A}\,\mathbf{V}_{null} = \mathbf{0}`.

   :math:`\qed`

MATLAB’s ``null`` function compares the singular values to a threshold
to decide if and how many columns of :math:`\bf{V}` constitute the null
space. However, determining if a matrix is singular, or just close to
singular, is sometimes vague. The ``null`` function will sometimes not
return a solution for nearly singular matrices. In these cases, the SVD
can be used to find the borderline null solution. 

.. index:: null

::

    In [16]: from scipy.linalg import svd, null_space

    In [17]: np.linalg.matrix_rank(A)
    Out[17]: np.int64(2)

    # A is 3-by-3 with rank = 2
    In [18]: _,_,Vt = svd(A)

    In [19]: V = Vt.T  # V, not V transpose

    In [20]: x = V[:,[2]] # null_space(A)

    In [21]: A @ x
    Out[21]: 
    array([[-0.],
           [-0.],
           [ 0.]])

    In [22]: null_space(A) - x
    Out[22]: 
    array([[0.],
           [0.],
           [0.]])

The null space of an under-determined matrix is at least (:math:`m-n`)
columns. Remember from :ref:`underdetermined` that under-determined
systems have an infinite number of solutions. The RREF expresses the
solution in terms of the general and particular solutions, while the
null space from the SVD is the least squares solution. Although the
solutions are different, they are both correct.

::

    In [27]: A = 5*np.random.rand(3, 5) - 2

    In [28]: _,_,Vt = svd(A)

    In [29]: V = Vt.T

    In [30]: nullA = V[:, 3:] # Null space = last 2 columns

    In [31]: A @ nullA
    Out[31]: 
    array([[ 0., -0.],
           [ 0., -0.],
           [-0., -0.]])

.. index:: right null space
.. index:: null space

Row Space
---------

The *row space* (:math:`\mathbf{\tilde{V}}^T`) of a matrix
:math:`\bf{A}`, which we denote as :math:`\text{Row}( \bf{A} )`, is the
column space of :math:`\mathbf{A}^T`. It is the first :math:`r` columns
of :math:`\bf{V}` from the SVD.

.. index:: row space

Left Null Space
---------------

The *left null space* (:math:`\mathbf{U}_{null}`) of a matrix
:math:`\bf{A}` are the set of row vectors, :math:`\bf{Y}`, that satisfy
the relationship :math:`\bf{Y\,A} = \bm{0}`. It is the transpose of
columns :math:`r+1` to :math:`m` of :math:`\bf{U}`. It is also the right
null space of :math:`\mathbf{A}^T`, and it is common to compute it from
:math:`\mathbf{A}^T`, ``Y = null_space(A.T).T``. The left null space exists for
singular and over-determined matrices.

.. index:: left null space

Orthogonality of Spaces
-----------------------

The four fundamental vector subspaces form interesting orthogonality
relationships, which is expected since they are subsets of the
orthogonal matrices :math:`\bf{U}` and :math:`\bf{V}`. Vectors in the
null space are orthogonal to vectors in the row space. Similarly,
vectors in the column space are orthogonal to vectors in the left null
space.

.. index:: orthogonal matrix subspaces