How to write linearly dependent column in a matrix in terms of linearly independent columns?

Question

I have a large mxn matrix, and I have identified the linearly dependent columns. However, I want to know if there's a way in R to write the linearly dependent columns in terms of the linearly independent ones. Since it's a large matrix, it's not possible to do based on inspection.

Here's a toy example of the type of matrix I have.

> mat <- matrix(c(1,1,0,1,0,1,1,0,0,1,1,0,1,1,0,1,0,1,0,1), byrow=TRUE, ncol=5, nrow=4)
> mat
      [,1] [,2] [,3] [,4] [,5]
[1,]    1    1    0    1    0
[2,]    1    1    0    0    1
[3,]    1    0    1    1    0
[4,]    1    0    1    0    1

Here it's obvious that x3 = x1-x2, x5=x1-x4. I want to know if there's an automated way to get that for a larger matrix.

Thanks!

Answer 1

I'm sure there is a better way but I felt like playing around with this. I basically do a check at the beginning to see if the input matrix is full column rank to avoid unnecessary computation in case it is full rank. After that I start with the first two columns and check if that submatrix is of full column rank, if it is then I check the first thee columns and so on. Once we find some submatrix that isn't of full column rank I regress the last column in that submatrix on the previous one which tells us how to construct linear combinations of the first columns to get the last column.

My function isn't very clean right now and could do some additional checking but at least it's a start.

mat <- matrix(c(1,1,0,1,0,1,1,0,0,1,1,0,1,1,0,1,0,1,0,1), byrow=TRUE, ncol=5, nrow=4)


linfinder <- function(mat){
    # If the matrix is full rank then we're done
    if(qr(mat)$rank == ncol(mat)){
        print("Matrix is of full rank")
        return(invisible(seq(ncol(mat))))
    }
    m <- ncol(mat)
    # cols keeps track of which columns are linearly independent
    cols <- 1
    for(i in seq(2, m)){
        ids <- c(cols, i)
        mymat <- mat[, ids]
        if(qr(mymat)$rank != length(ids)){
            # Regression the column of interest on the previous
            # columns to figure out the relationship
            o <- lm(mat[,i] ~ mat[,cols] + 0)
            # Construct the output message
            start <- paste0("Column_", i, " = ")
            # Which coefs are nonzero
            nz <- !(abs(coef(o)) <= .Machine$double.eps^0.5)
            tmp <- paste("Column", cols[nz], sep = "_")
            vals <- paste(coef(o)[nz], tmp, sep = "*", collapse = " + ")
            message <- paste0(start, vals)
            print(message)
        }else{
            # If the matrix subset was of full rank
            # then the newest column in linearly independent
            # so add it to the cols list
            cols <- ids
        }
    }
    return(invisible(cols))
}

linfinder(mat)

which gives

> linfinder(mat)
[1] "Column_3 = 1*Column_1 + -1*Column_2"
[1] "Column_5 = 1*Column_1 + -1*Column_4"