Vamos considerar um sistema linear na forma matricial: $$ \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \vdots & \vdots \\ a_{k1} & \cdots & a_{kn} \end{pmatrix}\begin{pmatrix}x_1 \\ \vdots \\ x_n \end{pmatrix}=\begin{pmatrix}y_1 \\ \vdots \\ y_k \end{pmatrix}$$ com $k>n$.
O posto máximo da matriz $A$ é então $n$. Quer dizer a imagem da matriz $A$ é gerada pelas colunas de $A$. Observe que podemos escrever o produto acima como: $$ x_1 \begin{pmatrix}a_{11} \\ a_{21} \\ \vdots \\ a_{k1} \end{pmatrix} + \cdots +x_n\begin{pmatrix} a_{1n} \\ a_{2n} \\ \vdots \\ a_{kn}\end{pmatrix} = \begin{pmatrix}y_1 \\ y_2 \\ \vdots \\ y_k \end{pmatrix} $$ então variando os números $x_1,\dots, x_n$ obtemos, no máximo, um subespaço de dimensão $n$ em $\mathbb{R}^k$. A única forma de encontrarmos uma solução do sistema é se o vetor $\mathbf{y}$ está no subespaço de dimensão $n$ mencionado. E se as colunas da matriz $A$ forem linearmente independentes a solução será única!
Seja $A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix}$ o sistema $$ A\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \\ -1 \end{pmatrix}$$ tem uma única solução $(x,y)=(2,-1)$. enquanto o sistema $$ A\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \\ 0 \end{pmatrix}$$ não tem solução.
Podemos aumentar o conceito de solução do sistema sobredeterminado, de forma a incluir o caso em que ele tem uma solução explícita. Dizemos que $\mathbf{x}\in \mathbb{R}^n$ é solução do sistema sobredeterminado, $A\mathbf{x}=\mathbf{y}$, se $A\mathbf{x}$ for o elemento do espaço vetorial gerado pelas colunas de $A$ que esteja mais próximo de $\mathbf{y}$. E para medir a distância usamos: $$\|A\mathbf{x} -\mathbf{y}\|^2 = \langle A\mathbf{x} -\mathbf{y},A\mathbf{x} -\mathbf{y}\rangle $$ Para facilitar a notação, vamos denotar as colunas da matriz $A$ como $\mathbf{a}_i$, com $i\in \{1,\dots,n\}$. A solução do sistema sobredeterminada é a projeção ortogonal de $\mathbf{y}$ no na imagem de $A$, e portanto se escreve $x_1\mathbf{a}_1+ \cdots + x_n\mathbf{a}_n =\sum_{i=1}^n x_i\mathbf{a}_i$.
Por ser projeção ortogonal devemos ter que $\mathbf{y}-\sum_{i=1}^nx_i\mathbf{a}_i$ é ortogonal a cada $\mathbf{a}_j$ para $j$ de $1$ a $n$. Assim devem estar satisfeitas as seguintes equações: $$ \langle \mathbf{y}-\sum_{i=1}^nx_i\mathbf{a}_i, \mathbf{a}_j \rangle =0 $$ e usando a bilinearidade do produto escalar temos: $$ \sum_{i=1}^n x_i \langle, \mathbf{a}_i,\mathbf{a}_j\rangle = \langle \mathbf{y},\mathbf{a}_j \rangle $$ Este sistema linear é conhecido como o sistema normal do sistema sobredeterminado, e assim vemos a relação com o Método dos mínimos quadrados.
Exemplo: vamos encontrar o sistema normal dos sistemas do exemplo anterior. Como a matriz $A$ nos dois casos é $A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix}$, temos que a matriz de coeficientes do sistema normal é: $$ N = \begin{pmatrix}2 & 1 \\ 1 & 2 \end{pmatrix} $$ No primeiro caso o sistema normal é $$\begin{pmatrix}2 & 1 \\ 1 & 2 \end{pmatrix}\begin{pmatrix}x_1 \\ x_2 \end{pmatrix}=\begin{pmatrix} 3 \\ 0 \end{pmatrix}$$ e no segundo caso: $$\begin{pmatrix}2 & 1 \\ 1 & 2 \end{pmatrix}\begin{pmatrix}x_1 \\ x_2 \end{pmatrix}=\begin{pmatrix} 3 \\ 1 \end{pmatrix}$$
import numpy as np
def SistemaNormal(A,y):
'''Retorna os parametros do sistema normal de um sistema sobredeterminado.'''
k,n = np.shape(A)
N = np.array([[sum(A.T[i]*A.T[j]) for j in range(n)] for i in range(n)])
b = np.array([sum(A.T[i]*y) for i in range(n)])
return N,b
#teste
A=np.array([[1,2,3,4,5],[2,3,4,5,6],[3,4,5,0,0]]).T
y=np.array([1,0,1,0,1])
N,u = SistemaNormal(A,y)
N
array([[55, 70, 26], [70, 90, 38], [26, 38, 50]])
u
array([ 9, 12, 8])