Linear systems and matrices – Serlo

A practical example

Linear dependencies often occur in practice.

Example (Linear dependence in a practical situation)

Imagine a company that launches two types of home fragrance essences (“Spring” and “Exotic”) by mixing two raw materials that the company purchases (violet fragrance and jasmine oil) in different compositions:

• 10kg of the essence “Spring” consists of 7kg of violet fragrance and 3kg of jasmine oil.
• 10kg of the “Exotic” fragrance consists of 2kg of violet fragrance and 8kg of jasmine oil.

The cost of violet fragrance and jasmine oil increases slightly from time to time. We therefore do not commit ourselves to specific values, but rather designate:

• the variable price (in your preferred currency) for 1kg of violet fragrance with $x_{1}$
• and the variable price for 1kg of jasmine oil as $x_{2}$.

The company is now interested in two things:

• How much does it have to pay for the raw materials needed for 10kg of “Spring”?

Answer: $y_{1}=7x_{1}+3x_{2}$

• How much does it have to pay for the raw materials required for 10kg of “Exotic”?

Answer: $y_{2}=2x_{1}+8x_{2}$

Here we have a dependency of two variables $y_{1}$ and $y_{2}$ on two other variables $x_{1}$ and $x_{2}$. We can describe these as the system of equations:

${\begin{aligned}y_{1}&=7x_{1}+3x_{2}\\y_{2}&=2x_{1}+8x_{2}\end{aligned}}$

Alternatively, we can write this dependency as matrix multiplication:

${\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}7&3\\2&8\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}$

Definition

Definition (Linear system)

Let $K$ be a field. A linear system of equations over $K$ with $m$ equations for $n$ variables $x_{1},x_{2},\ldots ,x_{n}$ has the form:

${\begin{aligned}a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}&=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}&=b_{2}\\&\vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}&=b_{m}\end{aligned}}$

where $a_{ij},b_{i}\in K$ for $i\in \{1,2,\ldots ,m\}$ and $j\in \{1,2,\ldots ,n\}$.

The linear system is called homogeneous if $b_{1}=b_{2}=\cdots =b_{m}=0$, otherwise it is called inhomogeneous.

Definition (Matrix of coefficients)

The matrix $A=(a_{ij})\in K^{m\times n}$ is called the coefficient matrix of the linear system from the above definition. The vector $b=(b_{i})\in K^{m}$ is called the right-hand side.

Definition (Solution set of a linear system)

The vector $x={\begin{pmatrix}x_{1}\\\vdots \\x_{n}\end{pmatrix}}\in K^{n}$ is called the solution of the above linear system if $A\cdot x=b$. The set

$L(A,b)=\{x\in K^{n}\mid A\cdot x=b\}$

is called solution set of the system.

Examples

Example

${\begin{aligned}2x_{1}+x_{2}&=5\\x_{1}-3x_{2}&=-1\end{aligned}}$

is a linear system of equations over $\mathbb {Q}$ with 2 equations for the varibles $x_{1},x_{2}$ with coefficient matrix ${\begin{pmatrix}2&1\\1&-3\end{pmatrix}}$ and right-hand side ${\begin{pmatrix}5\\-1\end{pmatrix}}$.

Linear system with a unique solution

Example (Linear system with a unique solution)

We have already distinguished between different “types” of linear systems in the previous chapter.

${\begin{aligned}1x_{1}+3x_{2}+2x_{3}&=0\\-x_{1}-x_{2}&=2\\x_{1}+5x_{2}+ax_{3}=4\end{aligned}}$

This linear system can be represented by the matrix

${\begin{pmatrix}1&3&2&0\\-1&-1&0&2\\1&5&a&4\end{pmatrix}}$

Applying the Gaussian algorithm we obtain:

${\begin{pmatrix}1&0&-1&-3\\0&1&1&1\\0&0&a-4&2\end{pmatrix}}$

We get no solution for $a=4$. Or to put it another way, we are looking for a solution to

$0\cdot x_{3}=0$

Therefore, the system of equations with $a=4$ cannot be solved or has no solution. However, if we fix, e.g., $a=6$, we obtain a unique solution.

${\begin{pmatrix}1&0&-1&-3\\0&1&1&1\\0&0&2&2\end{pmatrix}}$

By multiplying the 3rd line by 1/2 and subtracting the 3rd from the second line or the third from the first line, we then obtain the Gaussian normal form.

${\begin{pmatrix}1&0&0&-2\\0&1&0&0\\0&0&1&1\end{pmatrix}}$

Now we have found a unique solution. Thanks to the Gaussian normal form, we can read it off directly:

$x_{1}=-2,x_{2}=0,x_{3}=1$

Linear system with a non-unique solution

Example (Linear system with a non-unique solution)

Linear systems of equations do not always have a unique solution. To see this, let us consider the following linear system of equations over $\mathbb {R}$.

${\begin{aligned}1x_{1}+3x_{2}+2x_{3}&=1\\x_{1}+2x_{2}+3x_{3}&=1\\2x_{1}+3x_{2}+4x_{3}&=2\\\end{aligned}}$

After running the Gaussian algorithm, we realize that there is no unique solution. The system of equations has an infinite number of solutions, as the system of equations has more variables than equations. Formally speaking, the rank of the matrix is less than $n$, where $n$ is the size of the matrix.

${\begin{pmatrix}1&0&-1&1\\0&1&2&0\\0&0&0&0\\\end{pmatrix}}$

Consequently, the system of equations has no unique solution but infinitely many solutions. We may explicitly convince ourselves that this is true, proceeding as follows:

1. Find a variable that is fixed. For example, set $x_{3}=t$. It doesn't matter which variable is fixed.
2. Solve all other equations depending on the fixed variable.

For the example above, set $x_{3}=t$. Now solve the first equation for $x_{1}$. Thus $x_{1}$:

$x_{1}-x_{3}=1\iff x_{1}=1+x_{3}$

As we set $x_{3}=t\in \mathbb {R}$, we have:

$x_{1}-x_{3}=1\iff x_{1}=1+t$

We now solve the second equation for $x_{2}$.

$x_{2}+2t=0\iff x_{2}=-t$

This process is repeated for all $n$ equations. In this example, $n=3$. Nevertheless, we can stop here, as the 3rd line only consists of zeros. The solution space now has the form

${\mathit {L}}:=\{(x_{1},x_{2},x_{3})\}$

Now we insert the rearranged equations for $x_{1},x_{2},\dots ,x_{n}$. Our $t$ in our example is arbitrary, and since our linear system of equations was realized via $\mathbb {R}$, our $t$ is also from $\mathbb {R}$. This gives us the following solution space:

${\mathit {L}}:=\{(1+t,-2t,t)|t\in \mathbb {R} \}$

We can now represent the solution space more simply. To do so, we factor out $t$. The solution space can then be written as

${\mathit {L}}:=\{(1,0,0)+t(1,-2,1)|t\in \mathbb {R} \}$

A solution space trick

Example (Linear system with a non-unique solution)

As we have already seen, setting up a solution space is not complicated. Nevertheless, it is error-prone. However, there exists a trick that simplifies setting up a solution space. Let's look at the previous solution:

${\begin{pmatrix}1&0&-1&1\\0&1&2&0\\0&0&0&0\end{pmatrix}}$

For this trick, it is important that the matrix is in Gaussian normal form and that the following properties are fulfilled for the matrix:

• The lower left triangular matrix contains only zeros
• First element of a row is a 1 and lies on the diagonal
• All elements in the column above and below are zero

If you try to use this trick on a matrix that does not meet these requirements, the trick will produce an incorrect result!

Proceed as follows:

1. Replace zeros with -1 on the diagonal
2. Each column where the diagonal zero has been replaced with -1 is automatically a solution vector.
3. The vector $b$ is the support vector in the system of equations

Let's see how this trick works on the system of equations considered above.

${\begin{pmatrix}1&0&-1&1\\0&1&2&0\\0&0&-1&0\end{pmatrix}}$

We have replaced the last diagonal zero with -1. This column is our solution vector. Thus, our first (and as we will see later, our only) solution vector is $(-1,2,-1)^{T}$.

The support vector is the vector b, that is, the rightmost column. So the support vector is $(1,0,0)$.

This gives us the solution space:

${\mathit {L}}:=\{(1,0,0)+t(1,-2,1)|t\in \mathbb {R} \}$

Linear systems and linear maps

As the name suggests, there is an important connection between linear systems of equations and linear maps. For example, let's look at the following linear system

${\begin{aligned}&{\text{(I)}}&3v-w&=4\\&{\text{(II)}}&2v&=2\end{aligned}}$

We can combine these two equations into one equation by using the vector notation. The left-hand side is a vector of variables $v,w$, the right-hand side is a constant vector. We can thus write the columns of the system of equations as vectors and obtain

${\begin{pmatrix}3v-w\\2v\end{pmatrix}}={\begin{pmatrix}4\\2\end{pmatrix}}$

The left-hand side depends on the variables $v$ and $w$. These can be described by a function

$f\colon \mathbb {R} ^{2}\to \mathbb {R} ^{2},\quad f{\begin{pmatrix}v\\w\end{pmatrix}}:={\begin{pmatrix}3v-w\\2v\end{pmatrix}}$

This gives us the equation

$f{\begin{pmatrix}v\\w\end{pmatrix}}={\begin{pmatrix}3v-w\\2v\end{pmatrix}}={\begin{pmatrix}4\\2\end{pmatrix}}$

In particular, $f$ is a linear map.

Exercise (Linear map)

Show that $f\colon \mathbb {R} ^{2}\to \mathbb {R} ^{2};f{\begin{pmatrix}v\\w\end{pmatrix}}={\begin{pmatrix}3v-w\\2v\end{pmatrix}}$ is a linear map.

Solution (Linear map)

With $\mathbb {R} ^{2}$, the original and target space of the map $f$ are both vector spaces.

Proof step: Proof of additivity

For all ${\begin{pmatrix}v_{1}\\w_{1}\end{pmatrix}},{\begin{pmatrix}v_{2}\\w_{2}\end{pmatrix}}\in \mathbb {R} ^{2}$ we have

${\begin{aligned}f\left({\begin{pmatrix}v_{1}\\w_{1}\end{pmatrix}}+{\begin{pmatrix}v_{2}\\w_{2}\end{pmatrix}}\right)&=f\left({\begin{pmatrix}v_{1}+v_{2}\\w_{1}+w_{2}\end{pmatrix}}\right)\\[0.3em]&={\begin{pmatrix}3(v_{1}+v_{2})-(w_{1}+w_{2})\\2(v_{1}+v_{2})\end{pmatrix}}\\[0.3em]&={\begin{pmatrix}3v_{1}-w_{1}\\2v_{1}\end{pmatrix}}+{\begin{pmatrix}3v_{2}-w_{2}\\2v_{2}\end{pmatrix}}\\[0.3em]&=f{\begin{pmatrix}v_{1}\\w_{1}\end{pmatrix}}+f{\begin{pmatrix}v_{2}\\w_{2}\end{pmatrix}}\end{aligned}}$

This proves additivity of $f$.

Proof step: Proof of homogeniety

Für alle ${\begin{pmatrix}v\\w\end{pmatrix}}\in \mathbb {R} ^{2},\lambda \in \mathbb {R}$ gilt

${\begin{aligned}f\left(\lambda \cdot {\begin{pmatrix}v\\w\end{pmatrix}}\right)&=f{\begin{pmatrix}\lambda v\\\lambda w\end{pmatrix}}\\[0.3em]&={\begin{pmatrix}3\lambda v-\lambda w\\2\rho v\end{pmatrix}}\\[0.3em]&=\lambda \cdot {\begin{pmatrix}3v-w\\2v\end{pmatrix}}\\[0.3em]&=\lambda \cdot f{\begin{pmatrix}v\\w\end{pmatrix}}\end{aligned}}$

This shows the homogeneity of $f$ and we have thus proven that this map is linear (i.e., a homomorphism).

We have rewritten the above system of equations into an equation for a linear map that results in a constant vector. In other words, the search for a solution to the above system of equations is the same as the search for an image of the right-hand side under $f$. In fact, we obtain the coefficient matrix of the above system of equations as the representation matrix of $f$ with respect to the basis $(1,0)^{T},(0,1)^{T}$.

More generally, for a linear system with $m$ equations and $n$ variables over a field $K$, we find a corresponding linear map $f\colon K^{n}\to K^{m}$ as follows: Let $A\in K^{m\times n}$ be the coefficient matrix and $b\in K^{m}$ the right-hand side of the linear system. Then we set $f(x):=Ax$. This function is linear and agrees with the above construction. Then the search for a solution to the system of equations corresponds to the search for a preimage of $b$ under $f$, that is, an $x$ satisfying $f(x)=b$.