SIMC2.0 Simplified: Fundamental Concepts of the Challenge
by Lye Ri-Yen, Zachary Seah
Illustrations by Ariel Joshua Lau
With SIMC2.0 underway, we’re sure that we’re not the only ones wondering about the concepts that the contestants are actually tackling with. So, here is Epigraph’s best attempt to understand the complex mathematical and computational ideas behind the challenge and break it down into simple terms that everyone can understand. This is SIMC2.0 Simplified, and we hope you learn something new.
Vectors and Matrices
Vectors and matrices are core concepts of math. To begin with vectors, they involve two parts: their magnitude and their direction. The magnitude of a vector is simple – it’s just a number telling us how big or small the vector is. The direction is also quite simple, being a direction in space.
When you combine the two, you get something like an arrow, which is also the typical visual representation of a vector. The length of the arrow is the magnitude of the vector, and the direction in which it points, indicated by the arrowhead, is the direction of the vector. Vectors are thus an easy way to represent a position, or a data point.
Matrices are slightly more complicated, but put simply, they are a way of storing lots of related numbers, which makes them very useful in keeping data. A matrix is a rectangular grid of numbers, which often share some correlation across the rows and columns. Think of it like a Microsoft Excel spreadsheet; you have rows and columns, and numbers in each row share some relationship – same for the numbers in the columns. Matrices are essentially a simple manner of data storage. Vectors can also be represented as matrices with only one column. Importantly, this allows for vectors to be multiplied by matrices, essentially allowing the matrix to transform the vectors, giving us a new vector as a result.
What else needs data storage? Transformations! Storing more numbers than a vector can, matrices can represent transformations made to positions or data points. In a transformation, you need to account for both the old system of data recording and the new one – exactly what a matrix can hold!
Eigenvectors and eigenvalues
To understand the eigenvector and eigenvalue, one must first understand the meaning of “eigen”. Its closest translation from German to English is “own”, or “individual”. Here, it is a prefix that describes a special type of vector.
An eigenvector describes a vector in relation to a matrix. For a vector to be an eigenvector of our matrix, when the two are multiplied, the direction of the vector must not change. That’s it – the magnitude may change in any way, but if the direction remains the same, our vector is an eigenvector of our matrix. And when the magnitude changes, the amount it changes by is the eigenvalue. The eigenvalue of an eigenvector is simply how much bigger or smaller the vector becomes without changing its direction when multiplied by a matrix.
Markov matrices
A Markov matrix (named after the Russian mathematician Andrey Markov) is a special type of matrix. If you recall, we stated earlier that a matrix is a way of storing data. When that data is the set of states a scenario could be in, with each state having a chance to lead into other states, that matrix of chances of changing into other states is known as a Markov matrix.
Importantly, one must also take note of the Markov property. This property tells us that the next state the scenario will take is only dependent on the chance of entering it from the current state. It is independent of the history of the scenario. So, if a matrix contains all the possible states of a scenario and its chances and process of changing states obeys the Markov property, then congratulations! You’ve just found yourself a Markov matrix.
Power method
Building on what we covered earlier, a matrix acts as a “set of instructions” that transforms a vector by scaling, stretching, rotating, or reflecting it. The power method is an algorithm used to find the dominant eigenvector (eigenvector with the largest value) in a square matrix.
Why is the dominant eigenvector important? It corresponds to the distribution of the states at equilibrium: any small changes to the data will produce a change which restores the data towards the equilibrium. This allows us to predict the long-term evolution of a pattern in data!
How does the Power Method work?
- Pick an arbitrary, non-zero vector. This can be any random vector.
- Multiply this vector by the matrix.
- Scale down the resulting vector by dividing both x and y components by the largest value in the vector. This prevents it from growing infinitely large during repeated multiplication.
- Put the resulting scaled vector back into the same matrix.
- After many iterations of this Steps 1-4, the vector you get will gradually settle into a single, stable direction where the ratio of the x value (horizontal component) to the y value (vertical component) of the vector does not change, even when subsequently put through the matrix. This final direction is the dominant eigenvector.
Why does the Power Method work?
When you are dealing with a matrix (whose dominant eigenvector you are trying to find), any arbitrary vector can be broken down and expressed as a sum of that matrix’s own eigenvectors. When you apply the matrix to that vector, each eigenvector component is scaled by its own eigenvalue without changing its direction. Therefore, components with larger magnitudes grow in magnitude much faster than those with smaller magnitudes. Eventually, the dominant eigenvector with the largest magnitude would drown out the other eigenvectors’ directional components, forcing the vector to align entirely with the dominant eigenvector.
Singular value decomposition
Singular value decomposition is a way of breaking down any matrix into three separate matrices that represent different characteristics of the original matrix.
Suppose A is the matrix you want to decompose, it can be represented by the formula:
A=U Σ VT
What do the 3 matrices represent?
U: This matrix identifies patterns along the rows of the matrix.
Σ: This matrix is a diagonal matrix containing the singular values of the matrix, which are non-negative square roots of the matrix’s eigenvalues. It acts like a “ranking” of how important each pattern in the matrix is.
VT: This matrix identifies patterns along the columns of the matrix.
Using SVD breaks down any complex matrix into these 3 components, allowing you to visualise it and find the most important patterns more easily.
Real world applications
After all these abstract mathematical definitions and processes, this begs the question: under what circumstance do such theoretical (and mildly intimidating) concepts distil into the real world?
Matrices and vectors are everywhere in our daily lives – from the mobile device you are currently reading this on, to the image processing that allows us to store and transmit photos digitally.
Matrices provide a powerful way to organise and manipulate large datasets. They are therefore vital to the Information Age we live in today. Almost every modern computational system relies on them in some form. Some interesting applications of matrices include data encryption, digital animation, or even seismic surveys of the Earth’s subsurface!
In the end, the concepts we explained here are just a few of the many ways mathematicians process data and find the patterns in a dataset. While this may be a very cursory introduction to matrices and vectors, we hope that you learned something and can better appreciate the SIMC2.0 Endeavour Challenge!