How to find an invertible linear transformation that sparsifies a basis Let $A$ be an $m\times n$ matrix over the reals, with linearly independent column vectors.
How can we find an invertible $n\times n$ matrix $T$ such that the product matrix $B = A T$ is as sparse as possible (as measured by the number of nonzero elements)?
In other words, given a set of basis vectors (the columns of $A$) I'm looking to find an alternative, sparser basis (the columns of $B$).
These are not big matrices -- in my application, I will have $m = 9$ and $n \leq 6$.  A greedy, approximate solution is probably sufficient.
 A: Ben Grossmann's second answer seems to be the solution!
Since the $n$ columns of $A$ are assumed to be linearly independent, it should also be possible to find $n$ rows of $A$ that are linearly independent. Stack these row vectors into an $n\times n$ matrix and invert to get $T$.
Here is Julia code that seems to work:
# Given an m×n matrix A with zero nullspace, linearly combine the n columns to
# make them sparser.
function sparsify_columns(A)
    if size(A, 2) <= 1
        return A
    else
        # By assumption, the n columns of A are linearly independent
        @assert isempty(nullspace(A; atol=1e-12))
        # Since row rank equals column rank, it should be possible to find n
        # linearly independent rows in A
        indep_rows = Vector{Float64}[]
        for row = eachrow(A)
            # If row is linearly independent with all existing ones, add it to the
            # list
            if isempty(nullspace(hcat(indep_rows..., row); atol=1e-12))
                push!(indep_rows, row)
            end
        end
        return A * inv(hcat(indep_rows...))'
    end
end

A: Here's some code in Matlab that uses the RREF function.
function T = sparsifier(A)

if size(A,2)<= 1
    T = A;
else
    [m,n] = size(A);
    M = [A.', eye(n)];
    R = rref(M);
    T = R(:,m+1:end).';
end

