rank([X;Y]) < rank(X) + rank(Y)

Discussion in 'MATLAB' started by Greg Heath, Oct 11, 2008.

  1. Greg Heath

    Greg Heath Guest

    I was given a protein-sequence/torsion-angle data set
    with 45 observations of 17 predictors and 60 responses.

    size(X) = [17 45]
    size(Y) = [60 45]
    Z = [X;Y]
    size(Z) = [77 45]

    Now

    rank(X) = 13 ==> 4 predictors are redundant
    rank(Y) = 31 ==> 29 responses are redundant
    rank(Z) = 37 ==> ?

    I am puzzled by the fact that

    rankZ < rankX + rankY

    What does this imply, if anything?

    TIA

    Greg
     
    Greg Heath, Oct 11, 2008
    #1
    1. Advertisements

  2. Greg Heath

    Bruno Luong Guest

    span(Z) = span(X) + span(Y) (not direct)

    rank(Z) = rank(X) + rank(Y) - rank(I(X,Y)))
    with I(V1,V2) = Intersect(span(X),span(Y))

    That means simply rank(I(X,Y)) = 13 + 31 - 37 = 7

    Bruno
     
    Bruno Luong, Oct 11, 2008
    #2
    1. Advertisements


  3. Merely that the two sets are not linearly
    independent.

    X = [1 0 0 0;1 1 1 1]
    Y = [0 1 0 0;1 1 1 1]

    See that the ranks of each of X and Y is 2.
    Yet the rank of [X;Y] will only be 3.

    John
     
    John D'Errico, Oct 11, 2008
    #3
  4. I take it that X is a 17 x 45 matrix, Y is 60 x 45, and Z is obtained by
    stacking X on top of Y. The fact that rank(Z) = 37 < rank(X) + rank(Y)
    = 44 means that the intersection of the row space of X and the row space of Y
    has dimension 44 - 37 = 7.
     
    Robert Israel, Oct 12, 2008
    #4
  5. Greg Heath

    Greg Heath Guest

    If by span(X)(spanX) you mean all possible linear
    combinations of the rows of X, then I do not
    agree. I'd say that

    span(Z) > span(X) + span(Y)

    because it contains mixed linear combinations.

    For what it is worth,

    rank(spanX) = rankX

    What does (not direct) mean?
    ?

    I just can't visualize it.
    Simply? ... I'm still having trouble with it!

    7 what?

    If BX is a basis for spanX and BY is a basis for
    spanY does this mean there are are 7 linear
    dependencies in union(BX,BY)?

    Thanks,

    Greg
     
    Greg Heath, Oct 13, 2008
    #5
  6. Greg Heath

    Greg Heath Guest

    Merely? It's significant if you are trying to
    design a linear regression model.
    Right, but I think it there are more complicated
    examples that are examples of other significant
    implications..

    Thanks,

    Greg
     
    Greg Heath, Oct 13, 2008
    #6
  7. Greg Heath

    Greg Heath Guest

     
    Greg Heath, Oct 13, 2008
    #7
  8. Greg Heath

    Greg Heath Guest

     
    Greg Heath, Oct 13, 2008
    #8
  9. Greg Heath

    Greg Heath Guest

     
    Greg Heath, Oct 13, 2008
    #9
  10. Greg Heath

    Greg Heath Guest

    Does row space of X mean the span of X
    (X and Y may have no common rows)?

    Thanks,

    Greg.
     
    Greg Heath, Oct 13, 2008
    #10
  11. Greg Heath

    Bruno Luong Guest


    No, I use the math notation

    U = V1 + V2

    where U, V1 and V2 are vectorial space means that U is defined as

    U = { x+y : x in V1 y in V2 }

    We put a circle around the "+" sign if and only if V1 intersect V2 = {0}.

    Intersection of two span spaces has dimension 7.
    Yes. In other word, the concatenated matrix [BX BY] has a null space (kernel) of dimension 7.

    Bruno
     
    Bruno Luong, Oct 13, 2008
    #11
  12. No. There are not. At least not different
    in any important way.

    I chose a simple example where the two
    column spaces shared a vector that was
    identical. But this merely says the two
    spaces are not independent. The simple
    counterexample I provided was chosen
    to show the fact as clearly as possible.

    John
     
    John D'Errico, Oct 13, 2008
    #12
  13. Greg Heath

    Greg Heath Guest

    I understand that. Well done.

    I was just referring to slightly less simple
    cases. Perhaps where X and Y do not
    intersect but span(X) and span(Y) do.

    THanks.

    Greg
     
    Greg Heath, Oct 13, 2008
    #13
  14. Greg Heath

    Bruno Luong Guest

    For example this:

    x1=[1; 1; 0]; x2=[1; -1; 0];
    y1=[0; 2; -1]; y2=[0; 0; -1];

    X=[x1 x2]
    Y=[y1 y2]

    nx = size(X,2);
    ny = size(Y,2);

    Z = [X Y]
    K=null(Z);
    nk=size(K,2)

    fprintf('Basis of intersection of span(X) and span(Y):\n')
    I = X*K(1:nx,:);
    disp(I)
    % I = -Y*K(nx+1:end,:)

    fprintf('rank[span<X>+span<Y>]= %d\n', rank(X)+rank(Y)-nk);
    fprintf('rank[span<Z>] = %d\n', rank(Z));

    % Bruno
     
    Bruno Luong, Oct 13, 2008
    #14
  15. No. This can never be true.

    The row spaces of each of X and Y can be
    represented by a set of linearly independent
    basis vectors. Because X has rank 13, there
    are 13 of those independent (and orthogonal)
    basis vectors for X. The row space of Y has
    31 such orthogonal basis vectors.

    Of course, the origin is included in the
    span of both of the spaces, but if the two
    spaces were independent of each other, the
    origin would be the only such intersection
    point.

    Suppose we start with X. Reduce that space
    to some set of orthogonal vectors. Orth is
    a good way to do so, or QR. The information
    content that was once in the rows of X
    is embodied in some linear combination
    of those 13 basis vectors.

    Likewise, we can reduce Y to a set of 31
    distinct basis vectors. Any row of Y can
    be written as some linear combination of
    those 31 vectors.

    Now, imagine the two sets of orthogonal
    vectors. We can rotate a set of orthogonal
    vectors around the origin. As it turns out,
    if we rotate one of these sets of vectors
    carefully, we will find that the two sets
    can be rotate around so they share exactly
    7 basis vectors. The intersection space has
    dimension 7.

    Perhaps best is to write some code.

    Given X and Y as above, if we did this:

    Bx = orth(X')';
    By = orth(Y')';

    Bx will have 13 rows, and By will have
    31 rows. These are sets of orthogonal
    basis vectors for the row spaces of each
    matrix. They span those row spaces.

    How do we find the intersection space?
    This is the subspace that the two share
    in common. We can do it by projecting
    one space onto the other.

    S = (Y*Bx')*Bx;

    Or, since By forms a basis for the rows
    of Y, we could have done so as

    S = (By*Bx')*Bx;

    Now we can use orth to find a basis for
    this shared subspace.

    Bs = orth(S')';

    It will have 7 rows, and thus a 7-d
    shared set of basis vectors.

    John
     
    John D'Errico, Oct 13, 2008
    #15
  16. Greg Heath

    israel Guest

    The span of the rows of X, yes.
     
    israel, Oct 13, 2008
    #16
  17. Greg Heath

    Greg Heath Guest

    Thanks, John. I have been determined to do a similar
    construction using 13 + 31 original vectors that create
    nonorthogonal bases. Hence the reason for this thread.
    I purposely excluded orthogonalization because I wanted
    to understand what lessons original vectors could tell
    me from a physical point of view.

    Kudos aside, maybe my basic problem is that I really
    don't understand the terminology (dumb engineer etc).

    spanX contains all possible linear combinations of the
    17 X row vectors.
    spanY contains all possible linear combinations of the
    60 Y row vectors
    spanZ contains all possible linear combinations of the
    77 Z row vectors.

    Therefore spanZ not only contains spanX and spanY,
    but it also contains all possible linear combinations
    of X and Y row vector mixtures. Consequently, I
    concluded that

    spanZ > spanX + spanY

    Maybe that is the wrong terminology for what i just
    described. If so, and my logic makes sense, what is
    the correct terminology?

    Greg
     
    Greg Heath, Oct 14, 2008
    #17
  18. Greg Heath

    Greg Heath Guest

     
    Greg Heath, Oct 14, 2008
    #18
  19. Greg Heath

    Bruno Luong Guest

    As I explain early the terminology is *vectorial-space* sum

    span Z = spanX + spanY (exactly equal, not bigger not larger)
    With the standard definision of space sum as following:
    U + V := { u in U and v in V }.

    The space sum is of course much larger (in term of set) than the "union", that might be a source some confusion.

    But the basic linear algebra dimensional relation is:

    rank (spanX + span Y) = rank X + rank Y - rank(X union Y).

    which implies

    rank (spanX + span Y) <= rank X + rank Y (ineq2)

    The space *sum* is called "direct space sum" if and only if union of the two space is {0}, thus eq (ineq2) becomes equality. In this case we write the "+" sign with a small circle around it.

    Bruno
     
    Bruno Luong, Oct 15, 2008
    #19
  20. Greg Heath

    Greg Heath Guest

    I'm missing something.

    However, I really appreciate your effort.

    Thanks.

    Greg.
     
    Greg Heath, Oct 17, 2008
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.