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.

The null space of the above matrix has dimension 2. Its intersection

with nonnegative vectors in R^5 is an infinite cone. In order to restrict

it to a finite set, we can consider its intersection with the set

of vectors with the sum of coordinates equal to 1. Then, the solution

is a finite convex polytop and we can search for its vertices. The

following code searches for vertices in random directions and finds two

vertices. In this simple case, the polytop is in fact a line segment,

so we get its endpoints. These endpoints form a linear basis of the

original null space consisting of nonnegative vectors.

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))

n <- nrow(a)

a1 <- rbind(a, colSums(a))

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))

out <- lp(objective.in=crit, const.mat=a1, const.dir=dir, const.rhs=b)

sol[i, ] <- a %*% out$solution

}

unique(round(sol, digits=10))

[,1] [,2] [,3] [,4] [,5]

[1,] 0.2500000 0.2500000 0.0000000 0.2500000 0.2500000

[2,] 0.1642631 0.3357369 0.1714738 0.1642631 0.1642631

Use this with care, since for more complex cases, this method does not

guarantee that all vertices are found. So, it is not guaranteed that

every nonnegative vector in the null space is a nonnegative combination

of the obtained vectors.

Hope this helps.

Petr Savicky.

______________________________________________

[hidden email] mailing list

https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide

http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.