# python - Get solution to overdetermined linear homogeneous system numpy

I'm trying to find the solution to overdetermined linear homogeneous system (Ax = 0) using numpy in order to get the least linear squares solution for a linear regression.

This is the code I am using to generate the linear regression:

``N = 100x_data = np.linspace(0, N-1, N)m = +5n = -5y_model = m*x_data + ny_noise = y_model + np.random.normal(0, +5, N)``

I want to recover m and n from y_noise. In other words, I want to resolve the homogeneous system (Ax = 0) where "x = (m, n)" and "A = (x_data | 1 | -y_noise)". So I convert non-homogeneous (Ax = y) into homogeneous (Ax = 0) using this code:

``A = np.array(np.vstack((x_data, np.ones(N), -y_noise)).T)``

I know I could resolve non-homogeneous system using np.linalg.lstsq((x_data | 1), y_noise)) but I want to get the solution for homogeneous system. I am finding a problem with this function as it only returns the trivial solution (x = 0):

``x = np.linalg.lstsq(A, np.zeros(N)) => array([ 0., 0., 0.])``

I was thinking about using eigenvectors to get the solution but it seems not to work:

``A_T_A = np.dot(A.T, A)eigen_values, eigen_vectors = np.linalg.eig(A_T_A)# eigenvectors[[ -2.03500000e-01 4.89890000e+00 5.31170000e+00][ -3.10000000e-03 1.02230000e+00 -2.64330000e+01][ 1.00000000e+00 1.00000000e+00 1.00000000e+00]]# eigenvectors normalized[[ -0.98365497700 -4.744666220 1.0] # (m1, n1, 1)[ 0.00304878118 0.210130914 1.0] # (m2, n2, 1)[ 25.7752417000 -5.132910010 1.0]] # (m3, n3, 1)``

Which none of them fits model parameters (m=+5, n=-5)

How can I find (m, n) correctly? Thanks!

I have already found how to fix it, the problem is how I was interpreting the output of np.linalg.eig function, but the approach using eigenvectors is right. In spite of that, @Stelios is in the right when he says that the function np.linalg.lstsq returns the trivial solution (x = 0) because matrix A is full column rank.

I was assuming the output of np.linalg.eig was:

``````[[m1 n1  1]
[m2 n2  1]
[m3 n3  1]]
``````

But it is not, the correct format is:

``````[[m1 m2 m3]
[n1 n2 n3]
[ 1  1  1]]
``````

So if we want to get the solution which better fits model paramaters (m, n), we have to choose the eigenvector with the smallest eigenvalue and normalize it:

``````A_T_A = np.dot(A_homo.T, A_homo)
eigen_values, eigen_vectors = np.linalg.eig(A_T_A)
# eigenvectors
[[  1.96409304e-01   9.48763118e-01  -2.47531678e-01]
[  2.94608003e-04   2.52391765e-01   9.67625088e-01]
[ -9.80521952e-01   1.90123494e-01  -4.92925776e-02]]
# MIN eigenvector
eigen_vector_min = eigen_vectors[:, np.argmin(eigen_values)]
[-0.24753168  0.96762509 -0.04929258]
# MIN eigenvector normalized
[  5.02168258 -19.63023915   1.        ]   # [m, n, 1]
``````

Finally we get that m = 5.02 and n = -19,6 which is a pretty good approximation.