You are now following this question
- You will see updates in your followed content feed.
- You may receive emails, depending on your communication preferences.
How to get the minimum number of rows that, if removed, reduces the rank.
4 views (last 30 days)
Show older comments
NA
on 28 Jun 2020
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
Answers (1)
Matt J
on 28 Jun 2020
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.
13 Comments
Walter Roberson
on 28 Jun 2020
Edited: Walter Roberson
on 28 Jun 2020
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
on 28 Jun 2020
Edited: NA
on 28 Jun 2020
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
on 28 Jun 2020
Edited: Matt J
on 23 Apr 2021
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
on 28 Jun 2020
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
on 28 Jun 2020
Edited: Matt J
on 28 Jun 2020
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
on 28 Jun 2020
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
on 29 Jun 2020
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
on 23 Apr 2021
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)
NA
on 23 Apr 2021
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)
See Also
Categories
Find more on Linear Algebra in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!An Error Occurred
Unable to complete the action because of changes made to the page. Reload the page to see its updated state.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)
Asia Pacific
- Australia (English)
- India (English)
- New Zealand (English)
- 中国
- 日本Japanese (日本語)
- 한국Korean (한국어)