Systems of Linear Equations

A system of linear equations is a collection of equations where every variable appears only to the first power — no squares, no products of variables, no transcendental functions. Because of this constraint, such systems have a rich algebraic structure that we can exploit computationally: matrix algebra lets us write any system of any size as a single compact equation, and then a family of efficient algorithms can solve it.

System Notation

A general system of $m$ equations in $n$ unknowns takes the form:

$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}$

Here $a_{ij}$ is the coefficient in equation $i$ that multiplies variable $x_j$ , and $b_i$ is the right-hand side constant of equation $i$ .

Matrix Form

The entire system can be compressed into a single matrix equation. Collecting the coefficients into a matrix $A$ , the unknowns into a column vector $x$ , and the constants into a column vector $b$ :

$\underbrace{\begin{bmatrix}a_{11}&a_{12}&\dots&a_{1n}\\a_{21}&a_{22}&\dots&a_{2n}\\\vdots&&\ddots&\vdots\\a_{m1}&a_{m2}&\dots&a_{mn}\end{bmatrix}}_{A}\underbrace{\begin{bmatrix}x_{1}\\x_{2}\\\vdots\\x_{n}\end{bmatrix}}_{x}=\underbrace{\begin{bmatrix}b_{1}\\b_{2}\\\vdots\\b_{m}\end{bmatrix}}_{b}$

This is written compactly as:

$A \cdot x = b$

where:

$A$ is an $(n \times n)$ matrix of coefficients
$x$ is an $(n \times 1)$ column vector of unknowns
$b$ is an $(n \times 1)$ column vector of right-hand side constants

Solution

If $A$ is invertible, multiplying both sides on the left by $A^{-1}$ gives the solution directly:

$x = A^{-1} \cdot b$

Basic Properties of $A$

For a unique solution to exist, two conditions must hold:

$A$ must be a square matrix of shape $(n \times n)$ — the number of equations equals the number of unknowns.
$A$ must be non-singular — its determinant must be non-zero, i.e. $\det(A) \ne 0$ .

A singular matrix ( $\det(A) = 0$ ) means the rows are linearly dependent: at least one equation is redundant, and the system either has no solution or infinitely many.