Linear Algebra

This is perhaps one of the more fundamentally important topics in modern advanced Mathematics. It is not uncommon for most graduate level Maths courses to either begin with or contain the fundamentals of Linear Algebra, either as a refresher, or as a brief introduction. Whether you study Analysis, Computational Mathematics, Discrete Mathematics, Geometry; Linear Algebra will always be needed.

The reason for this is that Linear Algebra deals with vectors and matrices. These are precisely the Mathematical constructs which we use to understand concepts of size and direction, as well as those that encode any concept we have of multiple measurements in a given scenario. For instance, we may need to consider a problem where a number of goods need to be shipped from various factories to various stores. These shipments come with specific costs and our goal may be to minimise these costs, whilst providing each store with all the goods they will need. This type of question is usually given in a form known as a Linear Problem. Certain values need to be selected (amount of each good going from each factory to each store), so that the costs are minimised and a certain calculation (generally a matrix multiplied by the vector of these values) meets certain conditions. In this post, I will try to explain the concepts of vectors and vector spaces. In a subsequent post, I hope to explore the basic ideas of matrices, but a good understanding of vectors will be required first.

In simple terms, a vector is nothing more than a collection of values, in a given order. Suppose you have a box of toy cars. You may count the number of cars it contains, of each different colour. You can then code your findings as a vector, by saying that you will give the number of red, green, blue and yellow cars in the box, in that order. If there are two cars of each colour, your box can be represented by the vector (2, 2, 2, 2). If you then buy 2 new green cars and one new red car, but lose on of your blue cars, the new vector representing the current state of affairs will be (3, 4, 1, 2). Note that the order of the values (or variables) must remain the same throughout. We could have selected a different order to begin with, but once this choice is made, we must keep it consistent.

Once we have the above concept, we can consider all vectors whose entries represent the same things. For instance, all collections of toy cars of these four colours can be thought of as a single family of objects. Such a family of vectors is called a vector space (or linear space), when certain properties are met. The first of these is known as closure in addition. That is, when we add two vectors in our vector space, we need to be able to get a new vector, which will also be in the same space. The second is closure to scalar multiplication. That is, if we take a number and multiply it with one of our vectors, we need to get a new vector, in the same space.

First, we will deal with vector addition. Suppose you buy one blue toy car and two red ones. Then, some time later, you may decide to buy another blue car and three green ones. The number of cars of each colour that you have does not depend on the order you acquired them in. It only depends on the sum of the individual purchases. Using the notation above, we have (2, 0, 1, 0) + (0, 3, 1, 0) = (2, 3, 2, 0). That is, the addition of vectors is done separately for each component. This establishes the first property of closure that we needed.

Next, we would like to see how scalars (i.e. numbers) multiply vectors. What if a standard box has two toy cars of each colour? How many cars would I have if I bought three such boxes? The calculation would be 3 * (2, 2, 2, 2) = (6, 6, 6, 6). That is, the scalar (in this case 3) multiplies each of the components of the vector, individually. This gives us the second property and ensures that our family of vectors is, in fact, a vector space

The final property we will consider is that of size. We know how to compare numbers to each other (for instance, 1 is less than 2). But we cannot compare vectors in this manner. We need to create some notion of a vector's "bigness"; if this "bigness" is represented by a number, we will be able to compare vectors in terms of this "bigness". We call these ideas of size, which allow us to compare vectors, norms. As it turns out, there are many different norms for vectors, and some will make more sense in some situations than others. For example, in our toy car scenario, we can say that a box of cars will be assigned a size, (or norm, symbolised with || . ||), based on the number of cars it contains. That is, the vector (a, b, c, d) will have norm ||(a, b, c, d)|| = a + b + c + d. Alternatively, your nephew may like green cars a lot, but not like yellow cars as much. Then, perhaps, the norm of the same vector could be ||(a, b, c, d)|| = a + 2b + c + d/2. In geometry, one of the most commonly used and most useful sizes of vectors is the square root of the sum of the squares of the components ||(a, b, c, d)|| = √(a^2 + b^2 + c^2 +d^2). (Think of what this would be if there were only two components. Does it remind you of something similar you may have seen before, in geometry or trigonometry?) Once we have selected a norm, we say that the set of all our vectors, with this norm, forms a normed vector space, or simply normed space.


The types of functions which can be vector norms are beyond the scope of this blog, but, in brief, the properties that make a function be a norm are based on how it behaves on the zero vector (a vector in which every component is zero), how it deals with scalar multiples of vectors and with sums of vectors.

Mathematical Philosophy

Perhaps the most fundamental question about Mathematics, as well as the one least explored by mathematicians is the nature of Mathematics. That is, how exactly can one define Mathematics as a field, properly and rigorously? We have rather good definitions about most fields of study. Chemistry is the study of the composition of matter, Biology is the study of living organisms, Medical Science is the study of disease and Sociology is the study of human societies. Mathematics, on the other hand, is a far more difficult field to encapsulate in a simple description like that.

To illustrate this difficulty, consider any simple definition of Mathematics. It cannot be the study of numbers and quantities, since the most fundamental fields of Mathematics (such as Set Theory, Group Theory, Logic and Proof Theory) rarely have much to do with these concepts. Similarly, it cannot be the study of proofs, since application of knowledge, rather than its formulation, is a very large part of Mathematics. Mathematics can be wholly taught without any symbols, but it can also be taught with only symbols. It is both conceptual and descriptive, both theoretical and applied.

So, what is Mathematics? As noted above, a simple definition as a field of study is hard to come up with. But perhaps Mathematics is not a field of study at all. Once we consider this idea, new possibilities arise. Mathematics is, in fact, a philosophy and a way of thinking. It is logic and inference, applied to any abstract or concrete structure, including numbers and quantities. It is the formulation and usage of knowledge about such structures, in a formal language which is shared by all mathematicians. In the end, it is the fruit of all curiosity. Whenever any field is studied in a formal and precise way, whenever a pattern is being sought out and described, whenever new knowledge is sought and created, the methods used are mathematical in nature.

Naturally, the above is too general a definition for a classroom subject; mathematical education is generally far less ambitious in its scope. But next time you are taking a course in Mathematics, or encounter a mathematical question, think of it as a chance for you to learn a new way of thinking; you may enjoy it, despite the amount of apparently irrelevant theory.

Graph Theory (III)

One of the largest topics within Graph Theory is that of Graph Colouring. Formally, a proper graph colouring is an assignment of labels, or "colours" to the vertices of a graph, so that no adjacent vertices share the same colour. The chromatic number of a graph is the smallest number of such labels that can be used to properly colour it. Consider the following assignment problem: A university has to offer certain classes in the next semester. Each specific class will be taught by a specific professor and at a specific time-slot in the day. Naturally, this means that two classes taught by the same professor, must not be offered at the same time; he can not be in two places at once. Furthermore, each class will have specific students who wish to take it. This means that if two classes will be taken by the same student, they also cannot be offered at the same time. The question then becomes, how can we assign the classes? What is the minimum number of time-slots that the university will need to use, to offer all its classes?

This question can be answered by using the idea of Graph Colouring. We draw a graph, as follows: The different classes to be offered, will be our vertices. The classes that cannot be offered together, either because they are taught by the same professor, or because they share a student, are connected together. Then, the given problem is simplified to finding a proper colouring of the graph, where the labels used will represent the time-slots. And, of course, if we want the smallest number of time-slots needed, we must find the chromatic number of the graph.

In practice, this sort of problem is far more complex, as it takes into account multiple sections, classroom availability, number of students expected to need the course and so forth. Also, the restriction on classes sharing a student is generally changed to a restriction on classes expected to share a significant number of students and only offered as single sections. Nevertheless, all problems of resource assignment can be represented as graph colouring problems. In addition to this, many other problems can be studied via Graph Colouring, particularly the all-important class of NP-Complete problems.

The name "colouring" originates in a rather old question: Given a map of a region, how many colours are needed to colour it, if no two adjacent regions (i.e. regions sharing a border) can have the same colour? The surprising answer is "no more than four". The proof for this is extremely long and complicated, which tells us that the field of Graph Colouring is a very deep one indeed.

Creative Thinking

The title of this post may not seem particularly related to Mathematics. Creativity, some might say, is limited to the world of Art. Mathematics, they may continue, is about using specific sets of tools, to solve problems, mechanically. Unfortunately, because of the way that arithmetic and Mathematics in general are taught in schools, this does seem to be the case. But, in reality, it could not be further from the truth.

Consider the following problem: 87 contestants are taking part in a knock-out tournament (perhaps in tennis, or chess; the specifics are irrelevant). The first round, will consist of 23 matches and 41 'byes'. That is, 41 contestants will move to the next round without a match and the remaining 46 will have their elimination matches (why 41 byes?). Then, the tournament will continue normally, with no more byes. How many matches will take place, before the champion can be declared?

This problem can be solved in a few different ways. The mechanical method would be to simply count the number of matches. The first round will have 23 matches. Then 64 players will remain. They will have a total of 32 matches in the second round. Continuing in this way, we find that the total number of matches needed is 23 + 32 + 16... + 1. But there is a more elegant and creative method to find the answer. There are 87 contestants. We can ignore the information on byes and so on. Each match will eliminate exactly one contestant. We need only one contestant to remain. So, 87 - 1 = 86 matches will be required. (This is also the answer we get by adding the number of matches in each round). This second method, is undeniably better. It is simpler, shorter and less prone to error from bad computation. That is where creativity enters the realm of Mathematics. It is often possible to solve a problem in many different ways. But some ways are clearly more creative than others.

The problem with this is that creativity cannot be taught. There is no way of knowing in advance which method will be most suitable to solving a specific problem. A good fundamental knowledge of many different methods can often give one a good idea of how to proceed, but again, this takes personal practice. A student needs to solve many problems, before they are fully familiar with a specific method. Unfortunately, this does not, generally, happen. School systems being what they are, do not create a setting whereby students are required to work through enough problems, to understand the concepts behind them. Worse, the students' natural curiosity for these things is not nurtured enough, for them to want to learn such things.

Mappings and Functions

This is a topic which is generally quite intuitive, but still gives trouble to many students, particularly since it is very rarely taught on its own.

We consider some sets A and B. We take each element of A and assign to it some subset of B. This assignment is called a mapping. More formally, if f is a mapping from A to B, then for each element a in A, there exists some subset B' of B, such that f(a) = B'. To illustrate, consider the set A as your 5 closest friends. Now let B be {tall, short, dark-haired, fair-haired, male, female}. Then you can have a mapping for each of your friends in A, which describes them in terms of the characteristics listed in B. For example, you might have some short, dark-haired female friend, let's call her Angela. Then if we say that f is the description mapping, f(Angela) = {short, dark-haired, female}.

As you can see, mappings are a general way of connecting the elements of one set, with the elements of another set. These sets, of course, will generally not be friends and descriptors. In more general settings, we will have the sets belong to some number system. However, this does not make a difference in what the mappings themselves mean. That is, if we take your 5 closest friends and call them 1, 2, ... 5, then take the descriptors in B and call them, in order, 1, 2, ... 6, we can do the same thing as before. If, for example, Angela is friend 1, we have f(1) = {2, 3, 6}. This statement gives exactly the same information as the one before, i.e., that your friend Angela is short, dark-haired and female.

Naturally, not all mappings will be from or to finite sets. In fact, most interesting mappings only happen in infinite (countable or uncountable) sets. This makes no difference to the definition of the mapping. The idea remains the same: to each specific element of A, we assign some subset of B.

We now move to a specific type of mapping, called a function. A function from A to B is a mapping which assigns to each element of A a subset of B with a single element in it. In other words, it assigns one element of B to each element of A. For example, let's take the integers (... -1, 0, 1, 2, ...) and take the function f(x) = x * x. Then f(0) = 0, f(1) = 1 = f(-1), f(2) = 4 = f(-2) and so on. Note that different elements of A can be assigned the same element from B, but not the other way around. We call A the domain of the function and B the codomain of the function. Furthermore, the set of all elements of B which are assigned to some element of A by f is called the range of f. In the above example, f will never give a negative number. Its range is the positive integers. In addition, we call f(x) the image of x under f.

The reason that functions are important is that, under certain conditions, they can be composed together. That is, if we have 3 sets, A, B and C and two functions, f and g, such that f is a function from A to B and g is a function from B to C, we can define the function h = gf from A to C. As an example, consider the functions f(x) = x * x and g(y) = y + 1. Then we can compose them together to get g(f(x)) = (x * x + 1).

Now the question is, under what conditions can we compose functions like that? The only real requirement is that the range of f is a subset of the domain of g. That is, we need that whatever f gives as its "output" can be plugged into g. If this is not the case, then there will be some f(x) which g can not assign any value to. We then say that g can not be composed with f.

We will now look at more specific families of function. The first such family are the "one-to-one" functions, or "injections". These are the functions for which, if f(x) = f(y), then x = y. That is, if we take two distinct elements in the domain of f, their images in the range of f are also distinct. If we have such a function, then we can also talk about the idea of a pre-image. That is, if f(x) = y, we say that x is the pre-image of y. If f is not on-to-one, we cannot say that, as there might be some other element 2, for which f(w) = y. But the restriction that at most one element can map into y means that the idea of a preimage is possible.

The second family we will consider are the "onto" functions, or surjections. These are the functions for which the codomain is also the range. If we take all the real numbers, f(x) = x * (x - 1) * (x + 1) is an onto function. For any y you pick, there exists some x, for which y = f(x). It is not a one-to-one function, since f(1) = f(0) = f(-1) = 0, but it is onto. Onto functions are important, because if a function f from A to B is onto, it can be composed with any function g with domain B.

Finally, we consider the functions which are both one-to-one and onto. These are known as bijections, or invertible functions. If an f is a bijection, it means that every element in the domain, A, maps to exactly one element in the codomain, B. This means that, going in reverse, we can assign to each element in B its preimage under f on A and make a new function g, which will be the inverse of f. For example, let us take the function f(x) = x + 1. It is both one-to-one and onto, so it is invertible. Since it maps x to x+1, we can simply reverse the mapping to get a function g, which maps x+1 to x. This function g, will be the inverse of f. Clearly, this function, as expected, is g(x) = x - 1.

As you can see, even a function as simple as f(x) = x + 1, belongs to a very special family of functions. This is unsurprising. The functions which are the most powerful and have the most desirable characteristics are generally very restricted. Though we generally think of functions as simple things like x + 1, x/2 and so on, these are very well-behaved functions, and not representative of the majority of functions.