Следующий ответ не основан на правильных математических рассуждениях, это всего лишь некоторые предположения (как вы просили интуиции):
norm(A) - это порядок величин элементов матрицы.
Таким образом,
eps(norm(A)) - это точность, которую обычно имеет представление элементов матрицы с плавающей запятой.
Теперь рассмотрим добавление N чисел, которые теоретически должны быть равны нулю, но каждое из них имеетошибка eps для него ... Я думаю, что мы ожидаем ошибку порядка sqrt(N) * eps для результата.
Тогда, учитывая, что алгоритм, который вычисляет ранг, выполняет N^2 операциина элементах матрицы (где N - ее размер), чтобы получить число, которое проверяется на ноль, мы ожидаем, что ошибка, о которой вы говорили в вашем вопросе.
Что я не делаюзнаете, действительно ли алгоритм, который использует Matlab, имеет сложность N^2?