2Linear equations

Modern mathematical terminology may seem abstract, but a lot of it comes from equation solving. We will talk about linear equations in this chapter to motivate the concept of matrices in the next chapter.Linear equations are equations, where the unknowns only appear to the first power. For example, $x^2 + x + 1 = 0$ is not a linear equation in the unknown $x$, since $x$ to the second power ($x^2$) appears in the equation, whereas $2 x - 3 = 1$ is. We may also consider several linear equations with several unknowns, such as $$\begin{aligned} x + y + z &= 3\\ x - y + z &= 1\\ x + y - z &= 1 \end{aligned}\tag{2.1}$$ consisting of three linear equations with the three unknowns $x$, $y$ and $z$. To be completeply precise, a solution to (2.1) is a triple $(x, y, z)\in \mathbb{R}^3$, such that the predicate $$(x + y + z = 3)\land (x - y + z = 1)\land (x + y - z = 1)$$ is true. Do the exercise above, before you evaluate the Sage code below, which uses the dreaded solve function. The solve function should always be used as a last resort.

2.1 One linear equation with one unknown

Very simple rules apply when solving linear equations.Consider as an example the linear equation $2 x - 3 = 1$ in the unknown $x$. Solving this equation amounts to reducing to an expression $x=$ a number. This is called isolating $x$. The process is very mechanical: $$\begin{aligned} 2 x - 3 &= 1\\ &\Updownarrow\\ 2 x - 3 + 3 &= 1 + 3\\ &\Updownarrow\\ 2 x &= 4\\ &\Updownarrow\\ \left(\frac{1}{2}\right) 2 x &= \left(\frac{1}{2}\right) 4\\ &\Updownarrow\\ x &= 2 \end{aligned}$$ If you look closely, you will see that we have used the rules $$\begin{aligned} &a=b\qquad \iff \qquad a + c = b + c\\ &a=b\qquad \iff \qquad t a = t b, \end{aligned}$$ where $a, b, c$ are numbers and $t$ is a number $\neq 0$.

2.2 Several linear equations with several unknowns

The linear equation $2 x - 3 = 1$ has only one unknown with the unique solution $x=2$. If one linear equation has more than one unknown, then it has infinitely many solutions. Consider as an example the linear equation $2 x - 3 y = 1$ with the unknowns $x$ and $y$. Using the procedure as before, we get $$\begin{aligned} 2 x - 3 y &= 1\\ &\Updownarrow\\ x &= \frac{1}{2} + \frac{3}{2} y \end{aligned}$$ Here we are free to choose $y$ in infinitely many ways giving infinitely many solutions $(x, y)\in \mathbb{R}^2$.

2.2.1 Several equations

Several equations with several unknowns also make sense. Consider $$\begin{aligned} x + y &= 3\\ 2 x - 3 y &= 1 \end{aligned}\tag{2.2}$$ Two numbers $x$ and $y$ form a solution $(x, y)\in \mathbb{R}^2$ if both equations are satisfied. From the example above, we know that $$x = \color{blue}{\frac{1}{2} + \frac{3}{2} y}. \tag{2.3}$$ This can be inserted for $x$ in the first equation and we get $$3 = x + y = {\color{blue}\frac{1}{2} + \frac{3}{2} y} + y = \frac{1}{2} + \frac{5}{2} y.$$ Here we end up with one linear equation in one variable $y$. The solution is $y=1$, which is inserted in the equation (2.3) giving $x = 2$. Therefore the solution to the equations is $(x, y) = (2, 1)$.

2.3 Gauss elimination

When solving systems of several linear equations, it is natural to fix one of the equations, isolate an unknown and then insert in the other equations.Let us study this procedure focusing on an example with two equations and three unknowns: $$\begin{aligned} x + 2 y + z &= 8\\ 2 x + y + z &= 7 \end{aligned}$$ In the first equation we isolate $x = 8 - 2 y - z$, which is then inserted into the second equation: $$2 x + y + z = 2(8 - 2 y - z) + y + z = - 3 y - z + 16 = 7 \implies -3 y - z = -9.$$ It makes perfect sense to multiply the first equations by $2$ and subtract from the second equations. This operation gives $$-3 y - z = -9.$$ It is not a coincidence that these two operations give the same result. Multiplying an equation by a number and then adding to another equation is easier to handle than the method of isolating and inserting. We have showed above that they produce the same result. Below is an extended example. The elimination or substitution method for solving systems of linear equations is old and well known. Sir Isaac Newton described in $1720$ the methods eloquently as follows.

And you are to know, that by each Æquation one unknown Quantity may be taken away, and consequently, when there are as many Æquations and unknown Quantities, all at length may be reduc'd into one, in which there shall be only one Quantity unknown.

'The mathematical rockstar Carl Friedrich Gauss used the method to determine the orbit for the asteroid Pallas. The mathematical analysis of the observations lead him to the famous least squares method and a system of six linear equations with six unknowns.The method is known today by the term Gaussian elimination even though Gauss was not the first to introduce it. In fact it appeared already in The Nine Chapters on the Mathematical Art, which is an ancient Chinese mathematics book compiled over several centuries from the 10th century BCE to the 2nd century CE. This book contains several practical problems and their solutions. An example is

There are three categories of corn. Three bundles of the first class, two of the second and one of the third make $39$ measures. Two of the first, three of the second, and one of the third make $34$ measures. Finally one of the first, two of the second and three of the third make $26$ measures. How many measures of graín are contained in one bundle of each class?

'

2.4 Polynomials

Before going further into examples of linear equations we need to introduce (non-linear) functions called polynomials. A polynomial of degree $n$ is a function $f:\mathbb{R}\rightarrow \mathbb{R}$ of the form $$f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0, \tag{2.7}$$ where $a_0, \dots, a_n$ are real numbers and $a_n\neq 0$. We call $a_0, \dots, a_n$ the coefficients of $f$. The degree of the polynomial $f$ is denoted $\deg(f)$. As an example, $$x^3 - 2 x + 17$$ is a polynomial of degree $3$ with $$\begin{aligned} a_3 &= 1\\ a_2 &= 0\\ a_1 &= -2\\ a_0 &= 17. \end{aligned}$$ In addition to the polynomials defined in (2.7) with $a_n\neq 0$, we also view the function $f(x) = 0$ as a polynomial, called the zero polynomial. The zero polynomial does not All its coefficients are zero! have a degree.The set of all polynomials is denoted $\mathbb{R}[x]$, so that for example it makes sense to write $$x^2 - 5 x + 6\in \mathbb{R}[x].$$ It is probably the most natural functions from $\mathbb{R}$ to $\mathbb{R}$ you can come up with. If you look at (2.7) , you will see that the output is formed by using addition and multiplication (by $x$ and selected real numbers). You can compute with polynomials treating the variable $x$ as a number obeying the rules in Proposition 1.12 . For example, $$(3 x^2 + 2 x + 1) (2 x + 1) = 6 x^3 + 7 x^2 + 4 x + 1.$$ In that sense polynomials obey the same arithmetic rules as numbers. A fundamental difference is the $x$ is a placeholder or a smbol where you can insert a number from $\mathbb{R}$. In general a polynomial of degree $m$ times a polynomial of degree $n$ is a polynomial of degree $m+n$.In the sage window below we encounter for the first time the sympy library. The input format and commands for handling polynomials should be clear from the context. You have already seen polynomials of degree one. They have the form $$f(x) = a x + b,$$ where $a$ and $b$ are real numbers and $a\neq 0$. Similarly polynomials of degree two are called quadratic polynomials. They look like $$f(x) = a x^2 + b x + c,$$ where $a, b$ and $c$ are real numbers and $a\neq 0$. To get a feeling for the behavior of polynomials you should experiment in the sage window below. Try varying the degree and the coefficients of the polynomial in the plot. Also adjust the plot interval for the right view.

2.4.1 Polynomial division

Division is sometimes referred to as long division when focusing on the method for division. Let us look at the situation for integers first.The remainder of $14$ divided by $4$ is $2$, since $$14 = 3\cdot 4 + 2.$$ Here the remainder $2$ is strictly less than the divisor $4$.For polynomials we have a similar situation, where the degree is taken into account. For example, the remainder of $x^3 + x + 1$ divided by $x^2 + x + 1$ is $x+2$, since $$x^3 + x + 1 = (x-1)(x^2 + x + 1) + (x+2). \tag{2.8}$$ Here the degree of the remainder $1$ is strictly less than the degree of the divisor $2$.The Python library sympy contains a wealth of functions for symbolic mathematics. In the window below, it is shown how the polynomial division (2.8) is computed using the Polynomial Manipulaton section of the sympy documentation. The (division) algorithm for carrying out (long) division of polynomials is explained by an example in the video below. The general result about division of polynomials is given below.

2.4.2 Roots of polynomials

A real number $\alpha\in \mathbb{R}$ is called a root of the polynomial $f(x)\in \mathbb{R}[x]$ if $f(\alpha) = 0$. This is a very fundamental definition. It is mirrored beautifully in the following result. A quadratic polynomial $$a x^2 + b x + c$$ has at most two roots given by the formula (one root for $+$ and one for $-$ in $\pm$ below) $$\frac{-b\pm \sqrt{b^2 - 4 a c}}{2 a}, \tag{2.11}$$ if its discriminant $b^2 - 4 a c$ is $\geq 0$. For polynomials of degree three (cubic polynomials) there is a formula, but these days nobody remembers it. Also for polynomials of degree four (quartic polynomials) there is a formula. But for polynomials of degree five (quintic polynomials) and up, one can prove that a formula cannot exist!An exceedingly important result is quoted and proved below: the degree of a polynomial is an upper bound for its number of roots. It might happen that a polynomial of degree $n$ has precisely $n$ roots, but it could have less or even no roots: the polynomials $$x^2 + 1, x^4 + 1, x^6 + 1, \dots$$ have no roots, whereas for example $$x^2 - 2 x + 1$$ is a quadratic polynomial with only one root. However polynomials of degree $1, 3, 5, \dots$ always have at least one root.The proof of this result is beyond our scope now and will have to wait for tools from analysis (Chapter 5).

2.5 Applications of linear equations to polynomials

A line in the plane is given by its equation $y = a x + b$, where $a$ is the slope and $b$ is the intersection with the $y$-axis. Two lines in the plane are either parallel or intersect in a single point. Through two (distinct) points $(x_1, y_1)$ and $(x_2, y_2)$ with $x_1\neq x_2$ passes a unique line You can find the equation for this line by solving two equations with two unknowns $a$ and $b$: $$\begin{aligned} x_1 a + b &= y_1\\ x_2 a + b &= y_2 \end{aligned}$$ We might as well apply Gauss elimination to solve this system. First we subtract the second equation from the first. This gives $(x_1 - x_2) a = y_1 - y_2$. Therefore $$a = \frac{y_1 - y_2}{x_1 - x_2}.$$ Inserting this $a$ in the first equation we get $$b = \frac{x_1 y_2 -x_2 y_1}{x_1 - x_2}.$$ We can also in a quite explicit way just write $$y = f(x) = y_1 \frac{x - x_2}{x_1 - x_2} + y_2 \frac{x - x_1}{x_2 - x_1}. \tag{2.14}$$ The function $f(x)$ in (2.14) is a polynomial of degree one with $f(x_1) = y_1$ and $f(x_2) = y_2$.In almost the same way we may find a unique quadratic polynomial $$y = a x^2 + b x + c$$ through three points $(x_1, y_1), (x_2, y_2)$ and $(x_3, y_3)$ with distinct $x$-values: Here we end up with three linear equations in the unknowns $a, b$ and $c$: $$\begin{aligned} x_1^2 a + x_1 b + c &= y_1\\ x_2^2 a + x_2 b + c &= y_2\\ x_3^2 a + x_3 b + c &= y_3 \end{aligned}\tag{2.15}$$ It is not immediately obvious that this system of equations has a solution. But watch the following trick evolve.We may explicitly construct the quadratic polynomial passing through the three points as $$\begin{aligned} y = f(x) = &y_1 \frac{(x - x_2)(x-x_3)}{(x_1 - x_2)(x_1-x_3)} + y_2 \frac{(x - x_1)(x - x_3)}{(x_2 - x_1)(x_2-x_3)}\\ &+ y_3 \frac{(x - x_1)(x - x_2)}{(x_3 - x_1)(x_3-x_2)} \end{aligned}\tag{2.16}$$ Take a moment and verify that $f(x_1) = y_1, f(x_2) = y_2$ and $f(x_3)= y_3$. This also proves that the system of equations in (2.15) can be solved. The natural generalization is that there exists a unique polynomial of degree $\leq n$ passing through $n+1$ points $(x_1, y_1), \dots, (x_{n+1}, y_{n+1})$ with distinct $x$-values.The rather miraculous trick above in (2.16) is called Lagrange interpolation and can be generalized to polynomials of arbitrary degree. Below is an example of five points defining a unique polynomial of degree four.

2.5.1 The magic of Lagrange polynomials

Example 2.34 can be generalized: suppose we have $n$ numbers $$x_1, x_2, \dots, x_n. \tag{2.17}$$ Then these numbers give $n$ polynomials each of degree $n-1$: $$L_i(x) = \frac{1}{C_i} (x-x_1) \cdots (x-x_{i-1})(x-x_{i+1}) \cdots (x - x_n),$$ where $C_i = (x_i-x_1) \cdots (x_i-x_{i-1})(x_i-x_{i+1}) \cdots (x_i - x_n)$ for $i = 1, \dots, n$.The polynomial $L_i(x)$ is called the $i$-th Lagrange basis polynomial associated to the $n$ numbers $x_1, \dots, x_n$. It satisfies $L_i(x_1) = \cdots = L_i(x_{i-1}) = 0$, $L_i(x_i) = 1$ and $L_i(x_{i+1}) = \cdots = L_i(x_n) = 0$ i.e., $L_i(x)$ is equal to zero evaluated at all of the numbers $x_1, \dots, x_n$ except at $x_i$ where it evaluates to $1$.The Lagrange basis polynomials allow us to construct a polynomial $f$ of degree $\leq n$ through $n+1$ points $(x_1, y_1), \dots, (x_{n+1}, y_{n+1})$ i.e., a polynomial $f$ such that $$\begin{aligned} f(x_1) &= y_1\\ &\vdots\\ f(x_{n+1}) &= y_{n+1} \end{aligned}$$ simply as $$f(x) = y_1 L_1(x) + \cdots + y_{n+1} L_{n+1}(x).$$ However, $f(x)$ does not have to have degree $n$. For example, it could come out as a line through three points $(x_1, y_1), (x_2, y_2)$ and $(x_3, y_3)$ (see Exercise 2.33 ).

2.6 Shamir secret sharing

Lagrange interpolation is used in cryptography in Shamir's secret sharing. Secret sharing is important in many practical situations. Here is an example quoted from Wikipedia:

A company needs to secure their vault's passcode. They could encrypt it, but what if the beholder of the secret key is unavailable or turns rogue?

One needs to distribute the secret. This is where SSS comes in. It can be used to encrypt the vault's passcode and generate a certain number of shares, where a certain number of shares can be allocated to each executive within the company. Now, only if they pool their shares can they unlock the vault. The threshold can be appropriately set for the number of executives, so the vault is always able to be accessed by the authorized individuals. Should a share or two fall into the wrong hands, they couldn't open the passcode unless the other executives cooperated.

'The mathematics that takes care of this is surprisingly simple. Suppose the secret is the number $a_0$. Then we construct the polynomial $$f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_m x^m \tag{2.19}$$ for some other numbers $a_1, \dots, a_m$. We know that this polynomial is uniquely given by its values in $m+1$ distinct numbers (see Remark 2.25 ). So if there are $n$ trusted people we could distribute the shares $$(1, f(1)), (2, f(2)), \dots, (n, f(n))$$ to them. Here we suppose that $n > m$. In this setting, if there are less than $m+1$ of the people present they cannot open the vault. If $m+1$ or more people are present they can reconstruct the polynomial in (2.19) , find the secret code $a_0$ and open the vault.

2.7 Fitting data

Given a data set $$\mathcal{D} = \{ (x_1,y_1), (x_2,y_2), \dots, (x_n, y_n) \}$$ one would often like to find a model (i.e. some function) that describes the data well. With Lagrange interpolation we can find a polynomial $f$ fitting the sample data $\mathcal{D}$ perfectly, i.e. satisfying $f(x_i) = y_i$ for $i = 1, 2, \dots n$. Is $f$ an optimal model? For the given data set it seems so, but we have been a bit imprecise in formulating the goal of a model.Actually, we are not very interested in modeling the data at hand with extreme precision. What we want is a model that fits new data well. Let us look at a concrete example.Consider the data set $$\begin{aligned} \mathcal{D} = \{ {}& (0, 0.06), (0.5, 0.33), (1, 0.56), (1.5, 1.35), (2, 1.48), (2.5, 1.15), \\ &(3, 1.45), (3.5, 1.12), (4, 0.68), (4.5, 0.22), (5, -0.10) \} \end{aligned}$$ The data points $(x_i,y_i)$, $i=1,2,\dots,11$, were generated as $(x_i, p(x_i) + \epsilon_i)$ where $p(x) = -0.2 x^2 + x$ is a quadratic polynomial and $\epsilon_i \in [-0.4,0.4]$ is a random number to simulate noise. The polynomial $p$ is the best possible model for unknown data as there will always by noise that can not be modeled. In real life $p$ is what needs to be modeled based on the available data.In the figure below is a fit with a degree $2$ and degree $10$ polynomial respectively. As we see, the degree $2$ polynomial is pretty close to the target $p$ compared to the degree 10 polynomial that nevertheless fits the data $\mathcal{D}$ perfectly. Generally a simple model is preferred over a complex, as the latter will have a tendency to fit noise. This phenomenon is called overfitting and is an extremely important topic.An interactive version of this illustration with a little more bells and whistles can be found here. In later chapters we will see how the degree two polynomial fit was obtained. This is a nice example of a convex optimization problem.