Saturday, 22 October 2011

linear algebra - Is there a version of inclusion/exclusion for vector spaces?

One way to look at this question is via quiver representations. Two subspaces of a vector space form a representation of the quiver $A_3$ with orientations $bullet rightarrow bullet leftarrow bullet$ with the additional condition that both maps are injective (that's tautology). Now, every representation of $A_3$ is a sum of indecomposables, whose dimension vectors are (1,0,0), (0,1,0), (0,0,1), (1,1,0), (0,1,1), (1,1,1), where for the first and the third one the maps are not injective, and for the remaining four the maps are injective. Thus, the dimension vector for a generic representation with injective maps is a(0,1,0)+b(1,1,0)+c(0,1,1)+d(1,1,1)=(b+d,a+b+c+d,c+d). Clearly, the dimension of the sum of the two subspaces is b+c+d (the complement is represented by the first summand a(0,1,0)), which is (b+d)+(c+d)-d, and d is the dimension of the intersection.



Now, for the three subspaces we deal with representations of the quiver $D_4$ with injective maps. (I am too lazy to draw $D_4$ on MO, sorry!). Indecomposable representations have dimension vectors $(d_1,d_2,d_3,d)$ (note different ordering of dimensions - the largest one is the last one) being (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (1,0,0,1), (0,1,0,1), (0,0,1,1), (1,1,0,1), (1,0,1,1), (0,1,1,1), (1,1,1,1), (1,1,1,2) - altogether 12 vectors. Among them, the first three have non-injective maps, and the fourth one captures the complement of the sum of our three subspaces. Thus, there are 8 numbers through which the dimension can be expressed (not 7, as in the inclusion-exclusion formula), and what remains is to choose the 8th number, in addition to the dimensions of all possible intersections, reasonably for your needs.



For $k>3$ subspaces the classification problem stops being of finite type so it becomes a bit more nasty...

No comments:

Post a Comment