How to get the minimum number of rows that, if removed, reduces the rank.

I have a matrix A

How can I get the number of rows that make matrix A rank deficient.

for example

A =[ 6.5480   -6.5480    0.0000   -0.0000
    6.5480   -6.5480    0.0000   -0.0000
   -6.5480    6.5480   -0.0000    0.0000
   -0.0000    0.0000    5.8267   -6.0073
   -0.0000    0.0000    5.8267   -6.0073
   -0.0000    0.0000   -6.1879    6.3685
         0         0    1.0000         0
         0         0         0    1.0000]
rank_A =rank(A) 

The rank of A is 3, if I remove 3 rows, the rank of the matrix changes to 2.

So, the result should be 3 ---> number of rows

Answer 1

[Matt J]

Well, if A were full rank, it's rank would be

min(size(A));

So, perhaps you want the difference between this and the actual rank.

[Walter Roberson]

Especially in cases where there are duplicate rows, then hypothetically it could be the case that reducing just one particular row could reduce the rank; and likewise, that reducing a number of rows might not change the rank at all because they might all happen to be duplicates of what is left behind.

For example,

rank(A(setdiff(1:end,[1 2 4]),:))   -> 3

so if you remove the correct 3 rows, you still have rank 3, which contradicts the premise that if you remove 3 rows you will always get down to rank 2.

It is not clear to me whether the user wants to know the minimum number of rows that, if removed, reduces the rank, or if they want to know the maximum number of rows that, if removed, would still leave the rank the same.

[NA]

Thank you for your comment. I want the minimum number of rows that, if removed, reduces the rank.

I wrote this code

n = size(A, 1);
rank_A = min(size(A)); %min(size(A))

for d = 1:(n-1)
    newn = n - d;
    indices_matrix = combnk(1:n, newn);
    Mset = 0;  
    for j = 1:size(indices_matrix, 1)
        indices = indices_matrix(j, :);
        A_minus_d = A(indices, :);
        rank_A_minus_d = min(size(A_minus_d));
        if (rank_A_minus_d < rank_A)
            dstar = d; % minimum number of rows that, if removed, reduces the rank.
            Mset = 1;
            break
        end
    end
    if Mset == 1 % breaking from first loop
        break
    end
end

But is not it is not efficient, if the size of A is large.

[Matt J]

How large will A get?

[NA]

157*64

[Matt J]

The code below isn't a complete solution, but it should help narrow the search considerably. Using this FEX submission (Download), it will extract disjoint, linearly independent, and full-rank subsets of the rows of A. It will stop only when the remaining non-extracted rows have reduced rank. So, you know that a final, minimal selection of rows will exist that

(1) Draws at least one row from each of these subsets.

(2) Does not draw rows from outside these subsets. (EDIT: Not so sure about this one anymore)

At=A.'; %work on columns instead of rows

[B,idx]=licols(At);
rankA=size(B,2);
At(:,idx)=[];

subset={B.'};
while true
    
    [B,idx]=licols(At);
     n=size(B,2);
    
     if n<rankA, break; end
    
    At(:,idx)=[];
    
    subset{end+1}=B.'; %#ok<SAGROW>
   
end

subset{:}

[NA]

Thank you for the code. For example for this matrix

A =

   16.4375  -16.4375         0    6.6072   -3.2451         0
    4.3822         0   -4.3822    1.7820         0   -0.2678
  -15.2586   20.8295   -5.5709   -6.9904    5.9336   -1.4319
   -4.0199   -5.3450    9.3648   -1.7655   -2.0406    1.6268
   -3.3911    3.3911         0   14.0359  -15.7297         0
   -0.2698         0    0.2698    4.0386         0   -4.3492
         0   -1.4428    1.4428         0    5.4882   -5.5289
   -3.6609    3.3911    0.2698   18.0744  -15.7297   -4.3492
    6.9904   -8.4331    1.4428  -15.2586   22.7313   -5.5289
    1.7655    2.1325   -3.8980   -4.0199   -5.1148    9.6219
         0         0         0    1.0000         0         0
         0         0         0         0    1.0000         0
         0         0         0         0         0    1.0000

If I run 'your code', row_of_subset =5;

But if I run 'my code' d=7

[Matt J]

I don't know what d or row_of_subset are supposed to signify, but when running my code, you should get,

>> subset{:}

ans =

  -15.2586   20.8295   -5.5709   -6.9904    5.9336   -1.4319
   -4.0199   -5.3450    9.3648   -1.7655   -2.0406    1.6268
   -3.3911    3.3911         0   14.0359  -15.7297         0
    6.9904   -8.4331    1.4428  -15.2586   22.7313   -5.5289
    1.7655    2.1325   -3.8980   -4.0199   -5.1148    9.6219
         0         0         0         0         0    1.0000

[NA]

I got this result

subset{:}

ans =

  -15.2586   20.8295   -5.5709   -6.9904    5.9336   -1.4319
   -4.0199   -5.3450    9.3648   -1.7655   -2.0406    1.6268
    6.9904   -8.4331    1.4428  -15.2586   22.7313   -5.5289
    1.7655    2.1325   -3.8980   -4.0199   -5.1148    9.6219
         0         0         0         0         0    1.0000


ans =

   16.4375  -16.4375         0    6.6072   -3.2451         0
    4.3822         0   -4.3822    1.7820         0   -0.2678
         0   -1.4428    1.4428         0    5.4882   -5.5289
   -3.6609    3.3911    0.2698   18.0744  -15.7297   -4.3492
         0         0         0    1.0000         0         0

[Matt J]

That's quite possible. I don't have your exact A matrix, so my output can be different from yours. Either way, the code appears to be working.

[NA]

Thank you for your time.

Please confirm if my understanding is correct.

It means that, in the matrix A, if I remove 5 rows according to subset{:}, A become rank deficient.

So, the minimum number of rows that, if removed, reduces the rank is

size(subset{1},1)

[Matt J]

No, that is not correct.

The code tells you that the optimal number of removed rows Nopt, is bounded from below by numel(subsets),

Nopt>=numel(subsets)

Also, any optimal set of removed rows must contain at least one row from each subsets{i}.

[NA]

If A is

A =[ 6.5480   -6.5480
    6.5480   -6.5480
   -6.5480    6.5480];

subsets are

subset{:}
ans = 6.5480   -6.5480
ans = 6.5480   -6.5480
ans =-6.5480    6.5480

So numel(subset) is 3,

 optimal_numbe_of_removed_rows>=3 

I think it should be

 Nopt>=size(subset{1},1)

[Matt J]

optimal_numbe_of_removed_rows>=3

That's correct. Because rank(A)=1 in your example, the only way to reduce the rank is to remove all 3 rows.