2.11. Over-determined Systems and Vector Projections

The over-determined matrix equation of the form \(\mathbf{A}\,\bm{x} = \bm{b}\) has more equations than unknown variables (\(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 \(\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 \(\bm{b}\) is in the column space (span) of \(\bf{A}\). But otherwise, we can only approximate the solution.

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

When \(\bm{b}\) is not in the column space of \(\bf{A}\), the only solution available is an approximation. In the following example, we use the rank test and see that \(\bm{b}\) is in the column space of \(\bf{A}\). Then, after a change to the \(\bf{A}\) matrix, we see from the rank test that \(\bm{b}\) is no longer in the column space of \(\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.