# Rank of a double-precision augmented matrix

Let $$A$$ be a matrix with real entries, and let $$A_+$$ be $$A$$ augmented by a single column. From linear algebra we know $$$$\operatorname{rank}(A_+) = \operatorname{rank}(A) \hspace{10pt} or \hspace{10pt} \operatorname{rank}(A_+) = \operatorname{rank}(A)+1$$$$ But what if $$A$$ has double-precision entries and $$\operatorname{rank}()$$ is a commonly used function in a numerical library ?

The most popular rank function seems to be the one in MATLAB, which computes the rank as the number of singular values that are larger than a specific tolerance $${\tt tol}$$. The default $${\tt tol = max(size(A))*eps(norm(A))}$$ seems to be carefully chosen.

Q1: Does MATLAB's $${\tt rank()}$$ satisfy the above?

Q2: If not, then is there a more clever choice of $${\tt tol}$$ that does?

Q1: No. Here's a counter-example:

>> A = eye(4)*1e-300
A =
1.0e-300 *
1.0000         0         0         0
0    1.0000         0         0
0         0    1.0000         0
0         0         0    1.0000
>> rank(A)
ans =
4
>>
>> rank([A, ones(4, 1)])
ans =
1
>>


so, if the added column is large enough, it can make the matrix seem rank 1.

Q2. This seems unlikely. The singular values of the augmented $$A$$ are:

>> svd([A, ones(4, 1)])
ans =
2
1e-300
1e-300
5.00000000000001e-301


You could simply set tol = 0 (and even that would fail if you underflow), but other than that, it is hard for me to imagine a clever choice of tol that would yield anything but 1 for the rank in this case.

EDIT: (responding to comment by OP)

A more subtle example with column norms that are $$O(1)$$

n = 3;
for i = 1:1000
% the following A should have rank(A) == 1 and column norms O(1)
A = orth(randn(n))*diag([1; n*eps*ones(n-1, 1)*0.95])*orth(randn(n));
if rank(A) == 1
i, A
break
end
end
assert(i<1000)
% find a column that makes the augmented matrix rank more than 2
for i = 1:1000
AAug = [A, randn(n, 1)];
if rank(AAug) > 2
i, AAug
break
end
end
assert(i<1000)
fprintf('rank(A) = %d, rank(AAug) = %d\n', rank(A), rank(AAug))


Here's my output:

i =
1
A =
-0.046045803605795         0.358096260855252         0.167217577109151
0.0939153553990513        -0.730375733980246         -0.34105818453341
0.0495185833028385        -0.385103921204328        -0.179829145619174
i =
35
AAug =
-0.046045803605795         0.358096260855252         0.167217577109151          1.25773638573877
0.0939153553990513        -0.730375733980246         -0.34105818453341        -0.728182736925861
0.0495185833028385        -0.385103921204328        -0.179829145619174          1.19290445411165
rank(A) = 1, rank(AAug) = 3


In general, you can have a matrix with column norms $$O(1)$$ which is nonetheless almost rank-1, but then adding a column can perturb more than one singular value over the tolerance.

• In my application, I really want the given property of the rank() to be true. In this excellent counter-example, the norms of the columns of $A_+$ are very different. For most applications it seems reasonable to ask the same questions, but with constraints of some sort on the column norms. I think the simplest case where there may be a solution might be when all the columns of $A_+$ are unit vectors. – Glenn Davis Oct 14 at 3:48