Re: [R] Gaussian elimination - singular matrix

From: Moshe Olshansky <m_olshansky_at_yahoo.com>
Date: Wed, 27 Jun 2007 17:10:36 -0700 (PDT)


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.

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


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. Received on Thu 28 Jun 2007 - 00:36:50 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Thu 28 Jun 2007 - 03:32:40 GMT.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.