ConceptLinear Algebra used inMSIAI-written · not yet proofread

System of Linear Equations

Also Linear System · Linear Equation System · Lineares Gleichungssystem · LGS

A system of m linear equations in n unknowns, written in matrix form Ax = b with coefficient matrix A ∈ ℝ^(m×n); its solvability is decided by the ranks of A and [A | b].

Know these firstMatrix Rank

Definition

A system of linear equations in the unknowns $x_1, \dots, x_n$ is

\begin{cases} a_{11} x_1 + \dots + a_{1n} x_n = b_1 \\ \quad \vdots \\ a_{m1} x_1 + \dots + a_{mn} x_n = b_m \end{cases}

with coefficients $a_{ij} \in \mathbb{R}$ and right-hand side $b_i \in \mathbb{R}$ . In matrix form it reads $Ax = b$ , with the coefficient matrix $A = (a_{ij}) \in \mathbb{R}^{m \times n}$ (row $i$ = equation $i$ , column $j$ = unknown $j$ ), $x \in \mathbb{R}^n$ and $b \in \mathbb{R}^m$ . The augmented matrix is $[A \mid b] \in \mathbb{R}^{m \times (n+1)}$ .

Properties#

Square, invertible case: if $m = n$ and $A$ is an invertible matrix, the unique solution is $x = A^{-1} b$ . In practice it is computed by Gaussian elimination, not by forming $A^{-1}$ .
Homogeneous system $Ax = 0$ : always solvable ( $x = 0$ ), with solution set $\ker(A)$ .
Overdetermined systems ( $m > n$ , typical for measurements): usually $\operatorname{rank}([A \mid b]) > \operatorname{rank}(A)$ , so there is no exact solution. MSI writes the model as $y \approx \Phi\theta$ and solves the least squares problem $\min_\theta \|y - \Phi\theta\|_2^2$ instead.

Example#

Example

\begin{cases} x_1 + 2x_2 = 5 \\ 3x_1 + 4x_2 = 6 \end{cases} \iff \underbrace{\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}}_{A \in \mathbb{R}^{2\times 2}} \underbrace{\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}}_{x \in \mathbb{R}^2} = \underbrace{\begin{bmatrix} 5 \\ 6 \end{bmatrix}}_{b \in \mathbb{R}^2}

$\det(A) = 4 - 6 = -2 \neq 0$ , so $\operatorname{rank}(A) = 2$ and the unique solution is $x = A^{-1}b = -\frac{1}{2}\begin{bmatrix} 4 & -2 \\ -3 & 1 \end{bmatrix}\begin{bmatrix} 5 \\ 6 \end{bmatrix} = \begin{bmatrix} -4 \\ 4.5 \end{bmatrix}$ . Check: $-4 + 9 = 5$ , $-12 + 18 = 6$ .

Sources#

Standard linear algebra. There’s no textbook in the subject’s sources: yet.
Use in MSI: MSI script p. 30 (linear model $y \approx \Phi\theta$ solved by least squares)
Exercise: MSI Sheet 00, task 1 (not published) (bring a linear system into the form $\Phi\theta = y$ )

Connections

Prerequisites know first1

Matrix Rank

Mentioned in inline links2

Eigenvector
Eigenspaces are subspaces: $E_\lambda$ is the solution set of the homogeneous linear system $(A - \lambda I)x = 0$ , so it is the kernel of $A - \lambda I$ . Every linear combination of eigenvectors for the same $\lambda$ is again in… §
Rank and Invertibility
System of Linear Equations — the problem $Ax = b$ whose solvability is at stake §
From system to matrix: a linear system becomes $Ax = b$ by writing one row per equation and one column per unknown. Its solvability then only depends on $\operatorname{rank}(A)$ vs. $\operatorname{rank}([A \mid b])$ and $n$ , which is the t… §

Search in these mentions →