Rank of a double-precision augmented matrix

Question

Let $A$ be a matrix with real entries, and let $A_+$ be $A$ augmented by a single column. From linear algebra we know \begin{equation} \operatorname{rank}(A_+) = \operatorname{rank}(A) \hspace{10pt} or \hspace{10pt} \operatorname{rank}(A_+) = \operatorname{rank}(A)+1 \end{equation} 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?

Answer 1

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.