Linear Systems of Equations

Last modified: October 27, 2023

This article is written in: 🇺🇸

Linear Systems of Equations

A linear system of equations is a collection of one or more linear equations involving the same set of variables. Such systems arise in diverse areas such as engineering, economics, physics, and computer science. The overarching goal is to find values of the variables that simultaneously satisfy all equations.

When working with linear systems, representing the equations in matrix form proves to be highly efficient. This matrix-based representation underpins a variety of numerical methods—such as Gaussian elimination, LU decomposition, and iterative techniques—used for both small and large-scale problems.

Mathematical Formulation

A general linear system with $n$ variables $x_{1}, x_{2}, \dots, x_{n}$ can be expressed as:

${\begin{cases} A_{11} x_{1} + A_{12} x_{2} + \dots + A_{1 n} x_{n} = b_{1}, \\ A_{21} x_{1} + A_{22} x_{2} + \dots + A_{2 n} x_{n} = b_{2}, \\ ⋮ \\ A_{n 1} x_{1} + A_{n 2} x_{2} + \dots + A_{n n} x_{n} = b_{n} . \end{cases}$

We can rewrite this collection of equations succinctly as:

$A x = b,$

where

$A = [\begin{matrix} A_{11} & A_{12} & \dots & A_{1 n} \\ A_{21} & A_{22} & \dots & A_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ A_{n 1} & A_{n 2} & \dots & A_{n n} \end{matrix}], x = [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}], b = [\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix}] .$

In this form:

I. $A$ (an $n \times n$ matrix) contains the coefficients of the variables.

II. $x$ (an $n \times 1$ column vector) represents the unknowns of the system.

III. $b$ (an $n \times 1$ column vector) contains the constant terms from the right-hand side of each equation.

Expressing the system in matrix form allows us to apply well-studied algebraic procedures and computational routines to solve for $x$ .

Criteria for a Unique Solution

A system $A x = b$ of $n$ linear equations in $n$ unknowns has a unique solution if and only if any one (and thus all) of the following equivalent conditions holds:

I. Non-zero determinant: $det (A) \neq 0$ .

A non-zero determinant indicates that the matrix $A$ is invertible.

II. Invertibility of $A$ : There exists an inverse matrix $A^{- 1}$ such that

$x = A^{- 1} b .$

III. Linear independence of columns: The columns of $A$ are linearly independent vectors in $R^{n}$ . In practical terms, no column can be written as a linear combination of the other columns.

IV. Linear independence of rows: Similarly, the rows of $A$ are also linearly independent. No row can be expressed as a linear combination of the other rows.

If any of these criteria fail (e.g., $det (A) = 0$ ), the system does not have a unique solution: it may either have no solution (inconsistent system) or infinitely many solutions (underdetermined system).

Example

Consider the following system of three linear equations in three unknowns $x, y, z$ :

${\begin{cases} 3 x + 2 y - z = 1, \\ 2 x - 2 y + 4 z = - 2, \\ - x + 0.5 y - z = 0. \end{cases}$

We can represent it in matrix form $A x = b$ as:

$A = [\begin{matrix} 3 & 2 & - 1 \\ 2 & - 2 & 4 \\ - 1 & 0.5 & - 1 \end{matrix}], x = [\begin{matrix} x \\ y \\ z \end{matrix}], b = [\begin{matrix} 1 \\ - 2 \\ 0 \end{matrix}] .$

To solve this system, one may use:

Transform $A$ into an upper-triangular (or row-echelon) form via elementary row operations, then perform back-substitution to determine $x, y, z$ .
Factor $A$ into a product of a lower-triangular matrix $L$ and an upper-triangular matrix $U$ . Then solve two simpler triangular systems.
Compute $A^{- 1}$ and multiply both sides of $A x = b$ by $A^{- 1}$ .

Each approach exploits the structure of linear systems to systematically isolate the solution for $x$ .

Advantages

Matrix methods, such as Gaussian elimination, provide a systematic framework for solving linear systems, making both theoretical understanding and practical implementation more straightforward.
Representing a system of equations as $A x = b$ creates a compact representation that reduces complexity, especially for systems involving many equations and variables.
Computational efficiency benefits from scalability, as many matrix-based algorithms have predictable complexities, and optimized libraries like BLAS and LAPACK are designed to utilize modern hardware capabilities.
Properties of the system can be analyzed using matrix insights, such as the determinant to assess solution existence or uniqueness, or matrix decompositions (e.g., LU, QR, SVD) to reveal structure and enhance solving methods.

Limitations

When the matrix $A$ is singular or nearly singular, solutions may not exist, may be infinite, or may be numerically unstable due to amplified computational errors.
Solving large systems can be computationally expensive since direct methods like Gaussian elimination scale with $O (n^{3})$ , and dense matrices increase memory requirements significantly.
Numerical instability can arise from ill-conditioned matrices where small changes in $A$ or $b$ lead to large deviations in the solution, requiring techniques like pivoting or iterative refinement to mitigate errors.
Sparse systems can be inefficiently handled if treated as dense, leading to unnecessary computational and memory overhead unless specialized sparse techniques are employed.