How to compare each individual column vectors of a matrix to a set of vectors

What i basically need is to find if the system of equations that i have, already has a identity matrix or atleast part of it. i.e. if i have a matrix

1 2 1 0;
2 3 0 1;
3 4 0 0;

Though there is no 3x3 identity matrix in the above matrix it still contains 2/3 vectors that make one.

So how to code this?

Really appreciate the help. I am completely new to matlab.

Regards

[the cyclist]

What specifically do you want the output to be, if the algorithm does (or doesn't) find an identity matrix (or more than one).

Does just a single "1" count as an identity matrix, or does it need to be at least 2x2?

[Image Analyst]

What if they're in a different order but still extracted from the identity matrix, like

1 2 0 1;
2 3 0 0;
3 4 1 0;

The right two columns come from a 3x3 identity matrix - column 3 of this matrix is the third column of the identity matrix, and column 4 is column 1 of the identity matrix, and column 2 is missing. So do you want that to return "true", "false", or 2/3? And why? What is the use case?

[Yuvaraj Pazhamalai]

I have to code 2-phase simplex for solving linear programming problems. One of the requisites is that the program should be able to identify if an initial basis exists, if not how many addition artificial variables have to be added to create a basis. Hope that answers your questions. Appreciate your help.

I don't follow the single "1" query. The program has to check for the number of rows, which is easy to get and then check each column vector in the matrix if it has "1" in some row and rest should be zero.

[Image Analyst]

To check a single column for a single 1:

thisColumn = yourMatrix(:, columnNumber);
single1 = nnz(thisColumn==1) == 1 && sum(thisColumn == 0) == length(thisColumn)-1;

single1 will be either true or false.

[Walter Roberson]

However, I suspect that for

1 2 1 0;
2 3 0 1;
3 4 1 5;

that the upper-right identity matrix should be found, even though column 3 contains two 1's.

Yuvaraj Pazhamalai, I do not think you have really answered the questions about what to do if the order is changed, or what the smallest identity matrix is that you wish to consider. Also, a basis matrix does not need to be an identity matrix.

I think you should be more concerned about rank() of the matrix than about finding identity matrices.

[Yuvaraj Pazhamalai]

Thanks for the reply. Appreciate the help. I agree that the basis doesn't have to be an identity matrix. Let me put it this way, i just need to find out if an unit vector is already there in the linear problem in it's standard form.

[Yuvaraj Pazhamalai]

Thanks, Image Analyst your code helps. I can build on it. Appreciate the help.

Answer 1

[the cyclist]

Here is my best guess at some core code that might do what you want.

A = [1 2 1 0;
     2 3 0 1;
     3 4 0 0];

[m,n] = size(A);

for m1 = 1:m-1
for m2 = m1+1:m
for n1 = 1:n-1
for n2 = n1+1:n
    T = A(m1:m2,n1:n2);
    [tm,tn] = size(T);
    if tm==tn && isequal(T,eye(tm))
        sprintf('Identity matrix at A(%d:%d,%d:%d)',m1,m2,n1,n2)
    end
end
end
end
end

It is a very straightforward implementation, and I do not take advantage of even simple methods to make it more efficient. (For example, the loops run over non-square submatrices of A.) But I hope you get the idea, and perhaps can tailor it to what you need.