Rank-robustness of the parallel complexity of linear algebra problems

Question

It is known that most computational problems related to linear algebra can be computed in $NC^2$ - i.e. for an $n\times n$ matrix $A$, over the reals or a finite field, we can compute the rank of $A$, $\det(A)$ or $A^{-1}$, etc. in parallel time $O(\log^2(n))$.

The complexity of these linear-algebra problems remains the same (i.e. in $NC^2$) even if the rank of $A$ is say $n^{\epsilon}$ for some small constant $\epsilon>0$ (just by padding zeros) but what happens to the complexity of these problems when $A$ has very small rank, i.e. $r = rank(A) \leq \log(n)$?

Clearly, if $A$ is ${\it given}$ to us as a full-rank matrix of dimension $n \times r$ then the complexity drops: Consider for example the problem of determining whether $A x = b$ for inputs $A,b$ over $\mathbf{F}_2$ for some vector $x$.

One can simply enumerate over all possible column subsets of $A$, and compute $x$ in constant parallel time ($ACC^0[2]$). However, the problem is that we do not posses such a succinct description from the input. Naively, trying to brute-force enumerate over all possible column combinations of size $\log(n)$ results in time ${n\choose \log(n)}$ which is quasi-polynomial.

Answer 1

I think the following procedure computes a basis of the column span of an $n \times n$-matrix of rank at most $\log n$ in $\mathrm{AC}_1$.

If you have a matrix of size $n \times 2 \log n$, you can find a basis of its column span in $\mathrm{AC}_0$ by running over all subsets in parallel and checking in parallel whether a nontrivial linear combination vanishes (say over $\mathbb{F}_2$). From all sets of maximal rank you select the lexicographically smallest.

Now given an $n \times n$-matrix of rank at most $\log n$, we can find a basis of its column span in $\mathrm{AC}_1$ as follows: Divide the columns into two halfves, compute a basis recursively. From these two bases we can compute a common basis using the algorithm from above.