[R] convex nonnegative basis vectors in nullspace of matrix

[Petr Savicky]

On Wed, Apr 11, 2012 at 06:04:28AM -0700, capy_bara wrote:
> Dear all,
> 
> I want to explore the nullspace of a matrix S: I currently use the function
> Null from the MASS package to get a basis for the null space:
> > S  = matrix(nrow=3, ncol=5, c(1,0,0,-1,1,1,1,-1,-1,0,-1,0,0,0,-1)); S
> > MASS::Null(t(S))
> My problem is that I actually need a nonnegative basis for the null space of
> S.
> There should be a unique set of convex basis vectors spanning a vector space
> in which each vector v satisfies sum (S %*%  v) == 0 and min(v)>=0. 

Hi.

In my previous solution, i forgot that lp() assumes all variables
nonnegative. So, the code was searching only a subset of the true
set of solutions. A better alternative is as follows.

  library(lpSolve)
  S <- matrix(nrow=3, ncol=5, c(1,0,0,-1,1,1,1,-1,-1,0,-1,0,0,0,-1))
  a <- MASS::Null(t(S))
  a1 <- cbind(a, -a)
  n <- nrow(a1)
  a2 <- rbind(a1, colSums(a1))
  b <- rep(0, times=n+1)
  b[n+1] <- 1
  dir <- c(rep(">=", times=n), "==")
  sol <- matrix(nrow=100, ncol=n)
  for (i in seq.int(length=nrow(sol))) {
      crit <- rnorm(ncol(a))
      crit <- c(crit, -crit)
      out <- lp(objective.in=crit, const.mat=a2, const.dir=dir, const.rhs=b)
      sol[i, ] <- a1 %*% out$solution
  }
  unique(round(sol, digits=10))

       [,1] [,2] [,3] [,4] [,5]
  [1,] 0.00 0.50  0.5 0.00 0.00
  [2,] 0.25 0.25  0.0 0.25 0.25

Petr Savicky.