Introduction to systems of linear equations

There is one algebraic tool in math, which is absolutely requisite in pretty much every chapter of applied or theoretical studies. Whether you investigate big datasets, study some abstract algebra and vector calculus, or do simple practical calculations, you will probably be solving some systems of linear equations (SLE). These are generalizations of the idea of linear equations with one unknown variable (e.g. $3x + 5 = 0$). They allow us to find a set of unknown variables using combinations of different relations between them. The word "linear" here means, in some sense, that these relations are the simplest possible. However, that doesn't entail that SLEs are a very limited tool, on the contrary, there are a lot of non-linear problems that could be solved approximately with the help of SLE, moreover, there are many problems that could be solved only in this manner.

Systems of linear equations in real life

Let's say you live and work in Liverpool, and you get paid in pounds of sterling. At the end of the month, you find out that you have £100 unspent. You decide to keep savings in dollars. Knowing that $1 equals £0.83, what amount of dollars can you get for your pounds? That is an easy question! Denoting the required sum in dollars by $D$ you obtain the following equation$0.83 D = 100.$Obviously, you are going to get something around $120.5:$D = \frac{100}{0.83} \approx 120.5.$But what if you want to diversify your savings? For example, you want to convert one part of them to dollars ($1 = £0.83), another part to euros (€1 = £0.85) and keep the remaining in pounds. Let's denote the number of dollars you'll have again with $D$, the number of euros $E$ and the number of remaining pounds $P$. These three values are related by the following equation

$0.83D + 0.85 E + P = 100.$Note that now there are not one but three unknowns in this equation and there are a lot of ways to choose $D$, $E$, and $P$, such that they satisfy this equality. For example, if you'd have $40, €30 and £41.3 then$0.83 \cdot 40 + 0.85\cdot30 + 41.3 = 100.$But in the same way, you could have $25, €45, and £41, because, again,$0.83\cdot25 + 0.85\cdot45 + 41 = 100.$To be more specific, you decide that you want to split the money so that the amount you transfer in dollars and euros is three times the amount you leave in pounds. In addition, you decide that you will buy dollars and euros for the same amount of pounds. Now besides the previous equation, we can write two more (we will write them together with a curly brace):

You can check that values $D = 45.2$, $E = 44.1$ and $P = 25.0$ satisfy to all these three conditions with good accuracy.

The main tool we've just used here dealing with currency conversions are so-called linear equations of multiple variables and their systems. The key idea here is, that having some unknowns and some relations between them, we can write down a set (system) of equations from which, as we discuss later, we can find some of those unknowns. Now, without further ado, let's move on to precise definitions.

Main definitions

As we saw earlier, the relations were rewritten as equations, which only contained sums and differences of unknown variables with some numerical coefficients. Summarizing these facts we are giving the following definition: the formal equality$a_{1}x_{1} + a_{2}x_{2} + \dots +a_{n}x_{n} = b,$where $a_{1},a_{2},\dots,a_{n},b$ are some certain numbers (for example, real or complex), and $x_{1},x_{2},\dots,x_{n}$ are the set of $n$ unknown variables, is called a linear equation of $n$ variables $x_{1},x_{2},\dots,x_{n}$.

We often say that this equation gives a linear relation between variables $x_{1},x_{2},\dots,x_{n}$. The most elementary way to think about the word "linear" in above-mentioned definitions is to note that all the variables $x_{1},x_{2},\dots,x_{n}$do not enter the equation in any powers other than the first (e.g. $x_{1}^2-x_{2}=0$ is not a linear equation).

Note that variables could be denoted with any symbols as long as it is established that they correspond to unknown variables. For example, $5y_{1}-4y_{2}=5$ is a linear equation of two variables $y_{1}$ and $y_{2}$, $-\frac{3}{2}x + \sqrt{3}y-z + \sqrt{\frac{2}{3}}t=-\frac{1}{\sqrt{2}}$ is a linear equation of four variables $x,y,z$, and $t$, the above-mentioned $0.83D + 0.85 E + P = 100$ is a linear equation of three variables $D,E$, and $P$.

Let us consider an equation $a_{1}x_{1}+a_{2}x_{2}+\dots+a_{n}x_{n}=b$. The set of numbers (not variables!) $\chi_{1},\chi_{2},\dots,\chi_{n}$, such that $a_{1}\chi_{1} + a_{2}\chi_{2} + \dots + a_{n}\chi_{n} = b$ is called the solution of this equation. In other words, the solutions is the set of numbers $\chi_{1},\chi_{2},\dots,\chi_{n}$ such that substituting them to equation instead of variables $x_{1},x_{2},\dots,x_{n}$ gives the true equality. Usually, the solution is written down like this $(\chi_{1},\chi_{2},\dots,\chi_{n})$. Unlike a linear equation of one variable, the equation of multiple variables usually could have more than one solution.

For example, $(5,5)$ and $(1,0)$ are both solutions of equation $5y_{1} - 4y_{2} = 5$ (because $5\cdot 5 - 4\cdot 5 = 5$ and $5 \cdot 1 - 4\cdot 0 = 5$). In fact, for any particular substitution $y_{1} = \gamma$ there exists substitution $y_{2} = 5(\gamma - 1)/4$ such that, obviously, $\left(\gamma,\frac{5(\gamma - 1)}{4}\right)$ is a solution of this equation (as $5\gamma - 4\cdot\frac{5(\gamma - 1)}{4} = 5$). And as $\gamma$ is any number, then the equation $5y_{1} - 4y_{2} = 5$ have infinitely many solutions. To avoid messy notation, a set of variables is usually identified with a solution (e.g. we could say that $(y_{1},y_{2})$ is a solution of $5y_{1} - 4y_{2} = 5$), but it is useful to remember that formally these are still different concepts.

The last thing to say about linear equations themselves is that we will call linear any equation that could be reduced to the mentioned form by elementary manipulation (such as adding to each side of the equation the same combinations of variables and numbers, reduction of similar terms and multiplying both sides of the equation by the same number). For example, $5y - 4xz + 3y - z - 5 = -4xz+6x - 7$ is in fact linear equation, as

$\underline{5y} - \cancel{4xz} + \underline{3y} - z - 5 = - \cancel{4xz} + 6x - 7,\\ 8y-z-5=6x-7,\\ -6x+8y-z = -7 + 5,\\ -6x+8y-z = -2.$Two equations that have the same set of solutions are called equivalent. Obviously, $5y - 4xz + 3y - z - 5 = -4xz+6x - 7$ and $-6x+8y-z = -2$ are equivalent.

Now the set of $m$ linear equations written in the following way

is called the system of linear equations of $n$ variables $x_{1},x_{2},\dots,x_{n}$. Here as previously $a_{ij}$ ($i$ is a natural number from $1$ to $m$, $j$ is a natural number from $1$ to $n$) are some particular numbers. A set of numbers $(\chi_{1},\chi_{2},\dots,\chi_{n})$ is called a solution of this system if it is a solution of all the equations in it.

Let us look at some examples. All the following systems are systems of linear equations

Here we again adhere to the convention that all equations that reduce to linear are as well linear. We also mean that if a variable is not explicitly included in any of the equations of the system, then it is included in it with a coefficient of 0. Let us rewrite the last system to illustrate it:

The number of solutions and the geometrical interpretation of SLEs

Note that $(1,3)$ is a solution of the system

Furthermore, we can show that this is the unique solution of the system.

This fact could be easily illustrated by the geometrical meaning of linear equations. For instance, the set of solutions of a linear equation of two variables is a set of some pairs (x,y), and they could be interpreted as points on a plane. Any linear equation of two variables defines a straight line on a plane (we will leave this fact without proof here, however it is good to ponder this statement because it allows to look at the word "linear" from a new perspective). As you can draw only one straight line, through any two points on a plane, you could find two particular solutions of each equation in your system and draw those lines, which correspond to them. For example, for the above-mentioned system: $3x - 2y + 3 = 0$ the solutions are $(-1,0)$ and $(3,6)$. The line which goes through these points looks like this:

Let's in the same way draw a blue line for the second equation:

The point of the intersection of these two lines is a solution because the coordinates of these points are the only ones that satisfy both equations. Thus, $(1,3)$ is indeed the unique solution of this system.

The increase of the number of conditions on variables acts as you are fixing one of the manifold possible solutions. Intuitively it seems that if the number of unknowns matches the number of equations in the system, the solution has to be unique. This is not entirely true, although close to the truth. However, here we only demonstrate a couple of counterexamples, such as systems

On the one hand, it is easy to see that the first system has solution $(1,1)$, but also $(3,0)$, in fact, it has infinitely many solutions. On the other hand, the second system does not have any solutions. You can think of the first system as if the two lines defined by its equations are the same, therefore every point on them is a solution. And the second system gives you two parallel lines, which don't intersect at all.

The problem of solving an arbitrary system of linear equations is actually not as difficult as it might seem, furthermore, the geometrical interpretation could be generalized to higher dimensions. However, now let us look at some more particular examples of applications.

Some examples of SLEs applications

Consider some process, which is described with the following model dependence $f(t) = at^2+bt +c$ (for example, this could be the dependence of the coordinate of the thrown body on time). As far as we know the form of dependency, we don't know the values of $a$, $b$, $c$. But after the series of 3 experiments, we know that $f(0) = 6$, $f(1)= 2$, $f(2) = -12$. Now we can determine $f(t)$ using SLE.

Simplifying:

It is not difficult to check, that $a = -5$, $b = 1$, $c = 6$ gives a unique solution, therefore our process is described by function $f(t) = - 5t^{2} + t + 6$. The problem we have just solved is called the search for an interpolation polynomial. In general, many interpolations and regressions are searched using SLE solutions. For example, the most famous linear regression method, which is the least squared method, is based on a solution of one specific SLE.

Let's look at another example, which will allow you to better understand the geometric meaning of SLEs. Imagine we have a coordinate plane and two straight lines drawn on it. The first line goes through points $(-2,5)$ and $(4,3)$, and the second one goes through points $(-1,0)$ and $(-2,-2)$. The question is, how to find the intersection point of these lines (if there is such a point)?

To solve this problem, first of all, we need to find the equations, which correspond to the lines. In fact, such an equation exists for any straight line on a plane. The first line goes through $(-2,5)$ and $(4,3)$, therefore if we find a linear equation such that both of those pairs of numbers are its solutions, this equation will uniquely determine the straight line we are interested in (as two distinct points on a plane define a particular straight line). The same is true with the second line.

There is a method that allows you to uniquely determine the equations in such a problem. This method, by the way, is based on solving SLE, however, since we have not yet discussed specific algorithms for solving SLEs, here we propose to guess such equations. They are $x + 3y - 13 = 0$ (for the first line) and $- 2x + y - 2= 0$ (for the second).

Of course, we cheated a little bit, extraditing the equations, but at least we can check if they are correct. Let's carry out such a check for the first equation. Points $(-2,5)$ and $(4,3)$ have to satisfy it. The following calculations confirm this fact.

It is better to carry out similar calculations for the second straight line. Now knowing both of the equations we can construct the following SLE:

The solution of this equation is $(1,4)$. Now, if you think about it, as $(1,4)$ is a solution of both of those equations, that means that it lies on both of these lines, which is possible only if it is their intersection. Thus $(1,4)$ is the required point.

Conclusion

• Solving SLE is a technique that is absolutely necessary for everyone whose life is somehow connected with mathematics or calculations.

• An equation is called linear if it could be reduced to the form $a_{1}x_{1}+a_{2}x_{2}+\dots+a_{n}x_{n} = b$.

• A set of linear equations of the same variables $x_{1},x_{2},\dots,x_{n}$ is called a system of linear equations.

• Any set of numbers that satisfies every equation in the system is called a solution of the system.

• One SLE could have more than one solution or could have no solutions at all. This is also true in a particular case when SLE contains only one equation (in this case it is just a linear equation).

• Linear equations of two variables describe straight lines on a plane. Using SLEs, we can find the common points of these lines.