Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a matrix $S$ and need to find a set of basis vectors $\{\mathbf{x_i}\}$ such that $S\mathbf{x_i}=0$ and $\mathbf{x_i} \ge \mathbf{0}$ (component-wise, i.e. $x_i^k \ge 0$).

This problem comes up in networks of chemical reactions where $S$ is the stoichiometric matrix and $\mathbf{x_i}$ are extreme vectors that define a proper, polyhedral cone at steady state (I don't understand entirely what all of this means - have a picture in my head though).

More detail: Suppose you're looking at a concentration network involving $n$ chemical species , summarized in a vector $\textbf{u}$, and $m$ reactions with rates $\textbf{w}(\textbf{u})$. Then an ODE that describes the behaviour of this dynamical system is $$\frac{d \textbf{u}}{dt}=S\textbf{w}(\textbf{u}).$$ The stoichiometric matrix $S \in \mathbb{Z}^{n \times m}$ describes how much of the species involved in a reaction is consumed / produced relative to one other.

At steady state, $d\textbf{u}/dt|_{\textbf{u}=\textbf{u}^*}=0$, we now look for the kernel / null space of $S$, i.e. reaction rates $\textbf{w}$ such that $S\mathbf{w}=0$.

Apparently (however I don't fully understand this), the intersection of $\text{ker}(S)$ and $\mathbb{R}_+^m$ forms a proper, polyhedral cone. This cone can be represented by a nonnegative combination of the finite set of extreme vectors that are unique up to scaling by a positive constant - the $\textbf{x}_i$ above are these extreme vectors.

(I quoted the latter bit mostly verbatim from http://www.springerlink.com/content/g5093r283160p518/)

Possible route of solving this:

So there appears to be a way to define this as a linear programming (LP) problem, but I don't quite see this. This seems to be suggested here: http://r.789695.n4.nabble.com/convex-nonnegative-basis-vectors-in-nullspace-of-matrix-td4548822.html

Any elaboration on the LP approach or any other way of solving this is greatly appreciated.

share|improve this question
2  
Notice that your task might be impossible to accomplish. If the kernel of your matrix is generated for example by $(1,-1)$ then it is impossible. –  Godot Aug 29 '12 at 15:05
    
If there some relationship between $S$ and $A$? –  copper.hat Aug 29 '12 at 15:37
    
Sorry, corrected typo ... they're the same matrix. –  Name Aug 29 '12 at 15:41
    
Do you have a small example? There is really not much to go on, here. –  rschwieb Aug 29 '12 at 16:22
    
Do you mean a basis for $\ker S$ that lies in the positive quadrant? –  copper.hat Aug 29 '12 at 17:30
show 1 more comment

3 Answers

up vote 2 down vote accepted

First note that $ker(S)$ is a linear subspace of $\mathbb{R}^m$ (I am assuming $S$ is an $n \times m$ matrix). Next observe that $\mathbb{R}_+^m$ is a polyhedral cone (a cone is polyhedral if it can be expressed as $Ax \leq 0$). The intersection of a linear subspace and the cone $\mathbb{R}_+^m$ will be another polyhedral cone. It is worth trying to visualize this. Consider $\mathbb{R}^3$. Then the non-negative orthant $\{(x,y,z) \mid x\geq 0, y\geq0, z\geq0\}$ is a polyhedral cone. Another description of this cone is that it is the convex hull of the following three extreme rays $\{t(1,0,0) \mid t \geq 0\}$, $\{t(0,1,0) \mid t \geq 0\}$, and $\{t(0,0,1) \mid t \geq 0\}$. Now you should be able to convince yourself that the intersection of the non-negative orthant with any hyperplane passing through the origin will result in another polyhedral cone.

Polyhedral cones have a finite number of extreme rays. There are various methods to enumerate these extreme rays. You can truncate the cone and enumerate the extreme points of the resulting polytope; this seems to be the approach in the link you included. There is also very good software that will explicitly enumerate the extreme rays: PORTA and cdd/cdd+ are two that come to mind.

share|improve this answer
add comment

It is a difficult problem, however such spaces are characterized by duality theorems of alternative, in particular you could use the Motzkin theorem of the alternative to check if a given set of vectors form a convex basis.

share|improve this answer
add comment

There is not much information in your question to go on, at present, but certainly there is always the possibility of using any one of numerous methods to solve the linear system $Sx=0$ with the additional constraint imposed by your nonnegativity condition.

As Godot mentioned, this is not possible in general. Maybe there are some additional properties about stoichiometric matrices that would be good to know?

share|improve this answer
    
I added more detail in the question. Hope this makes it a little more clear! –  Name Aug 30 '12 at 9:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.