[R] Gaussian elimination - singular matrix

[Moshe Olshansky]

All the nontrivial solutions to AX = 0 are the
eigenvectors of A corresponding to eigenvalue 0 (try
eigen function).
The non-negative solution may or may not exist.  For
example, if A is a 2x2 matrix Aij = 1 for 1 <=i,j <=2
then the only non-trivial solution to AX = 0 is X =
a*(1,-1), where a is any nonzero scalar.  So in this
case there is no non-negative solution. 
Let X1, X2,...,Xk be all the k independent
eigenvectors corresponding to eigenvalue 0, i.e. AXi =
0 for i = 1,2,...,k.  Any linear combination of them,
X = X1,...,Xk, i.e. a1*X1 + ... + ak*Xk is also a
solution of AX = 0.  Let B be a matrix whose COLUMNS
are the vectors X1,...,Xk (B = (X1,...,Xk).  Then
finding a1,...,ak for which all elements of X are
non-negative is equivalent to finding a vector a =
(a1,...,ak) such that B*a >= 0.  Of course a =
(0,...,0) is a solution.  The question whether there
exists another one.  Try to solve the following Linear
Programming problem:
max a1
subject to B*a >= 0
(you can start with a = (0,...,0) which is a feasible
solution).
If you get a non-zero solution fine.  If not try to
solve
min a1
subject to B*a >= 0
if you still get 0 try this with max a2, then min a2,
max a3, min a3, etc.  If all the 2k problems have only
0 solution then there are no nontrivial nonnegative
solutions.  Otherwise you will find it.
Instead of 2k LP (Linear Programming) problems you can
look at one QP (Quadratic Programming) problem:
max a1^2 + a2^2 + ... + ak^2 
subject to B*a >= 0
If there is a nonzero solution a = (a1,...,ak) then X
= a1&X1 +...+ak*Xk is what you are looking for. 
Otherwise there is no nontrivial nonnegative solution.

--- Bruce Willy <croero at hotmail.com> wrote:

> 
> I am sorry, there is just a mistake : the solution
> cannot be unique (because it is a vectorial space)
> (but then I might normalize it)
>  
> can R find one anyway ?
>  
> This is equivalent to finding an eigenvector in
> fact> From: croero at hotmail.com> To:
> r-help at stat.math.ethz.ch> Date: Wed, 27 Jun 2007
> 22:51:41 +0000> Subject: [R] Gaussian elimination -
> singular matrix> > > Hello,> > I hope it is not a
> too stupid question.> > I have a singular matrix A
> (so not invertible).> > I want to find a nontrivial
> nonnegative solution to AX=0 (kernel of A)> > It is
> a special matrix A (so maybe this nonnegative
> solution is unique)> > The authors of the article
> suggest a Gaussian elimination method> > Do you know
> if R can do that automatically ? I have seen that
> "solve" has an option "LAPACK" but it does not seem
> to work with me :(> > Thank you very much>
>
_________________________________________________________________>
> Le blog Messenger de Michel, candidat de la Nouvelle
> Star : analyse, news, coulisses
 A découvrir !> >
> [[alternative HTML version deleted]]> 
>
_________________________________________________________________
> Le blog Messenger de Michel, candidat de la Nouvelle
> Star : analyse, news, coulisses
 A découvrir !
> 
> 	[[alternative HTML version deleted]]
> 
> > ______________________________________________
> R-help at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained,
> reproducible code.
>