Column Space and Row Space

Suppose we have a system of equations with equations and unknowns.  How can we tell if this system has a solution?  Writing the system as , we see that the left-hand side gives us a particular linear combination of the columns of .  That is, the system can be thought of as

And so we see that the system has a solution if and only if can be expressed as a linear combination of the columns of .  In fact, taking the set of all possible vectors for which has a solution, we have a vector space called the column space of , which we’ll normally denote .  There are a couple of ways we can think of the column space:

1. The set of all linear combinations of the columns of
2. The set of all vectors such that has a solution
3. The set of all for any vector

These are all equivalent, but sometimes it may be more helpful to think of the column space in one way than another.

A similar concept is that of the row space, which is the set of all linear combinations of the rows of and denoted .  Notice that .

Now suppose that we multiply by a matrix on the right.  How might the column space of differ from ?  Using the third characterization of a column space above, and assuming is , we have that

So the column space of is contained in the column space of , and in particular .  The above is telling us that linear combinations of the columns of are actually linear combinations of the columns of .  One way to see this is to realize that each column of is actually a linear combination of combination of columns of .  Letting denote the -th column of , we can write as follows.

Now if we take a linear combination of these columns we have

Our choice of the values is arbitrary — they can be whatever we’d like them to be — but the are fixed since they’re entries in .  This restricts the possible linear combinations of the rows, so .  Repeating the same argument but using rows instead of columns, or just using the above argument with , we have that .  Notice if (or ) is non-singular, then we have .  Combined with the above we have equality when or is non-singular.

Now what we’d like to show is that the dimension of the row space and the dimension of the column space are actually equal for any matrix .  Simply pick to be the nonsingular matrix so that is in row-reduced echelon form, and pick to be the nonsingular matrix so that is in column-reduced echelon form.  Notice then

where is the identity matrix for some .  Since matrix multiplication is associative, .  Putting the matrix into row-reduced echelon form with the moves all the non-zero rows to the top with each row having a leading one and the rest of that column zeroed out.  When we multiply this by we put the matrix into column-reduced form which moves all the non-zero columns to the left and zeros out everything on in the rows with leading ones.  With this matrix we clearly have .  We can show that when and are both nonsingular that , using the rank-nullity theorem which we’ve yet to prove.

Every Vector Space Has a Basis

I just realized a few hours ago that the algebra prelim is six weeks from today, and went into “that’s way closer than I realized”-freakout mode.  Given that, I’d like to start posting on algebra.  In particular, for the next little bit I want to post on linear algebra since that’s what I’ve been studying the most recently.  A nice place to start might be showing that every vector space has a basis, since this is a fact that I remember being used throughout my linear algebra classes but don’t seem to remember ever being shown (presumably to avoid talking about the axiom of choice and Zorn’s lemma).  This proof is adopted from the one that appears in an appendix to Larry Grove’s Algebra.

Recall that Zorn’s lemma says that in a partially ordered set in which every chain has an upper bound, there exists a maximal element.  We will use this to show that there must be a maximal linearly independent subset in a vector space, and argue that this set is a basis.

Let be any vector space and define the set as the collection of all linearly independent subsets of .

Note that as is a collection of sets, it is partially ordered by .  Now let be any chain in .  Each element of this chain, being a linearly independent set of vectors in , forms the basis for some subspace of .  Furthermore, if and are in the chain with , the subspace of generated by is contained in the subspace generated by .

Define a set as follows:

Defining in this way, we have a collection of vectors in in which every subset is linearly independent, and so .  This means that has an upper bound.  Since our choice of the chain was arbitrary, this means every chain in has an upper bound.  By Zorn’s lemma this means has a maximal set.  Let be such a maximal set (recall Zorn’s lemma says that will have at least one maximal set, and not that the maximal set is unique).

Since , is a linearly independent set of vectors in .  This means that the span of is some subspace of .  Suppose this subspace is proper.  Then there exists some vector, call it , which can not be represented as a linear combination of the elements in .  This implies that is a linearly independent set.  However, as this contradicts the maximality of .  We must conclude that equals the span of , and so forms a basis for .

Extreme Points, Part 1 — Geometric Intuition

Recall from earlier that in a linear program we have a set of constraints, , each of which defines a half-space.  The intersection of all these half-spaces, along with our standing assumption defines our feasible region: the region in space where satisfying all of our constraints.  In general, the intersection of a finite number of half-spaces is called a polyhedral set, and if the set is bounded set call it a polytope.

One thing to notice about polyhedral sets is that they’re convex.  To see this, suppose that our polyhedral set is defined by .  Now let and be two points satisfying these constraints (in each of the corresponding half-spaces).  Let .  We have the following.

So and the set is convex.

Now, if we had only a few (two or three) variables, then we could explicitly graph the polyhedral set and we’d notice that it has some sharp “corners” when two lines (or planes) that form the boundary of a half-space intersect.  These points are of interest to us because if an optimal solution exists it must occur at one of these corner points.

As an example, consider the following linear program:

Maximize

Subject to the following:

Graphing these we have

The extreme points for our feasible region are the five corners above, each of which is the intersection of two of the lines determined by our constraints.  Now let’s consider all of the points where our objective function would be equal to 2.  These are the points satisfying the equation — all such points lie on a line, and in particular are the points on the red line below.

Note that if we were to consider the points where our objective function is 3 (the points lying on the line ), we’d have a similar picture, but with our line simply shifted up one unit:

Remember that our goal is to maximize our objective function while satisfying all of the constraints / staying within the feasible region.  Geometrically, then, what we should do is move this line up as far as we can — as our objective increases when we shift the line up — and stay in the feasible region.  Each of these lines is called an objective contour.  Looking at the set of all possible values the objective function could take on we have something similar to the following (I say “something similar” because the picture would just be solid red if we looked at all the contours).

From this picture we see that the optimal solution occurs at the top-right extreme point.  Since an extreme point is the intersection of two lines, we can simply calculate the intersection point of those two lines to see to find the precise point where optimality is obtained (these are called binding constraints since they’re satisfied by equality).

Those lines are and , so optimality occurs at and our objective function takes on the value 4.

This geometric argument is nice and intuitive, but falls apart if we have more than three variables (since we’re in at least four dimensional space where such pictures can’t be drawn).  In the next post we’ll see how to characterize the extreme points of the feasible region algebraically.  Later we’ll see how to traverse the extreme points of the feasible region, using that algebraic description, in such a way that we always move to a “closer to optimal” extreme point, until we finally get there (or determine no such optimal point exists).

An Quick Aside on Convexity

I’ve been meaning to write a post on the extreme points of a feasible set for the last few days, and in that post I need to talk about convexity.  Originally I was going to just define convex set and convex combination inside of that post, but decided it might be better for those to be defined in their own post.  It’s been busy at school the last couple of days, but I’m still hoping to get a couple more LP posts written this week.

Intuitively a convex set is one which doesn’t have any “inward bumps.”  In the image below, the region on the left is convex while the region on the right is not.

To say the set doesn’t have any “inward bumps” is rather vague, though.  A more precise notion is to say that for any two points in the set, the line segment connecting those points lies entirely in the set.  We see the region on the left has this property, while the region on the right does not: pick two points in opposite “legs,” and the line segment joining them will not lie completely within the region.  Of course, when we start talking about higher dimensional spaces simply drawing the line segment doesn’t really work.  What we’ll do instead is pick tow points, say and and take a convex combination of these points.  If all such convex combinations lie in the set, the set is convex.

By a convex combination of the points and , we mean the point where .  (Recall that we’re dealing with points inside of a vector space, so by adding two points we’re adding the associated vectors.)  One important thing to note about convex sets is that if is convex, then for any finite collection of points we have that

where

We will show this inductively where our base case, , follows immediately from our definition of convexity.  Now assume for the result holds for .  We will show the result holds for :  Let and with .  We begin by rewriting our sum:

Notice that implies , so the sum of the coefficients in the expression inside parenthesis is one.  Since each of these points is in our convex set , we have a convex combination and thus the sum is in the set — call this point .  Now we have is a convex combination of points inside , and so we have our result.

LP Part 3: The Feasible Region

Suppose we want to consider all of the points in the plane that satisfy the inequality .  What does such a set look like? Well, one way to visualize it is to draw the line and then take everything under or on the line.  This is an example of a half-space: a “line” that cuts the space in two, and then we take everything on one side of that “line.”  I write “line” because in higher dimensions this isn’t actually a line.  In three dimensions, for instance, it’s a plane.  In four dimensions it’s a hyperplane.  We’ll use the word hyperplane to just mean a linear equality regardless of dimension.  Recall that a linear equality is simply an equation of the form ; no exponents, no logs or square roots, just constant multiples added up.  And so a half-space is everything on one side of a hyperplane.

In a linear program we tend to have a few of these linear inequalities  in the form of our constraints.  When we actually write out , we see that each row in corresponds to a particular inequality and so each constraint defines a half-space.  We’re only concerned with points that satisfy all of the constraints, however, and thus want our optimal solution to occur within the intersection of these half-spaces.  This intersection of all the half-spaces defined by our constraints is called the feasible region of the program.

As far as the feasible region is concerned, there are four cases we need to be aware of when it comes time to actually solve a linear program: the feasible region is empty; the feasible region is not empty, but is bounded; the region is not bounded, but the objective function is;  neither the feasible region nor the objection function are bounded.

The first case occurs when our constraints “cancel each other out.”  For instance if we had the constraints and .  The first constraint puts us on one half of a hyperplane, and then the second tries to get us back on the other side.  Since both of these inequalities can’t hold at the same time, there are no points inside our feasible region.  That’s a simple example of an infeasible LP.  Another, slightly more complicated example occurs if our constraints are

Multiplying this out, we have the following.

An Infeasible Region

In the above picture, areas that satisfy an inequality are shaded in blue, and areas satisfying two equalities are in a dark blue (the shading is additive).  Notice that no area is in a blue any darker than the areas satisfying two inequalities; no area satisfies all three inequalities.  Since no point satisfies all three inequalities, our feasible region is empty.

We’ll say the feasible region is bounded if we can place a circle of finite radius around it, encompassing the entire feasible region.  If the feasible region is bounded, then our objective must be bounded.  As we will see later, our objective is minimized or maximized only at “corners” of the feasible region.  Such a corner occurs only when some number of our constraints are satisfied by equality (the particular number depending on the dimension of the problem).  In two dimensions, for instance, corners occur when two lines cross, and we’re only on a line if we satisfy a constraint with equality.  In three dimensions we’d need three planes to intersect.  Since we only concern ourselves with problems which have a finite number of constraints, we only have a finite number of these corners (this number may be huge, though, so just enumerating all possible corners isn’t a reasonable strategy).

If our feasible region is unbounded, however, our objective function may or may not be bounded.  It could be that we can make the objective arbitrarily large by picking numbers that are farther and farther out, but it could also be that picking huge numbers isn’t particularly helpful.  For example, suppose our only restrictions were , so we can pick any pair of points in the first quadrant.  If our goal is to maximize , then we can make this value as big as we want by picking big enough numbers.  If our goal is to minimize , however, then the best we can do is to pick .

For a slightly less trivial example, suppose we want to maximize subject to the constraints , , .  Now our feasible region is an infinite strip, a portion of which is given below.

Despite being able to pick very large numbers, our maximum occurs at the point , .  If we were to increase any our value would drop since we’re subtracting , and we’ve already made as large as we can.  So we have a bounded objective function, even though our feasible region is unbounded.  We will generally refer to a linear program as being bounded if it’s objective function is bounded, and unbounded if it’s objective function is unbounded.  Note that for the LP to be unbounded, the feasible region must be unbounded.  If the LP is bounded, however, the feasible region may be either bounded or unbounded.

In the next post we’ll look at the extreme points of the feasible region, which are the “corners” alluded to earlier, and give an argument for why the maximum/minimum must occur at an extreme point.

Linear Programming, Part II – Slack and Surplus

Recall from last time that a linear program is an optimization problem of the form

Maximize

Subject to and

Where the system of constraints is just a convenient way to write something of the form

Notice that our use of maximization, instead of minimization, is immaterial as any maximization problem can be turned into an equivalent minimization problem and vice versa.  The problem of maximizing is equivalent (has precisely the same solutions) as the problem of minimizing .

Likewise, our use of inequalities instead of is more a matter of taste and convenience than necessity: is the same thing as .  What we would like to do, though, is get rid of those inequalities altogheter.  If we can turn these constraints into a system of equations of the form , then we’ll be able to apply techniques from linear algebra to help us manipulate the LP (linear program).  Later we’ll see how to cleverly use elementary row operations to traverse the set of potential optimal solutions.  But first we have to lose those nasty little inequalities.

So here’s the idea: say we have .  We can turn this into an equation by inserting a non-negative variable, , which equals .  That is, takes up the slack left by , and becomes .  Algebraically, if we set , we have and that’s why we have equality.

If our inequality goes the other way, say , we’ll just subtract off the surplus: set (note that this means ) and so becomes .  So in the system of inequalities above we can get a system of equations by tacking on a slack, or taking out the surplus, for each inequality.  The earlier system then becomes

Where is the slack (surplus) we add (subtract) for the -th constraint.  Now our matrices will of course have to change a little bit to take these new variables into account.  Originally, was an matrix, was a -vector, and was a -vector.  For our system of equations we’ll let and where is the identity matrix; note that doesn’t change.  Note too that we append the identity because we have only slack variables; if some of those had been surplus variables, the corresponding entries we append would be negative.

So by throwing in an extra variable for each inequality constraint we have a system of equations which is amenable to the techniques of linear algebra.  If it were to happen that the resultant matrix was invertible (which requires it to be square — an equal number of equations and unknowns) then we could just multiply by the inverse and find the solution.  This doesn’t work for our general problem though since there will normally be infinitely many possible solutions.  Our goal will be to weed out the best solution from those possibilities.  In the next post we’ll look at this space of possible solutions.

An Introduction to Linear Programming, Part I

In a first semester calculus class you learn how to optimize a differentiable function by looking at what happens where the derivative is zero (and the endpoints if you’re concerned with a closed interval).  The idea being what comes up must come down: if the function goes up and then goes down, a maximum must occur somewhere between (and similarly for a minimization problem), so you look for the precise point that “up” turns to “down.”  What I want to talk about in the next few posts is how to maximize (or minimize) a linear function in the presence of linear constraints.  (Note that as it’s taught in calculus, such optimization problems have no additional constraints.)

That is, we’ll look at functions of the form where and are vectors in .  The is the dot product of these two vectors, and is just a convenient way of writing .  So the are our variables and the are constants normally referred to as cost coefficients.

An example of such a function is the cost of, say, building a house.  Let’s suppose is the amount of lumber used which costs $2 per pound (I have no idea how much lumber costs, so you’ll have to excuse me if that’s a completely ridiculous value); is the amount of brick which we’ll assume is $3 per pound; and let’s say is the amount of roofing we use and it costs $5 per pound.  Here our cost for building the house would be , and so we could just say and .  This function, , we will refer to as our objective function, and our goal will be to make this as small (or large) as possible given certain restrictions (linear constraints).

Now, by a linear constraint we mean that there are limits on the resources we use, and we can express these limits in the same way we expressed the cost.  In our house building example, for instance, we may not be able to use any more than 2000lb of brick, so we’d have a constraint .  Similarly let’s assume we must use less than 1500lb of lumber and 300lb of roofing materials: , and .  If we further assume that our house must weigh at least 2100lb (for whatever reason) then we’d have the constraint .  Just to make things more complicated, let’s assume we have to use at least 50lb of roofing materials: .  (I know this is a goofy example with silly constraints, but it still serves the purpose of showing us what a linear programming problem is.  The last two constraints are there only so we don’t have a trivial solution.)

Now our linear program is simply the following:

Minimize

Subject to the following:

This last constraint simply says that we can’t have a negative amount of brick, lumber, or roof.

So, our problem is that we want to minimize the cost of building a house when we’re faced with certain restrictions on amounts of material we can use.  (Now you should see why the last two constraints are needed to prevent a trivial solution: if you want to minimize the cost and there’s nothing telling you can’t, just use zero brick, zero lumber, and zero roofing!)

It is generally convenient to rewrite this set of constraints as a matrix.  In our particular problem we could set up the matrix

Then if we let , our constraints could be expressed simply as

Where we will adopt the convention that if and are vectors of the same size, means that each component of is less than or equal to the corresponding component of ; for all .  (Notice that in order to write our problem like this we had to multiply the last two inequalities by -1 so that we’d have instead of the we started with.)

This is all linear programming means: maximize (or minimize) the function under the condition that and .  The term linear programming, by the way, is due to George Dantzig who studied such problems while trying to optimize schedules for the US Air Force in the 1940s.  The Air Force referred to their schedules as “programs,” and so such problems came to be known as linear programs.

In the next post we’ll discuss slack and surplus variables which allow us to turn the inequalities above into equalities, which will be necessary for us to solve linear programs algorithmically.

The Fundamental Group, Part II – The Basepoint

We constructed the fundamental group by looking at the homotopy classes of loops with a fixed basepoint.  The question that naturally arises is how does the fundamental group change if we move the basepoint.  To begin let’s suppose we’re in a path connected space and we have two basepoints we’re concerned about, say and .  Since is path connected, there exists some path from to .  We can use this to convert loops into loops.

What we’ll do is take a loop, say , based at and use our path to get from to , follow the loop, then take the reverse path back to .  This is illustrated in the image below (adapted from an image in Hatcher’s book).

This new path is a loop based at .  Now, if two -loops, say and are homotopic, then so are the associated -loops: .

If we now construct a map by setting we see that the map will be well-defined since our construction of the -loops respects homotopy.  But what happens when we concatenate two -loops?

Suppose and are loops based at .  We want to see what this map does to the homotopy class of .

So our map is in fact a homomorphism.  Notice that implies , which means that our map is injective.

To show the map is surjective, let be an -loop, then is an -loop.  Applying we have , and so our map is surjective.  Together with injectivity above we have shown that in a path connected space the fundamental group of and are isomorphic.  We then simply write since the choice of basepoint is basically irrelevant.

If our space is not path connected, but and are in the same path component, the above gives us that .

An Aside on Path Connectedness

Long ago we talked about topological spaces being connected, which meant we couldn’t partition the space into two disjoint non-empty open sets.  There is a stronger notion that we’ll need when working with the fundamental group called path connectedness.  We say that a space is path connected if for every pair of points there exists a path in the space, , such that and ; we can connect every pair of points with a path.

If a space is not path connected, it can be decomposed into a collection of disjoint subsets with are path connected.  These subsets are called the path components of the space.  More specifically, path connectedness is an equivalence relation on the space and the path components are the equivalence classes.  Clearly every point is path connected to itself (reflexivity); if and are connected by path , then the reverse path connects and (symmetry); and the concatenation operation from last time gives us transitivity.

We said that path connectedness was a stronger condition than connectedness.  This means that path connectedness implies regular ol’ connectedness.  To see this, suppose that is path connected.  Let be connected by path .  Let be an open set containing , and an open set containing .  Now consider the preimages and .  Since is a path it is continuous, so these are two open subsets of [0, 1].  We must have since and .  We know that [0, 1] is connected, however.  This implies that must be connected (otherwise their preimages would be disjoint open sets covering [0, 1]).  Since and were arbitrary, we can generalize to get that is connected.

Notice that this also means that a continuous path must stay inside of one path component.

The Fundamental Group, Part I – Connecting Paths

Imagine that you have two paths, and .  If it should happen that the terminal point of is the initial point of (that is, if ), then we can basically concatenate and into a new path .  To do this formally we need to define , which means we have to reparameterize and a little bit.  We’ll define so that it behaves as on [0, 1/2] and as on [1/2, 1] (notice this will be well-defined since we’re assuming the terminal point of is the initial point of ).

We will let the asterisk denote this concatenation operation: .

In the case that and are loops with the same basepoint, we’re just gluing the two loops together.  In the image below the basepoint is represented by the red dot.  We’re taking these two loops and gluing them together so that we first wind around the first loop (the one on the left) and then around the second loop.

Note that the red dot is the same basepoint for both loops, even though in our picture it doesn’t stay aligned (just for graphical convenience).

If , and are loops (with the same basepoint) and , we can show that .  Letting be the homotopy taking to , we construct the homotopy by defining .  This always behaves as on the “second half” of the loop, and deforms to on the first half.  Of course, this also can be used to show that .

We can now use to help us form an operation on the homotopy classes of loops.  We will simply define as .  This operation is clearly associative, since our concatenation is associative. The identity element of this operation is the homotopy class of the constant function.  Keeping in mind that these are loops, the constant function is the function that maps everything to the basepoint.  Let denote this map.  Then we have that , where the last equality follows from the fact that with we traverse twice as fast as normal, then just sit at the basepoint.  This is homotopic to , and so and live in the same homotopy class.

Finally, our operation is invertible.  To define the inverse operation we will take a loop and will let denote the reverse loop: .  This reverse loop will have the same shape as the initial loop, but traverse the loop in the opposite direction.  Now notice that can be compressed into the constant map by constructing a homotopy that traverses most of , then goes ahead and starts coming back through .  This homotopy slowly reels back to the basepoint, which eventually turns it into the constant map.  Since ( being the constant basepoint map), we have that , and similarly .

So, our operation is associtiative, has an identity, and is invertible, so we have a group of the homotopy classes of loops for a fixed basepoint.  This is known as the fundamental group and is denoted , where is the space and is the basepoint.  In the next post we’ll look at what happens when the basepoint changes.