Dear Morteza,

I suggest you to see links and attached files on topic.

Basic concepts in Linear Algebra and Optimization

stanford.edu › ~yinbin › TEACHING › Optimization

A matrix nullspace approach for solving equality ... - eLib - DLR

https://elib.dlr.de › 1-s2.0-S0005109814004208-main....

A Null-Space-based Technique for the Estimation of Linear-Time ...

https://www.sciencedirect.com › science › article › pii

An efficient algorithm for sparse null space basis problem using ...

https://www.researchgate.net › publication › 25763461...

t - Mathematics

https://www.math.uwaterloo.ca › ~tfcolema › articles

Best regards

Your first failure is due to the fact that a null vector x is an obvious solution of the equation Ax=0. Your program very correctly goes for that (smart)!

Your second problem is that sum of all the oefficients of the null vectors is a very inadequate quantity to maximize or even just to consider; for example, a legitimate null-space vector could have large components of opposite signs summing to zero and then you would never find it. That is why the program deems the problem unbounded (very smart).

The proper way is to keep at all times all the null-space vectors individually normalized. Indeed, what you want is the solution of Ax=0 with a NORMALIZED x, not with a null x.

The reason your problem is infeasible is because for each column of x, the solution space is infinite. you need to fix (j-i) row of your vector x.

for example if A = [[1,2,4], [2,5,3]], the null space of this matrix is [-14x, 5x, x] where x is a real. In this problem (row num, i = 2, col num j = 3) so if for this problem you wrote:

Min x_null(3) = 1

st.

sum(j , A(i,j) * x_null (j)) = zero(i);

you get

min x_null(3) = 1

x_null(1) + 2x_null(2) + 4 = 0

2x_null(1) + 5x_null(2) + 3 = 0

in essence you're solving a square system of equations

How can I found out whether x (i.e., null space matrix) is empty or not, by using an optimization model?

Wouldn't it be easier to use Gaussian elimination?

If you have an LP solver but don't have an algorithm for Gaussian elimination, then try maximising e.x + e.x' subject to Ax - Ax' = 0, x >= 0, x' >= 0 and e.x + e x'

The null space is empty if the matrix is of full rank or if the number of linearly independent rows is equal or greater than the rank of the matrix

Adam N. Letchford Thank you for your answer. Actually, I have a simple LP tool by which I can only solve linear optimization problems and hence, the method of Gaussian elimination is not possible to use.

Adam N. Letchford I implemented your proposed LP model in MATLAB using linprog() function as below.

.

%% Null space finding:

A =...

[1 2 4

2 5 3];

% Solution:

% In MATLAB --> We can use null(A) or null(A,'r') =>

% x = ...... or ...... x =

% -0.9396 ....... -14

% 0.3356 ....... 5

% 0.0671 ....... 1

% ----------------------------------------------------------

.

% To find x_null by using an LP model (and not using Gaussian or null(A)):

% Note: Dimensions --> A(2*3) , e = ones(2,3) , x_null(3*1)

.

% Objective function --> Max f = e.x + e.x'

f = (-1)*0.5 * [1 ; 1 ; 1 ; 1 ; 1 ; 1]; % Making Max. by (-1)

.

% Constraint 1 --> e.x + e x' Ax - Ax' = 0

Aeq = [1 2 4 -1 -2 -4

2 5 3 -2 -5 -3];

beq = [0 ; 0];

.

% Constraint 3 --> x >= 0, x' >= 0

% (But, as can be seen in Solution above, the elements of x_null are not always positive!)

lb = [0 ; 0 ; 0 ; 0 ; 0 ; 0];

% lb = [-inf ; -inf ; -inf ; -inf ; -inf ; -inf];

ub = [inf ; inf ; inf ; inf ; inf ; inf];

.

[x , fmax] = linprog(f,A,b,Aeq,beq,lb,ub)

=> Result:

x = [x ; x']

0.1667

0.1667

0.1667

0.1667

0.1667

0.1667

fmax = -0.5000

Unfortunately, the obtained result is not correct.

Temitayo Bankole Thank you for your answer. I know when the null space is empty mathematically but my question is how we can recognize it using an OR model (and not by using MATLAB or Octave functions like 'null(A)' or 'rank(A)' which use Gaussian elimination or LU Factorization).

For instance, I tried to find the null space of your proposed matrix A = [[1,2,4], [2,5,3]], by the LP model proposed by Prof. Letchford. Do you have any idea to refine this initial LP model?

Mohamed-Mourad Lafifi Thank you for your papers. Could you please come up with an idea to find null space using an optimization model like the one that Prof. Letchford proposed?

Ah, yes, my previous LP had an error. Please try changing the objective function from e.x + e.x' to e.x - e.x'. This should drive the LP solution to a ray of the null space that has as many positive coefficients as possible.

Dear Morteza,

Please check the following MIP model for the same A.

1) Min Z=1

s.t.

sum(j , A(i,j) * x_null (j,m)) = zero(i,m);

x_null (j,m)=eps*(1-y(j,m))-Big_M*y(j,m);

y(j,m) is binary variable

Regards

Morteza Shabanzadeh

Oh Now i see the question

Use the formulation by Adam N. Letchford its an LP and should solve, i modified the last constraint in my example to be ex = 1.

use the link https://www.zweigmedia.com/RealWorld/simplex.html

enter the following in the space provided

Maximize p = x -x1 + y - y1 + z - z1 subject to

x - x1 + 2y - 2y1 + 4z - 4z1 = 0

2x - 2x1 + 5y - 5y1 +3z - 3z1 = 0

x + y + z = 1

set the option to fraction as in the screenshot attached. You will find a fractional solution of what i have earlier provided

You can also use Hossein Karimi formulation although i wouldnt prefer a MIP as this would grow in O(e^N) where N is the row dimension of your matrix A. Here is CPLEX OPL formulation attached, you can see that CPLEX obtains (blue arrow) the following result 14/1000, -5/1000, -1/1000, if we discard the denominators we obtain xnull = [14, -5, -1 ]

Hossein Karimi and Temitayo Bankole

Thank you for your good solutions.

However, this MILP model only works in cases in which we already know the matrix A is not full rank; because your proposed model is designed in a way to look for a none-zero solution (i.e., when we are sure that x is not null). Moreover, the parameters 'BigM' and 'eps' need to be tuned up separately in different cases which could be a tedious and time-consuming task!

On the other hand, what can we do if x might be more than one vector? For example, assume the matrix A as below:

A=[

1 3 -5 1 5

1 4 -7 3 -2

1 5 -9 5 -9

0 3 -6 2 -1

];

>> x = null(A,'r')

.

x =

-1........-1

2........-3

1.........0

0.........5

0.........1

In this case, x contains two column-wise vectors. I implemented the LP model proposed by Adam N. Letchford, it works well but unfortunately, it can only obtain one of these two independent vectors! I think this model needs to be developed a little more to be able to recognize and distinguish such linearly independent vectors.

Temitayo Bankole, could you please test the example above by your CPLEX code?

Hi Morteza Shabanzadeh LPs are only meant to return one solution of course, the only you can obtain multiple solution is to include xnull^T as a row in matrix A.

The reason you would need to do this is to render the new xnull orthogonal to the previous xnull.

see the first solution attached, i obtained a solution in 1.png attached, then i appended the solution as the last row in the second attachment and resolved. In the final attachment, you will realize i have no solutions since the rank of your matrix is 3 we can only have itercount = 5-3 = 2 solutions

In Matlab you would need to write sth like this

n = rank(A)

itercount = col - n

xnullMatrix = []

for i = 1:itercount

• xnull = getNULL(A); %getNULL is your linear program to obtain xnull
• xnullMatrix = [xnullMatrix xnull];
• A = [A; xnull'];

end

xnullMatrix should contain all your linearly independent solutions

Hi Temitayo Bankole ,

Great! That was a good point. I got it.

Thanks

@Tematayo is right. You can do something similar with the LP mentioned above, in order to avoid using binary variables.

Suppose you have found a null vector with positive part v and negative part v'. Then add the linear equation

v^Tx - (v')^Tx' = 0

to the LP, to ensure that the next solution is orthogonal.

Dear Prof. Adam N. Letchford ,

I am really grateful to you for your LP model. It was really helpful.