We start by showing that adding a random column to a (non full column rank) matrix increases the dimension of its column space by 1 with high probability. To maintain the sparsity of the initial matrix, we add random sparse Gaussian vectors. This is similar to a reduction by Wiedemann [1]} for finite fields.
