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

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

1. ### Greg HeathGuest

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

2. ### Bruno LuongGuest

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

3. ### John D'ErricoGuest

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
4. ### Robert IsraelGuest

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
5. ### Greg HeathGuest

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
6. ### Greg HeathGuest

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
7. ### Greg HeathGuest

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

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

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

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
11. ### Bruno LuongGuest

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
12. ### John D'ErricoGuest

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
13. ### Greg HeathGuest

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
14. ### Bruno LuongGuest

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
15. ### John D'ErricoGuest

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
16. ### israelGuest

The span of the rows of X, yes.

israel, Oct 13, 2008
17. ### Greg HeathGuest

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
18. ### Greg HeathGuest

Greg Heath, Oct 14, 2008
19. ### Bruno LuongGuest

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
20. ### Greg HeathGuest

I'm missing something.

However, I really appreciate your effort.

Thanks.

Greg.

Greg Heath, Oct 17, 2008