Re: diagnosing short rank matrices

[Mike Miller]

On Fri, 1 Aug 2003, Heber Farnsworth wrote:

> Here is something I occasionally need to do.  I have to figure out why a
> matrix is less than full rank.  I have seen other packages (like SAS)
> which will tell you which columns are nearly a linear combination of
> which other columns.  That's a good trick and I've never figured out how
> to do it.  Does anyone know?

For n x m matrix X, if there exists a vector b such that X*b = zeros(n,1),
and not all elements of b are zero, then X is less than full rank.  This
implies that at least one column of X can be written as a linear
combination of the other columns.  There's probably a more straightforward
way (maybe using eigenvalues and eigenvectors?) but I think taking out
each column of X and doing this sort of thing will give you an answer for
column k of X:

[n, m]=size(X);

B = X(:,[[1:(k-1)],[(k+1):m]]) \ X(:,k);

X(:,[[1:(k-1)],[(k+1):m]])*B-X(:,k)

Whenever that last thing equals zero(n,1), you've found your linear combo.
The vector 'B' will tell you exactly what linear combination that is.

You probably want to do this sort of thing:

max(abs(X(:,[[1:(k-1)],[(k+1):m]])*B-X(:,k))) < tiny_number

because it won't be *exactly* zero.


Mike

-- 
Michael B. Miller, Ph.D.
Assistant Professor
Division of Epidemiology
and Institute of Human Genetics
University of Minnesota
http://taxa.epi.umn.edu/~mbmiller/



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------