Inflate a simplex, change rows to make the rank n - MathOverflow

Inflate a simplex, change rows to make the rank n

2012-06-13T14:31:23Z

I have a simplex, n + 1 points in $\mathbb{R}^n$, which may have rank $r < n$.
Is there a cheap way of "inflating" it to rank $n$, changing a few, all but $r$, of the points ?

The points are also ordered, rows 1 2 3 $\dots$ in a matrix, and I'd like to keep as many of the leading rows as possible unchanged.

Answer by Andrew T. Barker for Inflate a simplex, change rows to make the rank n

2012-06-13T15:10:56Z

You are given a matrix with $ n + 1 $ rows (one for each point) and $ n $ columns. Without loss of generality we can say the first point is the origin, so the first row is all zeros and we delete it from the matrix to get a square $ n $ by $ n $ matrix $ A $.

Now you want to modify as few rows as possible of $ A $ so that the span of the rows of $ A $ is $ \mathbb R^n $. But the fundamental theorem of linear algebra says $$ \text{nulspace}(A) = (\text{span of rows}(A))^\perp = \text{image}(A^T)^\perp $$

So find a basis for the nulspace of $ A $, and for each vector you get replace one of the linearly dependent rows of $ A $ with that vector.

Answer by Vidit Nanda for Inflate a simplex, change rows to make the rank n

2012-06-13T15:31:05Z

There are three possible ways to proceed that I can think of immediately.

If you have no idea what the rank $r$ is for your given matrix, then of course you must perform the linear algebra: get your matrix into echelon form, isolate and replace the dependent rows, etc as outlined in Andrew's nice answer. This process is well known to be $O(n^3)$ in terms of time and exponentially nasty in terms of memory since the intermediate entries could get arbitrarily large.
If you do know what $r$ is, then you could try a probabilistic approach: Choose $n-r$ rows at random (it seems that you would prefer to skew the choice so that you are more likely to choose rows further down in the matrix) and add a normally distributed fuzz factor to each entry in those chosen rows. This is extremely cheap computationally and the entries don't get too much larger than they already are, but of course it is not guaranteed to work. In case the rank of the fuzzed matrix is still smaller than $n$, go back to square one and repeat the process: it is still much cheaper than the first method.
If you have to do this computation with a billion different matrices then neither of the approaches above will satisfy you: the first is computationally untenable and the second is likely to fail now and again. In this case, maybe you want to perform symbolic gaussian elimination once and for all on an $n \times n$ matrix of symbols. This is very expensive but you only need to do it once. Now just "plug in" your billion $n \times n$ matrices one by one. If the rank is less than $n$ for any such matrix, you will know exactly which columns' pivots to change and exactly which entries in the original matrix contributed towards making those pivots zero.