Linear Algebra (II)

In my previous post, I described briefly the idea of vectors, as well as certain properties that vectors have. You may recall that vectors are constructs which store information about different variables (for instance, how many toy cars of each colour a child has in their collection). Sometimes, however, we may wish to collect information which is stratified in two ways, rather than one.

In the toy car example, we may further wish to divide cars not only by colour, but also by size. For instance, we could still have red, green, blue and yellow toy cars, but perhaps we wish to further divide them into "large" and "small" ones (whatever these descriptors mean). Then we would have not four, but eight categories, as we would have large red cars, small red ones, large green ones, small green ones and so on. We could easily say that we will simply use vectors with eight entries, but in a sense, this would eliminate some of the structure we have; this is where matrices come in.

A matrix is very simply a rectangular array of numbers. (Note that a vector is also such an array, but with one dimension of the array only being one entry long). Using the toy car example again, we could have:

	Red	Green	Blue	Yellow
Large	1	2	0	1
Small	2	2	1	0

in which case, we can see that there are three red cars, of which one is large and two are small, and so on. Furthermore, if we have established what the rows and columns represent, we can do away with the headings and simply have the matrix:

1	2	0	1
2	2	1	0

Clearly, matrices are an extension of vectors, conceptually. So, we may be interested in thinking about how the properties of vectors translate to matrices. Suppose we have two matrices with the same dimensions (i.e. the same number of rows and the same number of columns). Then, we can add them, just as we added two vectors (of the same size) together. And since we have (presumably) established in advance what each entry represents, such an addition makes sense. In the toy car example, buying a new car of each colour and size corresponds to adding a matrix with two rows and four columns and whose entries are all 1s. Similarly, scalar multiplication extends naturally to matrices, as well. Multiplying a matrix A by some scalar k, is the same as multiplying each entry of A by k.

Then, we have the idea of norms. As it happens, matrices also have norms, which work in pretty much the same way as those for vectors. We could, for example, add the absolute values of each of the entries of a matrix, just as we would with a vector. In essence, we can treat a matrix as a vector, by simply ignoring the structure of rows and columns and using a vector norm. Additionally, we can get other types of norms for matrices, which do take their structure into account. For instance, we could take the sums of absolute values for each column and say that the norm of the matrix is the largest sum. In the toy car example above, this corresponds to finding the colour with the most cars; the norm will be the number of cars of that colour. As with vectors, we will not go into norms too deeply here, to keep things simple.

Finally, we can see how matrices interact with vectors. Clearly, Matrices and vectors cannot be added together, since they are dissimilar structures, but perhaps we can define a type of multiplication, which will be valid for matrices and vectors. To do so, we consider the following: Suppose that, in the toy example, we wish to find out how many large and how many small cars there are. Clearly, we can do this very easily, by adding the numbers along each row. Then we can see that there are 1 + 2 + 0 + 1 = 4 large cars and 2 + 2 + 1 + 0 = 5 small ones. But this is the same as taking the entries of each row, (w, x, y, z), multiplying each of them by 1 and then adding them, to obtain 1w + 1x + 1y +1z. And this is precisely one type of multiplication between matrices and vectors. That is, we multiply our toy car matrix by the vector (1, 1, 1, 1), precisely by taking those sums. This may seem like a silly example, but it can be extended. What if we really like green cars and hate yellow cars? We could assign a weight to each colour and get a vector, e.g. (1, 2, 1, 0). Now let's try multiplying our matrix by this vector, as we described. For the first row, we get 1*1 + 2*2 + 1*0 + 0*1 = 5 and for the second one, we get 1*2 + 2*2 + 1*1 + 0*0 = 7, or the vector (5, 7). (We can think of this as the weighted vector of how much we like the large and small toy cars in the set, respectively.)

This is precisely how matrix-vector multiplication is performed. For each row of the matrix, we multiply each entry with the corresponding entry of the vector, then add these together. This gives us a new vector, which is the product of the matrix and vector we started with. Of course, for this to make sense, the dimensions need to match up. That is, to multiply the matrix A by the vector x, we need the vector x to have as many entries as A has columns. Then, the vector b = Ax will have as many entries as A has rows. This type of multiplication is called post-multiplication. We can also pre-multiply a vector with a matrix. In this case, we use the columns of the matrix instead. So, to pre-multiply the vector p with the matrix A, p must have as many entries as A has rows. Then the resulting vector c = pA will have as many entries as A has columns. Furthermore, since a vector is simply a matrix with only one row (or column), this also allows us to multiply vectors together, as long as their dimensions match.

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.