2
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Glenn Davis Oct 14 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.