Note 1
System of Linear Equations
One of the most important applications of matrices would be in linear systems of equations. With the ideas on matrices, we can open our third eye when viewing systems of linear equations. This note is dedicated to matrices in linear equations, Gaussian Elimination, and LU decompositions.
1.1 Basics and Intuitions
As always, let’s get started with fundamental definitions, concepts, and intuitions that will be used throughout.
First, I am pretty sure most of you are aware of what a system of equations is. However, because it is always nice to formally state our understanding, here is the definition of a linear system of equations.
Definition 1.1.1
A system of linear equations is composed of linear equations, or equations whose highest degree is \(1\). A system of \(m\) equations and \(n\) variables adhere to the following forms where \(a_{ij}\) and \(b_{i}\) are known quantities. \begin{align*} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + \cdots + a_{1n}x_n &= b_1 \\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + \cdots + a_{2n}x_n &= b_2 \\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 + \cdots + a_{3n}x_n &= b_3 \\ \vdots \qquad \qquad & \\ a_{m1}x_1 + a_{m2}x_2 + a_{m3}x_3 + \cdots + a_{mn}x_n &= b_m \end{align*}
Below is an example of a system of linear equations. \begin{align*} x + 2y + 3z &= 4 \\ -x + 3y + 2z &= 5 \end{align*}
Notice that all equations above are linear, meaning, their degrees are \(1\). Now, what does it mean to find a solution to such systems?
Definition 1.1.2
A solution to a system of linear equations is a set of scalar values for unknown variables such that all linear equations are satisfied when substituted.
For instance, \((2, 1)\) is the solution to the following system of linear equations. \begin{align*} x - 2y &= 0 \\ x + y &= 3 \end{align*}
To check it, you can simply substitute to see if the equations are satisfied.
Now, if you recall from the previous note where we discussed matrix multiplication, system of linear equations can be written as a matrix multiplication.
Definition 1.1.3
A system of linear equations \begin{align*} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + \cdots + a_{1n}x_n &= b_1 \\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + \cdots + a_{2n}x_n &= b_2 \\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 + \cdots + a_{3n}x_n &= b_3 \\ \vdots \qquad \qquad & \\ a_{m1}x_1 + a_{m2}x_2 + a_{m3}x_3 + \cdots + a_{mn}x_n &= b_m \end{align*}
can be written as \(Ax = b\) where \(A\), \(x\), and \(b\) are matrices defined as the following. \[ A = \begin {bmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n} \\ a_{31} & a_{32} & a_{33} & \cdots & a_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} \\ \end {bmatrix}, \quad x = \begin {bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \end {bmatrix}, \quad b \begin {bmatrix} b_1 \\ b_2 \\ b_3 \\ \vdots \\ b_m \end {bmatrix} \]
When you actually perform matrix multiplication, you can see that \(Ax = b\) is identical to the system of linear equations. Now that we have a basic understanding of the relationship between matrices and linear systems of equations, let’s take a look at a theorem and an important corollary.
Theorem 1.1.4
For two distinct solutions \(x_1\) and \(x_2\) of \(Ax = b\), \(\alpha x_1 + \beta x_2\) is also a solution to the linear system given that \(\alpha , \beta \in \mathbb {R}\) and \(\alpha + \beta = 1\).
Proof.
From Theorem ??, it was shown that \(\lambda (AB) = A (\lambda B)\) for scalar \(\lambda \) and matrices \(A\) and \(B\) that can be multiplied. Substituting \(\alpha x_1 + \beta x_2\), the following system is obtained. \begin{align*} A (\alpha x_1 + \beta x_2) &= A(\alpha x_1) + A(\beta x_2) = \alpha (Ax_1) + \beta (Ax_2) \\ &= \alpha b + \beta b = b \end{align*}
Therefore, \((\alpha x_1 + \beta x_2)\) is another solution to the system.
From this theorem, we can establish an important corollary about the number of solutions to a system of linear equations.
Proof.
First, it is self-evident that a system can retain \(0\) or \(1\) solution. Therefore, the fact that there exist infinite solutions if there are more than \(1\) solution must be proven.
Let \(f(\alpha ) = \alpha x_1 + (1 - \alpha ) x_2\) be a function that returns possible solutions where \(x_1 \neq x_2\) are fixed values. It suffices to show that the function \(f\) is injective as there exists infinitely many values of \(\alpha \). Consider the following equations. \begin{align*} f(\alpha ) &= \alpha x_1 + (1 - \alpha ) x_2 = \alpha (x_1 - x_2) + x_2 \\ f(\alpha ') &= \alpha ' x_1 + (1 - \alpha ') x_2 = \alpha ' (x_1 - x_2) + x_2 \end{align*}
If \(f(\alpha ) = f(\alpha ')\), then \(\alpha (x_1 - x_2) + x_2 = \alpha ' (x_1 - x_2) + x_2\) and \(\alpha = \alpha '\), proving the injectivity. Therefore, a system of linear equations can only have \(0\), \(1\), or infinitely many solutions.
In middle school, you probably saw a visual understanding of the corollary above. Let’s do the same, except in 3-dimensional space. Below are two examples of when there exists no solution. Note that not all three planes intersect at a single point.
![[Picture]](/svg/MATH0203.260350x.svg)
![[Picture]](/svg/MATH0203.260351x.svg)
Continuing, the left diagram represents the case where there is a single solution while the right diagram shows the system with infinite solutions.
![[Picture]](/svg/MATH0203.260352x.svg)
![[Picture]](/svg/MATH0203.260353x.svg)
Wow, not going to lie, it took some time to draw the diagrams above. Anyhow, with that in mind, let’s discuss other fundamental terms and concepts before we move on to the next section of the note.
Definition 1.1.6
A linear system is consistent if it retains at least one solution, whereas a system is inconsistent if there is no solution.
We could also define a system based on the column matrix \(b\).
Definition 1.1.7
A linear system is homogeneous if the column matrix \(b\) in the linear system \(Ax = b\) is a zero matrix. If the matrix is not a zero matrix, the system is nonhomogeneous, or inhomogeneous.
Now from the definitions, we can see that all homogeneous systems are consistent. As you have guessed, we have a special name for a special solution in such cases.
Definition 1.1.8
Trivial solution is a solution where all the entries for \(x\) in \(Ax = b\) are zero.
With the fundamental terms in mind, let’s take a look at how matrices can be used to solve complex linear system with Gaussian Elimination.