.. _projection:

Over-determined Systems and Vector Projections
==============================================

The *over-determined* matrix equation of the form
:math:`\mathbf{A}\,\bm{x} = \bm{b}` has more equations than unknown
variables (:math:`m > n`). A common situation where an over-determined
system occurs is in the result of an experiment. The experiment may be
repeated many times as a control variable is adjusted. Thus, a
researcher may have many more equations relating the inputs to the
outputs than unknown variables.

It is required that :math:`\text{rank}(\mathbf{A}) = n` to find a
solution. A unique solution exists when all row equations are
consistent, which we formally describe as when :math:`\bm{b}` is *in the
column space* (span) of :math:`\bf{A}`. But otherwise, we can only
approximate the solution.

We can test if :math:`\bm{b}` is in the column space of :math:`\bf{A}`
by comparing the rank of the augmented matrix of both :math:`\bf{A}` and
:math:`\bm{b}` to the rank of :math:`\bf{A}`,
:math:`\text{rank}([\mathbf{A}\;\bm{b}]) = \text{rank}(\bf{A})`. If the
rank of the augmented matrix and :math:`\bf{A}` are the same, then
:math:`\bm{b}` is in the column space of :math:`\bf{A}`.

When :math:`\bm{b}` is *not* in the column space of :math:`\bf{A}`, the
only solution available is an approximation. In the following example,
we use the rank test and see that :math:`\bm{b}` is in the column space
of :math:`\bf{A}`. Then, after a change to the :math:`\bf{A}` matrix, we
see from the rank test that :math:`\bm{b}` is no longer in the column
space of :math:`\bf{A}`

::

    In [1]: import numpy as np

    In [2]: A = np.array([[5, 3], [6, -3], [-2, -1], [6, 2]]); print(A)
    [[ 5  3]
     [ 6 -3]
     [-2 -1]
     [ 6  2]]

    In [3]: b
    Out[3]: array([ 7, 15, -3, 10])

    In [4]: b = np.array([[7, 15, -3, 10]]).T; print(b)
    [[ 7]
     [15]
     [-3]
     [10]]

    # Rank test: 
    # b is in the column space of A
    In [5]: np.linalg.matrix_rank(np.hstack((A, b)))
    Out[5]: np.int64(2)

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

::

    # Change A
    In [12]: A[3,:] = np.array([[5, 1]]); print(A)
    [[ 5  3]
     [ 6 -3]
     [-2 -1]
     [ 5  1]]

    # Rank test: 
    # b is not in the column space of A
    In [13]: np.linalg.matrix_rank(np.hstack((A, b)))
    Out[13]: np.int64(3)

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

We can find the approximation solution by *projection*, or from the QR
decomposition.

.. index:: over-determined
.. index:: over-determined systems
.. index:: column space

.. toctree::
   :maxdepth: 2

   projectR2
   projectR3