System of homogeneous linear equations: Ax=0 with Det(A)=0


(Vladimir) #1

Hello!

I am trying to solve a systems of homogeneous linear equations like Ax=0.

Here is an example matrix which has already been reduced for simplicity:

1 2 | 0
3 6 | 0

The solution I am hoping to get to is at least [ 2, -1 ].
But the fundamental solution is folow: [2C; -1C].
You can see than Det(A)=0 and Rank(A) =1;
Of course you are know that such systems have trivial solution [0,0].

I am trying:

Matrix<double> A = Matrix<double>.Build.DenseOfArray(new double[,] {
    { 1, 2 }, 
    { 3, 6 }, 
});
Vector<double> B = Vector<double>.Build.Dense(new double[] { 0, 0 });

var result = A.Solve(B); //result = Nan, Nan

Please help me find solution for such tasks by MathNet, because in real task the dimention of A more than 20.

The solving for this problem: Math.Net system of linear equations with a 0 value in solution doesnt work for my situation.

Thanks


(Peter Vanderwaart) #2

You can use Matrix.PseudoInverse to avoid getting Nans. Solving with the pseudo inverse will get you the solution with the shortest solution vector, which for a homogeneous systems will be the all-zero solution. As usual,Wikipedia knows all even if not explained at the beginner level.

To get a non-zero solution, you have to add an additional criterion. Possibly the easiest thing to do is to set the value of one variable by adding a row (and column) to your matrix. So for your example, set x[1]=1 like this:

        Matrix<double> A = Matrix<double>.Build.DenseOfArray(new double[,] {
        { 1, 2, 0 },
        { 3, 6, 0 },
        { 1, 0, 0 },
        });
        Vector<double> B = Vector<double>.Build.Dense(new double[] { 0.0, 0.0, 1.0 });

        var pi = A.PseudoInverse();
        var rslt = pi * B;

This returns the solution (when rounded) of x[1] = 1, x[2] = -0.5, x[3] = 0.

If your matrix is comprised of independent blocks of variables, you will have to choose a value for each block, or you will get zero solutions for some blocks. If they are all interconnected, you will only have to set one.

Edit: changed variable name (c => x) for consistency.


(Vladimir) #3

@PVanderwaart thank you. I am going to try your idea


(Peter Vanderwaart) #4

Good luck.

Let me add the following for completeness even though they may be obvious: 1) The new bottom row can have non-zero values in more than one of the columns. Just leave the new, added column as zero. 2) Once you have a solution, you can multiply it by any scalar to get a different solution. 3) The two computation steps can be combined: var result = A.PseudoInverse()*B;


(Vladimir) #5

@PVanderwaart thank you. It works for this example. Now i have to test it for my real data.


(Vladimir) #6

@PVanderwaart Your add №1 is not obvious for me ). I tested it. It works. Thank you


(wo80) #7

The PseudoInverse uses SVD internally. You could take advantage of the SVD directly, see https://math.stackexchange.com/questions/1771013/null-space-from-svd:

var svd = A.Svd();

int rank = svd.Rank;

// Get a basis of the range of A.
var range = svd.U.EnumerateColumns().Take(rank);

// Get a basis of the nullspace of A.
var nullspace = svd.VT.EnumerateRows().Skip(rank);