Removing unsolvable equations from an underdetermined system

Question

My program tries to solve a system of linear equations. In order to do that, it assembles matrix coeff_matrix and vector value_vector, and uses Eigen to solve them like:

Eigen::VectorXd sol_vector = coeff_matrix
        .colPivHouseholderQr().solve(value_vector);

The problem is that the system can be both over- and under-determined. In the former case, Eigen either gives a correct or uncorrect solution, and I check the solution using coeff_matrix * sol_vector - value_vector.

However, please consider the following system of equations:

a + b - c     =  0
        c - d =  0
        c     = 11
      - c + d =  0

In this particular case, Eigen solves the three latter equations correctly but also gives solutions for a and b.

What I would like to achieve is that only the equations which have only one solution would be solved, and the remaining ones (the first equation here) would be retained in the system.

In other words, I'm looking for a method to find out which equations can be solved in a given system of equations at the time, and which cannot because there will be more than one solution.

Could you suggest any good way of achieving that?

Edit: please note that in most cases the matrix won't be square. I've added one more row here just to note that over-determination can happen too.

Answer 1

I think what you want to is the singular value decomposition (SVD), which will give you exact what you want. After SVD, "the equations which have only one solution will be solved", and the solution is pseudoinverse. It will also give you the null space (where infinite solutions come from) and left null space (where inconsistency comes from, i.e. no solution).

Answer 2

Based on the SVD comment, I was able to do something like this:

Eigen::FullPivLU<Eigen::MatrixXd> lu = coeff_matrix.fullPivLu();

Eigen::VectorXd sol_vector = lu.solve(value_vector);
Eigen::VectorXd null_vector = lu.kernel().rowwise().sum();

AFAICS, the null_vector rows corresponding to single solutions are 0s while the ones corresponding to non-determinate solutions are 1s. I can reproduce this throughout all my examples with the default treshold Eigen has.

However, I'm not sure if I'm doing something correct or just noticed a random pattern.