System of Linear Equations

Revision

An equation that represents a line, a plane or a hyperplane is called a linear equation.

Formal Definition of Linear Equation

A linear equations in $n$ variables $x_1, x_2, ..., x_n$ can be expressed in the form:

$$a_1x_1+a_2x_2+...+a_nx_n=b$$

or more concisely,

$$\sum_{j=1}^{n} a_jx_j = b$$

Where $a_1, a_2,...,a_n$ are called the coefficients of the equation and $b$ is called the constant term. These terms are constant/fixed for a linear equation and can be real or complex. If $b=0$ then the equation is said to be homogenous linear equation otherwise the equation is said to be non-homogenous linear equation. Homogenous linear equations always pass through the origin.

System of Linear Equation

A system of linear equations with $n$ variables is a finite set of one or more linear equations. A system of linear equations is also referred to as a linear system. Example:

$$x_1 + 2x_2 + x_3 + 5x_4 = 20,\\ x_1 + 10x_2 + 30x_3 = 30$$

is a linear system with two equations and four unknowns $x_1, x_2, x_3, x_4$.

A linear system with $n$ unknowns and $n$ equations can be represented as:

$$a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n = b_1\\ a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n = b_2\\ \vdots\\ a_{n1}x_1 + a_{n2}x_2 + ... + a_{nn}x_n = b_n$$

Matrix notation for linear system

$$\begin{bmatrix} a_{11} & a_{12} & ... & a_{1n}\\ a_{21} & a_{22} & ... & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & ... & a_{nn}\\ \end{bmatrix} \cdot \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix} = \begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_n \end{bmatrix}$$ $$\text{or, }AX = B$$

where,

$$A = \begin{bmatrix} a_{11} & a_{12} & ... & a_{1n}\\ a_{21} & a_{22} & ... & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & ... & a_{nn}\\ \end{bmatrix}, X = \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix} \text{and } B=\begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_n \end{bmatrix}$$

The matrix $A$ contains all the coefficients of the system and hence called coefficient matrix. $B$ is called as constant vector and $X$ is called the unknown vector. Our job is to find out the $X$ vector for which the system holds true.

If the constant vector $B=0$, then the system is called a homogenous system. For homogenous systems, $x_1=0,x_2=0,...,x_n=0$ or in vector form $X=0$ is a trivial solution. Similarly, if $B \neq 0$ then the system is called a non-homogenous system.

Augmented matrix notation

Augmented matrix notation is another form of representing linear systems. We can represent the above linear system in augmented matrix notation in the following way:

$$[A:B] = \begin{bmatrix} a_{11} & a_{12} & ... & a_{1n} & : & b_1\\ a_{21} & a_{22} & ... & a_{2n} & : & b_2\\ \vdots & \vdots & \ddots & \vdots & : & \vdots \\ a_{n1} & a_{n2} & ... & a_{nn} & : & b_n\\ \end{bmatrix}$$

Definition of Solution

A solution for a linear system is any vector $X$ such that if we substitute $x_1, x_2, ..., x_n$ to the equations of the system, all of the equations satisfy simultaneously.

Trivial solution

A solution of a linear system that can be inferred without solving the system is called a trivial solution. For example, homogenous systems have $X=0$ as a trivial solution.

Non Trivial solution

A solution of a linear system that requires solving the system is called a non-trivial solution. For example, if we have the following system:

$$x_1+3x_2+x_3=0,\\ 2x_1+x_2+2x_3=0$$

$x_1=0,x_2=0,x_3=0$ is a solution as

$$x_1 + 3x_2 + x_3=0+3\cdot0+0=0 \text{ and}\\ 2x_1+x_2+2x_3=2\cdot0+0+2\cdot0=0$$

This solution is called trivial as we know if all the constant terms are zero then $X=0$ is a solution.

Similarly, $x_1=-1, x_2=0, x_3=-1$ is a non-trivial solution as it requires solving the system.

Consistent and Inconsistent Systems

A linear system will always satisfy only one of the following conditions:

1. The system may have no solution
2. The system may have exactly one solution
3. The system may have infinitely many solutions

If a system has one or more solutions then the system is called a consistent system. Similarly, if a system doesn't have any solution then it is called an inconsistent system.

Geometrical Analogy of Solution

If we consider two lines in 2D then they will either intersect at some point or are parallel. In case they intersect, the intersection point will satisfy both the equations of lines this point will be a solution and the system will be consistent.

In case the two lines are parallel they never intersect and hence their equations form an inconsistent system.

Similarly, if we consider two planes in 3D that are not parallel, the intersection forms a line that contains infinitely many points. This is the case of a system having infinitely many solutions.

Methods of Solving Linear Systems

Direct Methods

Direct methods are preferred when we don't know an approximate solution of the system. These methods include:

1. Gauss Elimination method
2. Gauss Elimination with pivoting
3. Gauss-Jordan method
4. LU decomposition/Factorization method
5. Determinants method(Cramer's rule)
6. Matrix inversion method

Indirect/Iterative Methods

If we know an approximate solution of the system then we prefer indirect methods as they will converge faster in such case. These methods include:

1. Jacobi's iteration method
2. Gauss-Seidel iteration method