I’m trying to understand this paper by Alexander Postnikov. This post is mainly a summary of some the concepts that I do not understand. Some examples.
- Grassmannian- A Grassmannian
of a vector space
is a space that parametrizes all the
dimensional subspaces of
. For instance,
would be
. Why do we need Grassmannians? Because we need a continuous, and hopefully smooth way to characterize the
dimensional subspaces of
. An example would be the tangent spaces on a real
-manifold
. The map
which maps
to the tangent space at
is
. Some interesting things to note here. First that the tangent space of any manifold has a dimension that is equal to the dimension of the manifold. This much we know. Let us assume for easy visualization that the space in which the manifold and its tangent spaces have been embedded have a dimension bigger than
. What we’re doing here is that we’re mapping each
to the parameter corresponding to the tangent space at
. In general this map may not even be surjective. Because as
changes slightly, so does the parameter corresponding to the tangent space at that points, we have a feel for why this map may be continuous.
- Plucker coordinates- This is a way to assign six homogeneous coordinates to each line in
. How does one go about doing this, and why is it useful? A brilliant explanation is given on the Wikipedia page for Plucker coordinates. Say we take a line in
. It is uniquely determined by
points (say
and
). However, is it uniquely determined by the vector between those two points? No. This vector can be translated and placed anywhere. Hence, we need both the vector between the two points and some sort of an indication as to where this vector lies with respect to the origin. One such indication would be the cross product of the two points
and
. The direction would give the orientation of the plane containing
and
, and the magnitude would give the distance that
and
are from the origin. Hence, we need six coordinates- three for the vector between
and
, and three for
. Will these six coordinates uniquely describe the line? Yes. The direction will specify a plane that the three points
and
can lie in, and the magnitude will specify how far in that plane the vectors
and
lie. The vector
along with the direction of
will specify exactly where
and
lie with respect to
.
How we shall talk a little about the formal definition of Plucker coordinates. In , let
and
be two coordinates. Let
.
There are ways of selecting two elements from
. Why do we need
? Because if
, then
. This is because the second row would just be the same as the first row. Also,
. This is because we’d be exchanging two columns. Hence, there are only
independent coordinates here. This ratifies the assertion that we need just
homogeneous coordinates to specify a line in
.
- Matroid- A matroid is a structure that generalizes linear independence in vector spaces. More formally, it is a pair
, where
is a finite set, and
is a set of subsets of
which are “linearly independent”. The first property is that
is a linearly independent set. Secondly, if
is linearly independent, and
, then
is linearly independent too. This is called the hereditary property. Third, if
and
are linearly independent sets, and if
contains more elements than
, then there is an element in
that can be added to
to give a larger linearly independent subset than
.
The first two properties of linearly independent sets carry over smoothly from our intuition of what linearly independent sets are. The third property seems strange, but on a little thinking becomes clear. Think of the two independent sets and
in
. We can add either of
or
to
to create a larger linearly independent set. However, what if the smaller set was contained within the bigger set; i.e. what if the two sets were
and
? We could still find
to
to create a bigger linearly independent set. On a little experimentation, you will be able to convince yourself that this is a natural property of linearly independent sets of vector spaces.
Now we discuss some more properties of matroids. A subset that is not independent is called, you guessed correctly, a dependent set. A maximal independent set, one that becomes dependent on the addition of any element outside of it, is called a basis. A minimal dependent set, which becomes independent on the removal of any element, is called a circuit. Does a basis, on addition of an element, become a circuit? I don’t know. But I intend to find out.