Самый быстрый способ проверить, увеличивает ли вектор ранг матрицы

Дана матрица A размером n на m, причем гарантируется, что n>m=rank(A), и дан столбец v размером n на 1, какой самый быстрый способ проверить, имеет ли [A v] ранг строго больше A?

Для моего приложения A разрежена, n равно примерно 2^12, а m находится в пределах 1:n-1. Сравнение rank(full([A v])) занимает около секунды на моей машине, а мне нужно сделать это десятки тысяч раз, поэтому я буду очень рад найти более быстрый способ.