Systems of Linear Equations

A system of linear algebraic equations (SLAE) of size $m \times n$ is a system of the form

⎩ ⎨ ⎧ 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} \dots a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{mn} x_{n} = b_{m}

where $a_{ij}$ are the coefficients, $x_{j}$ are the unknowns ( $j = \overline{1, n}$ ), and $b_{i}$ are the constant terms ( $i = \overline{1, m}$ ).

In matrix form the system is written as

A X = B, A = a_{11} ⋮ a_{m 1} \dots ⋱ \dots a_{1 n} ⋮ a_{mn}, X = x_{1} ⋮ x_{n}, B = b_{1} ⋮ b_{m},

where $A$ is the coefficient matrix of the system. Appending the column of constant terms gives the augmented matrix $\overline{A} = (A ∣ B)$ .

Consistency and Determinacy

Definition. A solution of a system is a tuple $x_{1} = β_{1}, \dots, x_{n} = β_{n}$ that turns every equation into a true equality.

Definition. A system is called consistent if it has at least one solution, and inconsistent if it has none. A consistent system is called determinate if the solution is unique, and indeterminate if there is more than one solution (in which case there are infinitely many).

The Consistency Criterion (Kronecker–Capelli Theorem)

Theorem (Kronecker–Capelli). A SLAE is consistent if and only if the rank of the coefficient matrix equals the rank of the augmented matrix:

r (A) = r (\overline{A}) .

Idea: if, while reducing the augmented matrix to row-echelon form, a row $(00 \dots 0 ∣ β)$ appears with $β \neq = 0$ , then $r (\overline{A}) > r (A)$ — the system is inconsistent (we have obtained the equation $0 = β$ ).

If the system is consistent, denote $r = r (A) = r (\overline{A})$ . Pick a basis minor of order $r$ ; call the corresponding $r$ unknowns basic, and the remaining $k = n - r$ free. Two cases are possible:

$r = n$ — there are no free unknowns, the solution is unique: the system is determinate.
$r < n$ — the free unknowns may be assigned arbitrary values, expressing the basic ones through them: the system is indeterminate (infinitely many solutions with $k = n - r$ free parameters).

Scheme for Analyzing a SLAE

r (A) \neq = r (\overline{A}) \Rightarrow inconsistent; r (A) = r (\overline{A}) = n \Rightarrow consistent, determinate (a unique solution); r (A) = r (\overline{A}) < n \Rightarrow consistent, indeterminate (\infty solutions).

For practical methods of solving, see Cramer's Rule and Gaussian Elimination. In particular, when $m = n$ and $det A \neq = 0$ , the system is determinate and $X = A^{- 1} B$ .

Homogeneous Systems (HSLAE)

Definition. A SLAE is called homogeneous if all its constant terms are zero: $A X = O$ .

A homogeneous system is always consistent — it has the trivial (zero) solution $x_{1} = \dots = x_{n} = 0$ . The only question is whether nonzero solutions exist.

Theorem. A HSLAE has a nonzero solution $⟺ r (A) < n$ . In particular, if there are fewer equations than unknowns ( $m < n$ ), then $r \leq m < n$ — nonzero solutions always exist.

Corollary. For a square system $n \times n$ : a HSLAE has a nonzero solution $⟺ det A = 0$ .

Example. Does the system

⎩ ⎨ ⎧ 2 x_{1} - x_{2} + x_{3} = 0 x_{1} + x_{2} - 3 x_{3} = 0 x_{2} + x_{3} = 0

have nonzero solutions?

Δ = 210 - 1 11 1 - 3 1 = 10 \neq = 0,

so $r (A) = 3 = n$ , and the system has only the trivial solution.

The Structure of Solutions and the FSS

The set of all solutions of a homogeneous system $A X = O$ forms a linear space of dimension $k = n - r$ .

Definition. A fundamental system of solutions (FSS) of a homogeneous SLAE is any set of $k = n - r$ linearly independent solutions of it. Every solution is expressed through an FSS $E_{1}, \dots, E_{k}$ as

X = C_{1} E_{1} + C_{2} E_{2} + \dots + C_{k} E_{k}, C_{i} \in R .

Relation to the inhomogeneous system. The general solution of a consistent inhomogeneous system $A X = B$ is the sum of any particular solution $X_{0}$ of it and the general solution of the corresponding homogeneous system:

X = X_{0} + (C_{1} E_{1} + \dots + C_{k} E_{k}) .

Consistency and Determinacy

The Consistency Criterion (Kronecker–Capelli Theorem)

Scheme for Analyzing a SLAE

Homogeneous Systems (HSLAE)

The Structure of Solutions and the FSS

Related works