Finding m-linearly independent columns of a matrix on MATLAB

Question

Let us have a linear system Ax<= b. To find a vertex of this polyhedral set we need to choose m linearly independent columns of A and solve the system with the corresponding variables. How can I generate all the m-linearly-independent columns using MATLAB? I will then find all the vertices of the polyhedron I have.

What I can think about is: generate all the (n, m) combination of subsets. Check one by one ranks. Whenever the ranks are =m, take these solutions since they have full m-rank. Is there a more efficient method?

Answer 1

To find the linearly independent column you can use eig or qr.

for eig the eigenvalues equal to zero will indicate the non independent colums

for qr the zeros on the diagonal of R matrix will indicate the non independent colums

for example:

mat2 =
 1     1     1
 1     1     1
 0     0     2

qr gives

R =
-1.414213562373095  -1.414213562373095  -1.414213562373095
               0                   0                   0
               0                   0   2.000000000000000

and eig gives

ans =
 2
 0
 2